# An Illustration of the RSA Algorithm

The following 617-digit number (all 617 digits starting with $251$ and ending in $357$) is a product of two prime numbers $p$ and $q$. How long will it take to find these two prime factors?

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

The above number is a challenge to the public to come up with the two prime factors (see RSA challenge number and RSA factoring challenge). No one has been able to successfully meet the challenge. In fact, even with the current state of the art in supercomputing technology, it could take millions of years to factor a number as big as the one shown above. According to the organization that posed the challenge (RSA Laboratories), barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come.

RSA is a cryptographic algorithm that is used to send and receive sensitive data. The name RSA stands for the last names of the creators of the algorithm – Ron Rivest, Adi Shamir and Leonard Adleman.

The algorithm uses a pair of large prime numbers in setting up a public key to encrypt and a private key to decrypt data. The public key is known to the public and includes a large integer $N$ (such as the one indicated at the beginning of the post) that is a product of two prime numbers $p$ and $q$. The private key is computed using two prime factors $p$ and $q$ and is needed to decrypt the messages encrypted by the public key. The RSA scheme is built on the monumental difficulty in factoring large numbers. Barring some system vulnerability that hackers can exploit, it is all but certain that messages sent via RSA scheme can only be read by the intended party – the legitimate party that possesses the private key.

This post gives an illustration of how the RSA algorithm work using much smaller prime numbers. The RSA algorithm is also an application of the Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

The example given below makes use of congruence arithmetic. If $a$, $b$ and $m$ are integers, the symbol $a \equiv b \ (\text{mod } m)$ means that the difference $a-b$ is divisible by $m$ (we say that $a$ is congruent to $b$ modulo $m$). For example, $15 \equiv 3 \ (\text{mod } 12)$ (in terms of clock arithmetic, 6 hours after 9 o’clock is not 15th o’clock but is 3 o’clock). For more information about congruence relation and congruence arithmetic, see this blog post or this Wikipedia entry.

___________________________________________________________________________________________________________________

Example of RSA

The example uses small prime numbers to make the illustration easy to follow. The example has the following steps:

1. Andy creates a public key and a private key. He gives the public key to Becky and keeps the private key to himself.
2. Becky then uses the public key to encrypt a message and sends it to Andy.
3. Andy then uses the private key to decrypt the message received from Becky.
4. $\text{ }$

______________________________________________________
Step 1 – Generating the Public Key and Private Key

Choose two prime numbers $p$ and $q$. In this example, let $p=29$ and $q=47$. Then calculate the following numbers:

$N=p \times q=1363$

$(p-1) \times (q-1)=1288$

Choose an integer $e$ with $1 such that $e$ and $(p-1) \times (q-1)$ are relatively prime (meaning the only common divisor is 1). For this example, Andy chooses $e=11$.

The public key consists of $N=1363$ and $e=11$, which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy (see Step 2 below). The number $e$ is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number $d$ such that:

$e \cdot d \equiv 1 \ (\text{mod } (p-1) \cdot (q-1))$

In this example, find the number $d$ such that

$11 \cdot d \equiv 1 \ (\text{mod } 1288)$

Specifically, we need to find the number $d$ that satisfies $11d=1+1288 k$ for some integer $k$. When $k=10$, we have a solution $d=1171$.

The number $d=1171$ will be used to decrypt any message that will come from Becky. So Andy needs to keep $d$ private and secure.

______________________________________________________
Step 2 – Encrypting a Message using the Public Key

