The Math of Cryptography: RSA

The Math of Cryptography: RSA

Achyut Bharadwaj
September 2021
cryptography, RSA, encryption, decryption, one-way function, factorization, prime, modular arithmetic, modular inverse, kid-RSA, Euclid's division, gcd, Bezout, Euler, totient, Fermat, primality test, Miller-Rabin

A presentation on the mathematics of cryptography, with an emphasis on RSA. A link to the slides is here.

Basic Cryptography #

Sending Messages #

Say, there are 3 people, Aditi, Bhaskar and Diti.
Aditi wants to send the message “HELLO” to Bhaskar, using her computer.
Computers, however, can only store numbers. How will she send the message “HELLO” to Bhaskar?
To store characters, there is a code called the ASCII code. In ASCII, each character is given a value in binary.
“HELLO” is coded as: 1001000 1000101 1001100 1001100 1001111
So, Aditi has to send the above code to Bhaskar.

The problem #

Aditi can send the message to Bhaskar easily. But, she realises that Diti has been tapping into their conversation and can see any messages that Aditi sends to Bhaskar or Bhaskar sends to Aditi.
This is not really a big problem in this case, but it is a big problem when it comes to sharing military data and other secrets that cannot be allowed to read by anyone else.
How do we solve this? We will see it in the next slide.

Encryption to Solve the Problem #

To solve the problem, Aditi and Bhaskar can decide on a code. For example, every letter has to be written as the next letter of the alphabet. So, “Hello” will be written as: “IFMMP”. But, to say “HELLO” to Bhaskar, Aditi will actually have to type “IFMMP”. That is inconvenient. The computer should be able to encrypt the message to make it more convenient.
So, Aditi and Bhaskar decide on a “key”, say “DAVID” to make the computer encrypt the message.
DAVID in ASCII will be: 1000100 1000001 1010110 1001001 1000100

The computer takes the ASCII code of the message, “HELLO” (10010001000101100110010011001001111) and performs the “XOR” function on it with “DAVID” (It will put the key and the message under one another and compare their individual digits. If a digit of both the message and key is 1 or 0, it will be coded as 0. If a digit of either David or the message is 0 and the other is one, it will be coded as 1).
Bhaskar will receive the message 00011000000100001101000001010001011 and will again perform the xor function with the same key, “DAVID” on the message he received, to recover the original message “HELLO”. This way, Diti, who doesn’t know the key will not be able to decrypt the message.

Message in ASCII10010001000101100110010011001001111
Key (DAVID)10001001000001101011010010011000100
Encrypted Message00011000000100001101000001010001011

Table-1: Encryption using a Key #

Encryption process
Fig-1: Encryption process

Another Problem #

The encryption method we saw was good. But, how will they decide the key?
Either Aditi, or Bhaskar will have to send the key to the other person. Diti will easily be able to see what the key is. Using the key, she can decrypt the message. She can, again see what Aditi has sent to Bhaskar.
Is there a way to encrypt the message without exchanging a secret key?
This question will be answered in the next few slides.

One Way Functions #

Introduction to One Way Functions #

One way functions are functions that are easy to compute but near impossible to reverse engineer.
In other words, if you give an input $x$, you can easily get the output, $y$. But, given $y$, it’s almost impossible to get back $x$.
Product of two large primes is an example of a one way function. You can multiply two large primes to get a large composite number. But, you cannot, however, factorize a number that is a product of two large primes with even the best of computers.

Example #






This is easy to compute (using a calculator).

However, given


you will spend the rest of your life, travelling at the speed of light, with a (not so super) computer on earth trying to factorize the number!

Some Math #

Modular Arithmetic #

If you have an equation:

(1) $$x \equiv y \pmod n$$
where $x, y, n$ are positive integers, it means that,
(2) $$n|(x-y)$$
($\equiv$ is an equivalence operator). If $y$ is $x$ inverse under mod $n$, where $x, y$, are positive integers, it means:
(3) $$xy \equiv 1 \pmod n$$
In other words, when $xy$ is divided by $n$, the remainder is $1$.

$x\equiv y \pmod n$ is just another way of writing

