## 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):

- Extended Euclidean Algorithm
- Euler's Phi Function (Totient)
- Modular Inverse

Your function should return 0 if the number is not invertible.
- 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.
- 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 = x^{2} 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.
C_{i} = K + (M_{i} + C_{i-1}), where C_{0} = 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 (N_{1}, N_{2}, N_{3}) 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 m^{3}.
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. N_{1}N_{2}N_{3} is a large enough modulus, since in RSA encryption the message must be an element in Z_{Ni}. That is, you can see this is as m < N_{i} for i=1,2,3 and therefore m^{3} < N_{1}N_{2}N_{3}.
Give a hint

4. In order to find m^{3} 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 :)