In this post I will try to describe how public key cryptography works. Specifically, I will be using a watered down version of the Diffie-Hellman Key Exchange method for my examples of public key cryptography.

Public Key Exchange

The issue with sharing private keys is that there is no security in the transport of private keys. Public key exchange systems work around this by having two keys known as the Public Key and the Private Key. The two keys are used together to create a shared (but hard to crack) private key with which the parties can encrypt their data. Furthermore, the keys are intrinsically related, but not derivable from the other, and data encrypted with the public key can only be decrypted with the private and vice-versa. This is where Diffie-Hellman Key Exchange comes in… and the math (yay!). The trick of Diffie-Hellman is made possible using the modulus or remainder division operation. The encryption mechanism is as follows:

Alice and Bob want to exchange data privately without Carol being able to decipher the communication. Alice and Bob publicly agree on a prime modulus and a generator. For our example:

Prime modulus = 5
Generator = 3

Next, Alice and Bob decide on a random private key. Alice chooses 6, Bob, chooses 13. Alice and Bob then compute their public key from the prime modulus, generator, and their respective private key.

public key = (generator^private_key) % prime modulus, where % is the modulo operation.

Alice's public key = (3^6) % 5 = 4
Bob's public key =  (3^13) %5 = 3

Alice and Bob’s public keys are exchanged openly. At this point in the process, Carol has the public keys of Alice and Bob, and the agreed upon generator and prime modulus. Now comes the cool math parts. Alice takes Bob’s public key, raises it to the power of her private key, then performs the modulus against the prime modulus that was agreed upon; Bob does the same with Alice’s public key. The result is the shared secret. Look below:

Alice:
(3^6) % 5 = 4
Bob:
(4^13) %5 = 4

There it is! Now Alice and Bob have a shared private key that can be used to encrypt data. Carol is stuck trying to decrypt Alice and Bob’s messages using public keys to no avail. This is a greatly oversimplified version of the Diffie-Hellman system, but as one can imagine, if we were using very, very large prime numbers, and a pseudo-random number generator for our private key, it would begin to be more and more secure.

More neat stuff

As previously stated, data encrypted with a private key can only be decrypted using its corresponding public key and vice-versa. We can use this to our advantage to verify the authenticity of the sender of the data. If Alice encrypts a message using her private key, then encrypts the encrypted message with the calculated shared key, when Bob gets the message, he can decrypt the message using the shared key, and Alice’s public key which means she must have been the one sending the message. Putting together all the parts of this system, Alice can encrypt data with her private key, then the shared key, and when Bob decrypts the message using the shared key and Alice’s public key, he can be certain that the message is from Alice, and that no one has modified the message.

More on Public Key Cryptography