Becky wishes to send a message $T$ (in text) to Andy. Becky first translates $T$ into an integer $M$ (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message $M$ back to the text message $T$. Note that the mapping for translating letters into numbers and back is not part of the RSA algorithm, which only encrypts and decrypts numeric messages.

Suppose the message is $M=289$. The following is the encryption function – the function that generates the encrypted message $C$

$f(M) \equiv M^e \ (\text{mod } N)$

In this example, the encryption function is:

$f(M) \equiv 289^{11} \ (\text{mod } 1363)$

The encrypted message is the number $C=f(M)$ is the remainder that is obtained when $289^{11}$ is divided by $N=1363$. This can be done in a process using congruence arithemtic that can be described as “divide and conquer”. The process is to reduce the exponent by half in each step of the step by step approach.

First, note that $289^2 \equiv 378 \ (\text{mod} \ 1363)$ since $378$ is the remainder when $289^2$ is divided by $1363$ (i.e. division algorithm). Then use the division algorithm successively as shown in the following:

\displaystyle \begin{aligned} 289^{11}&\equiv (289^2)^5 \cdot 289 \ (\text{mod} \ 1363) \\&\text{ } \\&\equiv 378^5 \cdot 289 \equiv (378^2)^2 \cdot 378 \cdot 289 \\&\text{ } \\& \equiv 1132^2 \cdot 378 \cdot 289 \\&\text{ } \\&\equiv 1132^2 \cdot 202 \\&\text{ } \\&\equiv 204 \cdot 202 \\&\text{ } \\&\equiv 318 \ (\text{mod} \ 1363) \end{aligned}

In the “divide and conquer” approach, a congruence calculation in done in each step to reduce the exponent (applying the division algorithm). For example, to go from the first line to the second line, the remainder $378$ is obtained when $289^2$ is divided by $1363$. The number $318$ is the remainder when $204 \cdot 202$ is divided by $1363$.

______________________________________________________
Step 3 – Decrypting the Message Receiving from Becky

Andy receives the encrypted message $C=318$. To decrypt $C$, the private key $d$ that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message $M$.

$g(C) \equiv C^d \ (\text{mod } N)$

In particular, Any needs to find the number $M=g(C)$ that satisfies the following:

$g(C) \equiv 318^{1171} \ (\text{mod } 1363)$

The decrypted message $M=g(C)$ is the remainder when $318^{1171}$ is divided by $1363$. A “divide and conquer” approach can be used.

\displaystyle \begin{aligned} 318^{1171}&\equiv (318^2)^{585} \cdot 318 \ (\text{mod} \ 1363) \\&\text{ } \\&\equiv 262^{585} \cdot 318 \equiv (262^2)^{292} \cdot 262 \cdot 318 \\&\text{ } \\& \equiv 494^{292} \cdot 262 \cdot 318 \\&\text{ } \\&\equiv 494^{292} \cdot 173 \equiv (494^2)^{146} \cdot 173 \\&\text{ } \\& \equiv 59^{146} \cdot 173 \equiv (59^2)^{73} \cdot 173 \\&\text{ } \\& \equiv 755^{73} \cdot 173 \equiv (755^2)^{36} \cdot 755 \cdot 173 \\&\text{ } \\& \equiv 291^{36} \cdot 755 \cdot 173 \\&\text{ } \\&\equiv 291^{36} \cdot 1130 \equiv (291^2)^{18} \cdot 1130 \\&\text{ } \\& \equiv 175^{18} \cdot 1130 \equiv (175^2)^{9} \cdot 1130 \\&\text{ } \\& \equiv 639^{9} \cdot 1130 \equiv (639^2)^{4} \cdot 639 \cdot 1130 \\&\text{ } \\& \equiv 784^{4} \cdot 639 \cdot 1130 \\&\text{ } \\&\equiv 784^{4} \cdot 1043 \equiv (784^2)^{2} \cdot 1043 \\&\text{ } \\& \equiv 1306^{2} \cdot 1043 \\&\text{ } \\&\equiv 523 \cdot 1043 \\&\text{ } \\&\equiv 289 \ (\text{mod} \ 1363) \end{aligned}

We just illustrates how Andy decrypts Becky’s message of $C=318$ to find the original message of $M=289$. The calculation is tedious if done manually but is simple for a computer.

___________________________________________________________________________________________________________________

Summary

We summarize the main steps in the above example.

______________________________________________________
Step 1 – Generating the Public Key and Private Key

Choose two prime numbers $p$ and $q$. Then calculate the following numbers:

$N=p \times q$

$(p-1) \times (q-1)$

Choose an integer $e$ with $1 such that $e$ and $(p-1) \times (q-1)$ are relatively prime (meaning the only common divisor is 1).

The public key consists of $N$ and $e$, which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy. The number $e$ is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number $d$ such that:

$e \cdot d \equiv 1 \ (\text{mod } (p-1) \cdot (q-1))$

The number $d$ is the decryption key and will be used to decrypt any message that will come from Becky. So Andy needs to keep $d$ private and secure.

______________________________________________________
Step 2 – Encrypting a Message using the Public Key

Becky wishes to send a message $T$ (in text) to Andy. Becky first translates $T$ into an integer $M$ (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message $M$ back to the text message $T$.

The following is the encryption function – the function that generates the encrypted message $C$.

$f(M) \equiv M^e \ (\text{mod } N)$

The encrypted message that Becky will send to Andy is $C=f(M)$.

______________________________________________________
Step 3 – Decrypting the Message Receiving from Becky

Andy receives the encrypted message $C$. To decrypt $C$, the private key $d$ that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message $M$.

$g(C) \equiv C^d \ (\text{mod } N)$

The original message sent from Becky is $M=g(C)$.

Note that $M=g(f(M))$. Thus the function $f$ is the inverse function of $g$ (and vice versa). This fact can be established by using Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

___________________________________________________________________________________________________________________

RSA Exercise

Suppose you are Andy. You set $p=53$ and $q=67$. You also choose $e=7$.

You give the public key $N=3551$ and $e=7$.

Becky sends you an encrypted message $C=2691$.

What is the original message?

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$