(4) $$x\mod n = y\mod n$$
This implies that $n|x-y$.
Also note that while $x\mod n$ is a function, $x\equiv y \pmod n$ is an equivalence relation.

Problem: #

Find the inverse of $3$ mod $7$.


Say, $x$ is the inverse of $3$ under mod $7$. This means that $3x \equiv 1 \pmod 7$. $x=5$ satisfies this.

Kid-RSA #

RSA is a cryptography system most widely used across the web for secure data transmission, and kid-RSA is a similar precursor which is far easier to break.   Let’s say Aditi wants to send Bhaskar a message $m$, and she wants to encrypt it with kid-RSA. Then,

  1. She multiplies it with an encryption code, $e$, which is known by everyone.

  2. Then, she divides it with $n$, also made public by Bhaskar, and finds the remainder, and calls it, say $r$.

  3. When Bhaskar receives $r$, he multiplies it with the decryption code, $d$, which only he knows, to decrypt the message.

Note that $m$ is smaller than $n$ and is relatively prime with $n$. $e$ is also relatively prime with $n$.

So, Aditi finds the value of $r<n$ such that

(5) $$me \equiv r \pmod{n}$$
Since only Bhaskar knows $d$, Diti won’t be able to decode it easily.

But, what exactly are $e$, $n$ and $d$?

Choosing $d$ #

Bhaskar chooses $d$ and $e$ in such a way that

(6) $$de \equiv 1 \pmod n$$
(7) $$d<n$$
Since we know that
(8) $$me \equiv r \pmod n$$
we can say that
(9) $$med \equiv rd \pmod n$$

Substituting $de$ from Eq-6 into Eq-9, we get,

(10) $$m \equiv rd \pmod n$$
Since $m$ is smaller than $n$ and is also relatively prime,
(11) $$m = rd$$

You might realise that to crack this code, you need to find $d$.

Say, Diti also knows that $de \equiv 1 \pmod n$. Since e is made public by Bhaskar, she knows $e$ too. She now needs to find $d$.

So, how can Diti find $d$?

One way to do it is to use guesswork, but that will need high computational power, as $n$ is very large. Turns out that it gets much easier to find d with some math tricks.

More Math #

Euclid’s Division Lemma #

Lemma #

For every pair of integers $a,b$ $\exists$ $q,r\in\mathbb{Z}$ such that

(12) $$a=bq+r, 0\leq r < b$$

Motivation #

Take an example of $a=57, b=13$. We know

(13) $$ \begin{aligned} 57 &= 13\times0+57 \\ &= 13\times1+44 \\ &= 13\times2+31 \\ &= 13\times3+18 \\ &= 13\times4+5 \\ &= 13\times5 - 8 \end{aligned}$$
Notice that out of the set of different $q,r$ we got, one of the values of $r$ was greater than $0$ and less than $13$. Also notice that the value of $r$ that was less than $13$ was the smallest possible non-negative value of $r$ in the set of the possible values of $r$.

This motivates us to examine the set of remainders $r$ that are non-negative, say $S$.

Is it always true that the smallest element of $S$ is less than $13$? Does $S$ always have a smallest element? Why? Suppose the smallest element of $S$ is greater than $13$. So what?

Proof #

Consider the set

(14) $$S=\{a-bq\in\mathbb{N}_0 | q\in\mathbb{Z}\}$$
That is, the set of whole numbers of the form $a - bq$, where $a,b\in\mathbb{N}$.

Now, since

(15) $$a\in\mathbb{N}$$
we have
(16) $$a - b\cdot0 = a \in \mathbb{N} \in \mathbb{N}_0$$
Hence, S is non-empty.

Now, since $S$ is bounded below ($-1$ is less than all elements of $S$) and $S$ is non-empty, $S$ has a smallest element (can be proven using the Well Ordering Principle), say $s$.

So, we can write,

(17) $$a-bq_0 = s$$
for some integer
(18) $$q_0$$

We now prove that $s$ must be less than $b$. We assume for the sake of contradiction that

(19) $$s \geq b$$
That is,
(20) $$a-bq_0 \geq b$$
(21) $$ \begin{aligned} s’ &= a - bq_0 - b \\ &= a - b(q_0+1) \\ &< a-bq_0 = s \end{aligned}$$
Also, since
(22) $$a - bq_0 \geq b$$
(23) $$a - b(q_0+1) \geq 0$$

