## Section5.7RSA cryptosystem

We are now ready for our first public key cryptosystem to exchange messages. Remember that the goal for a public key cryptosytem is that there are separate encryption, $E(x)\text{,}$ and decryption, $D(x)\text{,}$ formulas. These formulas must satisfy the following properties:

1. For a message $M\text{,}$ $D(E(M))=M\text{.}$
2. Both $E(x)$ and $D(x)$ must be easy to compute.
3. It must be hard to compute $D(x)$ even though $E(x)$ is made public.

There are many different functions that can be used to create such a $D$ and $E\text{.}$ In this section we will discuss a commonly used system based on our number trick protocol. It is called the RSA cryptosytem, after inventors Ron Rivest, Adi Shamir, and Leonard Addleman who first published this algorithm in 1978 in their paper “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”.

For the RSA protocol, we are going to use exponentiation mod $n$ for our encryption and decryption formulas. In order to do so, we must first convert the message $M$ to a number using some agreed upon method. For this class, we will primarily use base 26. In practice, however it is more standard to use the ASCII representation for converting letters and symbols to numbers and an appropriate block size for groups of letters. We will introduce the RSA system using the description from Rivest, Shamir, and Adleman in their 1978 paper.

To encrypt a message $M$ with our method, using a public encryption key $(e,n)\text{,}$ proceed as follows. (Here $e$ and $n$ are a pair of positive integers.)

First, represent the message as an integer between 0 and $n−1\text{.}$ (Break a long message into a series of blocks, and represent each block as such an integer.) Use any standard representation. The purpose here is not to encrypt the message but only to get it into the numeric form necessary for encryption.

Then, encrypt the message by raising it to the $e$th power modulo $n\text{.}$ That is, the result (the ciphertext $C$) is the remainder when $M^e$ is divided by $n\text{.}$

To decrypt the ciphertext, raise it to another power $d\text{,}$ again modulo $n\text{.}$ The encryption and decryption algorithms $E$ and $D$ are thus:

\begin{equation*} C \equiv E(M) \equiv M^e \pmod{n} \end{equation*}
\begin{equation*} D(C)\equiv C^d \pmod{n} \end{equation*}

for a message $M$ and for a ciphertext $C\text{.}$

[omitted material]

How should you choose your encryption and decryption keys, if you want to use our method?

You first compute $n$ as the product of two primes $p$ and $q\text{:}$

\begin{equation*} n=p·q. \end{equation*}

These primes are very large, “random” primes. Although you will make $n$ public, the factors $p$ and $q$ will be effectively hidden from everyone else due to the enormous difficulty of factoring $n\text{.}$ This also hides the way $d$ can be derived from $e\text{.}$

You then pick the integer $d$ to be a large, random integer which is relatively prime to $(p−1)·(q−1)\text{.}$ That is, check that d satisfies:

\begin{equation*} gcd(d,(p−1)·(q−1)) = 1 \end{equation*}

(“gcd” means “greatest common divisor”).

The integer $e$ is finally computed from $p\text{,}$$q\text{,}$ and $d$ to be the “multiplicative inverse” of $e\text{,}$ modulo $(p−1)·(q−1)\text{.}$ Thus we have

\begin{equation*} e·d≡1 \pmod{(p−1)·(q−1)}. \end{equation*}
―Rivest, Shamir, and Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”

We can condense the description of the RSA algorithm using the Euler Phi function, $\phi(n)\text{.}$ What is the $\phi$ symbol? Answer

$\phi$ is a letter in the Greek alphabet. It is called phi and pronounced “fee”.

###### Definition5.7.2.Euler Phi Function.

The function $\phi(n)$ counts the number of integers, $k\text{,}$ where $1 \leq k \leq n$ and $gcd(k,n)=1\text{.}$

In order to use this method, the messsage $M$ must be converted to a number. The number must be in the range of 1 to $n-1$ for the mod $n\text{.}$ Generally a block of letters will be converted to a number. The block size should be chosen to make sure the numerical value of the message is small enough. If the message is long enough to require multiple blocks of letters, each block is encrypted separately. We will encrypt message using base 26 and blocks of an appropriate size for the given modulus. In practice, base 26 would not be used and a standard ASCII representation would be used. Blocks must still be chosen to be an appropriate size for the modulus.

Note that in the investigations, you found something a little better than $\phi(n)=(p-1)(q-1)$ for steps 2. and 3. You will revisit that in the homework.

###### Question5.7.4.

1. Why does it work? That is, why does $D(CT) \equiv M \pmod{n}\text{?}$
2. Why is it secure? That is, from the public information $e,n$ why can't anyone else find $M\text{?}$

