1.27: The RSA Scheme
- Page ID
- 83363
In this chapter we discuss the basis of the RSA scheme. This is one of the most important examples of a public key cryptographic scheme. Put simply, in a public key cryptographic system, information (called the “public key”) is provided to the world by a person or company (let’s call the person “Bob”) who wants to receive messages. Anyone in the world, including a person we’ll call “Alice,” can safely send messages to Bob by disguising, or encrypting messages before sending them. Once Alice’s encrypted messages are received by Bob, he uses private information that only he knows to decrypt the messages, or change them back into their original state before the decryption. What is important is that the messages Alice sends to Bob be encrypted in such a way that even if these messages were intercepted by a third party (call her "Eve,"\(^{1}\)), they would be unreadable even if Eve knew the information Bob made public that Alice used to encrypt the messages.
In other words, in order for a public key cryptographic scheme to be successful, everyone should be able to follow Bob’s instructions for encrypting messages to be sent to him, but only Bob should know how to decrypt those messages once they are encrypted. A big question immediately arises: is this even possible? If Eve knew how the messages were encrypted, shouldn’t she be able to figure out how to “undo” the encryption and read Alice’s messages that were sent to Bob?
A big step forward in public key cryptography happened in 1977 as R. Rivest, A. Shamir and L. Adelman (note their last initials) discovered and developed a number theoretic technique for encrypting information in such a way that the encryption could not be undone unless the recipient had secret information, or computing power and lots of time.\(^{2}\)
Let’s play the role of Alice to see how the RSA scheme works. In RSA Bob begins by making public two integers \(m\) and \(e\), called the modulus and encryption exponent, respectively. In our role as Alice, we take a message we wish to send to Bob and convert it to an integer in the set \(Z_m = \{0,1,2,\dots, m-1 \}\) where \(m\) is Bob’s modulus (\(m\) is usually a very large number, too big for anyone to factor quickly).
Having written our intended message to Bob as an integer (let’s denote this integer by \(x\)), we encrypt our message by raising \(x\) to the power \(e\) and reducing it modulo \(m\). In symbols, we encrypt our message by computing \[M = x^e \bmod m.\nonumber \] The number \(M\) resulting from this computation is our encrypted message; it’s \(M\), instead of \(x\), that we send to Bob.
You are invited to think about how an eavesdropper Eve, seeing the encrypted message \(M=x^e \bmod m\) and knowing \(m\) and \(e\) but not \(x\), could determine what \(x\) was. You’ll probably come to the conclusion that it’s not an easy task, especially if \(m\) is very large.
Now in the RSA scheme Bob receives our encrypted message \(M\) and needs to decrypt it to see what our original message \(x\) was. Luckily, Bob (and only Bob) knows a special integer \(d\) called the encryption exponent, which has the property that \[M^d \bmod m = x.\nonumber \] Bob simply raises the encrypted message \(M\) do the decryption exponent \(d\), reduces it modulo \(m\), and the original, unencrypted message \(x\) pops out.
Let’s see an example (using a much smaller modulus and encryption exponent than would be used in practice).
Suppose that Bob uses modulus \(m=57\) and \(e=25\); he publishes these online so that anyone in the world can use this information to encrypt messages they plan to send to him. Alice wants to communicate the number \(x = 23\) to Bob, but she doesn’t want Eve to know what her message is. Alice encrypts the message by computing \[M = x^e \bmod m = 23^{25}\bmod {57};\nonumber \] to do so she might use the binary method from Section 1.26—she finds that \(25 = 16 + 8 + 1\), and \[\begin{aligned} 23^1 &\equiv 23 \pmod{57};\\ 23^2 &\equiv 16 \pmod{57};\\ 23^4 &\equiv 28 \pmod{57};\\ 23^8 &\equiv 43 \pmod{57};\\ 23^{16} &\equiv 25 \pmod{57}, \end{aligned}\] so \[23^{25} = 23^{16}23^{8}23^1 \equiv 25\cdot 43 \cdot 23 \equiv 44 \pmod{57}.\nonumber \] Thus \(M=44\), and Alice sends the encrypted message \(44\) to Bob.
Now Eve intercepts the message 44 and knows it has to equal \(x^{25} \bmod{57}\), but Eve is unable to determine \(x\) directly (she might be able to just experiment by raising guessed numbers to the 25th power and reducing modulo \(57\) until she finds one that produces 44, but this process would take longer than Eve has patience for).
Bob, on the other hand, receives the message 44 and raises it to his decryption exponent \(d\); here \(d=13\), but no one knows this but Bob. He computes \[44^{13} \bmod 57 = 44^{8}44^{4}44^{1} \bmod{57} = (16 \cdot 4 \cdot 44) \bmod{57} = 23\nonumber \] and sees that Alice sent him the message 23.
There is a lot that can be said about implementing the RSA scheme in ways to make it more efficient computationally and more secure. Our purpose here, though, is to give the number theoretic underpinning of the basic scheme.
To explain why RSA works, we will require two functions: \[E:Z_m \to Z_m \qquad \mbox{(E for }encipher\text{)}\nonumber \] and \[D:Z_m \to Z_m \qquad \mbox{(D for }decipher\text{)}.\nonumber \] To be able to use \(D\) to decipher what \(E\) has enciphered we need to have \(D(E(x)) = x\) for all \(x \in Z_m\).
Now as described above, we will use \[E(x)=x^e\bmod m \quad \text{and} \quad D\left(M\right)=M^d\bmod m.\nonumber \]
To see why \(E\) and \(D\) are chosen this way, and to suggest how Bob can decide what to use for \(m\), we first prove a lemma:
Let \(p\) and \(q\) be any two distinct primes and let \(m=pq\). Let \(e\) and \(d\) be any two positive integers which are inverses of each other modulo \(\phi(m)\). Then \[\left(x^e\right)^d = x^{ed}\equiv x\pmod m\nonumber \] for all \(x\).
Proof
By Theorem 1.15.4, \(\phi(m)=(p-1)(q-1)\). Since \(ed\equiv 1 \pmod {\phi(m)}\) we have \(ed-1=k\phi(m)=k(p-1)(q-1)\) for some \(k\). Note \(k>0\) unless \(ed=1\) in which case the theorem is obvious. So we have \[\label{eq: lem28.1} ed=k\phi(m)+1=k(p-1)(q-1)+1\] for some \(k>0\).
Now by Fermat’s Little Theorem, if \(\gcd(x,p)=1\) we have \(x^{p-1}\equiv 1\pmod p\) and raising both sides of the congruence to the power \((q-1)k\) we obtain: \[x^{(p-1)(q-1)k}\equiv 1\pmod p\nonumber \] and multiplying both sides by \(x\) we have \[x^{(p-1)(q-1)k+1}\equiv x\pmod p\nonumber \] That is, by equation \(\eqref{eq: lem28.1}\), \[x^{ed}\equiv x\pmod p.\nonumber \] Now we proved this last statement when \(\gcd(x,p)=1\), but if \(\gcd(x,p)=p\), the same conclusion is true, since then \(x\equiv 0\pmod p\). Hence \(x^{ed}\equiv x\pmod p\) holds in all cases. A similar argument proves that for all \(x\), \[x^{ed}\equiv x\pmod q.\nonumber \] So by Exercise 1.17.11, since \(\gcd(p,q)=1\) and \(m=pq\), we have \[x^{ed}\equiv x\pmod m\nonumber \] for all \(x\).
The congruence in the statement of this lemma can be rewritten as \(D(E(x)) = x\) for all \(x\), meaning that the decryption function \(D\), as we have defined it, manages to undo the encryption function \(E\) if the following statements are true:
- The modulus \(m\) is the product of two distinct primes \(p\) and \(q\).
- The decryption exponent \(d\) is the inverse of the encryption exponent \(e\) in \(Z_{\phi(m)}\). Hence \(d\) and \(e\) are relatively prime to \(\phi(m)\).
In the example above, prior to Alice sending Bob any messages, Bob had created the modulus \(m\) by choosing two primes \(p=3\) and \(q=19\) and letting \(m = pq\). Since \(d\) and \(e\) needed to be inverses of each other modulo \(\phi(m)\), Bob found \[\phi(m) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1) = (3-1)(19-1) = 36.\nonumber \] Hence \(e\) must be a number that is relatively prime to \(36\); Bob chose \(e=25\) and computed \(25^*\) to be \(13\), which told him \(d\).
Now Bob had done all of this preliminary work in private. When he was ready, he shared none of this information with the world except for the modulus \(m\) and the encryption exponent \(e\). Still, \(m\) and \(e\) are the only things Alice (or anyone else) needs to send Bob encrypted messages.
Attacks on the RSA cryptographic scheme
Since its discovery in the late 1970’s, many attempts have been made to attack the RSA scheme, or in other words, find ways for an eavesdropper Eve to take an encrypted message \(M\) and determine what the original message \(x\) was without knowing the decryption exponent \(d\) ahead of time. Though we won’t say much about these here, we will encourage the interested reader to do a little library research; there are many articles describing such attacks.\(^{3}\)
In practice, every step of Bob’s preparation must be carried out carefully to prevent against attacks Eve can carry out. For instance, if Bob’s modulus \(m\) is too small, then Eve might be able to factor it and deduce what primes \(p\) and \(q\) were used to form it; from there \(\phi(m)\) is easy to compute and so is \(d\), since Eve knows what \(e\) is. Hence Bob’s primes \(p\) and \(q\) must both be very large—perhaps 100 digits long each, so that \(m\) has 200 digits and no algorithm is likely to stumble on a factorization of \(m\) in any reasonable amount of time.
Other quite clever attacks are possible if, for instance, multiple individuals are all known to use the same modulus \(m\), or if Bob’s decryption exponent is very small in comparison to \(m\). These attacks often use computing power to test a staggering number of possible cases, but if \(p,q,d,e\) are not chosen carefully, the number of cases to check is small enough that the encryption exponent \(d\) can somehow be determined by Eve, and all encrypted traffic intended for Bob can be read by Eve as soon as it is intercepted.
Since \(d\) may be determined from \(m\) and \(e\) if \(m\) can be factored into \(p\) and \(q\), and since one way to improve the security of the encryption is by making sure \(m\) is large enough to make factoring it unlikely, an unanswered question suggests itself:
Is there a fast algorithm for factoring large integers?
A truly fast algorithm for factoring would have important implications for cryptography and data security. It is interesting (and a little sobering!) to reflect upon the idea that the answers to abstract number theoretic questions have the potential to affect the well-being of humans across the world.
Exercises
Suppose you plan to use RSA to allow people to send you encrypted messages. Your use of RSA employs modulus \(m=pq\), encryption exponent \(e\), and decryption exponent \(d\).
- Which of the following pieces of information should be made public to people wanting to send you messages? \[p \qquad d \qquad m \qquad q \qquad e \qquad \phi(m)\nonumber \]
- For each of the pieces of information in part (a) that should not be made public, explain in detail how a person discovering this information could read the encrypted messages.
- Using modulus \(m=851\) and encryption exponent \(e = 7\), encrypt the message \(28\).
- The decryption exponent for \(e=7\) is \(d=679\). Show that decrypting your answer to part (a) produces the original message (i.e., \(28\)). It may help to know that \(679 = 512 + 128 + 32 + 4 + 2 + 1\).
A message has been previously encrypted as \(100\) using modulus \(m=851\) and a suitable encryption exponent. If we know that the decryption exponent is \(97\), then what is the original message?
- Suppose that we wish to carry out RSA using \(m = 35\). Which numbers in \(\{1,2,3,4,5,6,7,8,9,10\}\) could successfully be used as encryption exponents?
- For each potential encryption exponent you found in part (a), determine the corresponding decryption exponent.
In the next two Exercises, use the following table to convert letters to numbers before encryption or after decryption.
| A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
Using modulus \(m=391\) and encryption exponent \(3\), and the table above, what are the resulting encrypted numbers produced from the original message ‘NUMBER’?
Suppose an individual wants to use modulus \(m=55\) and encryption exponent \(3\). This is a poor choice, since it will easily allow the encryption to be broken. Let’s demonstrate this:
- What would the decryption exponent be? (Explain how you arrived at your answer.)
- Suppose you intercepted a message that was encrypted using this modulus and encryption exponent, and the encrypted message reads \[51 \quad 8 \quad 25 \quad 31.\nonumber \] What was the message before encryption? Use the table above to recognize the pre-encryption message as a word.
Is it possible to choose a modulus \(m\) and an encryption exponent \(e\) such that the decryption exponent \(d\) equals \(e\)? If not, explain why not. If so, provide an example of such an \(m\) and \(e\).
Footnotes
[1] For "eavesdropper" - or perhaps "evil".
[2] A copy of their paper "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems" may be downloaded from
http://citeseer.nj.nec.com/rivest78method.html .
[3] One well-known survey is "Twenty Years of Attacks on the RSA Cryptosystem" by Dan Boneh of Stanford University, available online at https://crypto.stanford.edu/dabo/papers/RSA-survey.pdf.