So, we have: $0\geq s’<s$ and $s$’ can be written as $a-bq$ for some integer $q$ (here $q = q_0+1$). So, $s’\in S$. We assumed that $s$ was the smallest element of $S$. But, we found another element $s’$, which is less than $s$. This gives us a contradiction.

Hence, $0\geq s<b$. So, there exists some $r$, which is the smallest element of $S$ such that $a-bq = r$ and $0\geq r<b$. Hence, for every $a$ and $b$, there exists integers $q$ and $r$ such that

(24) $$a = bq + r, 0\geq r<b$$
With that, we are done.

Euclid’s Division Algorithm #



From Euclid’s Lemma, we can write

(25) $$a=bq+r$$
given integers $a,b$. Now,
(26) $$\gcd(a,b) = \gcd(b,r)$$

Proof #

Let $d$ be a common divisor of $a$ and $b$. Hence, $d$ divides $a - bq = r$. Hence, $d$ divides $r$. In other words, $d$ is a divisor of $r$ too. Now, if $d$ is a common divisor of $b$ and $r$, then $d$ divides $bq+r = a$. Hence, $d$ is a divisor of $a$ too.

In conclusion, every number that divides $a$ and $b$, divides $r$, and every number that divides $b$ and $r$, divides $a$. So, if we let $d$ be the gcd of $a$ and $b$, then $d$ divides $r$. Which implies that $\gcd(b,r) = d’(\text{ say })\geq d$. Also, if we let $d’$ be the gcd of $b$ and $r$, then $d$ divides $a$. Which implies that $\gcd(a,b) = d \geq d’$. We have $d’\geq d$ and $d’\leq d$. Hence, $d’ = d$, or gcd of $a$ and $b$ equals the gcd of $b$ and $r$.

Iterating the Division Algorithm #

Let $a,b,q,r$ be integers such that

(27) $$a = bq_1 + r_1$$
From Theorem-1,
(28) $$\gcd(a,b) = gcd(b,r_1)$$
Now, say
(29) $$b = r_1q_2 + r_2$$
(30) $$\gcd(b,r_1) = gcd(r_1,r_2)$$
Again, let
(31) $$r_1 = r_2q_3 + r_3$$
(32) $$\gcd(r_1,r_2) = gcd(r_2,r_3)$$
From here, we can keep going until we reach
(33) $$r_{n-1} = r_nq_n$$
(34) $$\gcd(r_{n-1}, r_n)=r_n$$

Examples #



Find the gcd of $537$ and $103$.


(35) $$\begin{aligned} 537 &= 103\times5 + 22 \\ 103 &= 22\times4 + 15 \\ 22 &= 15\times1 + 7 \\ 15 &= 7\times2 + 1 \\ 7 &= 1\times7 + 0 \end{aligned}$$
(36) $$\begin{aligned} \gcd(537, 103) &= \gcd(103, 22)\\ &= \gcd(22, 15)\\ &= \gcd(15, 7)\\ &= \gcd(7,1)\\ &= \gcd(1,0)\\ &= 1\end{aligned}$$



Find the gcd of $490$ and $110$.


(37) $$\begin{aligned} 490 &= 110\times4 + 50 \\ 110 &= 50\times2 + 10 \\ 50 &= 10\times5 \end{aligned}$$
(38) $$\gcd(490, 110) = \gcd(110, 50) = \gcd(50, 10) = \gcd(10,0) = 10$$

Tabulation of the gcd Algorithm #

We want to find the gcd of $537$ and $103$. So, let us write $103$ (the smaller number) bellow $537$ (the larger number).


Table-2: Operations to find the gcd #

We now have,

(39) $$\gcd(537, 103) = \gcd(103, 537 - 5\times103) = \gcd(103, 22)$$
. So, we write a $\times5$ to the right of $103$, since we are multiplying it by $5$ and subtract it from $537$, in order to get the remainder when $537$ is divided by $103$. We now want to compute the gcd of $103$ and $22$ (the remainder).

We repeat this process until we get 0.

