Bob's Blog

How Does Asymmetric Cryptography Work?

I recently explained how asymmetric encryption is absolutely vital for protecting information and your identity. I mentioned that we have had two major forms for some time. RSA was publicly described in 1977, and Elliptic Curve Cryptography or ECC was first suggested in 1985.

I mentioned that both base their security on the difficult of solving a trapdoor problem, a math problem that is much harder to solve in one direction than the other.

Toward the end of that earlier post, I briefly mentioned the need for what are variously called quantum-safe or quantum-resistant or post-quantum algorithms. Because we believe that a large enough general-purpose quantum computer could quickly solve the trapdoor problems used by RSA and ECC, we need new asymmetric ciphers based on totally different mathematics.

That earlier article was already too long, and I promised that the details of the asymmetric ciphers would come in a later post. Here it is!

Where Did Cryptography Come From?

We've had encryption for millennia, and for almost all of that history it could be fairly described as symmetric. Decryption was plainly the reverse of the encryption process. Ancient ciphers like the Atbash and other simple monoalphabetic substitution ciphers, developed by Hebrew scholars around 600–500 BCE, were defined by a method. There wasn't really a key as a separate piece of data, beyond the specific details of the substitution. But it was straightforward to decipher the message by reversing the method.

Ahmad al-Qalqashandi wrote the Subh al-a 'sha, a 14-volume encyclopedia, in the early 15th century CE. It included a section on cryptography, attributed to Ibn al-Durayhim who lived 1312–1361, his original writings have been lost. His material included in Subh al-a 'sha included encryption by both substitution and transposition, the first description of homophonic substitution (multiple substitutions for one cleartext letter), and a discussion and demonstration of cryptanalysis.

The German monk and occultist known as Johannes Trithemius described a cipher that used a tabula recta, a rectangular substitution table, in 1508. It supported polyalphabetic encryption and was much more resistant to frequency analysis. The specific content of the tabula recta and the way in which it is used form a key. Things progressed from there, although the ciphers remained symmetric until the 1970s.

Where Did Asymmetric Ciphers Come From?

A huge problem with symmetric ciphers is that two parties wishing to communicate must share a secret key. One solution is to have a courier carry keys back and forth. But if you're going to do that, why not simply have the courier carry the actual messages?

Claude Shannon, from Wikipedia.

Claude Shannon had worked on various communication problems during World War II. A paper he had written late in the war at Bell Labs was published in the Bell System Technical Journal in 1949, "Communication Theory of Secrecy Systems". While statistics and logic had certainly played crucial roles in war-time cryptanalysis, Shannon's work was really the beginning of mathematical cryptography. He made a distinction between unconditional security, a cipher unbreakable by an attacker with unlimited resources, and practical security, resistant to an attack using limited resources.

Shannon proved that a one-time pad, created and used perfectly (and thus impractical), would be the only way to provide unconditional security. As we'll see, asymmetric ciphers can only provide practical security, sometimes called computational security, based on their mathematics. They not perfect, but they're considered "too strong" for an attacker to break them based on our assumptions about the attacker's resource and the length of time the information must remain secret.

There was academic discussion of the need for something totally different — encryption and decryption with keys, but without a shared secret key. Trapdoor functions seemed promising. Those are math problems that are much harder in one direction than the other.

Cryptographers at GCHQ, the British signals intelligence agency, wrote some classified papers during the 1960s and 1970s. That led to some asymmetric cryptography algorithms in the early 1970s, although of course they remained government secrets.

Things really started happening in the mid 1970s. First, the U.S. Federal Register published a draft of DES, the Data Encryption Standard, in 1975. That symmetric cipher was the first step toward government standardization and industrial adoption of cryptography. It was published as a standard in 1977.

In 1976 Whitfield Diffie and Martin Hellman published "New Directions in Cryptography". They had hoped to develop asymmetric encryption and decryption. What they ended up with is a fantastic system for key agreement, allowing two parties in an insecure setting to agree on a shared secret. It's known as Diffie-Hellman or simply DH. That shared secret could then be used as a symmetric cipher key. Diffie and Hellman also explained how to create and verify digital signatures, although its asymmetric cipher component wasn't available yet.

Whitfield Diffie, from Wikipedia.

Martin Hellman, from Wikipedia.

