RSA (Rivest–Shamir–Adleman) algorithm is an asymmetric cryptographic algorithm that is widely used . We have been hearing RSA algorithm all the time, but some of us actually did not know what it really is and how it works.
In this article, I will systematically discuss the theory behind the RSA algorithm. The theory guarantees that the cryptosystems built on the top of the RSA algorithm are relatively safe and hard to crack, which is fundamentally interesting.
Prerequisites
Euler’s Totient Function
In number theory, Euler’s totient function, also called Euler’s phi function, denoted as $\varphi(n)$, counts the positive integers up to a given integer n that are relatively prime to $n$. In other words, it is the number of integers $k$ in the range $1 \leq k \leq n$ for which the greatest common divisor $\gcd(n, k)$ is equal to 1.
Euler’s totient function is a multiplicative function, meaning that if two numbers $m$ and $n$ are relatively prime, then,
[\varphi(mn) = \varphi(m)\varphi(n)]
If $k$ numbers, $\{m_1, m_2, \cdots, m_k\}$, are pairwise relatively prime, then
[\varphi(\prod_{i=1}^{k}m_i) = \prod_{i=1}^{k} \varphi(m_i)]
A concrete proof of this property could be found here, which requires to use the Chinese remainder theorem.
When $n$ is prime number, according to the definition of prime, $\varphi(n) = n-1$. If $m$ and $n$ are different prime numbers, because $m$ and $n$ are relatively prime, we have
[\begin{aligned}
\varphi(mn) &= \varphi(m)\varphi(n)
&= (m-1)(n-1)
\end{aligned}]
Euler’s Theorem
If $m$ and $n$ are relatively prime, then,
[m^{\varphi(n)} \equiv 1 \pmod n]
where $\varphi(n)$ is Euler’s totient function. This theorem is very famous, and there a couple of different proofs to it. One of the proofs could be found here.
Multiplicative Inverse Theorem
Let $n$ and $x$ be positive integers. Then $x$ has a multiplicative inverse modulo $n$ if and only if $\gcd(n, x) = 1$. Moreover, if it exists, then the multiplicative inverse is unique.
Equivalently, that is to say, let $n$ and $x$ be positive integers,
[xy \equiv 1 \pmod n]
$y \bmod n$ exists if and only if $\gcd(n, x) = 1$, and $y \bmod n$ is unique.