RSA from Scratch — The Number Theory Behind Public Keys

RSA lets you publish a key that locks but cannot unlock. This builds it from congruence arithmetic up: key generation, the two modular exponentiations, and a line-by-line proof from Euler's theorem of why the message comes back — then a worked example small enough to check by hand, why factoring is the security assumption, and why textbook RSA must never be shipped without padding.

"Rivest

The problem: agreeing on a secret you never shared

For most of history, encryption meant both parties knew the same secret. You and I agree on a key in advance, I scramble a message with it, you unscramble it with the same key. This is symmetric encryption, and it is fast and well understood — but it has a bootstrapping problem that looks unsolvable. To talk securely, we must first meet securely to exchange the key. On the internet, where you want to buy something from a shop you have never contacted before, there is no such prior meeting.

Public-key cryptography breaks that circle with an idea that sounds impossible on first hearing: a key that can lock but not unlock. Everyone gets a public key they publish to the world and a private key they never reveal. Anyone can use your public key to encrypt a message to you; only your private key can decrypt it. No prior meeting, no shared secret.

Rivest, Shamir and Adleman published the first practical construction of this in 1978, and RSA is still the name on it. It is built out of ordinary integer arithmetic — no exotic mathematics — and this article assembles it from the ground up: the arithmetic you need, the key generation, the two operations, a proof that they undo each other, a small worked example, and the reasons the textbook version must be padded before it touches real traffic. (For where RSA sits among the other tools, see Cryptography from Scratch.)

Prerequisite: arithmetic on a clock

Everything in RSA happens modulo some integer $n$, which means: do the ordinary arithmetic, divide by $n$, and keep only the remainder. Clock arithmetic is the familiar case with $n = 12$: four hours after ten o'clock is two o'clock, because $14$ divided by $12$ leaves remainder $2$.

The notation for "$a$ and $b$ leave the same remainder when divided by $n$" is

$$a \equiv b \pmod{n}$$

read "$a$ is congruent to $b$ modulo $n$." In words: if you only look at the remainder after dividing by $n$, you cannot tell $a$ and $b$ apart. So $14 \equiv 2 \pmod{12}$. Three facts about congruences are all we need, and all three are easy to believe:

1. Addition and multiplication survive. If $a \equiv a'$ and $b \equiv b'$, then $a + b \equiv a' + b'$ and $ab \equiv a'b'$. You may reduce mod $n$ at any point in a calculation without changing the answer — which is what makes working with enormous numbers tractable at all.
2. Exponentiation is therefore cheap. $a^{2k} = (a^k)^2$, so you can square repeatedly and reduce mod $n$ after every step. Computing $a^{2048} \bmod n$ takes about 11 squarings, not 2048 multiplications. This is modular exponentiation by squaring, and it is why RSA is usable with 2048-bit numbers.
3. Division is the special one. There is no general "divide by $b$." What sometimes exists is a modular inverse: a number $b^{-1}$ with $b \cdot b^{-1} \equiv 1 \pmod{n}$. It exists exactly when $b$ and $n$ share no common factor besides 1, and the extended Euclidean algorithm finds it quickly.

One more object. Euler's totient function $\varphi(n)$ counts how many integers in $1, 2, \dots, n$ share no common factor with $n$. For a prime $p$, every one of $1, \dots, p-1$ qualifies, so $\varphi(p) = p - 1$. For a product of two distinct primes — the only case RSA needs —

$$\varphi(pq) = (p-1)(q-1)$$

which you can see by counting what gets excluded from $1, \dots, pq$: the $q$ multiples of $p$, the $p$ multiples of $q$, with $pq$ itself double-counted, giving $pq - q - p + 1 = (p-1)(q-1)$. In words: strike out the multiples of $p$ and the multiples of $q$, and exactly $(p-1)(q-1)$ numbers are left.

The asymmetry RSA is built on

A public-key scheme needs an operation that is easy to do and hard to undo. RSA's is multiplication of primes.

