Proof of the RSA Public Key Cryptosystem
Buildup
Let’s call them Alice, Bob, and Eve from left to right. Alice and Bob are the parties exchanging messages, and Eve is a passive attacker interested in the message. The orange box represents information only known by Alice, the sky blue box is information only known by Bob, and the black box represents information that is public (also known by Eve).
Alice has a message $m \in \mathbb{N}$ she needs to receive from Bob.
Algorithm 1
Key Setup: Alice selects and publishes a large prime number’s product $N=pq$ which satisfies $\gcd \left( e , (p-1)(q-1) \right) = 1$ and $e$.
Encryption: Bob computes $c \equiv m^{e} \pmod{N}$ and makes it public.
Decryption: Alice finds $d$ that satisfies $de \equiv 1 \pmod{(p-1)(q-1)}$ and calculates $x \equiv c^{d} \equiv m \pmod{N}$ to obtain $x=m$. Eve realistically cannot know $d$, therefore she cannot know $m$.
Description
The RSA Public Key Cryptosystem was developed by Ronald Rivest, Adi Shamir, and Leonard Adleman and is abbreviated as RSA, named after the first letters of their last names. The three were awarded the Turing Award in 2002 for this achievement.
It is based not only on the difficulty of the discrete logarithm problem like the ElGamal Public Key Cryptosystem but also on the difficulty of the prime factorization problem, making it worthwhile to find large primes just for its robustness. Moreover, it is a system that is fun to study because it’s not just theoretical or outdated but is actually used worldwide today. A potentially fatal attack method is the Shor’s Algorithm, based on quantum computers, but the commercialization of quantum computers is far off, so it will remain active for the foreseeable future.
Proof
Decryption
Alice knows the prime factorization $N = pq$ of $N$, so she can find $e$ that satisfies $\gcd \left( e , (p-1)(q-1) \right) = 1$.
Extended Euclidean Theorem: For two integers $a,b$, there always exists an integer solution to $aX + bY = \gcd (a,b)$.
For two integers $e$, $(p-1)(q-1)$, $$ e X + (p-1)(q-1) Y = 1 $$ there exists an integer solution $\begin{cases} X=d \\ Y = - k \end{cases}$, which means $$ de = 1 + k (p-1)(q-1) $$ In other words, $d$, i.e., the inverse of $e$ in the ring $\mathbb{Z}_{(p-1)(q-1)}$, and since Alice knows $p$, $q$, she can easily find $d$. [ NOTE: The existence of a multiplicative inverse in a ring is not at all trivial, which highlights the necessity of condition $\gcd \left( e , (p-1)(q-1) \right) = 1$. ]
Euler’s Totient Theorem: $$ \gcd(a,m) = 1 \implies a^{ \phi (m) } \equiv 1 \pmod{m} $$
Since $\gcd \left( e , (p-1)(q-1) \right) = 1$, the inverse of $e$, $d$, is found as follows: $$ d = e^{-1} = e^{\phi \left( (p-1)(q-1) \right) -1} $$ It simply involves exponentiation of $e$, so it can be easily and quickly calculated using the exponentiation by squaring method. Let’s consider the case where $\gcd ( c , pq ) = 1$ is satisfied and the case where it is not.
Case 1. $\gcd ( c , pq ) = 1$
It reduces to a problem of finding a modular square root of congruence equations.
Multiplicative property of the Totient function: $$ \gcd (p , q) =1 \implies \phi ( p q ) = \phi (p) \phi (q) $$
$\phi (p) = p-1$ and $\phi (q) = q-1$ so $$ \phi (pq) = \phi (p) \phi (q) = (p-1)(q-1) $$
Euler’s Totient Theorem: $$ \gcd(c,N) = 1 \implies c^{ \phi (N) } \equiv 1 \pmod{N} $$
$c^{(p-1)(q-1)} = c^{ \phi (pq ) }$ so $$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv c^{1 + k (p-1)(q-1)} \\ & \equiv c \cdot \left( c^{(p-1)(q-1)} \right)^{k} \\ & \equiv c \cdot 1^{k} \\ & \equiv c \pmod{pq} \end{align*} $$
Case 2. $\gcd ( c , pq ) \ne 1$
$$ C \equiv c^{(p-1)(q-1)} \pmod{pq} $$ If $c$ is a multiple of $pq$ then $x^{e} \equiv 0$, therefore $x = 0$ is necessary and meaningless. Hence, assume that $c$ is a multiple of either $p$ or $q$, but it doesn’t matter which one, so let’s assume it’s a multiple of $q$. Then, for some $n_{0} \in \mathbb{Z}$ and $p$ not a multiple of some $K \in \mathbb{Z}$, $$ \begin{align*} C =& c^{(p-1)(q-1)} + (pq) \cdot n_{0} \\ =& \left[ qK \right]^{(p-1)(q-1)} + p \cdot q n_{0} \end{align*} $$ there exists $q n_{0}$ satisfying the above equation, so $$ c^{(p-1)(q-1)} \equiv \left[ (qK)^{q-1} \right]^{p-1} \pmod{p} $$
Part 1. $\left( c^{d} \right)^{e} \equiv c \pmod{p}$
Fermat’s Little Theorem: For a prime $p$ and an integer $a$ relatively prime to $p$, $a^{p-1} \equiv 1 \pmod{p}$
Since $K$ is not a multiple of $p$, $\left[ (qK)^{q-1} \right]$ is relatively prime to $p$, $$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv c^{1 + k (p-1)(q-1)} \\ & \equiv c \cdot \left[ (qK)^{k(q-1)} \right]^{p-1} \\ & \equiv c \cdot 1 \pmod{p} \end{align*} $$
Part 2. $\left( c^{d} \right)^{e} \equiv c \pmod{q}$
$$ \begin{align*} \left( c^{d} \right)^{e} & \equiv c^{de} \\ & \equiv \left[ qK \right]^{de} \\ & \equiv 0 \\ & \equiv qK \\ & \equiv c \pmod{q} \end{align*} $$
Part 3. $\left( c^{d} \right)^{e} \equiv c \pmod{pq}$
Multiplication of Modulos: If $\gcd ( m_{1} , m_{2} ) = 1$ then $\begin{cases} a \equiv b \pmod{ m_{1} } \\ a = b \pmod{ m_{2} } \end{cases} \implies a \equiv b \pmod{ m_{1} m_{2} }$
From Part 1, 2, $\begin{cases} \left( c^{d} \right)^{e} \equiv c \pmod{p} \\ \left( c^{d} \right)^{e} \equiv c \pmod{q} \end{cases}$ is obtained, so we get: $$ \left( c^{d} \right)^{e} \equiv c \pmod{pq} $$
Therefore, $x=c^{d}$ exists as a solution to $x^{e} \equiv c \pmod{pq}$ under any circumstances. Also, another solution $u$, if it exists, can easily be shown to always appear as $u \equiv c^{d} \pmod{pq}$.
■
Encryption
Eve knows $e$, but to find the inverse $d$, she must solve the prime factorization problem $N=pq$. Since this is very difficult, Bob can securely transmit the message $m$ to Alice.
■
See Also
Security Algorithms Utilizing the Difficulty of Prime Factorization Problem
Attack Algorithms on the Prime Factorization Problem
- Pollard’s p-1 Prime Factorization Algorithm
- Conditions under Which the Prime Factorization Problem for Semiprimes Is Easily Solved
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p115~122. ↩︎