Solutions 4 IMC2021 course PDF

Preview

Summary

help you to prepare knowledge in Cryptography for the final exam...

Description

Introduction to Modern Cryptography: Assignment 4 Released: Friday 19th March 2021 Due: Friday 26th March 2021 at 13:00 UK time Student Name:

Total score: 15pt. Tested concepts: Key exchange, Diffie-Hellman protocol, ElGamal cryptosystem, RSA, digital signatures. NOTE: The points that each (sub)question counts is not indicative of how hard or how long the answer is. Parts of questions that are harder, are marked with a start *. 1. (a) (2 points) Let us consider the following key exchange protocol. Alice and Bob agree beforehand on a public description of a group G, its order q and generator g. Alice chooses a value x from Zq and sends to Bob the value X = g x . Bob chooses two values y, v from Zq and sends (g y , X y+v ) to Alice. Bob outputs X v as the shared key. How can Alice compute the shared key from her part such that correctness is satisfied? (b) (3 points) If the two parties have pre-agreed on the description of a group G, its order q and generator g, the Diffie-Hellman key exchange protocol described in the lectures can be modeled to work in one round to establish a key between two parties. Imagine now, that we have three parties that want to communicate, instead. By using the same idea as the Diffie-Hellman key exchange protocol, describe a secure two-round key exchange protocol for these three parties. [The messages of round 2 can only depend on information gathered up to round 1, a round 2 message cannot be based on information learned on round 2.] Solution: (a) Since Alice knows that Bob has output the value X v as the shared key, she must come up with a way to compute the same value. Bob has sent (g y , X y+v ) back to Alice, which means that she can use her secret value x in order to calculate (g y )x = g xy = (g x )y = X y , by using the first value Bob sent. Next, all she needs to do is calculate the inverse (X y )−1 and use that to obtain the final value by X y+v · (X y )−1 = X y+v−y = X v , which is the desired shared key we wanted to obtain, ensuring correctness. (b) Let us assume that there are three parties, Alice denoted by A, Bob denoted by B and Charlie denoted by C. Also, let us assume that they have pre-agreed on the description of the group G, its order q and generator g. The protocol can now progress in the following two rounds. • During round 1 we have the following: A chooses a uniform x ∈ Zq and sends X = g x to B . B chooses a uniform y ∈ Zq and sends Y = g y to C . C chooses a uniform z ∈ Zq and sends Z = g z to A.

• During round 2 we have the following: A sends X ′ = Z x to B. B sends Y ′ = X y to C. C sends Z ′ = Y z to A. Now all that remains is for each party to raise the last message they received to their secret values x, y, z respectively, in order to compute X ′′ =

(Z ′ )x = Y zx =g xyz

′′

(X ′ )y = Z xy =g xyz

Y = ′′

Z =

′ z

(Y ) = X

yz

=g

xyz

(1) ,

which results in the same shared key for everyone, making our protocol correct. 2. This question consists of four independent sub-questions about ElGamal Encryption. (a) (1 point) Consider an ElGamal Encryption where p = 23 and g = 7 is a generator of Z∗23 . Let x = 5 be the secret key (by which you construct the h) and your randomly chosen value to be y = 3. Encrypt message m = 10. (b) (1 point) Assume the following ElGamal Encryption where the public key is: pk = (G = Z∗31 , g = 3, h = 6) and the secret key is: sk = (x = 25). Decrypt (c1 = 22, c2 = 23). (c) (1 point) In an ElGamal Encryption with a group Z∗p , how many possible ciphertext pairs (c1 , c2 ) exist for a given prime number p and a specific value of x (secret key). (d) (2 point) Show that ElGamal is vulnerable against CCA (chosen ciphertext attack). [Hint: As a reminder CCA means that you have access to both encryption and decryption oracle. You need to show this via an attack example.] Solution: (a) The ciphertext of ElGamal is c = (g y , hy .m). So we have: h = g x = 75 (mod 23) = 17 c1 = 73 (mod 23) = 21 c2 = 173 × 10 (mod 23) = 2

(2)

