ABSTRACT
Imagine for a moment that you have the perfect cryptography system, completely impenetrable and totally unreadable by anyone who intercepts an encrypted message that you send. If you need to send classified information to agents thousands of miles away, they need the cryptographic key in order to read the message. This is a serious problem. You can’t just call them up or e-mail them or text them — if you trusted the phone or Internet, you could just tell them the message and you would have no need of the cryptography. This is called the Key Exchange Problem, and, in the past, couriers often used a diplomatic pouch system to solve it. Alternatively, there could be a meeting with all relevant people present. Keys would then be distributed and the agents would go out into the field. The problem is that these methods are expensive and time consuming, and they require a lot of planning. In 1976, Whitfield Diffie and Martin Hellman proposed a key exchange method that can be done publicly but nevertheless maintains the secrecy of the key. (Their idea is more accurately a key establishment system. Nevertheless, since it is universally referred to as a key exchange protocol, we will continue to use this terminology.) We now describe their idea, which is based on simple properties of exponents and congruences.
