$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.4: Public-Key Crypto - the RSA Cryptosystem

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Suppose Alice and Bob never had a chance to meet in person, and they nevertheless want to exchange messages which will be secret from Eve. What can they do?

This seems impossible within the context of cryptosystems we have been discussing so far. Let us tease out the crucial part that makes this so difficult.

Definition: Symmetric Cipher

A symmetric cipher (or symmetric cryptosystem) consists of the following parts, all known to both the communicating parties and the public in general:

• a message space $$\mathcal{M}$$
• a keyspace $$\mathcal{K}$$
• an encryption algorithm which creates a ciphertext $$c=e_k(m)$$ for any choice of $$k\in\mathcal{K}$$ and $$m\in\mathcal{M}$$.
• a decryption algorithm which generates a message $$d_k(c)\in\mathcal{M}$$ given a ciphertext $$c$$ and a $$k\in\mathcal{K}$$, which satisfies $$d_k(e_k(m))=m\ \forall k\in\mathcal{K},m\in\mathcal{M}$$.

Alice and Bob can use such a symmetric cipher by agreeing in private upon a key $$k\in\mathcal{K}$$ they will use for both encryption and decryption. For this reason, symmetric cryptosystems are also called private key cryptosystems.

Graphically:

Basic private key crypto set-up and notation:

 Alice $$\Leftrightarrow\;\;\;$$ private communication of shared key $$k ∈ \mathcal{K}$$ $$\;\;\;\Leftrightarrow$$ Bob on public network message $$m_A\in\mathcal{M}$$ compute $$c_A=e_k(m_A)$$ transmit $$c_A$$ $$\rightarrowtail\; \; \;$$ ciphertext $$c_A\; \; \; \rightarrowtail$$ receive $$c_A$$ compute $$m_A=d_k(c_A)$$ message $$m_B\in\mathcal{M}$$ compute $$c_B=e_k(m_B)$$ receive $$c_B$$ $$\leftarrowtail\; \; \;$$ ciphertext $$c_B\; \; \; \leftarrowtail$$ transmit $$c_B$$ compute $$m_B=d_k(c_B)$$ etc.

It is important for the security of the above cryptosystem that the keyspace $$\mathcal{K}$$ either be quite large, or that the whole system be structured in such a way that it is hard to tell if a particular possible decryption is valid or not (or both). Otherwise Eve can perform the brute-force attack of simply trying all the possible keys $$k\in\mathcal{K}$$ and seeing which $$d_k(c)$$ makes sense as the decryption.

In any case, because of the initial private key exchange, symmetric cryptosystems are not appropriate for the kind of situation we proposed at the start of this section. Instead, one would need a different kind of cryptosystem:

Definition: Asymmetric Cipher

An asymmetric cipher (or asymmetric cryptosystem) consists of the following parts, all known to any interested party, licit or il-:

• a message space $$\mathcal{M}$$
• an encryption keyspace $$\mathcal{K}_e$$
• a decryption keyspace $$\mathcal{K}_d$$
• a way of associating encryption keys to decryption keys, by a one-to-one function $$\mathcal{E}:\mathcal{K}_d\to\mathcal{K}_e$$
• an encryption algorithm which creates a ciphertext $$c=e_{k_e}(m)$$ for any choice of $$k_e\in\mathcal{K}_e$$ and $$m\in\mathcal{M}$$.
• a decryption algorithm which generates a message $$d_{k_d}(c)\in\mathcal{M}$$ given a ciphertext $$c$$ and a $$k_d\in\mathcal{K}_d$$, which satisfies $$d_{k_d}(e_{\mathcal{E}(k_d)}(m))=m\ \forall k_d\in\mathcal{K}_d,m\in\mathcal{M}$$.

To use such a cryptosystem, Bob picks a decryption key $$k_d$$, without telling it to anyone – but he makes the corresponding encryption key $$k_e=\mathcal{E}(k_d)$$ publicly available (probably on his website). For this reason, $$k_e$$ is also called his public key and $$k_d$$ his private key, while the whole system is called a public-key cryptosystem.

