[SOLVED] VE475 Introduction to Cryptography Homework 6

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

• Bob generates a random integer r and sends γ = α mod p to Alice;
• Upon receiving ‘y Alice randomly requests r or x + r mod (p − 1);
• Bob replies accordingly;

We now want to study Bod’s idea.

1. In the previous protocol,
2. Why are r and x + r considered modulo (p − 1) ?
3. Prove that neither Bob nor Alice can cheat, while Bob can successfully prove his identity.
4. How many times should this be repeated for a
5. 128 bits security level?
6. 256 bits security level?
7. 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³ + 2X² + 1 is irreducible over F3[x], and conclude that it defines the field F33, which has 27 elements.
2. Explain how to define a simple map from the set of the letters of the alphabet into F33.
3. What is the order of the subgroup generated by X?
4. If we set the secret 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² 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 = m1∥m2∥ ~ ~ ~ ∥ml. Which properties of a hash function does the function h(m) = m1 ⊕ m2 ⊕ ~~ ~ ⊕ mj verify?

Ex. 5 – Merkle-Damgârd construction

The Merkle-Damg~rd 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 = 11IF (x1)IF (x2)I … IF _(x|x|), where xi represents the i-th bit of x. Assuming |y| = k, compute

and define h(x) as zk.

1. Check that
2. The map s from x to y is injective.
3. There is no strings x =~ x’ and z such that s(x) = zIs(x’).
4. Explain why the two previous conditions are of a major importance.
5. 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.