# Public Key Cryptography

13 Oct 2012While not typically used an algorithm for transmitting messages securely, public key cryptography has become heavily relied upon in systems where user authentication is required. For example, every time you log into gmail, Facebook, or some other website with your email address and password, or whenever you make secure payments online, public key cryptography creates a secured tunnel through which you can transmit that data to the respective app without fear of it being compromised. All this is possible because of the unique mathematical principles behind public key cryptography which were first published in 1976 by Whitfield Diffie and Martin Hellman.

These two researchers came up with a method of establishing such a link, and published its mechanism under the name of the Diffie-Hellman Key Exchange. This type of communication is called asymmetric key exchange, as it describes a one-way function, or some process that cannot be undone in order to receive the original components. Their breakthrough is a remarkably fascinating process, and can be beautifully described in simple terms with an analogy to color theory.

Suppose Alice has some information she wants to send securely to a friend, Bob, across the room. However, every time Alice or Bob sends a message, it can and will be intercepted by Eve. Alice and Bob can not agree on a secret cryptographic key beforehand, nor can they move so that Eve cannot hear them. So how can Alice and Bob tell any secrets to each other if they do not have a method of encoding and decoding messages? The answer is to apply the method of public key cryptography, as explained with paint. Alice and Bob each have their own private colors of paint which are inaccessible by anyone but themselves. In addition, there is a public color that is common to Alice, Bob, and Eve.

Alice and Bob first mix their own private paint with the common paint to create a public transport paint, as their private color is then masked by the common color and indeterminable by Eve. Then, Alice and Bob send their public transport paints to each other, who mixes them with their private paints to create a shared secret (a common color of paint) between themselves and only themselves. Eve, since she does not have either of Alice nor Bob’s private colors, cannot recreate the shared secret and therefore is unable to snoop on messages or impersonate either Alice or Bob.

Incredible? I think so. This all relies on the assumption, however, that it is impossible (or *extremely* difficult or expensive) for Eve to “unmix” the paint to recreate either Alice or Bob’s private colors. In real application, communication is not done with paint, but with numbers. Bits, or ones and zeros, represent the information being transmitted, and can be masked to hide their contents just like paint. Many ideas in cryptography are based upon the XOR cipher, a symmetric exchange function, however asymmetric key exchange functions rely on both exponentiation of large prime numbers and modulus math to achieve their desired effect. Because it is not technically impossible to crack these private keys (to “unmix” the paint), they are not perfect, unbreakable solutions. The ability to reconstruct the private keys is dependent on the efficiency of factorization techniques, and therefore, with enough time it is possible to crack.

This does not discourage the use of the Diffie-Hellman Key Exchange, however. Although it is not suitable for large message encryption due to its need for expensive computation, it is entirely practical for small messages, such as determining a cipher to use for further secure communication between two parties. As mentioned, public key cryptography plays a crucial role in the security of authentication and private communication via the internet—a place where all communication is essentially public if not secured otherwise. Technologies such as Transport Layer Security (TLS), Pretty Good Privacy (PGP), and GNU Privacy Guard (GPG), as well as RSA, and Digital Signature Algorithm (DSA) all implement public key cryptography to help create a more secure internet.