Multiplying two 1024-bit primes together takes a computer no measurable time. Going the other way — given only the 2048-bit product, recover the two primes — is integer factorization, and no efficient algorithm for it is known. The best published classical method, the general number field sieve, runs in sub-exponential but still hopeless time at that size: the largest RSA modulus factored in public, the 829-bit RSA-250, took about 2700 core-years in 2020. 2048 bits is far beyond that.

So: the product is public, the factors are private. The rest of RSA is machinery for turning that gap into an encryption scheme.

Key generation

Five steps, each of which we now have the tools for.

1. Pick two large distinct primes $p$ and $q$. In practice, generate random odd numbers of the right size and test them for primality (Miller–Rabin) until two pass. For a 2048-bit key, each is about 1024 bits.

2. Compute the modulus $n = pq$. This number is public. Its size is what people mean by "a 2048-bit RSA key."

3. Compute $\varphi(n) = (p-1)(q-1)$. This number must stay secret — and note that anyone who can factor $n$ can compute it, which is the whole crux of the security.

4. Choose the public exponent $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$. The coprimality requirement is not aesthetic: it is exactly the condition for step 5 to have a solution. Nearly all real keys use $e = 65537 = 2^{16} + 1$, which is prime, and whose binary form 10000000000000001 has only two 1-bits — so encryption costs just 17 squarings and one multiply.

5. Compute the private exponent $d$ as the modular inverse of $e$:

$$d \equiv e^{-1} \pmod{\varphi(n)}, \quad\text{equivalently}\quad ed \equiv 1 \pmod{\varphi(n)}$$

Unpacking the "equivalently": $d$ is the number that, multiplied by $e$, lands exactly one step past a multiple of $\varphi(n)$. Written without congruences, there is some integer $k$ with $ed = 1 + k\varphi(n)$ — and it is this form we will need in the proof. The extended Euclidean algorithm produces $d$ from $e$ and $\varphi(n)$ in microseconds. In words, $d$ is the exponent that exactly cancels out raising to the $e$.

The result is two keys:

• Public key $(n, e)$ — publish it anywhere.
• Private key $(n, d)$ — never transmit it. And discard or protect $p$, $q$, $\varphi(n)$: any one of them hands over $d$.

Encryption and decryption

Represent the message as an integer $m$ with $0 \le m < n$. (How you get from bytes to an integer is where padding lives; that comes later.) Then both directions are a single modular exponentiation:

$$\textbf{encrypt:}\quad c \equiv m^{e} \pmod{n}$$

$$\textbf{decrypt:}\quad m \equiv c^{d} \pmod{n}$$

That is the entire algorithm. In words: encryption and decryption are the same operation — raise to a power, keep the remainder mod $n$ — and only the exponent differs. Raise to the public exponent to lock, raise to the private exponent to unlock, and reduce mod $n$ throughout. The asymmetry between the two operations is nothing but the asymmetry between knowing $d$ and not knowing it.

The obvious question is why the second undoes the first.

Why the message comes back

The engine is a theorem of Euler, stated here and then used once.

Euler's theorem. If $\gcd(a, n) = 1$, then $a^{\varphi(n)} \equiv 1 \pmod{n}$.

