An explanation of an important public key cryptography algorithm as well as some of the history behind it.

2017-06-19

programming

This post is largely based off of an awesome video that I stumbled upon today. Check it out.

We Need Encryption

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.

How can two people who have never met agree on a secret, shared key?

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.

1. Two parties, Alice and Bob, agree on a prime modulus and a generator of 17 and 3 (3 mod 17).
2. Alice then selects a private random number (15 for example.)
3. Alice calculates 3^15 mod 17 to get a result of 6, which she sends to Bob.
4. Bob does the same thing and selects his own private random number (13 for example.)
5. Bob calculates 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

1. Now Alice uses the 12 that was received from Bob and calculates 12^15 mod 17 to get 10, the shared secret.
2. Bob also uses the 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 of 3^13^15 mod 17. Similarly, Bob did 6^13 mod 17, which is the equivalent of 3^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.

Secret colors

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:

• The secret color is a combination of three colors.
• It’s easy to mix two colors of paint together to make a third color.
• Once a color is mixed, it’s practically impossible to figure out the three original colors it’s composed of. It’s impossible for Andy to take his brush and separate the paint back to their originals.

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:

1. Vincent and Pablo both agree publicly on the color green. Since this agreement happened publicly, Andy now knows that green is part of the mix.
2. Next, Vincent and Pablo both privately decide on another color. Vincent picks red and Pablo picks blue. Since this was not done in public, Andy does not know about these colors. In fact, Vincent doesn’t even know about Pablo’s color, and vice versa.
3. Both Vincent and Pablo mix their privately selected colors with the public green color of paint. Next, they send each other their mixtures publicly. Since it’s done publicly, Andy is able to obtain the mixtures as well.

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 MIXTURE

Andy 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 Vincent

Real world applications

This 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