One year later, in 1977, Ron Rivest, Adi Shamir, and Leonard Adleman published a cryptosystem that came to be known as RSA.

RSA was the first practical asymmetric encryption algorithm.

Taher Elgamal then described an asymmetric encryption algorithm based on Diffie-Hellman, in 1985. A variation of it came to be used in the standardized Digital Signature Algorithm.

Those are the systems and their developers up into the mid 1980s. You always encrypt the message itself with a symmetric cipher, DES originally, then TDES or 3DES, and typically AES today. You could negotiate the shared secret key with Diffie-Hellman. Or, one party could select the secret key and then encrypt it with the other party's RSA public key. They could safely transmit that because only the other party knows their corresponding private key needed for decryption of the shared secret.

So how do Diffie-Hellman and RSA work?

How Does Diffie-Hellman Work?

The standard two players in one of these cryptography scenarios are Alice and Bob. They agree on a base, \( b \), and a modulus, \( m \). They can safely agree on these values in public, and they probably should simply choose a base and modulus in common use. The modulus \( m \) should be a large prime number, at least 300 digits, while the base \( b \) can be a small number, with 2 and 5 being the usual choices.

I'm using MathJax to do math within HTML.

Alice and Bob each pick a secret number, \( S_{alice} \) and \( S_{bob} \), respectively. These should also be large, at least 100 digits each. Don't worry too much, computers are very fast at integer math, even with such enormous numbers.

Each of them then calculates a public value, \( P_{alice} \) and \( P_{bob} \), by raising \( b \) to the power of their secret and then applying modulo \( m \).

Alice calculates her public number as:

Bob calculates:

They then exchange those public numbers. This is safe because no one except the creator of the public value can figure out what the private value must have been. Information has been thrown away with the exponentiation followed by the modulo operation. An attacker would have to do a brute force attack using all values from 0 through \( m \), and at that point there would be an enormous number of possible solutions to be tested.

The would-be attacker is frustrated by the extreme difficulty of the Discrete Logarithm Problem. Put another way, the difficulty of the DLP provides the security of Diffie-Hellman.

Now that Alice and Bob have each other's public value, they can calculate a shared secret. Each raises the other party's public value to the power of their secret, and then applies the modulo operation.

Alice calculates the shared secret as follows. A computer algorithm would simply do the math shown as the first line. But that sounds like "And now magic happens", so I work through what that equation really means. That way you see see how the two parties come up with the same shared secret, while only knowing the other party's public value in addition to their own private and public values.

Bob does a calculation that looks similar but with the roles reversed:

As I said, a modern computer can calculate this quickly even though the numbers are huge. That means that Alice and Bob can each pick a new private value for every message, calculate new public values, exchange those, and calculate the new shared secret. That improvement make the shared secret be ephemeral, meaning that it is only used for this one message, and if the private value were somehow exposed, it would not expose the content of any other message. Since the private value is generated and then just used for two calculations, there's no reason to store it anywhere, making it extremely unlikely to be exposed. You will see DHE meaning Diffie-Hellman Ephemeral used in descriptions. For example, the Qualys SSL Labs evaluation of a web server.

How Does RSA Work?

Integer factoring serves as the trapdoor function for RSA. To use it, you select two large prime numbers, \( p \) and \( q \). They should be similar in magnitude but differing in length by a few digits, as that makes factoring even more difficult. For example, in base 10, a 615-digit prime \( p \) and a 617-dit prime \( q \). Multiplying them together leads to a 1232-digit product, approximately \( 2^{4096} \) and thus a 4096-bit modulus or key size.

At that point your public key is the product \( n \) of those two prime numbers, \( p \cdot q = n \). Your private key, which takes a few calculation steps, is based on \( p \) and \( q \).

An attacker would have to start by factoring your public key \( n \) into its two large prime factors \( p \) and \( q \). If you don't feel comfortable with this, if you think that factoring 4096-bit or 1232-digit numbers isn't hard enough, RSA supports using arbitrarily large prime factors and resulting keys.

I already had a page explaining how RSA works, see it if you're interested in how the private key is formed from the two large primes, or in the keys are used for encryption or decryption.

Elliptic Curves Arrive and Take Over

Above I said "Don't worry too much, computers are very fast at integer math, even with such enormous numbers." But I didn't say not to worry at all.