Graphically:

 Alice on public network Bob pick $$k_d\in\mathcal{K}_d$$ compute $$k_e=\mathcal{E}(k_d)\in\mathcal{K}_e$$ download $$k_e$$ $$\leftarrowtail\; \; \;$$ public key $$k_e\; \; \; \leftarrowtail$$ publish $$k_e$$ message $$m\in\mathcal{M}$$ compute $$c=e_{k_e}(m)$$ transmit $$c$$ $$\rightarrowtail\; \; \;$$ ciphertext $$c\; \; \; \rightarrowtail$$ receive $$c$$ compute $$m=d_{k_d}(c)$$

As before, the security of this cryptosystem against brute-force attacks relies upon the size of $$\mathcal{K}_d$$. In addition, since the encryption key and algorithm are known to Eve, it is important that the message space $$\mathcal{M}$$ not be too small. If $$\mathcal{M}$$ were small, Eve could simply compute all encryptions $$e_{k_e}(m)$$ as $$m$$ ran over $$\mathcal{M}$$, and compare them to a ciphertext $$c$$ she intercepted.

There is a way to prevent this attack on the message space, by making it artificially larger. In fact, one usually adds some:

Definition: Cryptographic Salt

Cryptographic salt is random data added to a message Alice desires to send to Bob before she encrypts it, which is automatically removed at Bob’s end.

Once Alice salts her messages, Eve must search the entire space of messages together with salt, which can be much larger than $$\mathcal{M}$$.

As an added benefit, salting messages makes the ciphertext change with each secret transmission – even if the plaintext is the same. Therefore even though Eve will of course know there is communication going on between Alice and Bob, her traffic analysis will no longer even be able to track when the same message is being sent on separate occasions. Absent this salt, a meticulous Eve might be able to correlate the message ciphertext with actions in the real world, and thus effectively learn their decryption even without cracking the cryptosystem. With salt, this is impossible.

Since Bob’s encryption key $$k_e=\mathcal{D}(k_d)$$ is public, the entire security of this cryptosystem falls apart if Eve can figure out the inverse of the function $$\mathcal{E}:\mathcal{K}_d\to\mathcal{K}_e$$. On the other hand, Bob must have been able to compute $$\mathcal{E}$$ itself, at least during the set-up phase of the cryptosystem. There is a name for this kind of function:

Definition: One-Way Function

A function $$f:A\to B$$ which is one-to-one and which can be computed in a reasonable amount of time on a standard (classical) computer but whose inverse cannot feasibly be computed is called a [cryptographic] one-way function.

Multiplying two numbers, even very large numbers, can be done quite quickly on a computer. It is even surprisingly fast to tell if very large numbers are prime or composite (see [AKS04] for this amazing recent result in the long history of primality testing).

But no one has found a way to factor large numbers, even when they are known to be composite, in a reasonable amount of time.1 For example, one of the largest ever to be factored, a famous challenge problem known as RSA-768, consisting of a $$232$$-digit ($$768$$ bit) composite number, was finally factored in $$2009$$ after a network of hundreds of computers working together (although not exclusively on this problem) had been processing for about two years. Larger composite numbers are easy to make and astronomically harder to factor.

Therefore, the function which multiplies two large primes together to get a very large composite is a good candidate for a cryptographic one-way function.

In $$1978$$, Ron Rivest, Adi Shamir, and Leonard Adleman described ([RSA78]) the following public-key cryptosystem based on this one-way function:

Definition: RSA Cryptosystem

Bob starts by picking two very large primes $$p$$ and $$q$$. Their product $$n=pq$$ is known as the corresponding RSA modulus. Bob also picks a number $$e$$, typically a number which when written in base two has very few $$1$$’s, such as $$3$$ or $$65537=10000000000000001_2$$, which satisfies $$\gcd(e,\phi(n))=1$$. This number is called the RSA exponent.

