Cryptography
April 15th, 2022
- Describe a man-in-the-middle attack on the Diffie-Hellman protocol where the ad- versary shares a key kA with Alice and a (different) key kB with Bob, and Alice and Bob cannot detect that anything is wrong. (problem 10.3 in the textbook)
- Consider the following public-key encryption scheme. The public key is (G, q, g, h) and the private key is x, generated exactly as in the El Gamal encryption scheme. In order to encrypt a bit b, the sender does the following:
- (a) Ifb=0thenchoseuniformlyy∈Zq andcomputec1 :=gy andc2 :=hy. The cipher text is ⟨c1, c2⟩.
- (b) If b = 1 then choose independent uniform y,z ∈ Zq, compute c1 := gy and c2 := gz and set the ciphertext equal to ⟨c1, c2⟩.
- Show that it is possible to decrypt efficiently given knowledge of x.
- (a) Ifb=0thenchoseuniformlyy∈Zq andcomputec1 :=gy andc2 :=hy. The cipher text is ⟨c1, c2⟩.
3. How can CRT be used to speed up RSA decryption? 4. Consider the following key-exchange protocol:
(a) Alice chooses uniform k, r ∈ {0, 1}n, and sends s := k ⊕ r to Bob. (b) Bob chooses uniform t ∈ {0, 1}n, and sends u := s ⊕ t to Alice.
(c) Alice computes w := u ⊕ r and sends w to Bob. (d) Alice outputs k and Bob outputs w ⊕ t.
Show that Alice and Bob output the same key. Analyze the security of the scheme (i.e., either prove its security or show a concrete attack). (problem 10.4 in the textbook)