Todays post is my attempt at reproducing my understanding of how the Math in RSA works.

I've mentioned references at the bottom of the email -- hopefully those links will help you dig deeper and provide you the clarity this post might not be able to provide.

Well, lets get started. I'm going to assume that the reader already know what PKI is, and that public keys and private keys are used to encrypt and decrypt respectively and that private keys are used for signing.

Most tutorials start off with a little bit of Math, and this is for good reason, I assure you. Also, whenever a theorem is mentioned I strongly urge you to play around with

Sage, and check if the theorem does hold true(which is probably the next best thing to reading the proof of the theorem itself).

-==================]

**The Modulus operation**

As computer programmers we all know what the following does :-

a = b % c;

*NOTE:*

*=> From this point onward "=" refers to the "congruence operator" and not the "equality operator".*

When we talk about Modular arithmetic in Math, we would write the above statement as :-

b = a (mod c)

-=============================]

**Primes and Relatively-Prime numbers**

We all know what primes are, so I'm not even going to bother with it. **Relatively Prime** numbers are the ones that have a gcd of 1.

gcd (a, b) = 1, __iff__ **a** and **b** are relatively prime.

If you give it a bit of thought you realize that 1 is relatively prime to every number out there.

-======================]

**Extended Euclidean Theorem**

Again you've probably heard of this, but I'll just mention it anyhow. With Extended Euclidean Theorem, you can calculate values **x** and **y** such that,

ax + by = 1,

when gcd(a, b) = 1

*It isn't hard to do this on pen and paper for small values -- I also urge you to check out the sage function "xgcd" which performs this computation for you.*

-=====================]

**The notation "Zn" and "Zn*"**

**Zn **has different meanings in different contexts -- however in the context of Cryptography, **Zn** is the set of all numbers from **0** to **n-1**.

**Zn*** is the a subset of **Zn **in which all the numbers are **relatively prime to n**

*So far, so good huh?*

-=====================]

**When I say....**

Later in this post I will say stuff like "**a **is **1 in Zn"**.

What I mean when I say that is :-

" **a = 1 mod n **"

-====================]

**Fermat's Theorem**

Fermat came up with a ton of theorems -- one of them stated the following :-

" For any **x** in **Zp* **such that __p is prime__, the value **x^(p-1) **is **1 in** **Zp **".

In other words,

" **x ^ (p-1) = 1 mod p **"

*Why this is relevant will hopefully become more clear in the next part.*

-====================]

**Euler Totient Function**

Simply put, its the size of **Zn***.

In other words, it is the count of the numbers in the range **0 to n-1** that are relatively prime to **n**.

-====================]

**Euler's Theorem**

About a hundred years later, Euler came with an extension of Fermat's theorem. Fermat's theorem only applied to primes, but Euler extended it to composite numbers too.

" For a number **x** in **Zn***, the value **x^(phi(n)) **is **1 in** **Zn **"

In other words,

" **x ^ (phi(n)) = 1 mod n** "

Even better, the theorem suggests a way to compute **phi(n) **for certain values of **n**.

If **n = p * q** such that **p **and **q **are primes, you can compute **n** as :-

" **phi(n) = phi(p) * phi(q) = (p-1)(q-1)**"

Please note that if **n** is sufficiently huge and if its prime factorization cannot be computed, phi(n) also cant be computed.

-====================]

**Steps of RSA**

*About time, huh?*

__Step 1__. Choose two primes **p** and **q **and compute **n = p * q**

__Step 2__. Choose a value **e** in **Zn***

__Step 3__. Using Euler's Theorem, compute **d** such that

"** de = 1 ( mod phi(n) ) **"

At this point, our public key is (n, e) and our private key is (p, q, d).

__Step 4__. Encryption is done as

" **c = m^e (mod n)** "

__Step 5__. Decryption is done as

" **d = c^d (mod n)** "

-====================]

**A short note on Step 3**

At step 3 we have the equation :-

"** de = 1 ( mod phi(n) ) **"

Please note that this can be re-written as :-

**d.e - k.phi(n) = 1**

At this point, the value of **d** is solved using the Extended Euclidean Theorem.

-====================]

**References :-**

- "Number Theory and the RSA Cryptosystem" - Minh Van Nguyen

- Stanford Coursera course on Cryptography(10-1, 10-2) - Dan Boneh