In words: raise any number coprime to $n$ to the power $\varphi(n)$, and modulo $n$ you land exactly on 1. (Fermat's little theorem, $a^{p-1} \equiv 1 \pmod p$ for prime $p$, is the special case $n = p$.) What this gives us is a way to make exponents wrap around: multiplying by $a^{\varphi(n)}$ changes nothing mod $n$, so exponents effectively live mod $\varphi(n)$. That is precisely why $d$ was defined mod $\varphi(n)$ and not mod $n$.

Now decrypt, one line at a time. Start from the ciphertext and substitute:

$$c^{d} \equiv (m^{e})^{d} \pmod{n}$$

Because $c \equiv m^e$ by definition of encryption.

$$(m^{e})^{d} = m^{ed}$$

Because a power of a power multiplies the exponents — no modular arithmetic involved yet.

$$m^{ed} = m^{1 + k\varphi(n)}$$

Because step 5 of key generation gave us exactly $ed = 1 + k\varphi(n)$ for some integer $k$. This is the step the whole construction was engineered to make available.

$$m^{1 + k\varphi(n)} = m^{1} \cdot \left(m^{\varphi(n)}\right)^{k}$$

Because $x^{a+b} = x^a x^b$, and then $x^{k\varphi(n)} = (x^{\varphi(n)})^k$ — still just exponent rules.

$$m \cdot \left(m^{\varphi(n)}\right)^{k} \equiv m \cdot 1^{k} \pmod{n}$$

Because Euler's theorem replaces $m^{\varphi(n)}$ with 1, provided $\gcd(m, n) = 1$.

$$m \cdot 1^{k} = m$$

Because 1 to any power is 1. So $c^d \equiv m \pmod n$, and since we required $0 \le m < n$, the residue we get back is $m$ rather than something congruent to it. The message returns. In words, the six lines say: raise to $e$, then to $d$, and the exponent goes $k$ full laps of $\varphi(n)$ and lands back at 1.

Notice what did the work: the whole scheme is an exercise in choosing $d$ so that $ed$ is one more than a multiple of $\varphi(n)$, because that is the exponent Euler's theorem collapses. And $\varphi(n)$ is computable from $p$ and $q$ — which is why the factors must stay secret.

One honest caveat, since the proof above has a gap. Euler's theorem needed $\gcd(m, n) = 1$, and a message could in principle be a multiple of $p$ or $q$. RSA does still decrypt correctly in those cases; the argument uses the Chinese Remainder Theorem to handle each prime factor separately rather than Euler's theorem on $n$ directly. For random messages the odds of hitting such an $m$ are about $1/p + 1/q$ — astronomically small at real key sizes, and irrelevant in practice because padding randomizes $m$ anyway. The gap is worth knowing about so you are not surprised when a rigorous treatment spends a page on it.

A worked example you can check by hand

Real keys use 617-digit numbers. Take tiny primes instead so every step is verifiable with a pencil.

Key generation. Let $p = 3$, $q = 11$.

• $n = pq = 33$
• $\varphi(n) = (3-1)(11-1) = 2 \times 10 = 20$
• Choose $e = 3$. Check $\gcd(3, 20) = 1$. ✓
• Find $d$ with $3d \equiv 1 \pmod{20}$. Try $d = 7$: $3 \times 7 = 21 = 1 + 1 \times 20$. ✓

So the public key is $(33, 3)$ and the private key is $(33, 7)$. Note $ed = 21 = 1 + k\varphi(n)$ with $k = 1$ — the exact form the proof needed.

Encrypt $m = 5$.

$$c \equiv 5^{3} = 125 \pmod{33}$$

$125 = 3 \times 33 + 26$, so $c = 26$. In words, the ciphertext is nothing more than "5 multiplied by itself three times, remainder after dividing by 33."

Decrypt. We need $26^{7} \bmod 33$, computed by repeated squaring, reducing at every step:

• $26^{2} = 676 = 20 \times 33 + 16 \implies 26^2 \equiv 16$
• $26^{4} \equiv 16^{2} = 256 = 7 \times 33 + 25 \implies 26^4 \equiv 25$
• $26^{6} = 26^{4} \cdot 26^{2} \equiv 25 \times 16 = 400 = 12 \times 33 + 4 \implies 26^6 \equiv 4$
• $26^{7} = 26^{6} \cdot 26 \equiv 4 \times 26 = 104 = 3 \times 33 + 5 \implies 26^7 \equiv 5$

We get 5 back. Every number here was small enough to check, and the same six lines with 2048-bit integers are what your browser runs.

Two things this toy example also makes visible. First, $m$ must be less than $n$: with $n = 33$ there are only 33 possible messages, and $m = 40$ would come back as $40 - 33 = 7$. Second, the encryption is deterministic — 5 always maps to 26 — and with only 33 possibilities an attacker simply encrypts all of them and looks up the answer. That is not an artifact of the small size, as the next-but-one section explains.

Why it is hard to break

The attacker sees $(n, e)$ and $c$ and wants $m$. Consider the routes.

Factor $n$. With $p$ and $q$ in hand, compute $\varphi(n) = (p-1)(q-1)$, run the extended Euclidean algorithm to get $d$, decrypt. This is the primary attack and it is why RSA's security rests on the hardness of factoring. At 2048 bits it is out of reach of all known classical methods — the general number field sieve's cost grows sub-exponentially in the number of digits, and the 829-bit public record already cost thousands of core-years.

Compute $\varphi(n)$ some other way. No help: knowing both $n = pq$ and $\varphi(n) = (p-1)(q-1) = n - p - q + 1$ gives you $p + q$, and from a sum and a product you recover $p$ and $q$ with the quadratic formula. Finding $\varphi(n)$ is equivalent to factoring.

Take the $e$-th root of $c$ directly. Over the integers, $e$-th roots are easy. Modulo a composite $n$ whose factorization you do not know, the "RSA problem" of computing $c^{1/e} \bmod n$ has no known efficient solution. Worth being precise, though: it is not proven that breaking RSA is as hard as factoring. Factoring breaks RSA; whether every attack on RSA implies a factoring algorithm is an open question.

Brute-force $m$. Encrypt candidate messages and compare — devastating whenever the message space is small, and the reason padding exists.

Practical consequences: 1024-bit keys are deprecated, 2048 bits is the current floor, and 3072 bits corresponds to roughly the 128-bit security level in NIST's guidance. And the whole edifice has an expiry date: Shor's algorithm factors integers in polynomial time on a sufficiently large quantum computer, which is why standards bodies are migrating to post-quantum schemes. Nothing about the classical analysis above protects data that an adversary can record now and decrypt later.

Textbook RSA is not RSA you can ship

Everything up to here is what cryptographers call textbook RSA, and deploying it as written is a serious vulnerability. The mathematics is correct; the scheme built directly on it is broken. Three reasons, each fatal on its own.

It is deterministic. The same plaintext always produces the same ciphertext under the same key. So an attacker who can guess the message space wins without any number theory: encrypt every candidate with the public key — which is public — and match. A yes/no field, a credit card number, a room number, an AES key from a weak generator: all recoverable by table lookup. Formally, textbook RSA fails IND-CPA security, and the fix must involve randomness.

It is malleable. Because exponentiation distributes over multiplication,

$$c_1 c_2 \equiv m_1^{e} m_2^{e} = (m_1 m_2)^{e} \pmod{n}$$

In words: multiply two ciphertexts and you get the ciphertext of the product of their plaintexts. So an attacker who cannot read a ciphertext can still multiply it by $2^e$ and hand you something that decrypts to $2m$. Any protocol that treats "it decrypted" as "it is authentic" is exploitable.

Small exponents leak small messages. If $m^e < n$ — easy to arrange with $e = 3$ and a short message — then $c = m^e$ holds over the integers, with no wrap-around at all. Take the ordinary integer cube root of $c$ and read the message. No factoring required.

The cure is padding: a standardized transformation that pads the message out to nearly the full width of $n$, mixes in fresh random bytes, and adds structure the decryptor can verify.

• For encryption, use RSAES-OAEP (Optimal Asymmetric Encryption Padding). It is randomized, so the same plaintext encrypts differently every time, and it destroys the multiplicative structure.
• For signatures, use RSASSA-PSS.
• The older PKCS#1 v1.5 encryption padding is where Bleichenbacher's 1998 padding-oracle attack lives: a server that distinguishes "bad padding" from "bad message" in its error responses can be queried into decrypting a ciphertext it never had the plaintext for. Variants of this bug have been rediscovered in TLS stacks repeatedly (ROBOT, 2017). Treat v1.5 as legacy-compatibility only.

There is a further reason RSA never encrypts your actual data: $m < n$ caps a 2048-bit key at 256 bytes minus padding overhead, and modular exponentiation is orders of magnitude slower than a symmetric cipher. Real systems are hybrid — RSA (when used at all) encrypts a short symmetric key, and AES encrypts the payload. In modern TLS 1.3 even that role is gone: key establishment moved to ephemeral Diffie–Hellman for forward secrecy, and RSA survives mainly as a signature algorithm on certificates. (See TLS from Scratch for how those pieces fit.)

Signatures: the same two exponents, swapped

Because $e$ and $d$ are inverses, applying them in the other order also round-trips: $(m^d)^e \equiv m$. That gives a digital signature. The signer, who alone holds $d$, produces

$$s \equiv H(m)^{d} \pmod{n}$$

and anyone verifies by checking

$$s^{e} \stackrel{?}{\equiv} H(m) \pmod{n}$$

using the public key. Only the holder of $d$ could have produced an $s$ that passes, so the signature binds the message to that key. Read together, the two equations say, in words: the signer locks the hash with the private exponent, and the verifier unlocks it with the public exponent and checks it against a hash computed locally.

Note the hash $H$. You sign a digest, not the message, for two reasons: the message is almost always longer than $n$ allows, and signing raw values inherits the malleability above — an attacker can multiply two signatures together to forge a signature on the product. A collision-resistant hash plus PSS padding closes both. This is the operation that actually matters for the modern web: every certificate chain your browser validates is a stack of these verifications.

Pitfalls

Never implement it yourself. This is the standard advice and it is correct. Everything below is a real class of break in deployed RSA, and library authors have spent decades on each.

Standards use $\lambda(n)$, not $\varphi(n)$. FIPS and PKCS#1 define $d$ modulo $\lambda(n) = \operatorname{lcm}(p-1, q-1)$, which divides $\varphi(n)$. The proof still works and the resulting $d$ is smaller, hence faster. If you compare a library's $d$ against one you derived from $\varphi(n)$ they may differ while both being valid — the exponents are congruent mod $\lambda(n)$.

Weak randomness is catastrophic, and it composes across keys. If a bad entropy source makes two independently generated keys share a prime, then $\gcd(n_1, n_2)$ reveals it, and both keys fall — to a computation costing nothing. A 2012 survey ("Mining your Ps and Qs") found tens of thousands of live TLS hosts broken exactly this way, mostly embedded devices generating keys at first boot before any entropy existed.

Timing is a side channel. Naive modular exponentiation takes a different amount of time depending on the bits of $d$, and that has been used to extract private keys over a network. Real implementations use blinding — multiply by a random factor before exponentiating and divide it out after — plus constant-time code paths.

Fault attacks on the CRT speedup. Decryption is usually done via the Chinese Remainder Theorem, computing mod $p$ and mod $q$ separately for about a 4× speedup. If a single computation error corrupts one of the two halves, comparing the faulty signature with a correct one reveals $p$ by a GCD. Libraries defend by verifying the result before releasing it.

Small private exponents are breakable. Choosing a tiny $d$ to speed up decryption invites Wiener's attack, which recovers $d$ efficiently when $d$ is roughly below $n^{1/4}$. Small public exponents are fine — $e = 65537$ is standard — but $d$ must be large.

Padding must be checked in constant time, and errors must not be distinguishable. This is the Bleichenbacher lesson: the vulnerability was never in the arithmetic, it was in the error message.

How it is used in practice

Almost nobody writes RSA arithmetic on the job. What you actually touch is key generation, key formats, and the choice of padding — and that is where the accidents happen.

When it comes up. Backend and infrastructure engineers meet RSA when generating a CSR for a TLS certificate, issuing SSH keys, or choosing a JWT signing algorithm. Security reviewers meet it when inventorying key sizes and padding modes across existing systems.

The commands you type and the names they print.

• Generate a key: openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:3072 -out key.pem. The public exponent defaults to 65537.
• Inspect it: openssl pkey -in key.pem -text -noout lists modulus ($n$), publicExponent ($e$), privateExponent ($d$), prime1/prime2 ($p, q$), plus exponent1/exponent2/coefficient — the precomputed values for the CRT speedup from the pitfalls section. A private key file carries not just $d$ but $p$ and $q$ outright, which is why a leaked one is game over.
• JWT: RS256 in the alg header means a PKCS#1 v1.5 signature, PS256 means PSS. Both are verified with a public key, unlike HS256, which uses a shared secret.
• Application code: in Python's cryptography, you call it with the padding spelled out, e.g. padding.OAEP(mgf=padding.MGF1(hashes.SHA256()), algorithm=hashes.SHA256(), label=None).

Mistakes that bite people who don't know.

• Java's Cipher.getInstance("RSA") without a padding spec gives you PKCS#1 v1.5 (the default provider's choice). New code should name it explicitly, e.g. "RSA/ECB/OAEPWithSHA-256AndMGF1Padding". The "ECB" is a naming artifact; it means nothing as a block mode for RSA.
• JWT algorithm confusion. If the verifier trusts the token's own alg, an attacker can make it use the RS256 public key as an HS256 HMAC secret and forge tokens. Pin the allowed algorithms at verification time.
• In SSH, ssh-rsa names a SHA-1 signature scheme, not just a key type. Since OpenSSH 8.8 that SHA-1 signature is disabled by default, so an RSA key can stop connecting to old servers that don't support rsa-sha2-256/rsa-sha2-512. The key is not broken.
• Hitting the length limit by encrypting data directly. A 2048-bit key caps out at 256 bytes, padding included. Chunking a file and RSA-encrypting each piece is the wrong design; wrap a symmetric key instead, as in the hybrid scheme above.

