Public Key Encryption - RSA

Introduction

RSA is a public-key cryptosystem developed by Ron Rivest, Adi Shamir and Leonard Adleman and published in 1977. The encryption key (public key) and the decryption key (secret key) are distinct. Anyone can encrypt the message but only whom keeps the secret key can decrypt it.

The Core Ideas

From an original message \(m\), the encrypted message is created by powering it to an "encryption factor" and modulo to an appropriate value \(k\), calculated by: \(m^{\text{encryption factor}} \mod k= M\)

And then, from the encrypted message \(M\), the original message \(m\) can be recorvered by powering it to a "decryption factor" and also modulo to \(k\): \(M^{\text{decryption factor}} \mod k = m\)

This means \(m^{\text{encryption factor * decryption factor}} \mod k= m\), this implies:

$$m^{\text{encryption factor * decryption factor} - 1} \equiv 1 (\mod k)$$

Let the "encryption factor" be revealed to the public for encryption and the "decryption factor" be used to decrypt a message and kept private. But how to find those keys, and especially, how to find \(k\)?

Moving next, the Euler's Theorem and the totient function \(\phi(n)\)

For any \(a,n \in \mathbb{N}, \gcd(a,n)=1\), then \(a^{\phi(n)} \equiv 1 \quad (\mod{n})\) in which \(\phi(n)\) is the totient function defined by:

$$\phi(n)=|\set{0\lt x \lt n, \gcd(n,x)=1}|$$

Some properties of the totient function:

1. \(\phi(1)=1\)

2. If \(\gcd(a,b)=1\), then \(\phi(a)*\phi(b)=\phi(a*b)\)

3. If \(p\) is a prime, then \(\phi(p)=p-1\)

Applying the Euler's theorem to the encryption scheme

If letting the original message \(m\) to be \(a\), then the target is to find an appropriate \(n\) satisfying:

1. \(\gcd(a,n)=1\)

2. \(t.\phi(n) + 1=\text{encryption factor}\times\text{decryption factor}, \forall t>0, t\in \mathbb{N}\)

The RSA Algorithm

1. Choose 2 prime numbers: \(p,q\)

2. Calculate \(n=p.q, \phi(p)=p-1, \phi(q)=q-1 \implies \phi(n)=(p-1)(q-1)\)

3. Choose \(d,e \in \mathbb{N}\) such that: \(d.e=1+t.\phi(n), \forall t > 0, t \in \mathbb{N}\). This is written in the algorithm as:

   1. Choose \(1 \lt e \lt \phi(n)\) such that \(\gcd(e,\phi(n))=1\)

   2. Choose \(d\) such that \(d.e \equiv 1 (\mod \phi(n))\)

4. The public key is \(pk=(n,e)\) and secret key is \(sk=(d,n)\)

Encryption: \(M = m^e \mod{n}\)

Decryption: \(m=M^d\mod{n}\)

It is clearly seen that: \(M^d \mod n = (\underbrace{m^e}_{M})^d \mod n = m^{e.d} \mod n \mod n = m\)

Hope this post helps you a better understanding.
You could find an interactive demo of this algorithm here.