Asymmetric-Key Encryption

One of the primary problems with Symmetric-Key Encryption is that a single key must be kept secret, yet paradoxically it must also be shared among communication partners. This means that symmetric-key encryption is only as secure as the channel used to share the key.

Asymmetric or public-key encryption solves this issue by employing two different, but mathematically related keys for encryption and decryption respectively.

Overview

Let's imagine that Alice wants to send an encrypted message to Bob. Before Alice sends the message, Bob will generate an asymmetric key-pair. This key-pair consists of two keys: a public key, which Bob can distribute freely and widely, and a private key, which Bob will keep entirely confidential.

Bob sends his public key to Alice. He does not need to worry about the security of the communication channel, because secrecy is not a requirement for public keys.

Once Alice has Bob's public key, she is ready to encrypt her message, and she'll do so using Bob's public key.

Alice sends the message to Bob, and Bob can now use his private key to decrypt it. By following this protocol, Alice and Bob can enjoy complete confidentiality because the only secret that needs to be transmitted is the message itself.

Theory

Now that we know how to generate and use key-pairs, we can start to understand how asymmetric cryptography works. Earlier, we touched on the fact that the public and private keys of an asymmetric key-pair are mathematically related. There are several methods for implementing the relationship between keys in a key-pair, but each of them hinge on a fundamental mathematical concept: the procedure that generates the key-pairs must be easy to compute given some input, but it must be difficult to reverse given some output.

One of the most ubiquitous one-way functions used for asymmetric encryption is the factorization of prime numbers. Recall that every natural greater than 1 is either prime (that is, it can only be divided by 1 or by itself), or it must be made up of some product of unique prime numbers. For example, the product of the prime numbers 89 and 239 is 21271. The only way to get 21271 out of prime numbers is via these two inputs. This concept is known as the Fundamental Theorem of Arithmetic.

Prime factorization is a powerful basis for asymmetric cryptography because it is computationally easy to multiply two primes together to generate a product , butit is computationally hard to start with a product, and obtain its prime factors as output.

Let's examine how we can do asymmetric encryption with prime numbers. First, we select two prime numbers (designated by p and q) and then multiply them together to form the product n. Using n as a base, we can perform some additional math to output two special numbers e and d, such that they have particular properties relative to n. We can then define a public key as the tuple (n,e), and a private key as the tuple (n,d).

Relevant Note(s): Encryption Diffie–Hellman Key Exchange