# RSA Protocol, A Public Key Cryptosystem

As we discussed here, the enciphering and deciphering transformations involve secret keys called encryption and decryption keys. These keys are shared only by the transmitter and the receiver, so they are called private keys. An Achilles heel of cryptographic communication systems that use private keys is that secret communications can take place only after a key is transmitted in secret over a totally secure communication channel. This is referred to as the CATCH 22 of cryptography. First there are two most famous people when it comes to cryptography and communications, way even more famous than the great mathematician Claude E. Shannon formerly at Bell Lab, who is dubbed the father of modern communication theory. They are Alice and Bob. Literally any books and papers on cryptography, communications, or even quantum computing would mention their names.

CATCH 22: Before the transmitter and the receiver Alice and Bob can communicate in secret, they must first communicate in secret.

There is more to this CATCH 22.

CATCH 22a: Even if Alice and Bob succeed in tansmitting their key over a secure communication channel, there is no mechanism that guarantees with full certainty that no one is able to eavesdrop.

To remedy this issue with private key sharing, public key cryptosystems were invented. In a public key cryptosystem, Alice makes the encryption key available to the public, so anyone can encrypt messages using the key but only Alice can decrypt the messages, and Bob can do the same. So, there is no need to secretly communicate to share keys prior to communicating in secret. Using such trapdoor function (also called one-way function ) is crucial for public key cryptosystems. The most famous public key cryptosytem is RSA (named after its inventors Ronald Rivest, Adi Shamir and Leonard Adleman) which was (officially) introduced in 1978 (unofficially, it was already invented years before they did by researchers secretly working in the Communications-Electronics Security Group at GCHQ, the British counterpart of NSA). RSA is based on the difficulty of factoring. Here is a basic idea of the textbook RSA cryptosystem.

Suppose that Alice wants to receive secret messages. She selects two large primes $p$ and $q$ and then forms the product $n=pq$. Alice also chooses an integer $E<n$ coprime to $\phi(n)=(p-1)(q-1)$. The integers $n$ and $E$ are made public and constitute the encryption key, so everybody can encrypt messages. We assume that our message is a sequence of positive integers $T<n$. Bob encypts each integer $T$ as $C\equiv T^E\mod n$, and send the ciphertext to Alice. Alice can decrypt the ciphertext as follows: Let $m=\phi(n)=(p-1)(q-1)$. Since $(E,m)=1$, there exists $D\in\mathbb{Z}/m\mathbb{Z}$ such that $DE\equiv 1\mod m$ or equivalently $DE=1$ in $\mathbb{Z}/m\mathbb{Z}$. Thus, $DE=\phi(n)k+1$ for some $k\in\mathbb{Z}$. The prime numbers $p$ and $q$ are supposedly huge, so $T$ being one of them is improbable and we can safely assume that $(T,n)=1$. Then by the Euler-Fermat theorem, we have $T^{\phi(n)}\equiv 1\mod n$. Finally, we see that the paintext $T$ is recovered by computing $C^D$ modulo $n$. \begin{align*} C^D&\equiv (T^E)^D\mod n\\ &\equiv T^{ED}\mod n\\ &\equiv T^{\phi(n)k+1}\mod n\\ &\equiv T\mod n \end{align*}
Now, assume that Celia is is eavesdropping. She knows the public key $(n,E)$. She also knows the ciphertext $C$. However, in order to decrypt $C$ she needs the decryption key $D$, the inverse of $E$ in $\mathbb{Z}/m\mathbb{Z}$ where $m=\phi(n)=(p-1)(q-1)$, and she needs to know the prime factors $p$ and $q$ of $n$ in order to compute $D$.

