Asymmetric Key Cryptography

Asymmetric key cryptography allows encrypting small amounts of plaintext into ciphertext and back, using a matching pair of keys - you encrypt with one key of the pair and decrypt with the other. Examples of real-world asymmetric algorithms are: RSA, DSA, ECC, ElGamal and Diffie Hellman Key Exchange.

Compared to symmetric key cryptography, asymmetric key cryptography is very recent. It was developed first by a team at GCHQ in the UK in 1973, but was kept classified for years. It was independently invented a few years later by Whitfield Diffie and Martin Hellman at MIT in the U.S. (published in 1976).

The first application of asymmetric key cryptography was the Whitfield-Diffie Key Agreement Algorithm. Later the RSA encryption algorithm was created by Ron Rivest, Adi Shamir and Leonard Adelman (also of MIT). They founded RSA Security to commercialize this invention. This algorithm is very different from symmetric key "slice and dice" algorithms, and depends on the difficulty of factoring the product of two large prime numbers. It is fairly quick to multiply together two 150 digit primes, but can take millions of times longer to factor that product into the two primes. Creating a key pair requires only the creation of two large primes and multiplying them together (a few seconds for typical keys on modern PCs), while deriving one key from the other (usually the private from the public) requires factoring the product into the two original primes (requires thousands of years using many computers, with current technology for 1024 bit or larger RSA keys).

Another asymmetric algorithm (ElGamal) is based on a similar hard math problem involving "discrete logarithms". These kind of math problems are called "trapdoor functions". This is because there is an enormous difference in effort and time to go through the trapdoor in one direction (required to create key pairs) versus the other direction (to derive one key from the other). This is similar to the behavior of an actual trapdoor in a pump, or an electronic diode.

Asymmetric key cryptography is not very intuitive. Instead of using the same key to lock and unlock my padlock, imagine that I lock my padlock with one key (that can only lock it) and unlock it with a different key (that can only unlock it). I can't unlock the padlock with the key I used to lock it!

Actually the two keys of a pair are closely related, and are created together. One key of a pair is used to lock the padlock - and it is OK to publish this one, so that anyone can lock the padlock. This is the public key. The other key of the pair is used to unlock the padlock, so it must be kept secret from everyone else - so only I can unlock the padlock. This is the private key. In theory you can derive the private key from the public key, but that involves "going through the trapdoor" in the hard direction (e.g. factoring a 300 digit product of two primes).

You want anyone to be able to obtain and use your public key to encrypt something they want to send to you, but you should be the only one that can decrypt it (using your private key).

 

Here it basic asymmetric encryption and decryption in mathematical notation.

PT = the plaintext (message), CT = the ciphertext (encrypted information)

RSA = asymmetric encryption algorithm, RSA-1 (RSA "inverse") = asymmetric decryption algorithm

Kpub = someone's public key, Kpriv = that same person's private key

PT' = the recovered plaintext

 

Encryption:

CT = RSA(PT, Kpub)

Decryption:

PT' = RSA-1(CT, Kpriv)

Interestingly enough, it also works the other way around, where I am the only one that can encrypt something (using my private key) but anyone can decrypt it (using my public key):

Encryption:

CT = RSA(PT, Kpriv)

Decryption:

PT' = RSA-1(CT, Kpub)

This may sound kind of strange, but it is used in conjunction with a message digest to create a digital signature.

 

Hybrid Systems

Asymmetric key cryptography is slow (in terms of amount of data that can be encrypted per second) and difficult to implement (compared to symmetric key), but effectively solves the key management problem. Instead of every communicating pair needing a unique symmetric key (or every message needing a unique one), each communicating party needs exactly two keys - a matching public/private key pair. This is far easier to set up and manage than symmetric keys.

However, since asymmetric is thousands of times slower than symmetric, real world systems combine the two technologies in a hybrid system. Asymmetric algorithms are used only to securely exchange a unique symmetric session key, which involves encrypting or decrypting only 56 to 512 bits of data (a symmetric key or a message digest). The bulk data is handled by symmetric key or message digest algorithms.

Here it is a typical real world hybrid "digital envelope" scheme in mathematical notation.

PT = the plaintext (message), CT = the ciphertext (encrypted message)

RSA = asymmetric encryption algorithm, RSA-1 (RSA "inverse") = asymmetric decryption algorithm

Kpub = someone's public key, Kpriv = that same person's private key

AES = symmetric encryption algorithm, AES-1= symmetric decryption algorithm

SSK = symmetric session key, ESSK = encrypted session key, SSK' = recovered session key

PT' = the recovered plaintext

 

Sender creates CT and ESSK, sends to recipient

SSK = random symmetric key

CT = AES(PT, SSK)

ESSK = RSA(SSK, Kpub)

Recipient gets CT and ESSK, recovers SSK' and PT', destroys SSK'

SSK' = RSA-1(ESSK, Kpriv)

PT' = AES-1(CT, SSK')