RSA Encryption: How Two Primes Lock the World's Secrets

Q: Who invented RSA?

Ron Rivest, Adi Shamir, and Leonard Adleman, working at MIT in 1977. Their paper described the first published practical public-key cryptosystem, building on Diffie and Hellman's 1976 paper that introduced the concept of public-key cryptography. Unknown to the public, a closely related system had been invented in 1973 by Clifford Cocks, working for the British intelligence agency GCHQ; that work was classified and not released until 1997, by which time RSA had already become the dominant cryptosystem in the world.

Q: How exactly does RSA work?

Choose two large primes p and q (typically each around 1024 bits long today). Compute n = pq and φ(n) = (p−1)(q−1). Choose a small odd integer e coprime to φ(n) (often e = 65537). Compute d as the multiplicative inverse of e modulo φ(n). The public key is (n, e); the private key is d. To encrypt a message m (encoded as a number less than n), compute c = m^e mod n. To decrypt, compute m = c^d mod n. The decryption works because of Euler's theorem: m^(ed) ≡ m^(1+kφ(n)) ≡ m (mod n).

Q: Why does the security depend on factoring?

Because anyone who can factor n = pq immediately knows φ(n) = (p−1)(q−1), and from φ(n) and the public e they can compute d as the inverse of e modulo φ(n). Once they know d, they can decrypt anything you encrypt. The whole security of RSA reduces to: can an attacker factor n? For n of around 2048 bits (the current standard), the best known classical factoring algorithms — the general number field sieve — would take longer than the age of the universe on the world's fastest classical computer. A sufficiently large quantum computer running Shor's algorithm could factor n in polynomial time, which is why 'post-quantum' cryptography is a major active field.

Q: How is RSA actually used in practice?

Almost never to encrypt the actual content of messages — that would be computationally too slow. Instead, RSA is used to encrypt a small symmetric key (e.g., for AES), and the symmetric key is used to encrypt the bulk data. Every HTTPS connection begins with a 'handshake' that uses RSA (or its descendants ECDSA, Ed25519) to negotiate a shared symmetric key, and then the rest of the session uses faster symmetric encryption. RSA also signs digital certificates, software updates, and SSH connections.

In 1976, Whitfield Diffie and Martin Hellman published a paper that proposed an extraordinary idea: a cryptographic system in which the encryption key is public and the decryption key is private. Anyone could encrypt a message to you using your public key, but only you, holding the private key, could decrypt it. The two keys are mathematically linked, but in a way that knowing the public key does not let anyone reconstruct the private key.

Diffie and Hellman did not show how to build such a system; they only argued it was possible in principle. A year later, in 1977, three MIT mathematicians — Ron Rivest, Adi Shamir, and Leonard Adleman — published the first practical construction. The system, named RSA after their initials, is based on the difficulty of factoring large integers and on Euler’s theorem from 18th-century number theory. Forty-seven years later, RSA still protects most of the encrypted traffic on the modern web. This article is about how it works.

The mathematics

The cryptographic ingredients are three classical results from number theory:

The Euclidean algorithm. Given two integers, you can quickly compute their greatest common divisor — and, with a small extension, find integers that express the gcd as a linear combination of the inputs.
Euler’s totient function $\varphi(n)$ . For $n$ a product of two distinct primes $p$ and $q$ , $\varphi(n) = (p-1)(q-1)$ .
Euler’s theorem. If $\gcd(a, n) = 1$ , then $a^{\varphi(n)} \equiv 1 \pmod{n}$ .

These three ingredients fit together to produce RSA.

The protocol

Key generation. Choose two large prime numbers $p$ and $q$ (typically each around $1024$ bits long, so each is roughly a $300$ -digit number). Compute $n = pq$ and $\varphi(n) = (p-1)(q-1)$ . Choose a small integer $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$ . (In practice, $e = 65537$ is almost always used.) Use the extended Euclidean algorithm to compute $d$ , the multiplicative inverse of $e$ modulo $\varphi(n)$ — that is, the integer $d$ with $ed \equiv 1 \pmod{\varphi(n)}$ .

Now publish the pair $(n, e)$ as your public key. Keep $d$ secret as your private key. Discard $p$ , $q$ , and $\varphi(n)$ — or, more carefully, store them as part of the private key for future operations, but never share them.

Encryption. Suppose someone wants to send you a message $m$ (encoded as an integer with $0 \leq m < n$ ). They compute

$c \;\equiv\; m^e \pmod{n}$

and send $c$ . This is the ciphertext.