Example. Let $n=1073$, $p=29$, and $q=37$. The public key is $(n,E)=(1073,25)$. The plaintext $T$ is “MISS PIGGY” and the numerical equivalents are
$$13\ 9\ 19\ 19\ 27\ 16\ 9\ 7\ 7\ 25$$
Enciphering $T$: $C\equiv T^{25}\mod n=1073$
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} \hline T & 13 & 9 & 19 & 19 & 27 & 16 & 9 & 7 & 7 & 25\\ \hline C & 671 & 312 & 901 & 901 & 656 & 1011 & 312 & 922 & 922 & 546\\ \hline \end{array}$$
Deciphering: Compute $D$, the inverse of 25 modulo $\phi(n)=(p-1)(q-1)=1008$. Since $1=25\cdot 121+1008(-3)$, $D=121$ is the decipering key and the paintext $T$ is retrieved by
$$C^{121}\equiv T\mod n=1073$$
For example, $671^{121}\equiv 13\mod 1073$.

Remark. In practical sense, there is a problem with the above example. If we encrypt the message letter for letter, the cryptosystem can be easily broken by frequency analysis. This problem can be remedied if we encrypt the message in blocks of about 100 letters. The chance that any two message blocks of 100 letters coincide is practically none.

Remark. Of course in practice we wouldn’t be using such small key sizes shown in the above example. Here is an example of practically usable keys: \begin{align*}E&=198778434778923476493186960677288219412181391439289859633481192496758260063\\n&=2555942223974189195272679217974555794863882765417656848825203904501780583533\\D&=1774134686349434385697798709945131299127046225553502224286279549365461014283\end{align*} Messages can be encypted more securely if one uses key sizes of about 200 digits in addition to using many-letter message blocks suggested in the above remark.

Remark. As mentioned earlier, the presumed security of RSA is based on the belief that factoring is a difficult problem to crack on a computer. So, how difficulty can it be? Umesh Vazirani, a computer scientist at UC Berkely, summed it up using the example of factoring a 2,000-digit number back in 1994: “It’s not just a case that all the computers in the world today would be unable to factor that number. Even if you imagine that every particle in the universe was a computer and was computing at full speed for the entire life of the universe, that would be insufficient to factor that number.”

Remark. RSA protocol begins with picking prime numbers to make the key. We know there are infinitely many prime numbers although we don’t know if that is still the case for a particular type of prime numbers. For example, it is an open problem in number theory if there are infinitely many Mersenne prime numbers, i.e. primes numbers of the form $2^n-1$. (The conjecture is there are infinitely many Mersenne prime numbers.) The largest prime number known to date is a Mersenne prime $2^{82589933}-1$. Especially from computational perspective, it would be interesting to see how prime numbers are distributed, and prime number theorem gives us a pretty good picture about how many prime numbers are there within a certain bound. Let $\pi(x)$ denotes the number of prime numbers less than or equal to $x$. $\pi(x)$ is called prime-counting function. Then Prime Number Theorem sates that $$\lim_{x\to\infty}\frac{\pi(x)}{\left[\frac{x}{\log(x)}\right]}=1$$ which can be restated as $$\pi(x)\sim\frac{x}{\log(x)}$$ for large $x$. This can be interpreted that for large $x$, the probability that a random integer not greater than $x$ is prime is very closed to $\frac{1}{\log(x)}$. This theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Pousin in 1896. For example, if one wants to know how many prime numbers there are between $\frac{x}{2}$ and $x$ for a given lager number $x$, we can get an estimate from prime number theorem: \begin{align*}\pi(x)-\pi\left(\frac{x}{2}\right)&\sim\frac{x}{\log(x)}-\frac{x}{2\log\left(\frac{x}{2}\right)}\\&\sim\frac{x}{\log(x)}-\frac{x}{2\log(x)}\ (\mbox{because $x$ is large})\\&=\frac{x}{2\log(x)}\end{align*} Figure 1 shows the comparison between the asymptotic distribution of prime number between $\frac{x}{2}$ and $x$ (in blue), and its approximation (in red).

For $x=100000$, using the approximation $\frac{x}{2\log(x)}$ there are 4343 estimated prime numbers between 50000 and 100000, so there are plentiful of them to choose from.