Description
Ex. 1 — Simple questions
1. Alice want to arrange a secret meeting with Bob. Using Caesar cipher she sends the ciphertext
EVIRE. Unfortunately brainless Bob has forgotten the secret key they agreed on. Help him finding
where to meet Alice.
2. Using a Hill cipher the ciphertext corresponding to dont is ELNI. Find the encryption matrix.
3. Let a, b, and n be three positive integers such that n|ab and gcd(a, n) = 1. Prove that n|b.
4. Compute gcd(30030, 257), providing the details of your calculations. Deduce than 257 is prime.
5. Explain why using the same key twice in the OTP is dangerous.
6. Assuming that the best algorithm that determines whether two finite graphs are isomorphic has
complexity 2O(
√
n log n)
, what size of graph should be used to be secure?
Ex. 2 — Vigen`ere cipher
1. Research and explain how the Vigen`ere cipher works.
2. Bob being exhausted he falls asleep on his Vigen`ere encryption device and sends the same letter
repeated several hundred times. The key is a six letters long English word.
a) Why can Eve suspect that the plaintext is one repeated letter?
b) How can Eve guess the key length?
c) How can Eve determine the key?
Hint: no English word of length six is a shift of another English word
Ex. 3 — Programming
1. Install the GNU Multi Precision Arithmetic Library (GMP) from https://gmplib.org/ or its fork
MPIR available at http://mpir.org/. Note that MPIR has a better support for Windows, although
no binaries are officially provided. GMP is available on any modern Linux distribution.
2. Implement the extended Euclidean algorithm.
3. Write a short program that generates two random 4096 bits integers, computes their gcd using
the previous implementation and compares it to the result of the corresponding GMP function.
