RSA

Problem

Given $n=pq$, where $p$ and $q$ are large prime numbers, and an integer $e$ such that $e$ is coprime with $\varphi (n)=(p-1)(q-1)$ (Euler’s totient function), solve the congruence:

$$x^e\equiv c\mathrm{mod}n$$

---

Theorem

Under the conditions of the RSA problem, the function $c=x^e\mathrm{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 $\varphi (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,\varphi (n))=1 \\ ae+b\varphi (n)=1 \\ \text{(coefficients }a,b\text{ can be found using the Euclidean algorithm)} \\ {c}^{\varphi (n)}\equiv 1\mathrm{mod}n\text{(Euler’s theorem)} \\ c\equiv c^{ae+b\varphi (n)}\equiv c^{ae}\equiv c^a\mathrm{mod}n \end{gathered}$$

---

RSA Cryptosystem

Alice wants to send a message to Bob, represented as a natural number $m$.

1. Bob generates two prime numbers $p$ and $q$, then computes $n=pq$ and $\varphi (n)=(p-1)(q-1)$.

2. Bob chooses an integer $0<e<\varphi (n)$ such that $\gcd (e,\varphi (n))=1$, and then computes $d$ such that $ed\equiv 1\mathrm{mod}\varphi (n)$. Bob’s public key is the pair $(e,n)$, which he sends to Alice.

3. Alice computes the ciphertext:

   $$c=m^e\mathrm{mod}n$$

   and sends $c$ to Bob.

4. To decrypt, Bob uses his private key $d$ and computes:

   $$m=c^d\mathrm{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$.