RSA Encryption
Background
Definitions
The Euler’s totient function, represented as $\phi(n)$, gives us the number of positive integers up to $n$, that are relatively prime to $n$. For example, $\phi(9) = 6$ since the numbers $1,2,4,5,7,8$ are relatively prime.
Lemmas
Lemma 1: If $k$ is relatively prime to $n$, then there exists a multiplicative inverse $k^{-1}$ such that
\[k\cdot k^{-1} \equiv 1 \mod n\]Proof: Suppose $k$ is relatively prime to $n$, then $\gcd (k, n) = 1$. That means that there exists a linear combination of $k$ and $n$ that equals to $1$.
\[sk + tn = 1\]Then, we can rearrange to get:
\[tn = 1 - sk\]Hence,
\[n \mid (1-sk) \implies n \mid -(1-sk) \implies n \mid (sk - 1)\implies sk \equiv 1 \mod n\]$\square$
Lemma 2: Given $n = pq$ where $p$ and $q$ are prime numbers,
\[\phi(n) = (p-1)(q-1)\]Proof: Since $p$ and $q$ are prime, then the only numbers smaller than $n$ that have greatest common divisors larger than $1$ are numbers containing $p$ and $q$ as factors. There is precisely $p-1$ multiples if $q$ and $q-1$ multiples of $p$ in the range $[1, pq)$. In the range $[1, pq]$ there is $p-1 + q - 1 + 1$ multiples of either $p$ or $q$, since $pq$ is a multiple of either one of them.
For the rest of the numbers, they must be relatively prime since $n$ only has factors of $p$ and $q$. Hence
\[\phi(n) = pq - p + 1 - q + 1 - 1 = pq - p - q + 1 = (p - 1)(q - 1)\]$\square$
Lemma 3: Suppose $k$ is relatively prime to $n$, then
\[k^{\phi(n)} \equiv 1 \mod n\]Proof: Let $k_1,\dots k_r$ be the numbers that are relatively prime to $n$, where $r = \phi(n)$. Then, we let:
\[k_1 \cdots k_r = \text{rem}(k\cdot k_1, n) \cdots\text{rem}(k\cdot k_r, n)\] \[\equiv (k\cdot k_1)\cdots (k\cdot k_r) \mod n\] \[\equiv (k_1 \cdot k_2 \cdots k_r) \cdot k^r \mod n\]Since $k_1,\dots, k_r$ are relatively prime, we can multiply the multiplicative inverse on both sides, cancelling out the values, leaving us with:
\[k^{\phi(n)} \equiv 1 \mod n\]$\square$
The Algorithm
High level overview
We want to be able to get an integer $e$, the public key, and an integer $d$, the private key, such that we can encrypt a message $m$ using $e$ and decrypt it using $d$. We want to do it using modulo arithmetic.
Now, here’s the confusing part. Follow closely. We eventually want to be able to get an encoded message of some form $\text{rem}(m^e, n)$, where $e$ is the public key, such that we can decode it by exponentiating it using $d$, the private key, like so:
\[\text{rem}(\text{rem}(m^e, n)^d, n) \equiv \text{rem}(m^e, n)^d \equiv (m^e)^d \equiv m^{ed} \mod n\]Then, we want to get some representation of $ed$ such that we can cancel things out to get $m$. That is, we want to find an $ed$ where $m^{ed - 1}\equiv 1 \mod n$, so we can do:
\[m^{ed} \equiv m^{ed - 1}\cdot m \equiv 1\cdot m \equiv m \mod n\]For us to retrieve exactly back $m$, $m < n$. How do we do this?
Building from first principles
First, we need to define some constraints on $m$. $m < n$ and $m$ must be relatively prime with $n$. Hence, $m$ cannot contain factors of either $p$ or $q$.
- $m<n$ as we need to not lose any data when we calculate the remainder after division with $n$.
- $m$ must be relatively prime, if not the following technique won’t work.
Next, we need to find an $ed$ such that
\[m^{ed - 1} \equiv 1 \mod n\]So that we can do $m^{ed}\equiv m^{ed - 1}\cdot m \equiv 1\cdot m \mod n$ We can recognize that this is possible if: \(ed \equiv 1 \mod z\) where $z = \phi(n)$. Since that means that $z \mid (ed - 1$), hence $(ed - 1) = rz$ where $r\in \mathbb{N}$. Thus, we have:
\[m^{rz} \equiv m^z\cdot m^z \cdots m^z \equiv 1\cdots 1 \equiv 1 \mod n\]by lemma 3.
Equivalently, that means that $e$ needs to be some integer that has a multiplicative inverse $e^{-1} = d$. By lemma 1, if we find any relatively prime number $e$ to $z = \phi(n)$, we can do just that.
Therefore, we search through $[1,z]$ and find a relatively prime number to $n$, then we compute its modulo multiplicative inverse $d$. Then we can let $e$ be our public key and $d$ be the private key used to decode $m$. That’s how we get the following procedure for RSA.
Procedure
- Find two prime numbers $p$ and $q$.
- Compute $n = pq$.
- Find $z = \phi(n) = (p - 1)(q - 1)$.
- Find a relatively prime number to $z$. Let this number be $e$. This is our public key.
- Find the modulo multiplicative inverse of $e$ under $z$. Let this be $d$. This is our private key.
- Given a message $m$ that is relatively prime to $n$ and smaller than $n$,
- We encode it using $k = \text{rem}(m^e, n)$
- We decode it using $\text{rem}(m^d, n)$, to obtain $m$.
We will prove step 7 and 8.
\[rem(m^e, n) \equiv m^e \mod n\]Hence:
\[k^d \equiv (m^e)^d \mod n\]\(\equiv m^{ed} \mod n\)\(\equiv m^{rz + 1} \mod n\)\(\equiv m\cdot m^{rz} \mod n\)
\[\equiv m \cdot (m^z\cdots m^z) \mod n\] \[\equiv m \cdot (1\cdots 1) \mod n\] \[\equiv m \mod n\]Obtaining back $m$.