For the first question, we need properties of the Euler $\phi$ function, and Euler's theorem. We will first prove our formula for $\phi(pq)\text{.}$

###### Example5.7.6.

To see how this proof works we do an example with $p=3$ and $q=7\text{.}$ We want to calculate $\phi(3*7)=\phi(21)\text{.}$ We start with all numbers from 1 to 21 and then remove all the ones that have a factor in common with 21.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

Since 21=3*7 the only way a number in this list could have a factor in common with 21 is if it has a factor of 3 or 7. We first examine numbers in this set that share a factor of 7 with 21; they are 7,14,21. Since every seventh number is a multiple of 7, there are $\frac{21}{7}=3$ of them. We next examine all the numbers in this set that are multiples of 3; they are 3,6,9,12,15,18,21. Since every third number is a multiple of three, there are $\frac{21}{3}=7$ of them. Note that 21 is listed in both sets, so we need to be careful about doublecounting it. Thus, to get the number of integers which are relative prime to $\phi(n)$ we start with all 21 numbers, subtract off the multiples of seve, subtract off the multiples of three, and then add one because we subtracted 21 twice. We see that

\begin{equation*} \phi(21)=21-3-7+1=3(7-1)-1(7-1)=(3-1)(7-1). \end{equation*}

To compute $\phi(pq)$ we start with all numbers from 1 to $pq$ and subtract all numbers that are not relatively prime to $pq\text{.}$ This will only include numbers that have a factor of $p$ or a factor of $q$ (or both). The numbers that have a factor of $p$ are $p, 2p, 3p, \cdots qp\text{.}$ So there are $q$ of those numbers. The numbers that have a factor in common with $q$ are $q,2q, \cdots pq$ so there are $p$ of those numbers. We now have to check if we have double counted any numbers (i.e., if any numbers can appear on both lists). In this case, that would mean a number is a multiple of $p$ and a multiple of $q\text{.}$ Because $p$ and $q$ are distinct primes the only way a number could be a multiple of both $p$ and $q$ is if it is a multiple of $pq\text{.}$ Thus there is just the one number $pq$ that is counted on both lists. Thus, the number of integers between 1 and $pq$ that are relatively prime to $pq$ is $pq-p-q+1\text{.}$ That is, all the numbers between 1 and $pq$ ($=pq$) minus the count of numbers that have a factor in common with $q$ ($=p$) minus the numbers that have a factor in common with $p$ ($=q$) plus the double counted numbers that have a factor in common with both $p$ and $q$ ($=1$). Thus,

\begin{equation*} \phi(pq)=pq-p-q+1=p(q-1)-1(q-1)=(p-1)(q-1). \end{equation*}

You will prove this in the exercises and show that $x^{\phi(pq)k+1} \equiv x \pmod{pq}\text{.}$ This is a special case of Euler's theorem because there is a generalization for any $n\text{.}$ While we only need $n=pq$ for the RSA cryptosystem, the full theorem is quite important in general.

To understand why RSA is secure, or rather for what values of $n$ RSA is secure, we need to understand how we could break RSA. We could break RSA if we could:

1. Factor $n$ to find $p,q\text{.}$ If we know $p,q$ then computing $\phi(n)$ and $d$ is easy. Factoring is hard.
2. Compute $\phi(n)$ without factoring $n\text{.}$ However, if we know $\phi(n)$ then we will be able to factor $n\text{.}$ You will show this in the exercises.
3. Compute $d$ without factoring $n\text{.}$ Again, one can show that if you know $d$ you can factor $n\text{.}$ Since $ed-1$ is a multiple of $\phi(n)\text{,}$ this also gives you information about factoring $n\text{.}$
4. Compute $e$th roots mod $n\text{.}$ Solve $C \equiv M^e \pmod{n}.$ Computing $e$th roots mod $n$ is also hard.
5. Try all $M$ until $M^e \equiv C \pmod{n}\text{.}$ ( Brute force. )

Thus, the security of RSA is primarily related to the difficult of factoring. Note that this is not a provable security. At present, if $n$ is large enough there is not a computationally efficient way to factor $n\text{.}$ This doesn't mean it is impossible to factor $n\text{,}$ only that the time it would take to do so is much too long. So, how big does $n$ need to be? In the original paper Rivest, Shamir and Adleman, “recommend using 100-digit (decimal) prime numbers $p$ and $q\text{,}$ so that $n$ has 200 digits.” This size has increased over time as both computer processing speed and factoring algorithms have improved. You will examine some actual RSA sizes in the exercises.

### ReferencesReferences

[1]

Ron Rivest, Adi Shamir, Leonard Adleman “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications of the ACM, 21 (2):120-126, February 1978.