c = (c1 , c1 ) = (21, 2) (b) In order to decrypt a ciphertext (c1 , c2 ), we should compute c−x 1 c2 = m. So the message is m = 22−25 × 23 = 2231−1−25 × 23 (mod 31) = 14. (c) An ElGamal ciphertext (c1 , c2 ) is equal to (g y , hy .m) = (g y , (g x )y m). There are p − 1 possible values for y and p − 1 possible values for m. Since x (the secret key) is fixed, then it means that for a fixed generator g, there are (p − 1)2 possible values for the combination of c1 and c2 . We note that g is a generator of the group with order p and by definition it generates all the possible members of the group by applying all the possible powers of y. Thus given x and y the term g xy m can take all possible p − 1 for different values of m, as m takes values from {g 0 , g 1 , ..., g p−2 }. Now we point that the p − 1 values {g xy g 0 , ..., g xy g p−2 } exhaust the group. This is the case as the value g xy+i where i = 0, ..., p − 2 is a member of the group due to the cyclic property group and the generator. Thus the total number of possible ciphertexts is (p − 1)2 .

IMC Semester 2

Introduction to Modern Cryptography

Page 2 of 4

(d) If we have access to decryption oracle exist then the adversary A, who wants to decrypt the ciphertext c = (c1 , c2 ), with c = g k and c2 = my k , chooses random elements k ′ and m′ and ′ ′ asks for the decryption of c′ = (c1 g k , mm′ yk+k ). Oracle responds with mm′ , the plaintext of ′ ′ c′ = (g k+k , mm′ yk+k ) to adversary. Now A simply divides by m′ and obtains the plaintext m of c with probability 1 and hence break CCA. (the attack is not unique, any other reasonable attack that shows this vulnerability is also accepted)

3. The Chinese Remainder Theorem (CRT) is a result in number theory that (in a simplified case with two equations) states the following: For any two distinct primes p, q and a, b ∈ Z, there exists a unique x ∈ Zpq satisfying the following two relations: x ≡ a (mod p) and x ≡ b (mod q) simultaneously. The concrete formula is x = (b − a)(p−1 mod q)p + a. One can see that x mod p = a because the first term cancels. At the same time, x mod q = (b − a mod q )(p−1 mod q )(p mod q ) + (a mod q) mod q = (b mod q) − (a mod q) + (a mod q) mod q = b mod q where mod is used as an arithmetic reduction operation. This proves correctness1 . Assume the uniqueness for now. Now, consider the following cryptosystem which is intended to be more efficient than RSA. Assume that $ N generated in KeyGen is of the same order as in RSA. We denote by a ← − S random sampling from the uniform distribution on the set S . KeyGen(1n )

Encpk(m ∈ ZN )

Generate p, q large primes N ← p·q $

− ZN g, r1 , r2 ← g 1 ← g r1 (p−1) ; g 2 ← g r2 (q−1) sk ← (p, q); pk ← (N, g 1 , g 2 ) return (sk, pk)

$

− ZN s1 , s2 ← c 1 ← mg1s1 (mod N ) c 2 ← mg2s2 (mod N ) return (c 1 , c 2 )

Decsk(c1 , c2 ) Using CRT, find x such that x ≡ c 1 (mod p) x ≡ c 2 (mod q) return x

The following remark should help you with solving the question. Note that a typical randomly chosen value has a negligibly small chance to have common factors with either p or q – thus we can assume that g, and therefore also g1 , g2 with high probability do not have p or q as factors. Recall that Fermat’s little theorem says that for any a 6= 0 mod p the following holds: ap = a mod p, where p is prime. From what we just explained, ap = a holds for randomly sampled a with overwhelming probability. (a) (3 points) Prove that the scheme is correct, namely that Decsk (Encpk (m)) = m under each valid keypair (sk, pk). (b) (2 points)∗ Explain why this encryption scheme is not secure. [Hint: pk leaks information about the factors of N ] [Hint: solution for each sub-question does not take more than a few lines.] 1 For

an alternative proof, see e.g. this link

IMC Semester 2

Introduction to Modern Cryptography

Page 3 of 4

Solution: (a) Observe that mg s11 ≡ mg s1 r1 (p−1) ≡ m(1)s1 r1 ≡ m mod p, since ∀a. a(p−1) = 1 mod p. Similarly mg2s2 ≡ m mod q. By CRT, the solution exists and is unique in ZN , thus x = m. (b) Unfortunately, it is easy to deduce the secret key from the public key. Given g1 = g r1 (p−1) ≡ 1 mod p, we have g1 − 1 ≡ 0 mod p. So p divides g1 − 1. Since r1 is uniformly random, it is unlikely that g1 ≡ 0 mod N . Thus, we merely need to find gcd(g1 − 1, N ) to obtain p with high probability.

IMC Semester 2

Introduction to Modern Cryptography

Page 4 of 4...