The RSA public [encryption] key $$k_e$$ consists of the pair $$(n,e)$$; the set of possible such pairs is $$\mathcal{K}_e$$.

The RSA private [decryption] key $$k_d$$ consists of the pair $$(n,d)$$, where $d=e^{-1}\pmod{\phi(n)},$ and $$\mathcal{K}_d$$ is the set of such pairs.

The association of encryption to decryption keys is by $$\mathcal{E}:(n,e)\mapsto(n,e^{-1}\pmod{\phi(n)})$$.

The message space of this cryptosystem is $$\mathcal{M}=\left\{m\in\mathbb{Z} \mid 0\le m<n\right\}$$.

Encryption is by $c=e_{(n,e)}(m)=m^e\pmod{n}\ .$

Decryption is $d_{(n,d)}(c)=c^d\pmod{n}\ .$

All together, the above is called the RSA cryptosystem.

Graphically:

 Alice on public network Bob pick large primes $$p$$ and $$q$$ compute RSA modulus $$n=pq$$ pick RSA exponent $$e\in\mathbb{N}$$ with $$\gcd(e,\phi(n))$$ download $$k_e$$ $$\leftarrowtail\; \; \;$$ public key $$k_e\; \; \; \leftarrowtail$$ publish $$k_e=(n,e)$$ compute $$d=e^{-1}\pmod*{\phi(n)}$$ message $$m\in\mathcal{M}$$ compute $$c=e_{(n,e)}(m)$$ $${}=m^e\pmod*{n}$$ transmit $$c$$ $$\rightarrowtail\; \; \;$$ ciphertext $$c\; \; \; \rightarrowtail$$ receive $$c$$ compute $$m=d_{(n,d)}(c)$$ $${}=c^d\pmod*{n}$$

The first thing we need to see is that this satisfies the basic condition to be a functioning cryptosystem:

Proposition $$\PageIndex{1}$$

Let notation be as in the above definition of the RSA cryptosystem. Then for any message $$m\in\mathcal{M}$$, $$d_{(n,d)}(e_{(n,e)}(m))=m$$.

Proof

Any $$m\in\mathcal{M}$$ represents a class in $$\mathbb{Z}/n\mathbb{Z}$$, and we will blur the distinction between the class and its representative $$m$$ satisfying $$0\le m<n$$.

We have built $$d$$ as $$d=e^{-1}\pmod{\phi(n)}$$. This means $$e\cdot d\equiv1\pmod{\phi(n)}$$, so $$\exists k\in\mathbb{Z}$$ such that $$e\cdot d=1+k\phi(n)$$.

Then by Euler’s Theorem 3.3.2, $$\forall m\in\mathcal{M}$$ such that $$\gcd(m,n)=1$$ $d_{(n,d)}(e_{(n,e)}(m))\equiv(m^e)^d=m^{ed}=m^{1+k\phi(n)}\equiv m\cdot(m^{\phi(n)})^k\equiv m\cdot(1)^k\equiv m\pmod{n}$ as desired. The case where $$\gcd(m,n)\neq1$$ is Exercise 4.4.1(1) in this section.

Beyond basic functionality, we need to see how practical RSA is. So let us go through it carefully, picking out the algorithms needed at each step.

1. Bob must choose the large primes $$p$$ and $$q$$. As we have said, there are algorithms which can tell if a number is prime in a reasonable amount of time. More precisely, this means that a (classical) computer can determine if a number $$k$$ is prime in an amount of time which is less than a polynomial function of $$\log(k)$$. [That’s the usual meaning of feasible computation in cryptology.]
2. Furthermore, there are enough primes that Eve will not be able to do a brute force search through all the possibilities. We can tell this because The Prime Number Theorem tells us the (asymptotic) number of primes:

Theorem $$\PageIndex{1}$$: Prime Counting Function

