There is another type of encryption that is very different from symmetric key encryption. It is based on some recent technology and algorithms. The technical term for it is asymmetric key encryption, but it also sometimes is called public-private key encryption .
The first paper on asymmetric key cryptography was by Whitfield Diffie and Martin Hellman in 1975. In 1976, they released their first asymmetric key algorithm, Diffie-Hellman Key Exchange. In 1977, RSA released a scheme for general asymmetric key encryption and decryption now known as the RSA algorithm. It was patented by RSA, so widespread use didn’t happen until the patent expired in 2000.
Although it was not made public until long after this, Clifford Cocks and Malcolm Williams at GCHQ in the UK were actually the first to invent the Diffie-Hellmann algorithm in 1974.
In comparison, the “Caesar Cipher,” which is a form of symmetric key cryptography, literally dates from Roman times (2000 years ago).
Symmetric key encryption uses the same key for both encrypting and decrypting. If Alice encrypts something with a particular symmetric key, then Bob needs a copy of that same key to decrypt it.
Asymmetric key encryption uses a matched pair of keys, usually called public and private keys, as the key owner should publish the public key (e.g., in Active Directory), but keep the private key secret (never reveal it or share it with anyone). Anyone can encrypt something with Alice’s public key, but only she can decrypt the resulting ciphertext, using her private key. This is ideal for authentication and key management (securely sharing a symmetric session key with someone else).
The server sends its server certificate (including its public key) to the client.
The client verifies the server certificate as valid, trusted, unexpired, and unrevoked.
The client extracts the server’s public key.
The client creates a random string of characters and encrypts it with the server’s public key.
The client sends the resulting ciphertext to the server as a crypto challenge.
The server decrypts the challenge using its private key and returns the recovered plaintext as the challenge response.
The client compares the returned challenge response to the original string – if they match, that proves the server possesses the private key corresponding to its server certificate (without revealing it), which provides strong authentication.
Client-to-server authentication (aka Strong Client Authentication) does the same thing using an X.509 client certificate (which identifies a person, not a node), with the roles reversed. This is not widely used due to the cost and complexity of providing every user with a unique, trusted client certificate.
The client securely creates a symmetric session key (unique to this connection).
The client encrypts the symmetric session key with the server’s public key (from its server certificate).
The client sends the resulting ciphertext to the server.
The server decrypts the encrypted session key with its private key, recovering the original symmetric session key created by the client.
The server and client have now securely exchanged a symmetric session key.
Note that today, this key exchange is often done using Diffie-Hellman Key Exchange instead of the preceding.
Public keys are always provided in the context of a signed X.509 digital certificate, ideally from a trusted third party (Certificate Authority) to prevent the “public key substitution threat.” Without a certificate, a hacker could trick you into using a public key they created, thereby assuming the victim’s identity. The certificate is protected by a digital signature to prevent tampering with any of the items as well as authentication of the issuer. It “binds” the certificate subject’s identity to the public key. A great deal of the security provided by PKI depends on this mechanism. There is more detail on X.509 certificates and PKI provided in later chapters.
Note that there is no such thing as a “private key digital certificate,” since you never publish private keys nor need to determine if one belongs to the purported owner.
We showed examples of some of the very large numbers used in symmetric key cryptography in an earlier chapter. Those are tiny compared to the numbers used in asymmetric cryptography. For example, a 1024-bit number takes 309 digits to represent it in decimal, while a 2048-bit number takes 617 digits. When creating a key pair for 2018-bit keys, you multiply together two 2048-bit prime numbers resulting in a mind-boggling 1,234-digit number.
Likewise, Alice can encrypt something with her private key, and anyone can decrypt the resulting ciphertext with her public key. This is ideal for digital signatures. Only Alice can digitally sign something with her private key, but anyone can verify her digital signature. Note that symmetric key encryption does not do either of these things well. Hence, asymmetric key encryption is complementary to symmetric key encryption. It is not a competitor to it. Most modern cryptographic tools use both symmetric key and asymmetric key cryptography often including hash algorithms as well.
The math behind asymmetric key cryptography is complex, but you don’t need to understand that in order to use it.
In practice, each pair of users exchanging things securely using symmetric key encryption needs a unique symmetric key. This can get complicated in a hurry with a large number of users. In comparison, with asymmetric key encryption, each user has exactly two keys, one public and one private. And only the private one needs to be secured. The public key can be shared with everyone. The two keys are related mathematically, but it is extremely difficult, time-consuming, and/or expensive to derive one from the other. At the current state of the art, a 2048-bit RSA key would require thousands of years of computer time to derive the private key from the public one.
Unfortunately, when practical quantum computers arrive, many current existing asymmetric algorithms will be crackable in a very short time (minutes or hours). Many groups are now creating quantum safe asymmetric key algorithms for applications that may be used for a long time.
Typical key lengths with symmetric key encryption today range from 128 bits to 256 bits. Asymmetric keys are usually much longer. With RSA keys, the minimum recommended length today is 2,048 bits, and high-security (e.g., DoD Top Secret) users may use RSA keys over 15,000 bits long! There is a more recent set of asymmetric key algorithms based on Elliptic Curve Cryptography (ECC) . The key lengths for equivalent cryptographic strength for these algorithms are much shorter (e.g., 384-bit ECC is as strong as 8,192-bit RSA).
The math behind ECC is similar to that for RSA, but the two primes must be a coordinate pair that lies on one of a list of possible elliptic curves. For reasons we won’t go into here, the strength of the encryption goes up far more rapidly with increasing key length than with RSA. Due to the shorter key lengths in ECC, it is an ideal solution for low-end devices (as in IoT) that have limited CPU power.
Asymmetric key encryption is also much slower than symmetric key encryption. You typically only encrypt or decrypt short things, like a 128- to 256-bit symmetric key or a 256- to 512-bit message digest. You would never encrypt an entire one-megabyte file with asymmetric key cryptography.
To send an encrypted message, you would create a random symmetric session key, encrypt the message with that session key, and then encrypt the symmetric session key with the recipient’s public key. The recipient would decrypt the encrypted session key with their own private key and then decrypt the message using the recovered symmetric session key. Most real-world systems use both symmetric key and asymmetric key algorithms: symmetric key for bulk encryption and asymmetric key for secure session key exchange.
For a digital signature, you would create a message digest of the message (e.g., using SHA-256, producing a 256-bit digest) and then encrypt that using the signer’s private key. The recipient would recover that digest by decrypting it with the sender’s public key and then generate a new message digest of the received message. If the recovered digest and the regenerated digest match, that is a valid signature. That provides message integrity (you know the message has not been tampered with since it was signed) and sender authentication (you know for certain who signed the message). Here, asymmetric key and message digest algorithms are used together.
Comparing Asymmetric Key to Symmetric Key
Symmetric key cryptography is based on “slice and dice” operations (substitution and transposition ciphers), while asymmetric key cryptography is based on complex mathematical operations (“trap door functions”) that require far more time to reverse than to create. For example, RSA keys are created by multiplying together two giant (300-digit) prime numbers. Deriving the private key from the public key requires factoring that product into the two original primes (a known difficult problem in math). This can take tens of thousands of times longer than multiplying two primes together.
If I encrypt something with someone’s public key, only that person’s private key can decrypt it. The public key it was encrypted with cannot decrypt it. If I encrypt a message digest with my private key (to create a digital signature), only my public key can decrypt it to validate my signature.
Common Asymmetric Key Algorithms
Diffie-Hellman Key Exchange (1976) – A scheme for remote symmetric key agreement, based on the discrete logarithm problem.
RSA (1978) – Specified in PKCS #1. Note that “PKCS” was a set of standards (Public Key Cryptography Standards) published by RSA. These have since been incorporated in IETF RFCs, but most people still refer to them by their RSA names. For example, PKCS #1 is now specified in RFC 8017. General asymmetric encryption and decryption are based on the “factoring the product of two large primes” problem. It was patented, but that expired in 2000. Key lengths currently range from 2048 bits to over 15,000 bits. We are now reaching the point of diminishing returns for increasing key length. RSA was patented for a long time, but that expired, and anyone can implement or use it with no royalties today.
El-Gamal (1985) – General asymmetric encryption/decryption based on Diffie-Hellman Key Exchange and the discrete logarithm problem.
DSA – Digital Signature Algorithm (adopted as FIPS 186 in 1993) – derived from the El Gamal algorithm. Only used for digital signatures, not encryption. Available worldwide royalty-free.
ECC – Elliptic Curve Cryptography (first introduced in 2004–2005) – similar to RSA, but the two primes must be coordinate pairs that fall on one of a number of “elliptic curve” functions. With ECC, good curves are patented, and you must pay royalties to use them. ECC is now starting to replace RSA. For example, 256-bit ECC is roughly as strong as 2048-bit RSA, and the strength goes up much faster with increasing key length than with RSA. It is also much faster for a given cryptographic strength than RSA, so is being used heavily on low-end devices, as are often found in IoT products.
Conceptual Model
Visual representation of mathematical functions or transforms
This would be the way to use it to encrypt something. You must obtain the client certificate of the recipient in order to send them an encrypted object. The recipient would use their own private key to decrypt it.
Visual of encrypting with a private key and decrypting with the corresponding public key
Asymmetric keys tend to be rather larger (thousands of bits) than symmetric keys (128 to 256 bits). Asymmetric key algorithms are very, very slow compared to symmetric key algorithms. Typically, only relatively small things (a symmetric key, a message digest, or a short random string of characters) are ever encrypted or decrypted using asymmetric key algorithms. They are ideal for key management or creating digital signatures. They are not suitable for bulk encryption or decryption (like an entire message or file). Most real-world systems use both symmetric key and asymmetric key algorithms.
Cryptographic Algorithm Performance
Comparison of speed of various cryptographic algorithms on a typical desktop PC
Crypto Challenge Demo
This screenshot from a demo app I wrote can give you a better idea of how this all works. I load the public key (from a certificate) and the corresponding private key. I then generate the plaintext (the random string ) and encrypt it with the RSA and the loaded public key (producing the ciphertext or challenge string). I finally decrypt the ciphertext with the private key, recovering the original plaintext (the challenge response). Normally, one computer would create the challenge and send it to another computer. The other computer would respond to the challenge by decrypting it and returning the result to the first computer which would compare that result to the original random string.
Ciphertext is a binary object, but is represented here encoded with base64
To use this app, you load the certificate and corresponding private key, then enter or generate a random string (e.g., by clicking Generate), and then produce the challenge string by clicking Encrypt Random String with Public Key. Finally, you recover the random string by clicking Decrypt Challenge String with Private Key. If an attacker makes any change at all to the challenge string, the decryption will fail.