RSA is similar to, yet very different from, Diffie-Hellman (see Chapter 11). Diffie-Hellman (DH for short) is based on a one-way function: assuming p and g are publicly known, you can compute (gx mod p) from x, but you cannot compute x given gx mod p. RSA is based on a trapdoor one-way function. Given the publicly known information n and e, it is easy to compute me mod n from m, but not the other way around. However, if you know the factorization of n, then it is easy to do the inverse computation. The factorization of n is the trapdoor information. If you know it, you can invert the function; if you do not know it, you cannot invert the function. This trapdoor functionality allows RSA to be used both for encryption and digital signatures. RSA was invented by Ronald Rivest, Adi Shamir, and Leonard Adleman, and first published in 1978 [105].

Throughout this chapter we will use the values p, q, and n. The values p and q are different large primes, each on the order of a thousand bits long or more. The value n is defined by n := pq. (An ordinary product, that is, not modulo something.)

Instead of doing computations modulo a prime p as in the DH system, we will be doing computations modulo the composite number n. To explain what is going on, we will need a little more number theory about computations modulo n. A very useful tool is the Chinese Remainder Theorem, or CRT. It is named so because the basic version was first stated by the first-century Chinese mathematician Sun Tzu. (Most of the math you need for DH and RSA dates back thousands of years, so it can't be too difficult, right?)

The numbers modulo n are 0, 1, …, n − 1. These numbers do not form a finite field as they would if n were a prime. Mathematicians still write n for these numbers and call this a ring, but that is a term we won't need. For each x in n, we can compute the pair (x mod p, x mod q). The Chinese Remainder Theorem states that you can compute the inverse function: if you know (x mod p, x mod q), you can reconstruct x.

For ease of notation, we will define (a, b) := (x mod p, x mod q).

First, we show that reconstruction is possible, then we'll give an algorithm to compute the original x. To be able to compute x given (a, b), we must be sure there is not a second number x′ in n such that x′ mod p = a and x′ mod q = b. If this were the case, both x′ and x would result in the same (a, b) pair, and no algorithm could figure out which of these two numbers was the original input.

Let d := x − x′, the difference between the numbers that lead to the same (a, b) pair. We have (d mod p) = (x − x′) mod p = (x mod p) − (x′ mod p) = a − a = 0; thus, d is a multiple of p. For much the same reason, d is a multiple of q. This implies that d is a multiple of lcm(p, q), because lcm is, after all, the least common multiple. As p and q are different primes, lcm(p, q) = pq = n, and thus x − x′ is a multiple of n. But both x and x′ are in the range 0, …, n − 1, so x − x′ must be a multiple of n in the range −n + 1, …, n − 1. The only valid solution is x − x′ = 0, or x = x′. This proves that for any given pair (a, b), there is at most one solution for x. All we have to do now is find that solution.

12.2.1 Garner's Formula

The most practical way of computing the solution is Garner's formula.

Here the (q−1 mod p) term is a constant that depends only on p and q. Remember that we can divide modulo p, and therefore we can compute (1/q mod p), which is just a different way of writing (q−1 mod p).

We don't need to understand Garner's formula. All we need to do is prove that the result x is correct.

First of all, we show that x is in the right range 0, …, n − 1. Obviously x ≥ 0. The part t := (((a − b)(q−1 mod p))mod p) must be in the range 0, …, p − 1 because it is a modulo p result. If t ≤ p−1, then tq ≤ (p−1)q and x = tq + b ≤ (p−1)q+ (q−1) = pq− 1 = n − 1. This shows that x is in the range 0, …, n − 1.

The result should also be correct modulo both p and q.

The whole thing in front of the multiplication by q is some integer K, but any multiple of q is irrelevant when computing modulo q. Modulo p is a bit more complicated:

In the first line, we simply expand (x mod p). In the next line, we eliminate a couple of redundant mod p operators. We then change the order of the multiplications, which does not change the result. (You might remember from school that multiplication is associative, so (ab)c = a(bc).) The next step is to observe that q−1q = 1 (mod p), so we can remove this term altogether. The rest is trivial.

This derivation is a bit more complicated than the ones we have seen so far, especially as we use more of the algebraic properties. Don't worry if you can't follow it.

We can conclude that Garner's formula gives a result x that is in the right range and for which (a, b) = (x mod p, x mod q). As we already know that there can only be one such solution, Garner's formula solves the CRT problem completely.

In real systems, you typically precompute the value q−1 mod p, so Garner's formula requires one subtraction modulo p, one multiplication modulo p, one full multiplication, and an addition.

12.2.2 Generalizations

Before we delve into the details of RSA, we must look at how numbers modulo n behave under multiplication. This is somewhat different from the modulo p case we discussed before.

For any prime p, we know that for all 0 < x < p the equation xp−1 = 1 (mod p) holds. This is not true modulo a composite number n. For RSA to work, we need to find an exponent t such that xt = 1 mod n for (almost) all x. Most textbooks just give the answer, which does not help you understand why the answer is true. It is actually relatively easy to find the correct answer by using the CRT.

We want a t such that, for almost all x, xt = 1 (mod n). This last equation implies that xt = 1 (mod p) and xt = 1 (mod q). As both p and q are prime, this only holds if p − 1 is a divisor of t, and q − 1 is a divisor of t. The smallest t that has this property is therefore lcm(p − 1, q − 1) = (p − 1)(q − 1)/gcd(p − 1, q − 1). For the rest of this chapter, we will use the convention that t = lcm(p − 1, q − 1).

The letters p, q, and n are used by everybody, although some use capital letters. Most books don't use our t, but instead use the Euler totient function ϕ(n). For an n of the form n = pq, the Euler totient function can be computed as ϕ(n) = (p − 1)(q − 1), which is a multiple of our t. It is certainly true that xϕ(n) = 1, and that using ϕ(n) instead of t gives correct answers, but using t is more precise.

We've skipped over one small issue in our discussion: xt mod p cannot be equal to 1 if x mod p = 0. So the equation xt mod n = 1 cannot hold for all values x. There are not many numbers that suffer from this deficiency; there are q numbers with x mod p = 0 and p numbers with x mod q = 0, so the total number of values that have this problem is p + q. Or p + q − 1, to be more precise, because we counted the value 0 twice. This is an insignificant fraction of the total number of values n = pq. Even better, the actual property used by RSA is that xt+1 = x (mod n), and this still holds even for these special numbers. Again, this is easy to see when using the CRT representation. If x = 0 (mod p), then xt+1 = 0 = x (mod p), and similarly modulo q. The fundamental property xt+1 = x (mod n) is preserved, and holds for all numbers in n.

We can now define the RSA system. Start by randomly choosing two different large primes p and q, and compute n = pq. The primes p and q should be of (almost) equal size, and the modulus n ends up being twice as long as p and q are.

We use two different exponents, traditionally called e and d. The requirement for e and d is that ed = 1 (mod t) where t: = lcm(p − 1, q − 1) as before. Recall that many texts write ed = 1 (mod ϕ(n)). We choose the public exponent e to be some small odd value and use the EXTENDEDGCD function from Section 10.3.5 to compute d as the inverse of e modulo t. This ensures that ed = 1 (mod t).

To encrypt a message m, the sender computes the ciphertext c: = me (mod n). To decrypt a ciphertext c, the receiver computes cd (mod n). This is equal to (me)d = med = mkt+1 = (mt)k · m = (1)k · m = m (mod n), where k is some value that exists. So the receiver can decrypt the ciphertext me to get the plaintext m.

The pair (n, e) forms the public key. These are typically distributed to many different parties. The values (p, q, t, d) are the private key and are kept secret by the person who generated the RSA key.

For convenience, we often write c1/e mod n instead of cd mod n. The exponents of a modulo n computation are all taken modulo t, because xt = 1 (mod n), so multiples of t in the exponent do not affect the result. And we computed d as the inverse of e modulo t, so writing d as 1/e is natural. The notation c1/e is often easier to follow, especially when multiple RSA keys are in use. That is why we also talk about taking the e'th root of a number. Just remember that computations of any roots modulo n require knowledge of the private key.

12.4.1 Digital Signatures with RSA

So far, we've only talked about encrypting messages with RSA. One of the great advantages of RSA is that it can be used for both encrypting messages and signing messages. These two operations use the same computations. To sign a message m, the owner of the private key computes s := m1/e mod n. The pair (m, s) is now a signed message. To verify the signature, anyone who knows the public key can verify that se = m (mod n).

As with encryption, the security of the signature is based on the fact that the e'th root of m can only be computed by someone who knows the private key.

12.4.2 Public Exponents

The procedure described so far has one problem. If e has a common factor with t = lcm(p − 1, q − 1), there is no solution for d. So we have to choose p, q, and e such that this situation does not occur. This is more of a nuisance than a problem, but it has to be dealt with.

Choosing a short public exponent makes RSA more efficient, as fewer computations are needed to raise a number to the power e. We therefore try to choose a small value for e. In this book, we will choose a fixed value for e, and choose p and q to satisfy the conditions above.

You have to be careful that the encryption functions and digital signature functions don't interact in undesirable ways. You don't want it to be possible for an attacker to decrypt a message c by convincing the owner of the private key to sign c. After all, signing the “message” c is the same operation as decrypting the ciphertext c. The encoding functions presented later in this book will prevent this. These encodings are remotely akin to block cipher modes of operation; you should not use the basic RSA operation directly. But even then, we still don't want to use the same RSA operation for both functions. We could use different RSA keys for encryption and authentication, but that would increase complexity and double the amount of key material.

Another approach, which we use here, is to use two different public exponents on the same n. We will use e = 3 for signatures and e = 5 for encryption. This decouples the systems because cube roots and fifth roots modulo n are independent of each other. Knowing one does not help the attacker to compute the other [46].

Choosing fixed values for e simplifies the system and also gives predictable performance. It does impose a restriction on the primes that you can use, as both p − 1 and q − 1 cannot be multiples of 3 or 5. It is easy to check for this when you generate the primes in the first place.

Using RSA as presented so far is very dangerous. The problem is the mathematical structure. For example, if Alice digitally signs two messages m1 and m2, then Bob can compute Alice's signature on m3 := m1 m2 mod n. After all, Alice has computed and and Bob can multiply the two results to get (m1m2)1/e.

Another problem arises if Bob encrypts a very small message m with Alice's public key. If e = 5 and , then me = m5 < n, so no modular reduction ever takes place. The attacker Eve can recover m by simply taking the fifth root of m5, which is easy to do because there are no modulo reductions involved. A typical situation in which this could go wrong is if Bob tries to send an AES key to Alice. If she just takes the 256-bit value as an integer, then the encrypted key is less than 2256·5 = 21280, which is much smaller than our n. There is never a modulo reduction, and Eve can compute the key by simply computing the fifth root of the encrypted key value.

One of the reasons we have explained the theory behind RSA in such detail is to teach you some of the mathematical structure that we encounter. This very same structure invites many types of attack. We've mentioned some simple ones in the previous paragraph. There are far more advanced attacks, based on techniques for solving polynomial equations modulo n. All of them come down to a single thing: it is very bad to have any kind of structure in the numbers that RSA operates on.

The solution is to use a function that destroys any available structure. Sometimes this is called a padding function, but this is a misnomer. The word padding is normally used for adding additional bytes to get a result of the right length. People have used various forms of padding for RSA encryption and signatures, and quite a few times this has resulted in attacks on their designs. What you need is a function that removes as much structure as possible. We'll call this the encoding function.

There are standards for this, most notably PKCS #1 v2.1 [110]. As usual, this is not a single standard. There are two RSA encryption schemes and two RSA signature schemes, each of which can take a variety of hash functions. This is not necessarily bad, but from a pedagogical perspective we don't like the extra complexity. We'll therefore present some simpler methods, even though they might not have all the features of some of the PKCS methods. And, as we mentioned before in the case of AES, there are many advantages to using a standardized algorithm in practice. For example, for encryption you might use RSA-OAEP [9], and for signatures you might use RSA-PSS [8].

The PKCS #1 v2.1 standard also demonstrates a common problem in technical documentation: it mixes specification with implementation. The RSA decryption function is specified twice; once using the equation m = cd mod n and once using the CRT equations. These two computations have the same result: one is merely an optimized implementation of the other. Such implementation descriptions should not be part of the standard, as they do not produce different behavior. They should be discussed separately. We don't want to criticize this PKCS standard in particular; it is a very widespread problem that you find throughout the computer industry.

Encrypting a message is the canonical application of RSA, yet it is almost never used in practice. The reason is simple: the size of the message that can be encrypted using RSA is limited by the size of n. In real systems, you cannot even use all the bits, because the encoding function has an overhead. This limited message size is too impractical for most applications, and because the RSA operation is quite expensive in computational terms, you don't want to split a message into smaller blocks and encrypt each of them with a separate RSA operation.

The solution used almost everywhere is to choose a random secret key K, and encrypt K with the RSA keys. The actual message m is then encrypted with key K using a block cipher or stream cipher. So instead of sending something like ERSA(m), you send ERSA(K), EK(m). The size of the message is no longer limited, and only a single RSA operation is required, even for large messages. You have to transmit a small amount of extra data, but this is usually a minor price to pay for the advantages you get.

We will use an even simpler method of encryption. Instead of choosing a K and encrypting K, we choose a random r ∈ n and define the bulk encryption key as K := h(r) for some hash function h. Encrypting r is done by simply raising it to the fifth power modulo n. (Remember, we use e = 5 for encryption.) This solution is simple and secure. As r is chosen randomly, there is no structure in r that can be used to attack the RSA portion of the encryption. The hash function in turn ensures that no structure between different r's propagates to structure in the K's, except for the obvious requirement that equal inputs must yield equal outputs.

For simplicity of implementation, we choose our r's in the range 0, …, 2k − 1, where k is the largest number such that 2k < n. It is easier to generate a random k-bit number than to generate a random number in n, and this small deviation from the uniform distribution is harmless in this situation.

Here is a more formal definition:

The receiver computes K = h(c1/e mod n) and gets the same key K.

We previously dealt extensively with how to compute c1/e given the private key, so we won't discuss that here again. Just don't forget to use the CRT for a factor of 3–4 speed-up.

Here is a good way to look at the security. Let's assume that Bob encrypts a key K for Alice, and Eve wants to know more about this key. Bob's message depends only on some random data and on Alice's public key. So at worst this message could leak data to Eve about K, but it cannot leak any data about any other secret, such as Alice's private key. The key K is computed using a hash function, and we can pretend that the hash function is a random mapping. (If we cannot treat the hash function as a random mapping, it doesn't satisfy our security requirement for hash functions.) The only way to get information about the output of a hash function is to know most of the input. That means having information about r. But if RSA is secure—and we have to assume that since we have chosen to use it—then it is impossible to get any significant amount of information about a randomly chosen r given just (re mod n). This leaves the attacker with a lot of uncertainty about r, and consequently, no knowledge about K.

Suppose the key K is later revealed to Eve, maybe due to a failure of another component of the system. Does this reveal anything about Alice's private key? No. K is the output of a hash function, and it is impossible for Eve to derive any information about the inputs to the hash function. So even if Eve chose c in some special way, the K she acquires does not reveal anything about r. Alice's private key was only used to compute r, so Eve cannot learn anything about Alice's private key either.

This is one of the advantages of having a hash function in the DECRYPTRANDOMKEYWITHRSA function. Suppose it just returned c1/e mod n. This routine could then be used to play all kinds of games. Suppose some other part of the system had a weakness and Eve learned the least significant bit of the output. Eve could then send specially chosen values c1, c2, c3, … to Alice and get the least significant bits of . These answers have all kinds of algebraic properties, and it is quite conceivable that Eve could learn something useful from a situation like this. The hash function h in DECRYPTRANDOMKEYWITHRSA destroys all mathematical structure. Learning one bit from the output K gives Eve almost no information about c1/e. Even the full result K divulges very little useful information; the hash function is not invertible. Adding the hash function here makes the RSA routines more secure against failures in the rest of the system.

For signatures, we have to do a bit more work. The problem is that the message m we want to sign can have a lot of structure to it, and we do not want any structure in the number we compute the RSA root on. We have to destroy the structure.

The first step is to hash the message. So instead of a variable-length message m, we deal with a fixed-size value h(m) where h is a hash function. If we use SHAd-256, we get a 256-bit result. But n is much bigger than that, so we cannot use h(m) directly.

The simple solution is to use a pseudorandom mapping to expand h(m) to a random number s in the range 0, …, n − 1. The signature on m is then computed as s1/e (mod n). Mapping h(m) to a modulo n value is a bit of work (see the discussion in Section 9.7). In this particular situation, we can safely simplify our problem by mapping h(m) to a random element in the range 0, …, 2k − 1, where k is the largest number such that 2k < n. Numbers in the range 0, …, 2k − 1 are easy to generate because we only need to generate k random bits. In this particular situation, this is a safe solution, but don't use it just anywhere. There are many situations in cryptography where this will break your entire system.

We will use the generator from our Fortuna PRNG from Chapter 9. Many systems use the hash function h to build a special little random number generator for this purpose, but we've already defined a good one. Besides, you need the PRNG to choose the primes to generate the RSA keys, so you have the PRNG in the software already.

This results in three functions—one to map the message to s, one to sign the message, and one to verify the signature.

The letter σ, or sigma, is often used for signatures because it is the Greek equivalent of our letter s. By now you should know how to compute s1/e mod n, given the private key.

Of course, in a real application there will be some action to take if the signature verification fails. We've just written an assertion here to indicate that normal operations should not proceed. A signature failure should be taken like any other failure in a cryptographic protocol: as a clear signal that you are under active attack. Don't send any replies unless you absolutely have to, and destroy all the material you are working on. The more information you send out, the more information you give the attacker.

The security argument for our RSA signatures is similar to that of the RSA encryptions. If you ask Alice to sign a bunch of messages m1, m2, …, mi, then you are getting pairs of the form (s, s1/e), but the s values are effectively random. As long as the hash function is secure, you can only affect h(m) by trial and error. The random generator is again a random mapping. Anyone can create pairs of the form (s, s1/e) for random s values, so this provides no new information that helps the attacker forge a signature. However, for any particular message m, only someone who knows the private key can compute the corresponding (s, s1/e) pair, because s must be computed from h(m), then s1/e must be computed from s. This requires the private key. Therefore, anyone who verifies the signature knows that Alice must have signed it.

This brings us to the end of our treatment of RSA, and to the end of the math-heavy part of this book. We will be using DH and RSA for our key negotiation protocol and the PKI, but that only uses the math we have already explained. No new mathematics will be introduced.

Exercise 12.1 Let p = 89, q = 107, n = pq, a = 3, and b = 5. Find x in n such that a = x (mod p) and b = x (mod q).

Exercise 12.2 Let p = 89, q = 107, n = pq, x = 1796, and y = 8931. Compute x + y (mod n) directly. Compute x + y (mod n) using CRT representations.

Exercise 12.3 Let p = 89, q = 107, n = pq, x = 1796, and y = 8931. Compute xy (mod n) directly. Compute xy(mod n) using CRT representations.

Exercise 12.4 Let p = 83, q = 101, n = pq, and e = 3. Is (n, e) a valid RSA public key? If so, compute the corresponding private RSA key d. If not, why not?

Exercise 12.5 Let p = 79, q = 89, n = pq, and e = 3. Is (n, e) a valid RSA public key? If so, compute the corresponding private RSA key d. If not, why not?

Exercise 12.6 To speed up decryption, Alice has chosen to set her private key d = 3 and computes e as the inverse of d modulo t. Is this a good design decision?

Exercise 12.7 Does a 256-bit RSA key (a key with a 256-bit modulus) provide strength similar to that of a 256-bit AES key?

Exercise 12.8 Let p = 71, q = 89, n = pq, and e = 3. First find d. Then compute the signature on m1 = 5416, m2 = 2397, and m3 = m1m2 (mod n) using the basic RSA operation. Show that the third signature is equivalent to the product of the first two signatures.