Given $$x\in\mathbb{N}$$, $$x>0$$, let $$\pi(x)=\#\{p\in\mathbb{N}|p\le n\}$$ be the prime counting function. Then $\lim_{x\to\infty} \frac{\pi(x)}{x/\ln(x)} = 1.$

This theorem is one of the gems of analytic number theory. It was proven in $$1896$$ by Jacques Hadamard and Charles Jean de la Vallée-Poussin, although important pieces were known before then by people like Euler, Legendre, and Riemann. The proof is hard, even an elementary one from $$1948$$ by Atle Selberg and Paul Erdös.

One consequence of the Prime Number Theorem is that the probability that a randomly chosen number $$k$$ is prime is approximately $$1/{\ln(k)}$$. For example, looking for a prime with $$200$$ digits, we pick a random number of that size, and then we will have to test on the order of $$\ln(10^{200})=461$$ numbers before we have a prime. This is not an unreasonable amount of computation.

3. Having an RSA modulus $$n=pq$$, we can compute the Euler totient function $$\phi(n)=(p-1)(q-1)$$ nearly instantly by Theorem 2.5.2.

4. Finding the RSA exponent $$e$$ which is relatively prime to $$\phi(n)$$ is not hard, since there are many such – in fact, in a real sense, the probability that two randomly chosen numbers are relatively prime is $$\frac{6}{\pi^2}$$ (for a precise statement of this, and its proof, see ). Testing candidates for $$e$$ is also efficient because, as we shall see below in Exercise 4.4.1(3), the Euclidean Algorithm takes an amount of time which is less than a polynomial function of the $$\log$$’s of the numbers involved – it is feasible.

5. Next, computing $$d=e^{-1}\pmod{\phi(n)}$$ is very fast using the Extended Euclidean Algorithm (Theorem 1.6.1) which is certainly slower than the basic Euclidean Algorithm, but is still feasible.

6. RSA encryption and decryption both consist of raising a number to a power in $$\pmod{n}$$. Fortunately, there is an algorithm called fast modular exponentiation which again does this in an amount of time less than a polynomial function of the $$\log$$’s of the given numbers.

7. One last practical point is how Alice actually uses RSA to send the message she wants, and not merely a number $$m\in\mathbb{Z}$$ such that $$0\le m<n$$.

This is a standard problem in mathematical cryptography and has standard solutions. Typically, Alice must take her message, character by character, and transcribe it into a sequence of numbers using some accepted standard. This has been done since $$1960$$ using the ASCII code [American Standard Code for Information Interchange], which gives $$7$$ bit binary numbers for the $$26$$ letters of the (modern) Latin alphabet, both upper and lower case, as well as for a set of commonly found symbols and a few modern additions, usually no-printing, such as $$11110_2$$ Record Separator, $$111_2$$ Bell, $$1011_2$$ Vertical Tab, etc. These ASCII codes are today always stored in one byte ($$8$$ bits), padded with a leading $$0$$ bit.

Actually, as the World Wide Web has become a global phenomenon, there has been an increasing need for more alphabets and even writing systems (like Chinese) which do not use alphabets. This has resulted in a system called Unicode which as, in version $$6.3$$ as of $$2013$$, more than $$110,000$$ characters. Unicode is stored in a variety encodings, of which the most common are UTF-8 and UTF-16, which use between two and four bytes to store each character.

What Alice typically does, then, is to write out her message in either ASCII or Unicode, simply attach all the bytes in sequence, and then cut the entire message into blocks of $$b$$ bits. Here $$b\in\mathbb{N}$$ is chosen to be the largest value such that $$2^b<n$$, so that those blocks of $$b$$ bits can be thought of as representing an integer $$m\in\mathbb{Z}$$ such that $$0\le m<n$$, so RSA can now be used on the message, a block at a time.

(We are glossing over many details here, such as how to leave space for some salt, other approaches and issues in the structure of the blocks, etc. See any standard reference on cryptography, such as [FS03] or [MVOV96].)

