The most successful public key cryptosystem in use today is RSA – named for its inventors Rivest, Shamir, and Adleman. I first learned about RSA in grad school from one of my professors, Errol Lloyd, who was one of Ron Rivest’s students. Errol is without a doubt the best teacher I’ve ever had (and also a thoroughly nice guy). If you want to go to grad school to study algorithms, you frankly couldn’t do better than heading to Delaware to work with Errol. I have very fond memories of Errol’s class where we talked about this. He’s got a way of teaching where he doesn’t come out and tell you anything; what he does is ask questions that lead you through the process of figuring it out yourself. That’s an incredibly effective way to teach if you can carry it off. Personally, I can’t. And I’ve never known anyone except Errol who could do it for a topic like RSA encryption!
Anyway, moving on… In general, public key cryptosystems are based on problems that are easy to solve computationally in one direction, but really hard to solve computationally in the other. In the case of RSA, the basic underlying problem involves prime numbers: if you’ve got two really large prime numbers, then multiplying them together is easy; but if you’ve got a number that’s the product of two really large primes, factoring it is very hard.
One of the things that makes RSA difficult to explain is that it’s hard to find a starting point. The actual encryption and decryption processes are so simple that
they seem like they can’t possibly work; there’s just no way to make sense out
of why they work without understanding where the keys come from; but it’s strange to describe an encryption system by starting with how to generate keys, when you don’t yet know how they’re going to get used.
The reason for this tangling comes back to the fundamental goal of a public key
system: you’ve got to have two keys which share a complex mathematical relationship.
The encryption system itself is really just a simple expression of the relationship
between the keys. So the algorithm is (conceptually) very simple; the whole thing is
based on the nature of the keys, their relationship, and the way that they’re
generate. It’s not like symmetric cryptography, where you can simply chose a key; in
public key systems, the keys have to be generated to satisfy a set of mathematical
With that it mind, we’ll start working through the way that RSA works by showing
how you can create a public/private key pair. The key generation process is actually
pretty simple, but most descriptions of it get tangled up because it uses a lot of
terminology from number theory. I’ll try to present the standard terms as clearly as I
The basic structure underlying an RSA key pair is a pair of two large prime
numbers. What’s large? That depends on how hard you want it to be to crack. The
tradeoff is that the larger the original pair of primes are, the more complex it is to
compute ciphertext using a key. So you need to choose a key size which makes your keys
hard to crack, without making the cost of encryption and decryption unacceptably
high. Once you’ve decided on a key size, that dictates the size of your two prime numbers, and you’re ready to compute a key pair, as follows.
- Compute two large primes, which are typically named P and Q.
- Using P and Q, you compute a number N=P×Q, which is called the modulus of the keys being generated.
- Compute the totient of the modulus. For any integer, I,
the totient of I (written φ(I)) is the number of integers smaller
than I that are relatively prime to I. Because P and Q are prime, φ(P×Q)=(P-1)×(Q-1). (The totient of P is P-1, because there are P-1 numbers relatively prime to P; the totient of Q is Q-1 for the same reason; and since P and Q are (trivially) relatively prime to each other, the totient of P×Q is (P-1)×(Q-1)).
- Choose an integer, E, smaller than and relatively prime to φ(N). E is
called the public key exponent.
- Compute an integer D such that D×E=1 mod φ(N). D is called the private key exponent.
The public key is the pair (N, E) of the modulus and the public key exponent; and the private key is the pain (N, D) of the modulus and the private key exponent. So you’ve got your key pair.
Encryption and decryption are amazingly simple.
Suppose that the ubiquitous Alice and Bob want to communicate. Alice gives Bob her
public key, (N, E). Now, when Alice wants to send a message to Bob, she encodes the
plaintext of the message as an integer, M. (I’ll leave the exact encoding of plaintext open for now.) To encrypt with her private key, (N, D),
she takes that integer and computes:
Ciphertext = MD mod N
Then to decrypt the message, Bob uses his key pair, and computes:
M = CiphertextE mod N
For Bob to encrypt a message for Alice, he does exactly the same thing that he did to the ciphertext – except he does it to the encoded message, M. For Alice to decrypt that, she does exactly what she did to encrypt the original M, except that she uses the ciphertext she recieved from Bob instead of the encoded plaintext M. In other words, if you’ve got a ciphertext message encrypted by the private key, decrypting it is exactly the same process as encrypting a plaintext with the public key, and vice versa. (This point is what used to cause me lots of confusion remembering what was symmetric and what was assymetric – RSA style asymmetric encryption is really very symmetric in how the algorithm works.)
How can this possibly work? On the face of it, it looks ridiculous! You encode by exponentiating once; you decode not by taking a root, but by exponentiating again!
It all comes back to the way the keys were generated. If we look at the process
in terms of modulo arithmetic, it’s pretty easy to see why it works:
- Take an original message, M. Encrypted, it’s
C = MD mod N.
- Now, take the ciphertext, C, and decrypt it.
M’ = CE mod N.
- Now, expand C: M’ = (MD mod N)E mod N.
- Now, we can combine the exponents: M’ = MD×E mod N.
- D×E = 1 mod N.
- By some trickiness, related to the fact that D and E are relative primes related to both each other and N by their relation to the
totient of N, we can show that the fact that D×E = 1 mod N means
that M’ = MD×E = M1 = M.
Watch how we can walk through a ridiculously simplified example. Let’s start with
a pair of primes – 29 and 61.
- Generate keys:
- First, we compute the modulus: 29×61=1769.
- Then we compute the totient: 1680.
- Then we choose an E which is relatively prime with 1680. To make things easy,
I’ll just pick a prime number: E=13.
- Now, I need to compute a D, such that D×E=1 mod 1680;
or to pull out a bit of standard terminology, D is the modular multiplicative
inverse of E mod 1680. Doing that is an exercise in modulo arithmetic
which gets beyond the scope of what I want to talk about today, so I’ll
cheat: whipping out Mathematica, I get D=517.
- So, the public key is (1769,13), and the private key is (1769,517).
- Now, let’s encode a message. Say the message is 236. So, encrypted by
the public key, that’s 23613 mod 1769 = 7044595136617487310722334457856 mod 1769 = 573.
- And now, let’s decode it. That’s 573517 mod 1769 = 9245694881849602770197401240655288154608138663291308421093411147578949
56675958655700624098981453 mod 1769 = 236.
So it works – but computing those results is not exactly trivial. It happens that there is a fast algorithm for doing those sorts of exponentiations – but “fast” is a relative term. RSA encryption is a lot slower than most symmetric encryptions, by a significant factor.
In real-world use, RSA is rarely used for full-message encryption. It’s used for signatures (where you encrypt a small summary of a message), and for protocol negotiations to allow the two sides to settle on a symmetric encryption key to
use for the rest of their communication.
You’ll notice that I still haven’t gotten back to how you take a message
and convert it to an integer. That’s not trivial. The problem is,
for certain message sizes, or messages with certain numeric properties,
RSA can be easily broken. So you need to protect against those cases. That’s
done by padding the message – adding bits to it in a way that removes
or obscures the properties of the message that would otherwise make it vulnerable.
Discussing the vulnerabilities of RSA for certain types of messages, and how
to build a padding system that defeats them is a topic for another post.
In future posts, I’ll also describe the two most common uses of RSA in more detail – both using RSA for signing a message to prove that you really wrote it; and using
RSA as part of a secure cryptographic protocol where most of the traffic is really
encrypted using a symmetric algorithm.