The process can be seen in Table-2. The gcd of the two original numbers will be the first number above 0 in the table.

Another Tabulation #

$537$$1$$0$$537 = 537\times1 + 103\times0$
$103$$0$$1$$\times5$$103 = 537\times0+103\times1$
$1$$-14$$73$$537\times(-14)+103\times73 = 1$

Table-3: Another way of tabulating the division algorithm #

Bezout’s Identity #

In the previous section, we found two integers such that $537$ times an integer plus $103$ times another integer gives $1$. But, how do we know that such integers exist?



For natural numbers $a,b$ where $(a,b) = d$, $\exists x,y\in\mathbb{Z}$ such that $ax+by = d$.

Proof #

Consider the set

(40) $$S=\{ax+by\in\mathbb{N}\}$$
This set must have a minimum element by the Well Ordering Principle (WOP), say $s$. Since $s\in S$, we can write $s=ax_0+by_0$ for some integers $x_0,y_0$.

Now, by the division algorithm, we can write

(41) $$a = dq+r, 0\leq r<d$$
(42) $$d = ax_0+by_0$$
into this, we get:
(43) $$\begin{aligned} & a = (ax_0+by_0)q + r \\ \implies & a - ax_0q - by_0q = r \\ \implies & a(1-x_0q) + b(-y_0q) = r \\ \implies & ax_1 + by_1 = r \end{aligned}$$
where $x_1$ and $y_1$ are integers such that
(44) $$x_1 = 1-x_0q \\ y_1 = -y_0q$$
Now, if $r\neq0$, then, $r>0$ so $r\in\mathbb{N}$. Hence, $r\in S$. But, $r<s$, which contradicts the minimality of $s$. Hence, $r=0$, or $s|a$. Similarly, $s|b$.

Say $d’$ is a common divisor of $a$ and $b$. That is, $d’|a, d’|b$. So, $d’|ax_0, d’|by_0$, which implies that $d’|ax_0+by_0 = s$.   So, all common divisors of $a$ and $b$ divide $s$. Hence, $s$ is the gcd of $a$ and $b$, by the definition gcd.

Breaking Kid-RSA #

Now that we have sufficient ammunition in our backpack, we can proceed to break the kid-RSA.

Say, Bhaskar chooses his encryption key, $e$, as $103$, $n$ as $537$, and decryption key as $73$. Also, assume that Aditi wants to send Bhaskar the message $20$.

So, Aditi multiplies the message with the encryption key and finds the remainder: Remainder of $20\times\frac{103}{573}$ is $449$.

Aditi then sends the message $449$ to Bhaskar.

It is hard for Diti to decode this. But, Bhaskar has his own decryption key, that no one else knows. Bhaskar’s decryption key is $73$, as we have assumed earlier.   So, to decrypt the message, Bhaskar multiplies what he got by $73$, and finds the remainder when it is divided by $537$.   The remainder when $449\times73$ is divided by $537$ is $20$, which was the message!   Now, in order to break the code, Diti needs to use the techniques we saw in the last few slides.

Diti Breaks it! Recall that $d$ is chosen in such a way that $de\equiv 1\pmod n$ and $d<n$. Diti’s goal is to find $d$ given $n$ and $e$.


Table-4: Diti’s application of the division algorithm #

Diti now applies Bezout’s identity with $(a,b) = (e,n) = (537, 103)$ and computes $x,y$ such that $ax+by=1$ using the process shown in Table-4.

She finds that $537\times(-14)+103\times73 = 1$, or $103\times73 = 537\times14+1$. This implies that $103\times17 \equiv 1 \pmod{537}$, and that’s it! We had $e=103, n=537$, and she found an integer, d, less than $537$ such that $ed\equiv1\pmod{n}$.

In general, Diti can use the gcd algorithm to find $x,y$ such that $ex+ny = 1$. We can rearrange this to get $ex=n(-y)+1$, which in turn implies that $ex \equiv 1 \pmod n$. Since $e$ is coprime with $n$, $e$ has a distinct inverse modulo $n$.

Even More Math #

Euler’s Totient Function #

Euler’s Totient function is represented by $\phi(n)$, where $n$ is the input to the function.

The function counts the number of positive integers less than and coprime with $n$.

