## Description

Ex. 1 — Application of the the DLP

Bob wants to prove his identity to Alice. Alice knows that Bob can compute logα β in Z/pZ, where α is

a generator of the group Z/pZ, and p is a known prime. Unfortunately Bob is not willing to share the

result with her, so he offers to apply the following strategy.

(i) Bob generates a random integer r and sends γ = α

r mod p to Alice;

(ii) Upon receiving γ Alice randomly requests r or x + r mod (p − 1);

(iii) Bob replies accordingly;

We now want to study Bod’s idea.

1. In the previous protocol,

a) Why are r and x + r considered modulo (p − 1)?

b) Prove that neither Bob nor Alice can cheat, while Bob can successfully prove his identity.

2. How many times should this be repeated for a

a) 128 bits security level?

b) 256 bits security level?

3. What type of protocol is this?

Ex. 2 — Pohlig-Hellman

Search and explain in details how the Pohlig-Hellman algorithm computes the discrete logarithm of an

element in a multiplicative group whose order can be completely factorized into small primes. As an

example calculate log3 3344 in G = U(Z/24389Z), knowing that 3 is generator of G.

Ex. 3 — Elgamal

1. Prove that the polynomial X

3 + 2X

2 + 1 is irreducible over F3[x], and conclude that it defines

the field F3

3 , which has 27 elements.

2. Explain how to define a simple map from the set of the letters of the alphabet into F3

3 .

3. What is the order of the subgroup generated by X?

4. If we set the ecret key to be 11, determine the public key.

5. Encrypt the message “goodmorning”, and then decrypt the ciphertext.

Ex. 4 — Simple questions

1. Let n be the product two large primes, p and q. We define h(x) ≡ x

2 mod n. Is h (i) pre-image

resistant, (ii) second pre-image resistant, and (iii) collision resistant?

2. Supposed a message m is divided into blocks of 160 bits: m = m1km2k · · · kml

. Which properties

of a hash function does the function h(m) = m1 ⊕ m2 ⊕ · · · ⊕ ml verify?

Ex. 5 — Merkle-Damg˚ard construction

The Merkle-Damg˚ard construction provided in the slides is only valid when t ≤ 2, therefore we now use

the same notations as in the slides to provide an alternative construction for t = 1.

Let g be a compression function from {0, 1}

m+1 −→ {0, 1}

m, and f be the function defined by f (0) = 0

and f (1) = 01. The map from x to y is defined by y = 11kf (x1)kf (x2)k … kf (x|x|), where xi represents

the i-th bit of x. Assuming |y| = k, compute

z1 = g(0mky1)

zi+1 = g(zikyi+1), 1 ≤ i ≤ k − 1,

and define h(x) as zk .

1. Check that

a) The map s from x to y is injective.

b) There is no strings x 6= x

0 and z such that s(x) = zks(x

0

).

2. Explain why the two previous conditions are of a major importance.

3. Following a similar strategy as in the case t ≥ 2, prove that h is a collision resistant hash function.

Ex. 6 — Programming

Implement the Pollard-rho factorization algorithm.