An explanation of an important public key cryptography algorithm as well as some of the history behind it.
keywords
programming2017-06-19
This post is largely based off of an awesome video that I stumbled upon today. Check it out.
The idea that computers can be used to connect and share information between people across the globe has, of course, made a huge impact on our society.
After World War II, The United States and Canada launched NORAD: A joint effort to defend the North American continent from potential nuclear attacks. The project included hundreds of long-distance radars across North America, which were connected to computers. These early computers transmitted the data via radio waves and telephone lines to a base in Colorado. This method of processing and transmitting data allowed operators to make split-second decisions on a large scale.
This idea of sharing data was further developed by researchers at universities who saw how valuable this type of “computer communication” could be. Fast forward to today and it’s true that the internet has grown to encompass just about everything we do.
Just as important as sharing our data with each other is the ability to secure it, and to prevent it from falling into the hands of an unwanted listener.
That’s one of the problems that encryption attempts to solve. However, in order for encryption to be usable, there must first be an exchange of keys between the sender and the receiver – a way for them to unlock the information. One question that remained unanswered for some time is how to safely share those encryption keys.
In 1976, Whitfield Diffie and Martin Hellman discovered a clever way to allow different parties to securely exchange encryption keys over a public channel. It works using very large prime numbers, and modular arithmetic. The video that I mentioned, provides the following example.
17
and 3
(3 mod 17
). 15
for example.) 3^15 mod 17
to get a result of 6
, which she sends to Bob. 13
for example.) 3^13 mod 17
to get a result of 12
, which he sends to Alice. At this point, Eve, who is an eavesdropper, knows everything that was sent between Alice and Bob, but does not know their private numbers that they used to perform the calculation
12
that was received from Bob and calculates 12^15 mod 17
to get 10
, the shared secret. 6
that he got from Alice to calculate 6^13 mod 17
to get 10
, the same shared secret that Alice calculated. Eve is unable to obtain the shared secret – there is no for her to calculate it.
This works because both Alice and Bob did the same calculations. Alice did
12^15 mod 17
, which is the equivalent of3^13^15 mod 17
. Similarly, Bob did6^13 mod 17
, which is the equivalent of3^15^13 mod 17
.
The technique relies on the fact that a problem like 12^15 mod 17 is easy to solve in one direction, but given only the solution, it’s very difficult to work backwards. Of course it’s easy to calculate using small numbers as in this example, but when the numbers become hundreds of digits long, it takes computers thousands of years to figure out.
To help illustrate how this technique works, we can also use colors.
Pretend that Pablo has a secret color of paint he wants to share with Vincent. Neither of them want Andy to find out about this color. Also, we’re going to assume the following:
Since it’s easy to mix paint, but hard to un-mix paint back to its initial colors, this is known as a one-way function. This property of paint forms the basis of how Pablo and Vincent can share their secret color.
So, how can Pablo and Vincent share their secret color of paint without Andy also learning about it? Here’s how it goes:
At this point, Here’s what it looks like:
Vincent has:
public color private color mixture from Pablo (green + blue)Pablo has:
public color private color mixture from Vincent (green + red)Andy (the spy) has:
public color public mixture (green + blue) public mixture (green + red)Now the essential part of the exchange. Both Pablo and Vincent add their private color into the mixtures that they received from each other. They are both able to create this color:
SECRET MIXTUREAndy does not have a combination of colors that will mix to form the secret color. Though the combination for the secret color of paint is buried within the colors he has, there’s no practical way for him to take his brush and unmix the colors to find the secret mixture.
green + mixture from Pablo green + mixture from Vincent mixture from Pablo + mixture from VincentThis is how the Diffie-Hellman key exchange algorithm works in a nutshell. Of course, in the real world, we are not dealing with colors of paint, but thanks to maths, this same concept can be used to securely and reliably transmit useful information.
As a practical example, when setting up an Nginx web server to use TLS/SSL, you can specify the ssl_dhparam
directive with the path to your Diffie-Hellman parameters. These params can be generated using openssl:
openssl dhparam -out dhparam4096.pem 4096