RSA

We discuss the problem of sending a message secretly over the internet. Suppose the original message is a sequence $x$, the encrypted message is $y$.

XOR Encryption

One solution is to via the XOR operation. Suppose there is a key $k$ that is known both to the sender the receiver. Given an integer $n \in \mathbb{N}$, denote $(n)_2$ its binary representation.

Sender Encryption. $ (y)_2 = (x)_2 \oplus (k)_2. $

Receiver Decryption. $ (x)_2 = (y)_2 \oplus (k)_2. $

Analysis

Given $x$ with length $n$, if $k$ is sampled uniformly at random from $\{0, 1\}^n$, then $(y)_2$ is a sequence uniformly at random from $\{0, 1\}^n$. If the message is sent only one time, the eavesdropper can't get more information about $x$ after seeing $y$.

Two drawbacks exists.

1. How can the sender exchange the key $k$ with the receiver without meeting each other?

2. If the many messages are sent, there are frequency pattern associated with $y$, making it breakable.

RSA Encryption

RSA encryption algorithm overcomes the first issue by generating two keys for the receiver: the secrete key and the public key. The public key is distributed across the internet. The sender encrypts the message $x$ with the public key. Only the receiver who has the secret key can decrypt the message. The mathematics behind is explained as follows.

Question to ponder: can we attack RSA by the frequency pattern?

Generation

First generate two prime number $p, q$ and let $N = pq$. Further, we find a integer $e$, such that

1. $e$ is coprime to $(p - 1)(q - 1)$, i.e., $\exists d$, such that$$ed \equiv 1 \pmod{(p - 1)(q - 1)}.$$
2. $e \neq p$, $e \neq q$.

Question to ponder: does such $e$ exists?

Answer: YES. There are $\Omega \left( \frac{(p - 1)(q - 1) }{ \log (p - 1)(q - 1) } - \frac{ \sqrt{ (p - 1)(q - 1) } }{ \log \sqrt { (p - 1)(q - 1) } } \right)$ prime numbers in $\left( \sqrt{(p - 1)(q - 1)}, (p - 1)(q - 1) \right)$. Find three distinct primes within this range, denoted as $p_1, p_2, p_3$. Then $p_1 \cdot p_2 \cdot p_3 > (p - 1) (q - 1)$, so at least one of them is not a prime factors of $(q - 1)(p - 1)$.

Encryption and Decryption

Release the pair as public key:

And keep in secrete the triple as private key:

The algorithm for encryption and decryption is as follows:

Sender Encryption. $ y \equiv x^e \pmod N. $

Receiver Decryption. $ x \equiv y^d \pmod N. $

To prove the correctness of the algorithm, we have

Theorem $ x^{e d} \equiv x \pmod N. $

Proof.

Since $ed \equiv 1 \pmod{(p - 1)(q - 1)}$, there exists some $k \in \mathbb{N}$, s.t., $e d = k (p - 1)(q - 1) + 1$. Hence,

By Fermat's Little Theorem,

Or equivalent, both $p$ and $q$ divides $m - x$:

It follows that $m - x$ is a common multiple of $p$ and $q$, and therefore, $m - x$ is divided by the least common multiple of $p$ and $q$, i.e., $N | (m - x)$.

Hence $m \equiv x \pmod N$.

$\square$