18 Oct 2026

If you are reading this, you have most likely heard about the RSA public-key cryptosystem.

The crux of the scheme is encrypting the secret to be sent with a key provided by the recipient, which everyone can use for that purpose, but only him or her can decrypt. The idea of a procedure that is easy to perform in one direction but computationally unfeasible to reverse was not new: see for instance the discrete logarithm problem present in other schemes such as the well-known Diffie-Hellman, which states that for a cyclic group $G = \langle g\rangle$, given $g$ and $g^k$ there is no easier way to find $k$ in general than to go over all the powers of $g$. RSA, in this case, exploits these ideas so that encryption enjoys the quality of being hard to break by someone who does not know the decryption key.

It, however, does not rely on the discrete logarithm, but in the difficulty of integer factorization, and the process of key generation reflects this:

  1. Pick two (very large) primes $p, q$, and let $n := pq$.

  2. Compute $\varphi(n) = (p - 1)(q - 1)$, Euler's totient function, and find $e$ coprime to $\varphi(n)$; this will be the public key used to encrypt:

    2.1. You may choose $e$ at random until it is coprime, since the probability for $n, m \in \ZZ$ to fulfill $\gcd(n, m) = 1$ is well known to be $6/\pi^2 > 60\%$.

  3. By means of the extended Euclidean algorithm, compute $d := e^{-1} \bmod \varphi(n)$, which will be the secret key used to decrypt.

  4. Publish $(e, n)$ and keep $d$ for yourself, as we have discussed.

Notice that knowing $e$ and $n$ is not enough to find $d$ easily, because that requires having $\varphi(n)$, which in turn can only be done quickly if $p$ and $q$ are known, and we know factoring takes time.

Then, we simply do $s^e \bmod n$ for encryption and $c^d \bmod n$ for decryption, which works because $$ c^d = s^{(ed)} = s^{(k\varphi(n) + 1)} = s\cdot\cancel{(s^\varphi(n))^k} \equiv s \pmod n. $$ The last cancellation is given by the Euler-Fermat theorem, which states that given $a, n \in \N$ with $\gcd(a, n) = 1$, then $a^{\varphi(n)}\equiv1\bmod n$, and its proof is quite easy to deduce from Lagrange's theorem and some basic group theory.

But does this actually work? Notice the assumption $\gcd(a, n) = 1$, it is fine for any $0 < s < n$ except $p$ and $q$, and since they cannot be known beforehand there is not a way to rule them out. Thankfully, in your crypto class you will be told that this is also satisfied in the previous two cases, yet at least in my case this claim was not proven.

My very good friend Kyryl Shyshko and I went for a walk today to Alcalá de Henares, and at some point we sat down and thought about this small problem for a while without having paper to write things down. Below is the proof we obtained:

Given $n := pq$ and $e, d$ output by the RSA key generation process, then for any $a \in \ZZ_n$, $$ (a^e)^d \equiv a \pmod n. \tag{$\star$} $$
As we have discussed, it suffices to show $(\star)$ when $a = p$ or $a = q$; without loss of generality assume the first case. We want to establish that $$ p^{ed} = p^{k\varphi(n) + 1} = p^{kpq - kp - kq + k + 1} \equiv p \pmod n, $$ that is, that $n = pq \mid p(p^{kpq - kp - kq + k} - 1)$, and equivalently $q \mid p^{kpq - kp - kq + k} - 1$, so it suffices to prove that $p^{kpq - kp - kq + k}\equiv 1 \bmod q$. Finally, using Fermat's little theorem $$ p^{kpq - kp - kq + k} \equiv (p^{kp})^q \cdot p^{-kp} \cdot p^k \cdot p^{-kq} \cancel{\equiv p^{kp} \cdot p^{-kp}} \cdot \cancel{p^k \cdot p^{-k}} \equiv 1 \pmod q, $$ as it was to be shown.