Recently, I’ve realized that it is not so trivial to fund a precise but still quite understandable definition of RSA cipher and the underling math problem. So, here it is:
The RSA problem
Given $n = pq$, where $p$ and $q$ are large prime numbers, and an integer $e$ such that $e$ is coprime with $\phi(n) = (p-1)(q-1)$ (Euler’s totient function), solve the congruence:
\[x^e \equiv c \mod n\]Theorem
Under the conditions of the RSA problem, the function $c = x^e \mod n$ is a bijection and therefore has a unique solution. To find $x$ in reasonable time $\mathcal{O}(1)$, it is necessary to know the Euler’s totient $\phi(n)$ or, equivalently, the factorization of $n$. Otherwise, if $p$ and $q$ are sufficiently large, solving the RSA problem in reasonable time is infeasible.
Key steps:
\[\begin{gathered} \gcd(e, \phi(n)) = 1 \\ ae + b\phi(n) = 1 \\ \text{(coefficients } a, b \text{ can be found using the Euclidean algorithm)}\\ c^{\phi(n)} \equiv 1 \mod n \quad \text{(Euler's theorem)}\\ c \equiv c^{ae + b\phi(n)} \equiv c^{ae} \equiv c^a \mod n \Rightarrow\\ x = c^a \end{gathered}\]RSA cryptosystem
Alice wants to send a message to Bob, represented as a natural number $m$.
- Bob generates two prime numbers $p$ and $q$, then computes $n = pq$ and $\phi(n) = (p-1)(q-1)$.
- Bob chooses an integer $0 < e < \phi(n)$ such that $\gcd(e, \phi(n)) = 1$, and then computes $d$ such that $ed \equiv 1 \mod \phi(n)$. Bob’s public key is the pair $(e, n)$, which he sends to Alice.
-
Alice computes the ciphertext:
\[c = m^e \mod n\]and sends $c$ to Bob.
-
To decrypt, Bob uses his private key $d$ and computes:
\[m = c^d \mod n\]
The public exponent is often constant and equals $65537$. This does not affect the cipher security because it as well as private key depends only on the modulus $n$.