The above math is plenty fast enough to do Diffie-Hellman or RSA for, say, each email you send, or each file you put into an archive. There aren't that many messages or files, and both of those are background types of operation where you don't really notice the start-up delay.

However, people are concerned about web browser connections starting as fast as possible. That's an interactive situation, with an impatient user waiting only a limited amount of time before giving up on a slow server and looking at something else.

Neal Koblitz and Victor Miller independently suggested using elliptic curves in cryptography back in 1985. There just wasn't much of a perceived need for that at the time. Notice that they were talking about elliptic curves, which might look like the following and are which are not at all like ellipses:

After the appearance of HTTP, and then HTTPS and the need to set up symmetric session keys, and parallel demands for increased security but with increased speed, Elliptic-Curve Cryptography or ECC really took off in 2004–2005. Its security comes from the difficulty of solving the elliptic curve discrete logarithm problem, similar to the problem Diffie-Hellman relies upon. It's another case of "extremely difficult to solve, but easy to verify."

The ECC keys are much shorter, for the same level of security. U.S. NIST's Special Publication SP 800-57, to which NSA cryptographers contributed, presents this table showing estimated equivalent strength against brute-force attack:

ECC keys must generally be about twice the length of a symmetric key for equal resistance. Yes, that "521" is correct in the last row. But look at how fast the required RSA key lengths grow!

The mathematics of elliptic-curve cryptography aren't that hard, much of it can be explained with grade-school arithmetic. But there are some concepts you probably don't expect, and so it takes careful explanation.

Once again, I already have a page on the topic. Actually, given what all is involved it'a series of three pages explaining how Elliptic-Curve Cryptography works.

Elliptic-Curve Cryptography can be used in the Diffie-Hellman logic, taking the place of the exponentiation and modulo operations. The result is called ECDH or Elliptic-Curve Diffie-Hellman. And, it's usually employed as it should be, to agree on an ephemeral symmetric session key. And so, ECDHE, for Elliptic-Curve Diffie-Hellman Ephemeral.

Below is the "Cipher Suites" section resulting from scanning this server with the Qualys SSL Labs analyzer. They leave the final "E" off DHE and ECDHE. TLS 1.3 only support ECDHE key agreement. For the ciphers I have enabled, only the two least-preferred ones use DHE. Nothing supports non-ephemeral key agreement, why would anyone do that? You will see that the ECDHE choices all use the x25519 elliptic curve.

If you scroll all the way to the bottom of any page on my site, you will see that the cryptographic details are reported in the footer: TLS version number, elliptic curve used for symmetric key agreement, and the symmetric cipher used to protect the data. With Chrome I see:
TLSv1.3 / X25519 / TLS_AES_256_GCM_SHA384

Quantum Worries Arise

I need to address the worry about how quantum computing could soon break all Internet security, and what's being done to alleviate that problem.

We're worried about an adequately large and stable general-purpose quantum computer. That's a lot of qualifiers for one sentence! But it comes down to:

Adequately large — It needs to have enough qubits, the working nodes of a quantum computer.

And stable — If you think you have enough qubits for the job, enough of them need to be really functional to solve the problem.

General purpose — It isn't some odd contraption put together to solve just one problem, which probably isn't the one you had in mind.

Quantum computers aren't going to be magical (as far as we know), they won't be able to solve every single problem almost instantaneously. But, unfortunately for the Internet, which has relied on Diffie-Hellman, RSA, and ECC, quantum computing poses a grave threat to all of them.

Shor's Algorithm was developed in 1994. If it had an appropriate quantum computer on which to run, if could break RSA, classic Diffie-Hellman, and Elliptic-Curve Diffie-Hellman.

Things aren't nearly so grim for symmetric ciphers. Grover's Algorithm came out just two years later, in 1996. It could reduce the strength of a symmetric cipher down to that of just half its key length. Dropping from 256-bit to 128-bit strength is a big hit, but \( 2^{123} \) is still a pretty big number, and NIST as seemed pretty comfortable with that level of security for some time.

The problem, though, is negotiating session keys for the symmetric ciphers which protect all the data. We need asymmetric algorithms, but ones whose security isn't based on the difficulty of the factoring problem or the discrete logarithm problem.

Fortunately, top cryptographers are working on it.

Unfortunately, they're off to a somewhat shaky start.