Cryptography

1. 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)
    
2. 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:
    
   1. (a)  Ifb=0thenchoseuniformlyy∈Zq andcomputec1 :=gy andc2 :=hy. The cipher text is ⟨c1, c2⟩.
       
   2. (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⟩.
       
   3. Show that it is possible to decrypt efficiently given knowledge of x.
       

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)