For example, take $\phi(18)$. The positive integers less than and coprime with $18$ are: $1,5,7,11,13,17$. These are 6 in number. Hence, $\phi(18)=6$.

If n can be written as

(45) $$p_1^{e_1}p_2^{e_2}...p_k^{e_k}$$
where $p_1, p_2, \dots , p_k$ are primes, then
(46) $$\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right)$$

For example,

(47) $$\phi(18) = \phi(2\times3^2) = 18(1-1/2)(1-1/3) = 18(1/2)(2/3) = 18/3 = 6$$

Euler’s Totient Theorem #



Let $a$ and $m$ be relatively prime positive integers. Let the set of positive integers relatively prime to $m$ and less than $m$ be

(48) $$R = \{a_1,a_2,\dots,a_{\phi(n)}\}$$
(there are $\phi(n)$ elements in the set). Let $S$ be another set such that
(49) $$S=\{aa_1,aa_2,\dots,aa_{\phi(n)}\}$$
Then, $S$ is the same as $R$ under mod $m$.

Motivation #

Let us take an example. Let $m = 18$. Then, $R = {1,5,7,11,13,17}$. Let us take $a = 25$. Then, $S = {25\times1,25\times5,25\times7,25\times11,25\times13,25\times17} = {25,125,175,275,325,425}$. We now take each element of $S$ under mod $m$ or mod $18$. Doing so, we get: ${7,17,13,5,1,11} = {1,5,7,11,13,17}$, which is the same as $R$ !

Observe that all elements of $S$ are co-prime to $18$. Why? So, if we take each element of $S$ mod $18$, they will all be elements of $R$. In other words, $S\subseteq R$. The length of $S$ is the same as the length of $R$. What can you do with this? What do you have to do to prove that $S\equiv R \pmod{18}$ from here?

We have

(50) $$R = \{a_1,a_2,\dots,a_{\phi(n)}\}$$
(51) $$S = \{aa_1,aa_2,\dots,aa_{\phi(n)}\}$$

Each element of $S$ is distinct. Also, the product of two numbers, both coprime to $m$ is also coprime to $m$. Hence, all elements of $R$ when taken modulo $m$ are elements of $S$. Also, the length of the sets $R$ and $S$ are equal. So, if we can prove that all elements of $R$ are distinct mod $m$, we can prove that $R\equiv S\pmod m$

Assume that

(52) $$aa_x \equiv aa_y \pmod n \implies a(a_x - a_y) \equiv 0 \pmod n$$

Since $a$ is coprime with $n$, $a \neq 0 \pmod n$. Hence, $a_x - a_y = 0 \pmod n$, or $a_x = a_y \pmod n$. This only happens when $a_x= a_y$.

Since all elements of $R$ are distinct, and $a_x , a_y$ are both part of $R$, this can only be true when $x = y$.

With that, we are done.

For $a$ coprime to $m$, we have

(53) $$a^{\phi(m)}\equiv1\pmod{m}$$

Define $S,R$ as the same as in the previous theorem.

We know that $R\equiv S\pmod{m}$. Hence, the product of the elements of $R$ will be equal to the product of the elements of $S$ mod $m$. In other words:

(54) $$\prod_{a_i\in S}a_i \equiv \prod_{a_i\in S}aa_i\pmod m$$

Rearranging the above, we get:

(55) $$\begin{aligned} & \prod_{a_i\in S}aa_i - \prod_{a_i\in S}a_i\equiv 0\pmod m \\ \implies & \prod_{a_i\in S}a_i\left(\prod_{i\in[1,\phi(m)]}a-1\right) \equiv 0 \pmod m \\ \implies & \prod_{a_i\in S}a_i\left(a^{\phi(m)}-1\right) \equiv 0 \pmod m \end{aligned}$$

Now, the product of all elements of $S$ is coprime to $m$ since all it’s elements are coprime to $m$. So, we must have

(56) $$a^{\phi(m)} - 1 \equiv 0\pmod m$$
(57) $$a^{\phi(m)}\equiv1\pmod{m}$$



Evaluate $65^6$ mod $18$.


