RSA is a foundational algorithm within modern Cryptography. If we understand how RSA is working behind the curtains then we’ll have an excellent framework to better understand TLS. When we contrast RSA to the more modern ECDSA, we’ll see just how sophisticated a seemingly simple HTTPS connection can be!
Our goal is to make the inner-workings of TLS accessible to developers of all skill levels. This is part two of an ongoing series on Cryptography and how Fly serves Let’s Encrypt TLS around the globe.
Part one: How We Delivery Global SSL with Let’s Encrypt.
To understand the state of the art, it’s useful to brush up on some history. When encryption is symmetrical it means that both the sender and the recipient have identical keys to use for encryption and decryption. When thinking in terms of global networks, distributing those keys safely is an awkward problem!
To address this malady, Whitfield Diffie and Martin Hellman popularized the Diffie-Hellman key exchange algorithm. Confusingly, Diffie-Hellman is a difficult asymmetrical formula that’s used to exchange symmetrical keys.
The purpose of Diffie-Hellman is to mystify the transmission of symmetrical keys so that prying eyes must decode an intensive discrete logarithm problem to peep into the data in transit. Within Diffie-Hellman both sides build their own secret key from a value they receive from the other participant.
There is a bit of a snag, though. Within modern communication, it would be much too burdensome to exchange keys with everyone. We wouldn’t want to give out the same keys, either. If we were a vault and people brought us secrets, we wouldn’t want to give each of our patrons the same key – that’d be silly, they could read each other’s secrets.
Considering that we need a distinct key for each individual, that exchanging keys with each person would be a significant computational burden, and that there are more cryptographic functions needed than simply exchanging keys, new methods arose.
Call Me Ellis: Rivest–Shamir–Adleman (RSA)
In the 70s, James Henry Ellis proposed an idea for non-secret encryption. Instead of exchanging secret keys, he mused, why not exchange the lock? It’s an elegant proposal: one party keeps a secret key then sends an empty lock and a public key to their recipient. That way, the recipient locks their message then sends it back.
Of course, over networks we are not dealing with keys and locks – we are working with 1s and 0s. Applying Ellis’ proposal, Clifford Cocks used discrete mathematics to bring the idea into practice. He created the “trapdoor” one-way function; the function is the lock.
From the perspective of a code-crunching computer, a trapdoor one-way function is easy to compute… when all inputs are known. If the inputs are not known, and one only knows the image, or the apparent pieces that result from or makeup the formula then computation is very difficult.
The ability to expose pieces while remaining encrypted is why you often hear about public and private keys. This method is known as public key encryption, in contrast to the key exchange method within Diffie-Hellman. It’s interesting to note that the keys are interchangeable. The private key is the key which opens the trap door and should be known only to the sender.
Without the private key, the best prying eyes can do is set themselves up for several thousand years grinding out a prime-factorization problem… Until machines hopped up on Quantum madness start slicing through formulae like a hot knife through butter, that is!
To lay a foundation upon which we can understand the old, current, and the new, we’ll take an accessible tour through the mathemagical side of RSA. Seeing public key exchange unfurl will help better your understanding of TLS.
Let’s Get Mathy
If you don’t like Math, feel free to hurdle over this section.
RSA uses mathematical formula to build a practical “lock”, or the trapdoor function. Within RSA, the eventual sender begins the dance by multiplying two large prime numbers to find n; later on, n travels within each key in the key pair. If the numbers that make up n were known then the encryption would be broken, yet we hide n in plain sight:
n = p * q
We call n our modulus. The linchpin within RSA is the mathematical reality that if a computer were to be presented only with n, if n is large enough, it is of great difficulty to determine its prime factors. That’s why it’s called a prime-factorization problem.
Modern cryptographic systems generate rather large prime numbers. After generating numbers of a specific length, they run through either the Fermat Primality Test or the Miller-Rabin Primality Test; that way, one knows their numbers are prime enough to be baffling.
Euler? Euler? Euler?
Next, we need to compute a totient. Somewhere in Switzerland during the 1700s while his compatriots were out engaging in debauchery and imbibing in illicit substance, Euler concocted the following function which counts the positive integers up to a given integer that are relatively prime to n:
ϕ(n) = (p-1)(q-1)
Our two primes, combined in different ways, have given us n and ϕ(n). With these two pieces we’re well on our way to building our “lock”.
In order to span distances, we need to make a public key available and have a private key to unlock the trapdoor function. So, we’ll need key pairs. We can use the following formula to derive our encryption and decryption values that we’ll use within our keys. As mentioned earlier, they’re interchangeable. It’s the distribution or secrecy of the keys which entitles it public or private, encryption or decryption:
e x d = 1 mod ϕ(n)
e is our public encryption value and d is our private decryption value; d is the key which unlocks the trapdoor. When building this formula, we know that e is an inverse of d and vice-versa. Creating one generates the other.
In order to generate e, we’ll need to find a random prime number that has a greatest common divisor (GCD) of 1 in relation to ϕ(n). It must also be less than ϕ(n). To reveal whether our prime number is or isn’t, we deploy the Extended Euclidean Algorithm, which looks like this:
ax + by = gcd(a,b)
This can be confounding; a bit of massaging will help. Once you’ve generated ϕ(n), you then take your e value and ϕ(n) value then plunk them into Extended Euclidean Algorithm. The e value is often made up; it’s an arbitrary factor of both of your primes. A common default for massive primes is 65537. Whatever the number, if the GCD between it ϕ(n) is 1 then you’re laughing. Ha-ha-ha-ha! Hahaha… Haha.. Hah.
Our value d, then, is the multiplicative inverse of ϕ(n): With it, we can derive our prime factors. Without it, intensive computations for hundreds or thousands of years.
Now, in to practice! When introducing the RSA function, we need to have values represent our message. Once encrypted the message is known as the cipher, and then we have our keys. Thus, we welcome m, c and k; k is either d or e and n is the combination of our large prime factors.
F(m,k) = mk mod n
We want to apply this in two ways: encryption and decryption…
F(m,e) = me mod n = c
F(c,d) = cd mod n = m
When dealing with numbers, it’s neat to see the pieces fall so wisely into place. We’ll start with two prime factors: 7 and 17…
n = q x p: 119
ϕ(n) = (p-1)(q-1): 96
e: 7 – found by picking a prime value, then running it through the Extended Euclidian Algorithm.
d (e x d = 1 mod ϕ(n)): 7x = 1mod96 = 55
We now have each variable. To demonstrate encryption and decryption, we’ll need a message. Consider that we want to send a secret meeting time to our compatriots across town. Our compatriots have given us their public key and their private key is known only to them; we’re trying to out 🦊 the villains. We want to meet at 7, therefore: m=7.
We’ll encrypt using the public key with me mod n = c:
77 mod 119 = 63 = c
Isn’t the cipher succinct and wonderful? Ahh, math.
Err– whoops! I’ll tone it down.
Our compatriots then use their private key for decryption:
cd mod n = m
6355 mod 119 = 7 = m
Coooool. Even if the villains have all values but d, they aren’t going to get very far. We just went deep into the guts of RSA. The purpose of our plunge is to convey the general logic that makes up encrypted communication.
Public and private keys contain the core, dense, hard-to-compute modulus and either an encryption value or decryption value. The lock and key metaphor is lovely, but when you see the numbers play together we see the power and the rhythm of public key exchange within asymmetric cryptography.
ESCDA is next. We won’t go as deep.
Encryption Gets Wavey: Elliptic Curve Digital Signature Algorithm (ECDSA)
When you connect over HTTPS, your browser will share all sorts of crucial information about the type of encryption used. It’s here you’ll find RSA or ECDSA referenced:
RSA and ECDSA are for digital signatures. They create, sign for, and verify keys. You’ll notice that there are many acronyms, among which ECDSA or RSA is one. For TLS, one still needs something to encrypt the data and a way to exchange keys.
ECDSA applies Elliptic curve cryptography (ECC) to sign and verify keys. We know that RSA computes monstrous prime numbers and derives keys from the modulus of those numbers. We’ve already bludgeoned you with enough mathematics, so we’ll focus more on the result: Ultimately, the ECC within ECDSA distills down into smaller, faster keys.
Breaking the ECDSA requires one to smeagol through the hard Elliptic Curve Discrete Logarithm Problem. Good luck with that! It’s more challenging, yet more “simple” from a computational perspective than the prime factorization problem that we see in RSA.
For context towards what cryptographers consider “hard”, here is a neat whitepaper!
The keys are not just smaller, they are more efficient. ENCRYPT is a cryptology network par excellence. According to their second report on active algorithms, a 256-bit elliptic curve key is equivalent in security to a 3,248-bit asymmetric key.
For some substance, if you’re using macOS or a unix system, you can query
openssl speed to receive some interesting data comparing RSA vs ECDSA:
openssl speed rsa sign verify sign/s verify/s rsa 512 bits 0.000979s 0.000057s 1021.0 17401.6 rsa 1024 bits 0.005943s 0.000272s 168.3 3675.5 rsa 2048 bits 0.041097s 0.001192s 24.3 839.2 rsa 4096 bits 0.286286s 0.004300s 3.5 232.6
openssl speed ecdsa sign verify sign/s verify/s 160 bit ecdsa (secp160r1) 0.0004s 0.0019s 2388.6 538.9 192 bit ecdsa (nistp192) 0.0004s 0.0017s 2505.4 581.0 224 bit ecdsa (nistp224) 0.0006s 0.0026s 1743.9 389.2 256 bit ecdsa (nistp256) 0.0007s 0.0034s 1376.7 296.3 384 bit ecdsa (nistp384) 0.0017s 0.0089s 580.5 112.5 521 bit ecdsa (nistp521) 0.0035s 0.0190s 285.4 52.6
Ahh, fascinating. You can see that the signing speeds of ECDSA are most excellent while it’s verification speeds are pretty good. While RSA could do all of signing and verifying, encrypting, and key-exchanging we only use it for signing and verifying. Given the security and performance improvements seen in ECDSA, though, its now our preferred method at Fly. ECDSA’s signatures per second results in more performant servers, which boils down to faster TLS for the end-user.
But, hey, if RSA and ECDSA are for “signature and verification” then what’s actually encrypting stuff? What’s doing the key exchange? We’ll break for awhile to let things marinate.
In our next article, we’ll explore forward secrecy and ciphersuites. When we’re all done, you’ll be able to look at strings like this: ECDHE-ECDSA-AES-256-GCM-SHA384 and know what’s doing the signing and verifying and the key exchange and the encryption.
Until next time…!
The next article, How Ciphersuites Work: TLS in Pieces, has been published and is available here!
This article was co-authored by Founding Engineer Mat Byczowski.