Decryption. You receive $c$ and recover the message by computing

$m \;\equiv\; c^d \pmod{n}.$

That’s it. Two modular exponentiations, one with the public key, one with the private key.

Why decryption recovers the message

The reason $c^d \equiv m \pmod{n}$ is an application of Euler’s theorem.

By construction, $ed \equiv 1 \pmod{\varphi(n)}$ , which means $ed = 1 + k\varphi(n)$ for some non-negative integer $k$ . So

$c^d \;=\; (m^e)^d \;=\; m^{ed} \;=\; m^{1 + k\varphi(n)} \;=\; m \cdot \big(m^{\varphi(n)}\big)^k.$

If $\gcd(m, n) = 1$ , then by Euler’s theorem $m^{\varphi(n)} \equiv 1 \pmod{n}$ , so $c^d \equiv m \pmod{n}$ . (The cases where $m$ shares a factor with $n$ — i.e., $m$ is a multiple of $p$ or $q$ — require a slightly more careful argument using the Chinese Remainder Theorem, but the conclusion is the same.) Decryption recovers the original message exactly.

The whole protocol is built on this one equation. Encryption raises $m$ to the power $e$ ; decryption raises the result to the power $d$ . Because $ed \equiv 1 \pmod{\varphi(n)}$ , the two operations undo each other modulo $n$ .

Why it is secure

The security of RSA rests on a single hard problem: integer factorisation. If an attacker could factor $n = pq$ , they would immediately know $\varphi(n) = (p-1)(q-1)$ , and from $\varphi(n)$ and the public $e$ they could compute $d$ as the inverse of $e$ modulo $\varphi(n)$ . With $d$ , they can decrypt anything.

For $n$ of around $2048$ bits (the current standard), the best known classical factoring algorithm — the general number field sieve — would require approximately $10^{20}$ operations to factor. Even at modern computational speeds, this is many orders of magnitude beyond what any human or organisation has ever computed. The estimated time required, on the fastest classical supercomputer in existence, exceeds the age of the universe.

This is the entire security argument: there is no known efficient algorithm for factoring large semiprimes. Note carefully what is not proven: it has not been proven that no such algorithm exists. Factoring is not known to be NP-hard. It is plausible that a clever new algorithm could be discovered tomorrow that factors numbers in polynomial time, in which case RSA would collapse overnight. But despite intensive search since the 1970s, no one has found such an algorithm.

What is known to break RSA is a sufficiently large quantum computer running Shor’s algorithm (Peter Shor, 1994). Shor’s algorithm factors integers in time polynomial in the number of bits — exponentially faster than any classical algorithm. Sufficiently large quantum computers do not yet exist, but the prospect of their development has driven a global research program on post-quantum cryptography, which seeks to replace RSA with cryptosystems based on hard problems that quantum computers cannot solve efficiently. As of 2024, several post-quantum standards have been finalised by NIST, and the transition away from RSA is beginning.

Where RSA actually lives

In practice, RSA is rarely used to encrypt the bulk of a message directly. Modular exponentiation with $2048$ -bit numbers is too slow for streaming video, downloading software, or sending a long email. Instead, RSA is used in a hybrid scheme: the sender chooses a fresh symmetric key (for a fast symmetric cipher like AES), encrypts that key with RSA, and uses AES to encrypt the actual data. The recipient decrypts the symmetric key using RSA, then uses AES to decrypt the bulk content.

Beyond encryption, RSA is used for:

Digital signatures. The signer computes $s = h(m)^d \pmod{n}$ where $h(m)$ is the hash of message $m$ and $d$ is their private key. Anyone can verify by checking that $s^e \equiv h(m) \pmod{n}$ . Only someone with $d$ could have produced $s$ , so the signature authenticates the signer.

Certificate authorities. Every HTTPS certificate is signed by a CA whose RSA (or ECDSA) signature attests to the binding between a domain name and a public key. Browsers come with built-in lists of trusted CA public keys, and the entire web’s trust infrastructure rests on these signatures.

SSH and Git. Remote login (SSH) and source code management (Git over SSH) use RSA-like cryptographic key pairs to authenticate users without passwords.

Software distribution. Linux package managers (apt, yum), application stores, and operating system update mechanisms verify signatures on downloaded software to ensure they have not been tampered with.

The Cocks anticipation