By Euler’s Totient Theorem, since $65$ is relatively prime to $18$, $65^{\phi(18)} \equiv 1 \pmod{18}$.
$\phi(18) = 6$. Hence, $65^6 \equiv 1\pmod{18}$ (Check this using a calculator yourself!)

Fermat’s Little Theorem #



(58) $$a^{p-1}\equiv 1 \pmod{p}$$
where $p$ is prime and $a$ is not a multiple of $p$.

By multiplying both sides of Eq-58 by $a$, we get

(59) $$a^p \equiv a \pmod{p}$$
This is another form of Fermat’s Little Theorem that you will see. Notice that this form of the theorem holds even when $a$ is a multiple of $p$ (Can you see why?).

Fermat preceeded Euler, so he did not prove his theorem using Euler’s Totient Theorem as we did. He instead used induction. We leave it as an exercise to the reader to prove it using induction.


Let us now extend the concept of Kid-RSA (which is easy to break, as we just saw), to a full blown encryption scheme that can’t be broken so easily.

The following steps are followed:

  1. Bhaskar chooses public key, $e,n$ such that $e$ is less than $n$ and coprime with $\phi(n)$ and private key, $d,n$ such that $d$ less than $n$ and coprime with $\phi(n)$ and $de\equiv 1\pmod{\phi(n)}$. He then publishes his public key pair to everyone, including Aditi and Diti.

  2. Aditi encodes the message she wants to send, say $m$, by finding the value of $m^e \mod n$ and sends the result, say $r$, to Bhaskar.

  3. Bhaskar then finds the value of $r^d \mod n$, *Drumroll* and that is the message!

How does this work? Why does Bhaskar get back the same number that Aditi sent?

Why RSA Works #

Bhaskar chooses his private key such that :

(60) $$de \equiv 1 \pmod{\phi(n)}$$


(61) $$r^d \equiv (m^e)^d \equiv m^{de} \pmod n$$

We can rewrite Eq-60 as:

(62) $$de = k\phi(n) + 1$$
for some integer $k$.


(63) $$m^{de} \equiv m^{k\phi(n)+1} \equiv \left(m^{\phi(n)}\right)^k \times m \pmod n$$
Now, by Euler’s totient theorem,
(64) $$m^{\phi(n)} \equiv 1 \pmod n$$
(65) $$r^d \equiv \left(m^{\phi(n)}\right)^k \times m \equiv 1^{k\times m} \equiv m \pmod n$$
With that, Bhaskar has got back the message that Aditi wanted to send!

Choosing $n$ #

Notice, that what we did in the previous slide holds true only if $m$ is coprime with $n$. So, how do we make sure that it always holds.

We have seen before that the message $m$ is smaller than $n$. So, if we can always choose $n$ such that it is the product of primes, all greater than $m$, then $m$ and $n$ are coprime.

So, we let $n$ be the product of two large primes, $p$ and $q$.

Also note that for $de \equiv 1 \pmod{\phi(n)}$ to exist, $e$ must be coprime with $\phi(n)$.

Generating $d$ #

There’s another problem. Sure, Diti can’t find d, but how will Bhaskar find it himself, when he is creating his private key?

He uses that fact that $n$ is the product of two large primes, $p$ and $q$. While Bhaskar knows both $p$ and $q$, Diti only knows $n$. As we have seen before in one way functions, it is very hard to factorize a large number, but it is easy to find the number given its factors.

Bhaskar needs to choose $d$ such that it satisfies Eq-60. $\phi(n)$ in Eq-60, where $n = pq$ is given by

(66) $$\phi(n) = \phi(pq) = (p-1)(q-1)$$
Hence, Bhaskar’s problem translates to finding $d$, given $e$ such that
(67) $$de \equiv 1 \pmod{ (p-1)(q-1)}$$
For this, he can use Bezout’s identity to find $d$.

On the other hand, Diti doesn’t know $p$ and $q$. So, it is impossible for her to find $d$ such that it satisfies Eq-67.

Let us take an example to understand this better. We shall use small primes, $p$ and $q$ so that it is easy to follow.

An Example to Explain RSA #

