12 - Diffie and Hellman's Exponential-Key-Agreement Protocol

Summary

Motivation

One of the difficulties with traditional, symmetric-key cryptosystems is in getting the two parties to both know a secret key without anybody else knowing. This is particularly difficult when the two parties have never met in person and can only communicate via an insecure channel such as the Internet.

One could try to forestall the above difficulty by providing keys to everybody in advance. However, this introduces another difficulty. Suppose that there are a million and one people that want to participate. We can't know in advance who's going to want to communicate private with whom, so we have to provide each person a million keys, one for each of the other people with whom she might want to communicate. I couldn't possibly remember all these keys, so I have to store them on my computer. Suppose Eve has been eavesdropping on my communication and storing all the messages. If she manages to break into my computer and learn my keys, she can decrypt all these messages.

Worse yet, suppose another person comes along and wants to join the crowd. In order that the new person be able to communicate with everyone else, we have to provide a new key to each of the people already in the crowd. How can we transmit these new keys securely to all these people?