RSA
Practical public-key cryptography
by Ben Goren
The problem
Cryptography—the art of sending messages that are meaningful to the intended recipients only, even if others see the message—has been around at least since the Romans. In some senses, it’s even been around as long as writing and could even have been part of the impetus behind the creation of writing.
And for all but the last couple decades of its history, cryptography has had a flaw that has significantly inhibited its usefulness. Traditionally, before two parties can exchange secret messages, they must first exchange some sort of secret key. Anybody who has the key can read the encrypted messages. And if you have a method of getting the key to the recipient without eavsdroppers getting a copy, why not use that method for the actual message, itself?
The solution
Then, in the mid-1970s, Whitfield Diffie, Martin Hellman, and Ralph Merkle figured out something amazing: how to use not one key for encryption, but two1. The keys work together in such a way that one of them can encrypt a given message but not decrypt it afterwards. The other key is used decrypt the message. The pair of keys are very closely related to each other; only the second half can decode messages encrypted with the first half, and the first half can only create messages that can be decoded by the second half.
How is this significant? Imagine two people, Alice and Bob, who have never met but who want to communicate without anybody knowing what they’re saying. Alice creates a pair of keys. One of them she will guard most carefully, for it will allow the decryption of messages. So long as she keeps it protected, only she will be able to read the encrypted messages. The other key is used to create those encrypted messages, and is what she first sends to Bob. How she gets it to Bob doesn’t matter (much; read below for a potential attack): she could send it to him on a postcard or even publish it in the classified section of the newspaper. When Bob wants to get a message to Alice, he uses the published key to encrypt his message, and then sends that result to Alice. If he wanted, Bob could publish it in the next edition of the paper.
Because Alice is the only person who has the key that can decrypt the message, nobody else can read it. If Bob destroys the message after he sends it, even he can’t read the encrypted message to Alice. All he can do is create messages that only Alice can read.
For that matter, anybody else who reads Alice’s advertisement with her public key (as it’s usually called) can send messages to Alice that only Alice can read. It’s actually to Alice’s advantage that as many people as possible get her public key; that way, anybody can easily contact her in a private, secure manner.
Naturally, Bob does the same thing at his end for Alice to communicate with him. Bob creates his own pair of keys, publishes the public one and holds the secret key close to his vest. Alice gets Bob’s key, encrypts her messages to him with them, and Bob decrypts them with the private key.
The end result is (a pair of) virtual drop boxes, like what you might see at a library (for after-hours returns) or a bank (for deposits). Anybody can come by and return a book or make a deposit, but only the librarian or bank manager (who has the keys to the drop box) can retrieve the book or checks.
But wait! There’s more!
There’s an interesting—and very useful—side effect to this trick. What happens when you turn things around? Let’s say that Alice keeps close the key for encrypting messages and gives away to all and sundry the key to decrypt them. When she sends a message to Bob, she first encrypts it. Bob has no trouble decrypting it because he’s got the key that Alice has given away for that purpose. However, Bob knows with some certainty that Alice was the one who sent the message—she’s the only one who has the private key that could have created the message that he decrypted. In essence, Alice has signed her message.
Combining the two techniques is also possible. First, Alice would encrypt the message with her private key (akin to signing her name at the bottom of a letter); then, she would encrypt the message again with Bob’s public key (like putting the letter in an envelope). Bob is the only person who can read the result; after he decrypts it with with his private key (opening the envelope), he decrypts it again with Alice’s public key (verifying her signature).
With some algorithms, the same pair of public and private keys can be used for both encryption and signing; others require the creation of separate keys. In any event, a well-designed implementation will make such details transparent.
The how
Hopefully, all of that makes sense on an abstract level. But how does it actually work? How do you create a pair of keys, what needs to be done to encrypt them, how do you decrypt…?
Fortunately, the mechanics aren’t too hard to follow—even if it’s not something you nor I would ever have a prayer of thinking up ourselves.
The strength of all public key cryptosystems—as these techniques are called—relies on what mathematicians call “hard problems.” That doesn’t mean things like long division or figuring out the length of the hypotenuse or other things that bothered you in school, but rather problems that really do require a lot of trial-and-error to solve, with no shortcuts that can give you the answer quickly.
Let me give you an example. Quick, what’s thirteen times seventeen? Use a calculator, if you like. Now, just as quick, what numbers, when multiplied together, make 133?
The first problem should be no trouble for you—especially if you use a calculator, but even if you use pencil and paper. The second one, unless you’ve got your multiplication tables mesmerized to twenty, will take you a bit of time. Give up yet? Thirteen times seventeen is 221. Seven times nineteen is 133.
The process of discovering what other numbers—if any—are to be multiplied to create a given number is called factoring. For small numbers, it’s not hard: what numbers can you multiply to get fifteen? Three and five. Twelve? Two twice and three, or three and four, or two and six. For large numbers, it’s hard. For numbers sufficiently large, it’s probably2 impossible. There are processes—algorithms—that are guaranteed to factor any given number, but it’s possible to pick a number that would require every atom in the entire universe to each be turned into a supercomputer more powerful than any ever made on Earth to work in concert for longer than the expected total lifetime of the universe to reach the answer.
RSA, the first widely-used public key cryptosystem, relies on factoring for its security3.
Prime time
Before going further, some additional definitions.
A prime number is one which, essentially, can’t be factored. Thirteen is a prime number: no number divides evenly (without remainders) into thirteen (except for thirteen itself, and the number one, which can be divided evenly into every number). Fifteen is composite because at least two other numbers (three and five) will evenly divide it.
Neither twenty-one nor fifty-five are prime, but they are relatively prime: they share no factors in common. That is, the three and seven that make twenty-one are not found in the five and eleven that make fifty-five. Fifteen is not relatively prime with either: three goes into both fifteen and twenty-one; and five goes into both fifteen and fifty-five.
You might not realize it, but you already know how modular arithmetic works. If it’s ten o’clock now, what time will it be in four hours? Two o’clock, of course—and you did that by adding ten and four modulo twelve. Or:
(10 + 4) mod 12 = 2
14 mod 12 = 2
Basically, to find out what time it’ll be, you add everything together and then keep subtracting twelve until you’ve got an answer that’s less than twelve.
There’s nothing that says that you can only compute things modulo twelve. Eleven plus seventeen modulo five is three:
(11 + 17) mod 5 = 3
28 mod 5 = 3
23 mod 5 = 3
18 mod 5 = 3
13 mod 5 = 3
8 mod 5 = 3
3 mod 5 = 3
The modulo operator is just like any other. It just means that, at that point, you “reduce” the number as shown above. You can do multiplication modulo a number, exponentiation modulo a number—whatever you like. Naturally, there are much more efficient ways to figure everything out, but this should be enough for you to understand the basic concept.
Key generation
To start, you want to randomly pick a pair of prime numbers of roughly the same size. For true security, these numbers need to be hundreds of digits long, but then you can’t do the math on the back of a napkin. For this example, I’ll “randomly” pick seventeen and nineteen. In the literature, one of them is designated “p” and the other “q”—for no special reason; it’s just a way to keep them straight when writing the documentation.
When we’re done generating our keys, p and q must be destroyed, (hopefully) never to be known again.
Next, you figure out thier product. Seventeen times nineteen is 323. This number, 323, is called “n.” What we have so far:
n = pq
323 = 17 × 19
Next, we need to pick our encryption (public) key, which we’ll call e. We can’t just pick any key completely at random; it needs special requirements. In particular, it must have no factors in common with:
(p - 1) × (q - 1)
(17 - 1) × (19 - 1)
16 × 18
288
The number, thirteen, meets our requirement. Thirteen and 288 share no common factors. 288 has a lot of factors, but its “prime factorization,” the shortest possible listing of its factors, is 25 × 32. There’s no way to get thirteen by multiplying some number of two’s and three’s.
Finally, we generate the decryption key, d. It is the number which modulo (p - 1) × (q - 1) is one. There are sophisticated methods for figuring this out…which I won’t describe here. You may, however, wish to verify my answer.
d = e-1 mod ((p - 1) × (q - 1))
d = 13-1 mod 288
d = 133
13 × 133 = 1729
1729 mod 288 = 1
1441 mod 288 = 1
1153 mod 288 = 1
865 mod 288 = 1
577 mod 288 = 1
289 mod 288 = 1
1 mod 288 = 1
It’s at this point that we throw away p and q, banishing them forever from the knowledge of the universe. So, forget the numbers seventeen and nineteen. They don’t exist, I tell you!
Our private key is d, which we calculated above to be 133. Don’t ever forget it, but don’t tell anybody, either. We’ll also need to know n, which is 323.
The public key, e, which we shout from the highest mountain, is thirteen. Thirteen, I say! We also let the world know that n is 323.
Encryption
Carol has heard us shouting, “e is thirteen! n is 233.” She decides she wants to tell us to stop making such a fool of ourselves, but doesn’t want to publicly say what she really means, so she decides to encrypt her response to us.
First, she turns her message into some sort of standard number format. Any time a computer stores text, it’s really stored as a number, and almost always in a format known as ASCII. If you look at the OpenBSD manual page for ASCII, you’ll see a table titled, “The decimal set.” We’ll get the values for our message from there.
| Character | S | h | u | t | u | p | ! | |
|---|---|---|---|---|---|---|---|---|
| ASCII Code | 83 | 104 | 117 | 116 | 32 | 117 | 112 | 33 |
Naturally, Carol is far too polite to ever say such a thing to us where somebody could overhear.
Each piece of the message—we have eight pieces—is encrypted as follows: the ciphertext, c, is the piece of the message, m to the public key eth power modulo n. Thus:
c = me mod n
c1 = 8313 mod 323
c1 = 8,871,870,642,308,873,326,043,363 mod 323
c1 = 121
How on Earth did I figure that out? I cheated. I wrote a quick-n-dirty Perl program that uses the Math::BigInt module to do the math for me. It does the multiplication without converting to scientific notation and has a built-in function (like a button on your calculator) to figure out what one number modulo another is.
Let me do the work for just one more, and then—in the interests of space—I’ll just give you the results for the rest.
c2 = 10413 mod 323
c2 = 166,507,350,731,038,802,170,609,664 mod 323
c2 = 253
In the same way, we’d go on to calculate c3, the third part of the message (“u”), and so on through (in our very short example) c8. Here’s everthing in one table:
| Character | S | h | u | t | u | p | ! | |
|---|---|---|---|---|---|---|---|---|
| ASCII Code | 83 | 104 | 117 | 116 | 32 | 117 | 112 | 33 |
| Encrypted form | 121 | 253 | 223 | 22 | 53 | 223 | 130 | 153 |
Decryption
We’ve recieved Carol’s very fashionable smoke signals of “121, 253, 223, 22, 53, 223, 130, 153.” Now what?
Decryption is a very similar process to encryption, just with different numbers in different positions. The plaintext message, m, is the ciphertext, c, raised to the private key dth power modulo our old friend n.
m = cd mod n
m1 = 121133 mod 323
m1 = 10,243,638,697,138,576,984,202,430,343,335,019,357,
267,108,580,564,211,604,232,059,721,868, 633,924,023,821,941,916,906,463,147,216,
508,965,051,721,092,939,916,707,840,775, 672,231,118,526,375,826,701,246,142,255,
114,305,620,999,624,480,598,859,516,392, 620,588,946,018,138,003,300,029,422,634,
801,612,379,471,700,640,444,576,825,836, 798,109,364,161,124,129,234,805,587,161 mod 323
m1 = 83
Yes, RSA uses some really honkin’ big numbers! That number above is many, many, many times more than the number of years it’ll take for all matter in the universe to cool to absolute zero—meaning all the stars and even black holes aren’t even distant memories any more4.
Anyway, as you can see, the result of all that calculation is 83, the same number we started with—namely, the ASCII code for the letter, “S.” Permit me a moment the liberty of using the Julia Child method once more and showing you the decrypted form of our message.
| Character | S | h | u | t | u | p | ! | |
|---|---|---|---|---|---|---|---|---|
| ASCII Code | 83 | 104 | 117 | 116 | 32 | 117 | 112 | 33 |
| Encrypted form | 121 | 253 | 223 | 22 | 53 | 223 | 130 | 153 |
| Decrypted form | 83 | 104 | 117 | 116 | 32 | 117 | 112 | 33 |
Because nobody made any mistrakes along the way—their pigeon-powered computers aparently didn’t run out of birdseed—the decrypted form is identical to the original ASCII. From the decrypted form, we can make the translation back through ASCII to the message Carol’s been trying to tell us all along: “Shut up!”
Consideration and actual usage
In and of itself, RSA actually isn’t all that useful. For one, as you can see from the fact that “u” got encrypted exactly the same (223) both times in our message that RSA is really just a very complicated codebook. Any given message, when encrypted using the same key, will always have the same ciphertext every time. (Naturally, a different key or a different message will yield a different ciphertext.) Historically, successful attacks against codebooks have been legion. Using RSA in the manner I used for this example would result in a system that would be no harder to break than those famous quotation puzzles in the Sunday paper.
And, RSA is slow. We’re talking “Grandma Molases in the Arctic” slow. More traditional forms of encryption can be thousands of times faster5.
Thus, RSA is commonly only used to encrypt a randomly-generated key for a traditional cipher (the kind where the same key is used for encryption as for decryption), and subsequent communications for that session use the traditional cipher. RSA therefore substitutes for the old method of meeting in secret to exchanging keys.
The codebook nature of RSA isn’t a problem because there are so many gazillions of potential keys for any decent traditional cipher that there’s no danger of re-using a traditional key with an RSA key. And, since traditional keys are small—this sentence is longer than one—there’s no real speed penalty because the RSA computation is over and done with right away.
When RSA is used to sign a message, the message itself is never actually signed. Instead, a message digest or secure hash of the message is produced, and that digest is signed. A digest is a certain, short, fixed-length summation of a message. You can’t recover a message given a digest, but, for all practical considerations, every message has a unique digest. The recipient computes the same digest from the original message and confirms that the signature of the digest is what it should be. Digests are about the same length as traditional cipher keys.
1Schneier, Bruce (1996). Applied Cryptography Second Edition: protocols, algorithms, and source code in C. John Wiley & Sons, Inc., New York. p 461.
2Factoring hasn’t been proven to be a hard problem, but it’s given every indication of being one. Until somebody comes up with a proof, though, nobody can be certain. Quantum computing would seem to offer an end-run around the problem, but we’re still a long way from a practical quantum computer. For the truly paranoid, there are other public key cryptosystems that don’t rely on factoring and which may or may not have advantages over RSA.
3Schneier p. 467.
4Schneier p. 18.
5Schneier p. 469.