Cryptology by Discovery: An Introduction to Conjecture and Proof

Section 5.7 RSA 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

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.

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{.}\)

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.