VE475 Introduction to Cryptography Homework 1 Solved

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 nlab and gcd(a, n) = 1. Prove that nib.

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 0TP is dangerous.

6.    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

1.   Research and explain how the Vigenêre cipher works.

2.   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.

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.