Exercise $$\PageIndex{1}$$

1. In this problem, you will finish the proof of Proposition 4.4.1, which states that RSA decryption functions correctly in all cases.

As a first step, formally state and prove a lemma that for distinct primes $$p$$ and $$q$$, two integers $$r$$ and $$s$$ are congruent mod $$pq$$ if and only if they are congruent mod $$p$$ and mod $$q$$. [Hint: the Chinese Remainder Theorem.]

Now, using the above, prove the missing case of Proposition 4.4.1: Given distinct primes $$p$$ and $$q$$, define $$n=pq$$. Let $$e\in\mathbb{N}$$ satisfy $$\gcd(e,\phi(n))=1$$ and $$d\in\mathbb{N}$$ be an inverse of $$e$$ mod $$\phi(n)$$. Then, for any $$m\in\mathbb{Z}$$ such that $$0\le m<n$$ and $$\gcd(m,n)\neq1$$, we have $$m^{ed}\equiv m\pmod{n}$$.

2. How much computation is required to compute $$a^k\pmod{n}$$ for $$a\in\mathbb{Z}$$ and $$k,n\in\mathbb{N}$$ with $$n\ge2$$?

Multiplying two numbers $$a,b\in\mathbb{Z}$$ is a basic instruction in most modern computers: it can be thought of as taking one unit of time. (Or you can do a number of smaller manipulations which is approximately a polynomial function of the number of digits in $$a$$ and $$b$$; it will make no difference for the rest of this problem.) Similarly, division with remainder is either a single machine instruction (e.g. on a processor in the Pentium family) or can be done by elementary school methods in time approximated by a polynomial function of the sizes of the inputs.

Let us then describe the work to do a multiplication followed by reducing $${}\pmod{n}$$ as being bounded by a polynomial function $$p(d)$$, where $$d$$ is the number of digits in the operands.

If we then simply multiply $$a$$ by itself $$k$$ times, reducing $${}\pmod{n}$$ each time, the time to do this will be approximately $$kp(d)=c_1 e^{c_2d} p(d)$$, for some constants $$c_1,c_2\in\mathbb{N}$$ – it will increase exponentially.

See if you can come up with a much fast exponentiation algorithm, polynomial rather than exponential.

[Hints: (1) Make a table of successive squares of $$a$$ in $${}\pmod{n}$$, being $$a^2$$, $$a^4$$, $$a^6$$, etc. (2) write out $$k$$ in base two, and expand $$a^k$$ using this binary version of $$k$$, the usual rules for exponentiation, and the table. End up with a description of how to compute $$a^k\pmod{n}$$, and check carefully how much time it would take to do your computation.]

3. For $$k\in\mathbb{N}$$, play the following game:

1. use the division algorithm on $$k$$ for division by two, getting quotient $$q$$ and remainder $$r$$;
2. replace $$k\leftarrow q$$;
3. if $$k>0$$, repeat from step (1); otherwise, terminate.

Give a bound on how many steps does it take for this game to finish – answer in terms of a function of $$k$$, or a function of the number of bits required to write $$k$$ down in base two, or a function of the number of digits require to write $$k$$ in base 10.

Show that for every two steps of the Euclidean Algorithm, the remainder terms $$r_i$$ decrease by a least a fraction of $$1/2$$. In other words, if we use the notation of Theorem 1.6.1 then $$r_{j+2}<\frac12r_{j}$$ for all $$j\in\mathbb{Z}$$ satisfying $$j\ge0$$.

Explain how this means the Euclidean Algorithm requires at most $$\log_2(b)$$ steps to compute $$\gcd(a,b)$$ and it therefore requires at most seven times the number of digits of $$b$$. [Hint: what is $$\log_2(10)$$?]

Explain how this means that the Euclidean Algorithm is a cryptologically feasible computation, in the sense of this section.