To avoid repeating tragedies like Mary, Queen of Scots, cryptography needed something safer. Symmetric algorithms such as AES are powerful, but they leave one stubborn question unanswered: when a key has to be shared, can that key itself be delivered securely?
That question pushed cryptography toward a very different idea: not a better shared secret, but a system that does not require sending the decryption key at all.
From one-way functions to public-key cryptography
A one-way function is easy to compute in one direction, but hard to reverse. In complexity terms, for each input the output can be computed efficiently, while recovering the input from a random output is not feasible in polynomial time.
A simple example is modular arithmetic:
$ m \bmod n = a $
For instance:
$ 10 \bmod 3 = 1 $
If you know the input 10, getting the output 1 is trivial. But if all you know is the output 1, there is no unique way to recover the original input. Many different numbers could produce the same result.
At first glance, this seems promising for encryption. Let $m$ be the plaintext, $n$ a public key, and $a$ the ciphertext. But there is an obvious problem: the function is so one-way that nobody can reverse it—not even the intended recipient. That makes it secure, but useless.
So cryptography needed something more specific: a one-way trapdoor function.
A trapdoor function keeps the one-way property for everyone else, but includes a hidden shortcut—a “trapdoor”—that allows inversion if you possess special information.
In 1976, W. Diffie and M. Hellman proposed a remarkable vision. The receiver would generate two keys in advance. One key, built from a one-way trapdoor function, would be published as the public key. The other, kept secret, would serve as the private key and act as the trapdoor needed for decryption.
The sender could then encrypt a message using only the public key. Even if the ciphertext were intercepted, an attacker without the private key would be unable to decrypt it. Since the private key never leaves the receiver’s hands, the old risk of key distribution being intercepted disappears.
This was the beginning of public-key cryptography, also called asymmetric cryptography because encryption and decryption no longer use the same key.
It was a beautiful idea—but at the time, Diffie and Hellman did not yet have a suitable trapdoor function.
RSA: the trapdoor function that worked
That changed in 1978, when R. L. Rivest, A. Shamir, and L. Adleman published A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. In it, they described the algorithm now known as RSA.
RSA is built around modular exponentiation:
$ m^e \bmod n = c $
Here:
- $m$ is the plaintext,
- $c$ is the ciphertext,
- $e$ and $n$ form the public key.
Decryption uses another exponent:
$ c^d \bmod n = m $
That means $d$ is the trapdoor.
If we substitute the encryption formula into decryption, we get:
[ \begin{array}{c} \left ( m^e \bmod n \right)^d \bmod n = m \end{array} ]
[ \begin{array}{c} m^{ed} \bmod n = m \end{array} ]
This starts to look very much like Euler’s theorem.
Euler’s theorem says:
$ m^{\phi(n)} = 1 \pmod{n} $
Multiply both sides by $m$, and it becomes:
$ m^{\phi(n)+1} = m \pmod{n} $
So if we can make:
$ ed = \phi(n) + 1 $
then decryption will recover the original message. That suggests:
$ d = \frac{\phi(n) + 1}{e} $
Why Euler’s totient matters
Here $\phi(n)$ is Euler’s totient function: the number of positive integers less than or equal to $n$ that are coprime to $n$.
It can be written as:
[ \phi(n) = n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdot \ldots \cdot \left(1 - \frac{1}{p_m}\right) ]
where the $p_i$ are prime numbers, and $n$ has the prime factorization:
[ n = p_{1}^{k 1} p_{2}^{k 2} \ldots p_{m}^{k m} ]
Because prime factorization of a positive integer is unique, $\phi(n)$ is always an integer.
But $d$ is not automatically an integer.
For example, if $n = 34$ and $e = 15$, then:
$ d = \frac{\phi(n)+1}{e} = \frac{7}{3} $
That is meaningless for modular exponentiation.
So we go back to Euler’s theorem and use another property of modular arithmetic: if
$ m^{\phi(n)} = 1 \pmod{n} $
then multiplying that exponent by any positive integer $k$ still preserves the congruence:
$ (m^{\phi(n)})^k = 1 \pmod{n} $
This gives a more general expression:
$ d = \frac{k\phi(n) + 1}{e} $
Now we can choose $k$ so that $d$ becomes a positive integer.
Using the earlier example $n = 34, e = 15$:
[ \begin{matrix} k=1 & d=\frac{7}{3} & & k=4 & d=\frac{13}{3} \end{matrix} ] [ \begin{matrix} k=2 & d=\frac{11}{5} & & k=5 & d=\frac{27}{5} \end{matrix} ] [ \begin{matrix} k=3 & d=\frac{49}{15} & & k=6 & d=\frac{97}{15} \end{matrix} ] [ \begin{matrix} & & ... & & \end{matrix} ] [ \begin{matrix} & k=14 & & d=15 & \end{matrix} ] [ \begin{matrix} \end{matrix} ]
At $k=14$, we get $d=15$, which is valid. But $k=29$ would also give an integer $d$. In practice, the usual choice is the smallest positive integer that works.
A common way to find such values efficiently is the extended Euclidean algorithm. The following JavaScript snippet computes a suitable $k$ exactly as shown below:
function extendedEuclidean(a, e) { if (e === 0) { return [1, 0, a]; } const [x, y, gcd] = extendedEuclidean(e, a % e); return [y, x - Math.floor(a / e) * y, gcd]; } function findK(n, e) { const phiN = phi(n); let k = 1; while (true) { const [x, y, gcd] = extendedEuclidean(k * phiN + 1, e); const d = (k * phiN + 1) / e; if (d > 0 && Number.isInteger(d)) { return k; } k++; } return -1; // No valid k found } function phi(n) { let result = n; let i = 2; while (i * i <= n) { if (n % i === 0) { while (n % i === 0) { n /= i; } result -= result / i; } i++; } if (n > 1) { result -= result / n; } return result; } const n = 30; const e = 15; const k = findK(n, e); console.log(`k = ${k}`);
If the public key is public, why is the private key still safe?
RSA publishes both $e$ and $n$. So why can’t everyone simply compute $d$?
The answer is that computing $d$ requires knowing $\phi(n)$. And while $\phi(n)$ is easy to calculate for small values of $n$, it becomes extremely hard when $n$ is very large.
For example, try working with this value:
n = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
The receiver, however, is in a very different position. Since the receiver generates the key pair, they can choose the factors used to construct $n$ and therefore compute $\phi(n)$ directly.
RSA simplifies the setup further by choosing:
$ n = pq $
where $p$ and $q$ are two large prime numbers. Their product creates a large composite number that is difficult to factor. This becomes RSA’s second one-way step.
With this choice, the totient becomes much simpler:
$ \phi(n) = (p - 1)(q - 1) $
The RSA process in one flow
The receiver selects large primes $p$ and $q$, along with a suitable $e$.
Then:
- Compute $n = pq$.
- Compute $\phi(n) = (p-1)(q-1)$.
- Choose an appropriate $k$ and calculate the private key using
$ d = \frac{k\phi(n) + 1}{e} $
The pair $(e, n)$ is published as the public key.
When a sender wants to transmit a message $m$, they encrypt it as:
$ m^e \bmod n = c $
The receiver decrypts the ciphertext $c$ with the private key:
$ c^d \bmod n = m $
and recovers the original plaintext.
An attacker may intercept the ciphertext and know the public key, but without factoring $n$ into $p$ and $q$, they cannot compute $\phi(n)$, and without $\phi(n)$ they cannot derive the private key $d$.
RSA did not just introduce another encryption formula. It provided the practical trapdoor function that turned the public-key idea into something real: encryption with one key, decryption with another, and no need to transmit the secret key in the first place.