First, Bhaskar needs to create a private key, for him to decrypt Aditi’s message, and a public key for Aditi to Encrypt her message. Bhaskar’s private key includes $d,n$ and his public key includes $e,n$. He first chooses $n$ such that it is a product of two primes, say $13$ and $37$ (In reality , the primes chosen are very large). Hence, $n = 13\times37 = 481$.

Now, Bhaskar chooses $e$ such that $e$ is coprime with $\phi(481) = (13-1)(37-1) = 12\times36 = 432$. So, $e$ must not have $2$ or $3$ as prime factors. Say, he chooses $e = 65$.

With that, Bhaskar has created his public key. He now needs to find $d$ to create his private key.

Generating a Private Key #

Recall that $de \equiv 1 \pmod{\phi(n)}$. $\phi(n) = 432$, as we have seen earlier. Also, $e = 65$.

Hence, he chooses $d$ such that $65d \equiv 1 \pmod{432}$. In other words, $65d = 432k+1$, for some integer $k$. Or, $65d + 432(-k) = 1$. By Bezout’s identity such integers, $d$ and $k$ exist, since $gcd(432, 65) = 1$. He now applies Euclid’s gcd algorithm on $432$ and $65$.


Table-5: Finding the gcd of $\phi\left(n\right)$ and $e$ #

After applying the Euclidean gcd algorithm on $65$ and $432$ (Table-5), Bhaskar got $65\times113 + 432(-17) = 1$. What Bhaskar wanted was: $65d + 432(-k) = 1$.

Equating the LHS of the two equations, we get $65d + 432(-k) = 65\times113 + 432(-17)$ Which implies that $d = 113$.

Hence, Bhaskar has arrived at his public key, $(65, 481)$ and private key, $(113, 481)$.

Encrypting the Message #

Bhaskar has created both a private key and a public key,

(68) $$(e,n)=(65, 481)$$
(69) $$(d,n)=(113, 481)$$

He shares his public key with everyone, including Aditi, and even Eve.

Say, Aditi wants to send Bhaskar the message $10$ ($10$ is less than both $13$ and $37$). She raises $10$ to the $e$th power. Here $e$ is $65$ (a part of Bhaskar’s public key). She then divides the result by $n = 481$ and finds the remainder. In other words, she finds $10^{65} \mod 481$. The result is $433$ (Check it!)

So, she sends $433$ to Bhaskar.

Decrypting the Message #

Now, Bhaskar receives $433$. He raises $433$ to the $d$th power, and finds the remainder. He had chosen $d = 113$ earlier. So, he finds the remainder when $433^{113}$ is divided by $481$. Doing so, he gets back $10$ (Check!)

Now, Diti intercepts the message. She sees $433$. She also knows Bhaskar’s public key $(65, 481)$. What Eve needs to do in order to decode the message is that, she needs to find $d$. She also knows that $de \equiv 1 \pmod{\phi(n)}$, or $65d \equiv 1 \pmod{\phi(481)}$.

She can easily find $d$ using Euclid’s algorithm if she knows $\phi(481)$. She also knows that $481$ is the product of two primes, and that $\phi(pq) = (p-1)(q-1)$.

So, her aim now becomes to factorize $481$. If she does so, she can decrypt Aditi’s message.

In this example, Bhaskar chose two small primes to multiply to get $n$, just to give us a good understanding of RSA. However, in reality, the two primes are very large. It is very very hard for Eve to factorize a number that is the product of two large primes, in a practical amount of time.

This makes RSA practicaly unbreakable

Primality Testing #

Miller Rabin Primality Test #

This is a probabilistic test, where the a prime is always correctly identified, but there is a space for false positives with the occurrence of Fermat’s Pseudoprimes.

It relies on Fermat’s little theorem. Which states that for a given prime number $p$, for any natural number $a$, where $1 < a < p-1$,

(70) $$a^p \equiv a \pmod p$$

Miller Rabin utilizes the following extension of Fermat’s little theorem

If $p$ is an odd prime number, such that

(71) $$p - 1 = 2^sd$$
with $d$ odd and $s \neq 0$, then for an $a$ coprime to $p$, either $a \equiv 1 \pmod p$, OR there exists an integer $t$ where $0 \leq t < s$. Let $X = 2t$, then $s^{Xd} \equiv -1 \pmod p$.