This page holds a collection of programming assignments. Each assignment is worth a different number of points, you are required to collect at least 20 points. To collect the points, your submission needs to be accepted by one of the TAs of the course.

Most assignments are personalised. Please provide the 12 digit personnummer from one group member to generate your assignments. Do not forget to include this number in your submission!

Programming Instructions You can choose among three programming languages: Java, C++ or Haskell. For each assignment we provide a minimal set-up to get you started (but feel free to create your own solution from scratch, if you like it). Here you can find a few programming hints for Java, C++ and Haskell.

Submission Instructions For each assignment that you choose to submit, include (1) the personnummer used to generate your assignment, (2) the source code of your program with a make/build file if appropriate and (3) a report documenting your approach and the retrieved secret message if appropriate.

A Math Library for Cryptography (10 points)

In this assignment you will implement a library that provides a number of mathematical functions commonly used in cryptography, such as Euler's Phi Function (Totient), the Extended Euclidean Algorithm and some Primality Test. Your library needs to successfully pass a test suite that we provide.

More

In this assignment you are required to follow the skeleton code we provide, to make sure that the test suite works. All functions should work for arbitrary integers. You are not allowed to call already implemented libraries (BigInteger, GMP, ...). Make sure your implementation passes our tests before submitting.

The following archives contain a skeleton code and test suite for each programming language: cryptolib_cpp.zip, cryptolib_java.zip and cryptolib_haskell.zip.

You should implement the following functions (plus any helper code you deem necessary):

  1. Extended Euclidean Algorithm
  2. Euler's Phi Function (Totient)
  3. Modular Inverse
    Your function should return 0 if the number is not invertible.
  4. Fermat Primality test
    Instead of picking random values a to test the primality of a number n, make a start from 2 and increment it by 1 at each new iteration, until you have tested all the values below n/3.
  5. HashCollisionProbability

Special Soundness of Fiat-Shamir sigma-protocol (10 points)

We eavesdropped on a number of Fiat-Shamir protocol runs and we found that the same nonce was used twice! Due to the special soundness property you should now be able to retrieve the secret key used in the protocol.

More

The Fiat-Shamir protocol is a zero-knowledge protocol, explained in these lecture notes. Then, inspired by exercise 2 from this exercise session (which also includes another exercise on Fiat-Shamir), compute the secret value.

The text box below displays (n), the modulus used, and (X) the public key of the prover. We know that X = x2 and your task is to find x.

The rest of the input is a sequence of runs of the Fiat Shamir protocol. R is the random value sent to the verifier, c is the challenge sent to the prover, and s is the proof sent back to the verifier. Give me a hint

Look for runs with the same random value, i.e. the same value of R.

Skeleton code: Place the above data in a file called input.txt and use one of the following files to get you started: FiatShamir.java, fiat_shamir.cpp or FiatShamir.hs.

Decrypting CBC with simple XOR (10 points)

We intercepted a message that was encrypted using cipher-block chaining. We also know the plain-text value of the first block. Can you reconstruct the complete plain-text message?

More

First, have a re-cap on how CBC works (Section 6). In this case the encryption function is simply a XOR (+) operation with the key, i.e. Ci = K + (Mi + Ci-1), where C0 = IV.

In the text box below you find the known first block (= the 12 digit number your provided, each digit represents one byte) and the encrypted message. You know that the block size is 12 bytes. The encrypted message is printed in hexadecimal format. The skeleton code below provides functions for converting both the personnummer and the message into byte arrays.

Skeleton code: Place the above data in a file called input.txt and use one of the following files to get you started: CBCXor.java, cbc_xor.cpp or XORCBC.hs.

Attacking RSA (20 points)

This attack applies to the case in which the same message is encrypted using RSA to three different recipients. The enablers of the attack are (1) all recipients have the same public key (e = 3) and (2) the recipients have different modulus (N1, N2, N3) that are coprime. Your goal in this assignment is to use the three eavesdropped ciphertexts and recover the secret message! The message you will recover is an ASCII encoding of a name you should know ;)

More

The text field below displays the modulus (N), the public key (e) and the cipher text (c) of three recipients of the same message (m). Your goal is to retrieve m.

You can try starting from here, but we provide additional hints if you want some help. Give a hint

1. We know that each cipher text is computed as m3. Why does it not make sense to directly compute the cube root on one the cipher texts (c)? Give a hint

2. Computing the cube root with some modulus N is equivalent to solving the discrete log problem for exponent e=3, which we know to be hard. What about trying to move to a bigger modulus so that no modular reduction occurs when you encrypt the message? Give a hint

3. N1N2N3 is a large enough modulus, since in RSA encryption the message must be an element in ZNi. That is, you can see this is as m < Ni for i=1,2,3 and therefore m3 < N1N2N3. Give a hint

4. In order to find m3 the large modulus you can use the Chinese Remainder Theorem (CRT). Give a final hint

5. This is your last hint.

Skeleton code: Place the above data in a file called input.txt and use one of the following files to get you started: AttackRSA.java, attack_rsa.cpp or AttackRSA.hs.

Helper code: For this assignment you are allowed to use the following helper code to determine the cube root of a value:

Attacking ElGamal (20 points)

Thanks to its random component, two ElGamal encryptions of the same message can look completely different. However, this also makes the strength of the encryption depend on the random number generation. In this assignment you will attack ElGamal under a weak number generator.

More

We intercepted you an ElGamal encryption of a message together with a partial time stamp at which it was encrypted. You can find a pseudo-code describing how the sender is choosing her randomness to encrypt the messages here. Your task is decrypt the message exploiting the weakness of this bad Pseudo Random Number Generator. Please do not break ElGamal's Discrete Log problem, otherwise it would be a threat against the security of the whole internet!

The text field below lists the group size (p), the generator of the group (g), the public key of the receiver (y), the time at which the message was encrypted (and the PRNG was called), and finally the ElGamal encryption of the message (c1, c2).

Skeleton code: Place the above data in a file called input.txt and use one of the following files to get you started: ElGamal.java, el_gamal.cpp or ElGamal.hs.

Breaking Telegram (600 points)

That's right, we are offering a 600 point reward to anyone who can break the Telegram encryption.

More

Some details about Telegram can be found here and in this contest. We recommend you to try the easier assignments first though :)