A footnote of considerable historical interest: in 1973 — four years before Rivest, Shamir, and Adleman — the same essential idea was discovered by Clifford Cocks, a young mathematician working at GCHQ, the British signals intelligence agency. Cocks’s note was classified and remained secret until 1997, by which time RSA was already the dominant public-key cryptosystem in the world. He received belated public credit but no commercial benefit; the intellectual influence of his work, having been hidden, was zero. The case is one of the most striking examples of how classified research can be paralleled (and even pre-empted) by open academic publication, and the standard reference still names the system RSA after Rivest, Shamir, and Adleman.

Two centuries of mathematics into one protocol

What RSA built is a strikingly tight stack of mathematics from the 18th and 19th centuries:

Euclidean algorithm (Euclid, c. 300 BCE): used for key generation and computing inverses.
Euler’s totient function (Euler, 1763): determines the structure of $(\mathbb{Z}/n\mathbb{Z})^\times$ .
Euler’s theorem (Euler, 1763): the reason decryption works.
Fast modular exponentiation (folklore, classical): the reason encryption is fast.
Difficulty of factoring (folklore, empirical): the reason security holds.

Each of these ingredients was developed long before computers existed, for reasons unrelated to communications security. Euclid was studying geometry. Euler was studying the structure of integers modulo $n$ . None of them anticipated that two and a half centuries later, their work would be the foundation of a global infrastructure for secure communication.

This is one of the cleanest examples of how pure mathematics produces unexpected applications. The mathematicians who developed the underlying theory had no inkling of cryptography. The cryptographers who built RSA used the theory because it was there, ready to be applied. The forty-seven years since 1977 have demonstrated that the theory was strong enough to support an entire civilisation’s secure communications.

RSA may eventually fall — to quantum computers, to a yet-undiscovered classical factoring algorithm, or to side-channel attacks that exploit implementation details rather than the underlying mathematics. But what it accomplished is permanent. It showed that public-key cryptography was practical, and it set the template that every subsequent cryptosystem has followed: take a hard mathematical problem, build a protocol whose security depends on it, and ship it to the world. From two primes, multiplied together and made public, an entire ecosystem of digital trust was born.

Frequently asked

Who invented RSA?

Ron Rivest, Adi Shamir, and Leonard Adleman, working at MIT in 1977. Their paper described the first published practical public-key cryptosystem, building on Diffie and Hellman's 1976 paper that introduced the concept of public-key cryptography. Unknown to the public, a closely related system had been invented in 1973 by Clifford Cocks, working for the British intelligence agency GCHQ; that work was classified and not released until 1997, by which time RSA had already become the dominant cryptosystem in the world.

How exactly does RSA work?

Choose two large primes p and q (typically each around 1024 bits long today). Compute n = pq and φ(n) = (p−1)(q−1). Choose a small odd integer e coprime to φ(n) (often e = 65537). Compute d as the multiplicative inverse of e modulo φ(n). The public key is (n, e); the private key is d. To encrypt a message m (encoded as a number less than n), compute c = m^e mod n. To decrypt, compute m = c^d mod n. The decryption works because of Euler's theorem: m^(ed) ≡ m^(1+kφ(n)) ≡ m (mod n).

Why does the security depend on factoring?

Because anyone who can factor n = pq immediately knows φ(n) = (p−1)(q−1), and from φ(n) and the public e they can compute d as the inverse of e modulo φ(n). Once they know d, they can decrypt anything you encrypt. The whole security of RSA reduces to: can an attacker factor n? For n of around 2048 bits (the current standard), the best known classical factoring algorithms — the general number field sieve — would take longer than the age of the universe on the world's fastest classical computer. A sufficiently large quantum computer running Shor's algorithm could factor n in polynomial time, which is why 'post-quantum' cryptography is a major active field.

How is RSA actually used in practice?

Almost never to encrypt the actual content of messages — that would be computationally too slow. Instead, RSA is used to encrypt a small symmetric key (e.g., for AES), and the symmetric key is used to encrypt the bulk data. Every HTTPS connection begins with a 'handshake' that uses RSA (or its descendants ECDSA, Ed25519) to negotiate a shared symmetric key, and then the rest of the session uses faster symmetric encryption. RSA also signs digital certificates, software updates, and SSH connections.

RSA Encryption: How Two Primes Lock the World's Secrets

The mathematics

The protocol

Why decryption recovers the message

Why it is secure

Where RSA actually lives

The Cocks anticipation

Two centuries of mathematics into one protocol

Frequently asked

Continue reading

Euler's Totient Function: Counting the Numbers That Share Nothing With n

Perfect Numbers and Mersenne Primes: A Twenty-Three-Centuries-Old Hunt

Modular Arithmetic: The Mathematics of Clocks and Cryptography

Keep exploring