Asymmetric Key Cryptography

There is a fairly recent cryptographic scheme that is quite different from symmetric key cryptography. It is called asymmetric key cryptography or public key cryptography. The primary difference is instead of using the same key to decrypt something that was used to encrypt it, each person is issued two keys, which are related and always generated together.

You can encrypt something with either key of a related keypair, but only decrypt it with the other key of the same keypair. With asymmetric keys, there is no combinatorial explosion of keys – for 50 people there are a total of 100 keys, only half of which need to be kept private. Anyone can encrypt something for me using my public key, but only I will be able to decrypt it using my private key. Anyone can check something I digitally signed using my public key, but only I can create such a signature using my private key.

Public and Private Keypair

One of the keys is the public key. It is published (made available to others), e.g. in a shared address book in Active Directory. It is normally embedded in a digital certificate which allows any user of that key to verify that it is the correct public key for some person or device. A Certification Authority (CA) issues the certificate after validating all of the information in it, and digitally signs it using their own private key. The CA’s public key (in another certificate) can be used by anyone to validate the digital signature on the certificate.

The other key is the private key, which is kept secret by the key owner, ideally in a hardware cryptographic token. It is never published or shared with anyone. It is not embedded in a digital certificate (there is no such thing as a private key certificate). The private key may be escrowed if it was used to encrypt information that belongs to the key owner’s employer, instead to the key owner. This allows the employer to recover their information even if the key owner loses or destroys their private key or they leave without surrendering it. Private Key Escrow may be required in some situations for compliance with various laws.

The two keys are related mathematically, but it can be 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 quantum computers arrive, most current 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.

How Asymmetric Key Cryptography Works

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).

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. General asymmetric encryption and decryption based on the “factoring the product of two large primes” problem. It was patented, but that expired in 2001. We are now reaching the point of diminishing returns for increasing key length.

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 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, 384-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.

Certificate Validation

Anytime you use a public key, you need to check several things about the certificate it is in before accepting the key as valid:

    • check the validity period – the current time should be after the start date but before the end date. After the end date the certificate (and corresponding private key) should not be used, except for opening old encrypted files. When a digital certificate expires, it should be renewed (re-issued with a later expiration date) by the issuing CA. This is to keep the identifying information in the certificate current and accurate.
    • check the digital signature on the certificate (using the public key of the issuing CA)
    • follow a trust chain (to parent, grandparent, etc) of the cert in question until you reach a trusted root certificate, which is self-signed.
    • check for revocation of the certificate by the issuing CA (by checking the appropriate Certificate Revocation List or Online Certificate Status Protocol)

Conceptual Model

As before, encryption and decryption with asymmetric key algorithms can be represented as mathematical functions or transforms:

ciphertext = RSA(plaintext, alice’s public key)

plaintext = RSA-1(ciphertext, alice’s private key)

Or if you are more visually oriented:

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.

You can reverse this (encrypt with a private key and decrypt with the corresponding public key) to create a digital signature. In this case, the signer uses their own private key, and the signature validator needs the signer’s public key (in a digital certificate). It is actually typical to include the signer’s digital certificate a part of the message, since it doesn’t matter how you get that certificate (it can be verified no matter how you got it).

ciphertext = RSA(plaintext, alice’s private key)

plaintext = RSA-1(ciphertext, alice’s public key)

or for the visually oriented:

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 types of cryptography.

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 a plaintext (the Random String) and encrypt the plaintext with the public key (producing the ciphertext or Challenge String). I finally decrypt the ciphertext with the private key, recovering the original plaintext (the Challenge Response).

Note how much larger the ciphertext is than the plaintext. The ciphertext is actually a binary object, but it is represented here encoded with base64. This crypto challenge is used in various places, like TLS authentication and the Sixscape SixToken application.