Consider the following protocol. Alice and Bob choose a common prime p . Alice picks a random r Zp and sets s such that rs = 1 (mod p 1) . Bob similarly picks a random t Zp and sets u such that tu = 1 (mod p 1) . They then exchange messages as follows:

AB : m mod p r (= m )

BA : (m) mod p t (= m )

AB : (m) mod p s (= m )

B computes (m) mod p and recovers u m

a) Why does this protocol work?

b) Show that the protocol is vulnerable to a man in the middle attack.

c) Show that if an eavesdropper can compute discrete logarithms, it can break this protocol.