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.