Questions you get asked in interviews and design reviews, and how to answer.

• "What does RSA do in TLS 1.3?" → It no longer does key exchange. It signs certificates, and the server uses it to prove possession of its private key during the handshake (CertificateVerify).
• "Why not encrypt data with RSA directly?" → The $m < n$ length cap and the speed. RSA only wraps a symmetric key.
• "What is wrong with textbook RSA?" → Deterministic, malleable, weak with small exponents — and OAEP/PSS is the fix.
• "What would you pick for a new key?" → If RSA, 2048 bits or more with OAEP/PSS; for signatures alone, also consider ECDSA or Ed25519, and keep the post-quantum migration in view. Getting that far is a solid answer.

Summary

• Symmetric encryption needs a shared secret you cannot establish over a hostile network; public-key cryptography solves the bootstrap with a key that locks but cannot unlock
• RSA rests on one asymmetry: multiplying two large primes is trivial, factoring the product is not
• Key generation: $n = pq$, $\varphi(n) = (p-1)(q-1)$, pick $e$ coprime to $\varphi(n)$, set $d \equiv e^{-1} \pmod{\varphi(n)}$. Public $(n,e)$, private $(n,d)$
• Encryption is $c \equiv m^e \bmod n$ and decryption $m \equiv c^d \bmod n$ — one modular exponentiation each
• It round-trips because $ed = 1 + k\varphi(n)$, so $m^{ed} = m \cdot (m^{\varphi(n)})^k \equiv m$ by Euler's theorem
• Security means factoring $n$ is infeasible; recovering $\varphi(n)$ is equivalent to factoring, and 2048 bits is today's floor — but Shor's algorithm ends this on a large quantum computer
• Textbook RSA must never be shipped: it is deterministic, malleable, and breakable at small exponents. Use OAEP for encryption and PSS for signatures
• In practice RSA encrypts a symmetric key rather than data, and in TLS 1.3 its surviving role is signing certificates

For the surrounding landscape, start with Cryptography from Scratch; to see RSA signatures doing their job inside a real handshake, continue to TLS from Scratch.

Check your understanding

1. Key generation requires $\gcd(e, \varphi(n)) = 1$. What exactly breaks if you pick an $e$ that violates it?
2. Why is $d$ computed modulo $\varphi(n)$ rather than modulo $n$?
3. Using the public key $(33, 3)$ from the worked example, encrypt $m = 2$. Then use $d = 7$ to decrypt your answer and confirm you get 2 back.
4. An attacker learns $\varphi(n)$ for some 2048-bit RSA key but not $p$ or $q$. Is the key compromised? Justify your answer.
5. A service encrypts a single-digit PIN with textbook RSA using a 2048-bit public key and stores the ciphertext. The key is strong and factoring is infeasible. Explain how an attacker reads the PIN anyway, and which countermeasure prevents it.