An Interactive Guide to RSA

RSA is a public-key encryption algorithm. It lets Alice publish a key that anyone can use to encrypt a message to her, while only she can decrypt it. The same keys work in reverse to prove who sent a message, which is how RSA is also used for digital signatures. Designed by Rivest, Shamir, and Adleman in 1977, it has since been used in TLS, SSH, PGP, and S/MIME, and remains widely deployed today.

# Trapdoor functions

Every public-key scheme rests on a trapdoor function. A trapdoor function is easy to compute in one direction and hard to reverse without a specific secret piece of information. RSA is built on multiplication.

Multiplying 2 large primes together takes a fraction of a second. Given only the product, recovering the original 2 primes is believed to be infeasible for large enough numbers. There is no known polynomial-time algorithm for factoring integers on a classical computer. This asymmetry is the entire foundation of RSA’s security.

# Key generation

To set up RSA, we choose 2 distinct primes $p$ and $q$. Their product is $n = p \cdot q$. The number $n$ is the modulus. Everything in RSA happens mod $n$.

Not any 2 primes will do. They must be distinct. If $p = q$, then $n = p^2$ and its square root is $p$. Factoring $n$ then becomes a matter of taking a square root instead of searching for 2 independent factors.

They also should not be close to each other. If $p$ and $q$ are near $\sqrt{n}$, Fermat’s factorization method finds them almost immediately. It searches for $a$ such that $a^2 - n$ is a perfect square. In practice, $p$ and $q$ are also chosen to be roughly the same bit length and large enough that trial division and the fastest known factoring algorithms are infeasible. That is why real keys use primes hundreds of digits long rather than the small ones below.

$p$ and $q$ are never published. Only their product $n$ is. Anyone who recovers $p$ and $q$ from $n$ can rebuild the entire private key, so the 2 primes are hidden below by default. Click the eye icon to reveal them.

Next, compute Euler’s totient, $\phi(n) = (p - 1)(q - 1)$. The totient counts how many integers from 1 to $n$ share no common factor with $n$. Because $p$ and $q$ are prime, the count is exactly $(p-1)(q-1)$. Like $p$ and $q$ themselves, $\phi(n)$ stays secret. Anyone who learns it can compute $d$ directly from the public $e$, without ever factoring $n$.

Choose a public exponent $e$ that is between 2 and $\phi(n)$ and coprime to $\phi(n)$, meaning $\gcd(e, \phi(n)) = 1$. The most common choice in practice is 65537, a Fermat prime that makes exponentiation fast. For the toy examples below, smaller values are used.

Finally, compute the private exponent $d$ such that $e \cdot d \equiv 1 \bmod \phi(n)$. This is the modular inverse of $e$ modulo $\phi(n)$, found with the extended Euclidean algorithm. The pair $(n, e)$ is the public key. The value $d$ is the private key and must stay secret.

The private exponent $d$ is hidden by default too, using the same toggle as $p$ and $q$ above. Reveal it and watch how it feeds into decryption below.

# Encrypting a message

To send Alice an encrypted message, Bob needs only Alice’s public key $(n, e)$. He represents the message as an integer $m$ in the range $[0, n)$ and computes the ciphertext.

The exponentiation can be done efficiently with square-and-multiply, even for large numbers. The result $c$ is safe to send over any channel. Without the private exponent $d$, recovering $m$ from $c$ requires breaking the factoring problem.

# Decrypting

Alice receives $c$ and applies her private exponent.

$m = c^d \bmod n$

It is not obvious why raising $c$ to the power $d$ should undo raising $m$ to the power $e$. The reason comes from a result in number theory called Euler’s theorem. It says that for any $m$ coprime to $n$, raising $m$ to the power $\phi(n)$ always lands back on 1 modulo $n$, no matter how large $m$ or $n$ is. This is what makes $\phi(n)$ special. It is the exponent at which powers of $m$ start repeating modulo $n$.

Remember that $e$ and $d$ were not picked independently. $d$ was computed specifically so that $e \cdot d \equiv 1 \bmod \phi(n)$. In plain terms, the product $e \cdot d$ is exactly 1 more than some whole multiple of $\phi(n)$. Write that multiple as $k$, so $e \cdot d = 1 + k \cdot \phi(n)$.

Now trace what decryption actually computes. Substituting $c = m^e \bmod n$ into $c^d$ gives the following chain.

The last step splits the exponent into 2 pieces, an $m$ left over and $\phi(n)$ repeated $k$ times. Euler’s theorem says $m^{\phi(n)} \equiv 1 \bmod n$. So the entire term $(m^{\phi(n)})^k$ is just 1 raised to a power, still 1. That leaves $m \cdot 1 = m$. Encryption and decryption cancel out precisely because $e$ and $d$ were chosen to multiply to 1 modulo $\phi(n)$, the exact cycle length Euler’s theorem guarantees.

# Proving who sent it

Encryption alone does not prove who sent a message. Anyone can grab Alice’s public key and send her a message. Bob has no way to prove a message came from him rather than an impostor. RSA fixes this by running the algorithm with the roles reversed.

To sign a message, Bob uses his own private exponent $d$, not Alice’s, and computes $s = m^d \bmod n$. Only Bob can produce this value, since only he holds $d$.

Anyone holding Bob’s public key $(n, e)$ can then check the signature by computing $m' = s^e \bmod n$. If $m'$ matches the original message $m$, the signature is genuine. This works because $s^e = (m^d)^e = m^{de} = m$, the same cancellation from Euler’s theorem used in decryption, just applied with the exponents swapped.

Encryption and signing use the same trapdoor in opposite directions. To encrypt, Bob uses Alice’s public key so only Alice’s private key can undo it. To sign, Bob uses his own private key so anyone with his public key can confirm it came from him.

In practice, RSA signatures are not computed over the raw message. The message is hashed first, typically with SHA-256, and only the hash is signed. This keeps the signed value shorter than $n$ and avoids structural weaknesses that can appear when signing raw plaintext directly.

# Why it is hard to break

An eavesdropper watching the channel sees the public key $(n, e)$ and the ciphertext $c$. To recover $m$ they need $d$. To compute $d$ they need $\phi(n) = (p - 1)(q - 1)$. To compute $\phi(n)$ they need $p$ and $q$. And to find $p$ and $q$ they must factor $n$. Knowing $e$ does not shortcut any of this. Computing $\phi(n)$ from $n$ alone is believed to be exactly as hard as factoring $n$, since $e$ is only required to be coprime to $\phi(n)$, not derived from it.

For small $n$ like in the demo, trial division finds the factors instantly. For a 2048-bit $n$, the best known classical algorithm is the General Number Field Sieve. Its runtime grows sub-exponentially but fast enough to be completely out of reach at proper key sizes. A 2048-bit RSA key is considered secure against classical computers through at least the 2030s. 4096-bit keys are used when longer-term security is needed.

Quantum computers change the picture. Shor’s algorithm factors integers in polynomial time on a quantum computer, which would break RSA entirely. This is why post-quantum cryptography is an active area of standardization. NIST finalized its first post-quantum standards in 2024, based on lattice problems and hash functions rather than integer factoring.

RSA itself is not used to encrypt bulk data directly. The modulus size limits what can be encrypted, and modular exponentiation is slow compared to symmetric ciphers like AES. In practice, RSA encrypts only a symmetric key. That key then protects the actual message. This hybrid approach combines RSA’s convenience (no shared secret needed upfront) with the speed of symmetric encryption.