Ex. 1 – Simple questions
- Alice want to arrange a secret meeting with Bob. Using Caesar cipher she sends the ciphertext Unfortunately brainless Bob has forgotten the secret key they agreed on. Help him finding where to meet Alice.
- Using a Hill cipher the ciphertext corresponding to dont is ELNI. Find the encryption matrix.
- Let a, b, and n be three positive integers such that nlab and gcd(a, n) = 1. Prove that nib.
- Compute gcd(30030, 257), providing the details of your calculations. Deduce than 257 is prime.
- Explain why using the same key twice in the 0TP is dangerous.
- Assuming that the best algorithm that determines whether two finite graphs are isomorphic has
Oi√n log n‘
complexity 2 ‘ ‘, what size of graph should be used to be secure?
Ex. 2 – Vigenère cipher
- Research and explain how the Vigenêre cipher works.
- Bob being exhausted he falls asleep on his Vigenêre encryption device and sends the same letter repeated several hundred times. The key is a six letters long English word.
- Why can Eve suspect that the plaintext is one repeated letter?
- How can Eve guess the key length?
- How can Eve determine the key?
Hint: no English word of length six is a shift of another English word Ex. 3 – Programming
- 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.
- Implement the extended Euclidean algorithm.
- 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.
