Public Key Cryptography

Diffie-Hellman key exchange

All of the ciphers we've covered up to this point need both sides of the communication to have a key. In the old days, people could meet up and exchange keys in person, but that won't work for the internet. The solution, discovered in the 1970s, surprised many people at the time. It's called Diffie-Hellman key exchange. It involves two parties communicating in public, yet being able to generate a shared secret number that only they will know.

Before we describe the way it works, here is a simpler, but insecure, idea. We will assume the two people communicating are Alice and Bob. Alice generates a random number a and sends it to Bob. Bob generates his own random number b and sends it to Alice. They then both multiply the numbers to get ab. This number would be the shared secret. The problem, of course, is that it's not secret since someone watching the communication could see a and b and thus compute ab themselves. But at least the value of ab is a value that both Alice and Bob now have, and they could use that as a key if they were sure no one else observed their communication.

It would be good to find a way to disguise a and b before sending them. The trick that Diffie-Hellman uses is to disguise a by doing ga mod p, where p is a large prime number and g is some other number. Raising a number to the a power and then modding by a prime seems to be a hard thing to reverse. As long as the prime is very large, no one has yet found a good way to do that.

Here is an example of the key exchange using g = 3 and p = 7927. First, Alice and Bob pick random numbers. Suppose Alice picks a = 45 and Bob picks b = 144. Alice disguises her number by computing ga mod p, which is A = 345 mod 7927 = 3147. Bob disguises his number by computing B = gb mod p, which is 3144 mod 7927 = 1975.

Alice then computes the shared secret by doing Ba mod p, which is 197545 mod 7927 = 3641. Bob computes the shared secret by doing Ab mod p, which is 3147144 mod 7927 = 3641. Notice that they both get the same value, 3641. This is the shared secret.

Some notes about the process:

Public-key cryptography

All of the ciphers we have seen so far are called symmetric. They are called this because both sides of the communication use the same key. There is another type of cryptography called asymmetric, in which different keys are used for encryption and decryption. Another name for this is public-key cryptography. One of the keys, the public key, is available to the public, and the other, the private key, is kept secret.

Here is the basic idea: Suppose Alice wants people to be able to send encrypted messages to her using public-key cryptography. She creates a public-private key pair. She publishes the public key and keeps the private key secret. If Bob wants to send an encrypted message to Alice, he encrypts it using the public key. Alice uses her private key to decrypt it. The public and private keys are tied together so that this works.

A nice analogy for this would be if Alice creates physical padlocks and keys. If someone wants to safely send something to Alice, they get a padlock from Alice and put their item in a box locked with Alice's padlock. Alice can use her key to open the lock. The padlock is like the public key and Alice's physical key is like the private key.

Trapdoor functions

The security of the Diffie-Hellman key exchange relies on the fact that it is easy to compute ga mod p, but it is hard to reverse the process to figure out a. This mathematical operation is an example of a trapdoor function, something that is easy to do in one direction and hard to do in the other. Trapdoor functions are very important in modern cryptography.

A simple, but powerful, trapdoor function is multiplication of prime numbers. It's easy to multiply to prime numbers, but it is hard to “unmultiply” them, i.e., to factor them. For instance, it is easy to multiply 999979 × 999983, but it is much harder to factor their product 999962000357. This trapdoor is the basis of one of the most well-known types of public-key cryptography—RSA.


RSA is named for the three people who created it: Rivest, Shamir, and Adleman. It's probably easiest to describe with an example. We'll use very small prime numbers in this example to demonstrate the concept, but in the real world, very large primes need to be used.

Alice starts by generating a public-private key pair. She does this by choosing two prime numbers, p and q. Let's use p = 101 and q = 137. She then multiplies them together to get n = pq = 13837. She next chooses a value e that has no factors in common with p–1 or q–1. In this case, e = 23 works. Finally, she computes a value d that has the property that de mod (p–1)(q–1) = 1. There is a very fast algorithm, the Extended Euclidean Algorithm, that can be used to do this. We won't go into the details here. The value of d turns out to be 7687 in this example. The public key that Alice publishes is n and e. The private key is d. Alice also shouldn't let anyone know what p and q are.

Let's say Bob wants to encrypt a message with Alice's private key. RSA only works with numbers, so Bob would have to convert his message to a sequence of numbers. There are many ways to do this, such as ASCII or Unicode character codes. Let's say Bob's message is the number M = 65. he computes C = Me mod n, which is 6523 mod 13837 = 12429. To decrypt, Alice does Cd mod n, which is 124297687 mod 13837. This comes out to 65, as it should. If you want to try this out, use Python's pow function (pow(x,y,z) does xy mod z). Below are a few notes about RSA.