> ## Content Index > Fetch the complete content index at: https://sudosecurity.org/llms.txt > Use this file to discover other available public pages before exploring further. # RSA in Python From Scratch: The Math, the Code, and What Breaks It - URL: https://sudosecurity.org/implementing-rsa-from-scratch-in-python/ - Published: 2021-08-19T04:00:00.000Z - Updated: 2026-10-16T05:46:05.000Z - Description: Every HTTPS connection you have ever made runs on a 1978 paper. You can build the core of it in about fifty lines of Python — and then see exactly why those fifty lines would get you destroyed in production. - Author: Traven - Tags: Cryptography, Python, RSA, Programming, Cybersecurity, Encryption, Algorithms, series-rsa-python Every HTTPS connection you've ever made runs on math published in a 1978 paper by Rivest, Shamir and Adleman. Not a variant. Not a descendant. The same core algorithm, scaled up and hardened, but structurally identical to what you're about to build in about fifty lines of Python. Most articles on RSA stop at the concept. They tell you it's "asymmetric," that one key encrypts and the other decrypts, hand you a diagram with padlocks, and point you at the `cryptography` library. That teaches you nothing about what's happening. You end up making decisions about key sizes and padding schemes with no foundation under them. This goes all the way down. Number theory, each component built from scratch, algorithms traced by hand, the result tested, and then an honest account of what it cannot do. Every figure printed below is generated by running the code, not transcribed. The full implementation, a test suite asserting every claim in both parts, and a script that regenerates each output are in the companion repository: [**rsa-from-scratch**](https://github.com/sudosecurity/rsa-from-scratch?ref=sudosecurity.org). ## The Math, Briefly RSA gives you two keys. One encrypts, one decrypts, and the same key cannot do both. Publish one, keep the other, and anyone can send you something only you can read. ``` ciphertext = m^e mod n plaintext = c^d mod n ``` `m` is the message as a number, `e` the public exponent, `d` the private exponent, `n` the modulus. The relationship between `e` and `d` is constructed so that applying both returns the original: ``` (m^e)^d ≡ m (mod n) ``` Security rests on one asymmetry: computing `n = p * q` from two large primes is trivial, factoring `n` back into `p` and `q` at 2048 bits is not. Three concepts do the work. **Modular arithmetic.** `a ≡ b (mod n)` means `a` and `b` leave the same remainder when divided by `n`. `17 ≡ 5 (mod 12)` — clock arithmetic. Seventeen hours after midnight is 5 AM. Modulo keeps numbers bounded, which is what makes RSA practical at all. **Greatest common divisor.** `gcd(a, b)` is the largest integer dividing both. Coprime means `gcd(a, b) = 1` — no shared factors. RSA needs `e` coprime with the key generation parameter, or the private key derivation has no solution. **The Carmichael function.** `λ(n)` is the smallest `m` where `x^m ≡ 1 (mod n)` for every `x` coprime to `n`. The property that matters: if `e * d ≡ 1 (mod λ(n))`, then ``` (m^e)^d = m^(e*d) ≡ m^1 = m (mod n) ``` Decryption undoes encryption exactly. Not approximately, not probabilistically. ### Generating the Keys Two distinct primes `p` and `q`, product `n = p * q`. For a prime, `λ(p) = p - 1`. For the product: ``` λ(n) = lcm(p - 1, q - 1) ``` A note on what this code actually does, because it matters and most tutorials paper over it. **The implementation below computes `(p-1)*(q-1)`, which is Euler's totient φ(n), not the Carmichael function.** Both produce a working key pair, because λ(n) always divides φ(n) — any `d` valid modulo φ(n) is also valid modulo λ(n). φ(n) just gives you a larger `d` than necessary. Real implementations use λ(n) for smaller keys; FIPS 186-5 actually requires it. The variable is called `lambda_n` below for continuity with the rest of the series, and that name is a small lie. Then choose `e`. The standard is 65537\. **This implementation uses 35537** so the worked examples stay small enough to check by hand. It's a legitimate choice here — it's prime, and `gcd(35537, φ(n)) = 1` for our primes, which is all the math requires. It is not a value you would ever ship. Find `d` by solving `e * d ≡ 1 (mod λ(n))`, equivalently finding integers `d` and `x` where: ``` e * d + x * λ(n) = 1 ``` That's the Extended Euclidean Algorithm. Then discard `p` and `q`. Public key `(e, n)`, private key `(d, n)`. Recovering `d` from `(e, n)` requires computing λ(n), which requires factoring `n`. ## The Extended Euclidean Algorithm It finds `(x, y)` such that `a*x + b*y = gcd(a, b)`. Call it with `a = e` and `b = λ(n)`, and since those are coprime the equation becomes `e*x + λ(n)*y = 1` — so `x` is `d`. ```python def eucalg(a, b): swapped = False if a < b: a, b = b, a swapped = True # ca and cb track current a and b as linear combinations # of the original inputs: # current_a = ca[0]*original_a + ca[1]*original_b ca = (1, 0) cb = (0, 1) while b != 0: k = a // b a, b, ca, cb = b, a - b * k, cb, (ca[0] - k * cb[0], ca[1] - k * cb[1]) if swapped: return (ca[1], ca[0]) return ca ``` Trace `eucalg(35537, 3120)` by hand and then check it. Initial: `a = 35537`, `b = 3120`, `ca = (1, 0)`, `cb = (0, 1)`. **Iteration 1:** `k = 35537 // 3120 = 11`. New `b = 35537 - 34320 = 1217`. New `cb = (1, -11)`. Check: `1*35537 + (-11)*3120 = 1217`. Correct. **Iteration 2:** `k = 3120 // 1217 = 2`. New `b = 686`. New `cb = (-2, 23)`. **Iteration 3:** `k = 1217 // 686 = 1`. New `b = 531`. New `cb = (3, -34)`. Run it to the end: ``` eucalg(35537, 3120) = (-1087, 12381) 35537*-1087 + 3120*12381 = 1 corrected d=2033, (35537*2033) % 3120 = 1 ``` Note the negative. Bezout coefficients oscillate sign throughout, and the final `x` here is `-1087`. Adding the modulus gives `2033`, which is the positive representative of the same value — `-1087 ≡ 2033 (mod 3120)`. **Skip that correction and your implementation silently fails on certain prime pairs.** Runtime is `O(log max(a, b))`, and the constants are worth knowing because the worst case and the real case are wildly different. Lamé's theorem gives the bound: the worst input is a pair of consecutive Fibonacci numbers, and the iteration count is `log_φ` of the input. Measured: ``` worst case (consecutive Fibonacci, 2048 bits): 2949 iterations Lame's theorem bound for 2048-bit inputs: 2949 iterations ``` Theory and measurement agree exactly. But that worst case never happens in RSA, because you aren't calling it on adversarial inputs — you're calling it with `e = 65537` and a 2048-bit λ(n): ``` realistic eucalg(lambda_n, 65537), 200 samples: max 16, mean 10.8 ``` **Eleven iterations on average.** The small second argument collapses it almost immediately. Key generation spends essentially all its time finding primes, and none worth mentioning on the extended Euclidean algorithm. --- > If you're enjoying what you've read so far, we recommend [RSA Part 2: Real Primes, Real Text, and a Bug That Eats Your Data](https://sudosecurity.org/implementing-rsa-from-scratch-in-python-part-2/) as your next read. --- ## Fast Modular Exponentiation Computing `m^e mod n` looks straightforward until you consider what `m^e` is before the modulo. Binary exponentiation takes the modulo at every step, keeping intermediates bounded by `n`. ```python def modpow(b, e, n): # Find the position of the highest set bit in e tst = 1 siz = 0 while e >= tst: tst <<= 1 siz += 1 siz -= 1 # Binary exponentiation: read bits of e high-to-low r = 1 for i in range(siz, -1, -1): r = (r * r) % n # Square if (e >> i) & 1: r = (r * b) % n # Multiply by base if bit is 1 return r ``` The largest intermediate is `(n-1)^2` — 4096 bits for a 2048-bit key. Multiplication count is `2 * floor(log2(e))`; for `e = 65537` that's at most 32 multiplications, not 65537. ``` modpow(2,10,10000) == 1024 -> True modpow(2,10,7) == 2 -> True modpow(3,4,5) == 1 -> True ``` Python's built-in `pow(b, e, n)` does the same thing in C, and it is faster. Build `modpow` to understand it, then use `pow()` for anything that runs. With one caveat that matters later, and that most tutorials skip: **`pow()` is not constant-time either.** Same test, same exponents, both implementations: ``` exponent weight -> modpow pow() 2 bits set 11.448ms 11.288ms 1024 bits set 12.482ms 13.284ms ratio 1.09x 1.18x ``` CPython's implementation leaks *more* signal than the Python version here, not less. Being written in C makes it faster; it does not make it safe against an attacker measuring how long your decryption took. So "use the built-in" is the right advice for correctness and speed, and it is not a fix for the side-channel problem. That takes blinding, which is Part 3. ## Why the Naive Version Isn't Just Slow You'll see benchmarks comparing `(b ** e) % n` against modular exponentiation, and a lot of them quote a "naive" time. Be careful with the exponent you pick, because past a certain size the naive version doesn't run slowly — it doesn't run. Take `b = 65537, e = 10^100`, a figure that shows up in exactly this kind of comparison: ``` b**e would have ~4.816e+100 decimal digits atoms in observable universe ~1e80 memory needed: ~2.000e+91 GB ``` Python will not compute that in "a few seconds." It will not compute it before the heat death of the universe, and it will exhaust your memory trying. Any benchmark quoting a completion time for that has not been run. So here is one that does run. Exponent small enough for the naive path to finish, `n` a real 2048-bit modulus: ``` e= 4096: naive 0.75 ms | modpow 0.064 ms | pow() 0.055 ms | b**e is 65,537 bits e= 65537: naive 40.95 ms | modpow 0.111 ms | pow() 0.097 ms | b**e is 1,048,594 bits ``` The scaling is the whole point. Sixteen times the exponent gives **fifty-five times** the naive runtime, because the intermediate grew from 65 thousand bits to over a million. `modpow` went from 0.064ms to 0.111ms — it barely noticed, because its intermediate never exceeded `n²` either time. Extrapolate that curve to `e = 10^100` and you get the memory figure above. ## Keys, Encryption, Decryption ```python def keysgen(p, q): n = p * q lambda_n = (p - 1) * (q - 1) e = 35537 d = eucalg(e, lambda_n)[0] if d < 0: d += lambda_n return {'priv': (d, n), 'pub': (e, n)} def numencrypt(m, pub): return modpow(m, pub[0], pub[1]) def numdecrypt(m, priv): return modpow(m, priv[0], priv[1]) ``` `numencrypt` and `numdecrypt` are identical. Both call `modpow(m, key[0], key[1])`. RSA's math does not distinguish encryption from decryption at the algorithmic level — the asymmetry is entirely in which key is secret. That symmetry is also what makes digital signatures possible: sign by "encrypting" with the private key, verify by "decrypting" with the public one. ## Running It ```python from rsa import keysgen, numencrypt, numdecrypt keys = keysgen(31337, 31357) priv, pub = keys['priv'], keys['pub'] enc = numencrypt(80087, pub) dec = numdecrypt(enc, priv) ``` Real output: ``` {'priv': (720926705, 982634309), 'pub': (35537, 982634309)} message = 80087 encrypted = 539186383 decrypted = 80087 ``` And the relationship that makes it work: ```python from math import gcd p, q = 31337, 31357 lambda_n = (p - 1) * (q - 1) print(gcd(35537, lambda_n)) # 1 -- e is coprime, as required print((35537 * 720926705) % lambda_n) # 1 -- e*d ≡ 1 (mod lambda_n) print(31337 * 31357) # 982634309 == n ``` All three hold. ## What This Cannot Do This is where most tutorials get quiet. Five gaps, each of which matters. **Message size.** `numencrypt` only works for `m < n`, and the boundary is exact: ``` n = 982634309 m= 80087 -> decrypts to 80087 OK m= 982634308 -> decrypts to 982634308 OK <- n-1, the last valid message m= 982634309 -> decrypts to 0 WRONG m= 982634310 -> decrypts to 1 WRONG m= 982714396 -> decrypts to 80087 WRONG (got m mod n) ``` Note the last row. A message of `n + 80087` decrypts to `80087` — a perfectly valid-looking number that is not what you encrypted. There is no exception and no signal. `pow` reduces modulo `n` on the way in, so what you get back is `m mod n` — decrypted correctly, into the wrong number. That's the same class of silent corruption as the block-size trap in Part 2, and it's why real implementations pad and chunk below `n` rather than trusting callers to check. **Toy primes.** We hand-picked two 15-bit primes. Watch how long the resulting modulus survives: ``` trial division of n=982634309 found p=31337 in 1.87 ms ``` Under two milliseconds, using the most naive factoring method there is. Not "slow" or "impractical" — trivially broken. Real RSA needs \~1024-bit primes from a cryptographically secure source. **No padding.** Textbook RSA is deterministic, and it's worth seeing rather than being told: ``` plaintext -> ciphertext 80087 -> 539186383 80087 -> 539186383 42 -> 392297916 80087 -> 539186383 42 -> 392297916 ``` Same input, same output, every time. An attacker who never breaks a single key still learns that messages 1, 2 and 4 are identical, and that 3 and 5 are identical. In a structured format — a status field, a boolean, a country code — that is frequently the whole secret. This is the same failure that made Adobe's 2013 breach so damaging: passwords encrypted in ECB mode, so identical passwords produced identical ciphertext, and the top 100 were recovered without anyone touching the key. OAEP fixes it by mixing in randomness before encryption, so the same plaintext encrypts differently every time. Part 2 covers the second half of the problem — that raw RSA is also *malleable*, meaning an attacker can modify the plaintext without ever decrypting it. **No side-channel protection.** `modpow` branches on the bits of the exponent — it squares every iteration but only multiplies when a bit is set. So its running time is a function of the exponent, and during decryption the exponent *is* the private key. That's measurable. Two exponents of identical bit length, one with 2 bits set and one with 1024: ``` modpow with 2 bits set: 12.075 ms modpow with 1024 bits set: 12.791 ms difference: 0.716 ms (1.06x) ``` Six percent. Small — but consistent and in the right direction, and it's the whole basis of Kocher's 1996 timing attack. Six percent sounds unusable as an attack, and it isn't — the exploitation is statistical, and Part 3 covers exactly how a signal that small becomes a private key. The point for now is narrower: the fix is not "make it faster." Speed is irrelevant. The requirement is that the running time stop depending on the key at all. **No CRT optimization.** Every real implementation decrypts by working modulo `p` and `q` separately and recombining. You'll see "four times faster" quoted for this. Measured on a freshly generated 2048-bit key, median of 20 decryptions: ``` plain pow(c, d, n) : 28.05 ms CRT (mod p and q) : 8.48 ms speedup : 3.31x exponent bits: d=2045, dP=1023, dQ=1023 ``` **3.31×**, not 4×. The theoretical argument for 4 is that modular exponentiation costs roughly the cube of the operand size, so halving the modulus should be 8× cheaper — but you do it twice, giving 4×. Reality lands lower because the recombination step isn't free and the halved exponents aren't exactly half the work. The exponent line explains where the win comes from: `d` is 2045 bits, while `dP` and `dQ` are 1023 each. Two exponentiations on 1024-bit moduli beat one on a 2048-bit modulus by a wide margin. This is also why a real private key stores `p`, `q`, `dP`, `dQ` and `qInv` rather than just `d` — and why leaking any one of them is fatal. | | This implementation | Production RSA | | ------------------- | ------------------- | ------------------------ | | Core algorithm | Correct | Correct | | Key size | 30-bit (toy) | 2048–4096 bit | | Prime generation | Manual input | Cryptographically random | | Message encoding | Integers only | OAEP-padded bytes | | Timing safety | Vulnerable | Constant-time | | CRT optimization | No | Yes | | Standard compliance | No | PKCS#1, OAEP | --- > Still with us? We think you'll like [RSA Part 3: Your Correct Implementation Still Leaks the Key](https://sudosecurity.org/implementing-rsa-from-scratch-in-python-part-3/) as your next read. --- ## Two Ways to Break It With Valid-Looking Parameters The failures above are about size. These two are about *choice*, and both produce code that looks fine. **Using the same prime twice.** `p` and `q` must be distinct, and it isn't a stylistic preference: ``` p==q: round-trip 12345 -> 772124688 OK=False and n is a perfect square: sqrt(n)=31337 -> factors instantly ``` Decryption returns the wrong number. The reason is that with `p = q`, the totient is no longer `(p-1)(q-1)` — it's `p(p-1)` — so the `d` you derived satisfies the wrong congruence and `e*d ≢ 1` for the actual group. And even if you patched the math, `n = p²` is a perfect square, so anyone can factor it with `isqrt(n)` in microseconds. Two failures for one mistake. **Choosing `e` that shares a factor with λ(n).** The coprimality requirement isn't decoration — it decides whether `d` exists at all: ``` e=65537: gcd=1, d=674413217, e*d mod lambda = 1 e=3: gcd(e,lambda)=3 -> no modular inverse exists, keygen must retry e=4: gcd(e,lambda)=4 -> no modular inverse exists, keygen must retry ``` With `e = 3` and these particular primes, no `d` exists. There is no clever fix — the extended Euclidean algorithm returns a gcd of 3 rather than 1, and the equation `3d + xλ(n) = 1` has no integer solution. This is why real key generation runs in a loop. Part 1's `keysgen` doesn't check, which means it can hand you a key pair that silently fails to decrypt on certain prime inputs. Production code either verifies `gcd(e, λ(n)) == 1` and regenerates the primes, or picks a fresh `e`. Go's FIPS implementation does the former, discarding both primes and starting over. The general lesson, and it applies well beyond RSA: **a cryptographic implementation that produces output is not the same as one that produces correct output.** Every example in this article round-trips successfully with the parameters given, and three of the four failure modes above produce no error at all. ## Key Size and What Actually Breaks Security is the difficulty of factoring `n`. The best known general algorithm is the General Number Field Sieve, running in sub-exponential time: ``` exp( (64/9)^(1/3) * (ln n)^(1/3) * (ln ln n)^(2/3) ) ``` Slower than exponential, much faster than polynomial. Adding bits raises the cost sharply but not linearly. That's checkable rather than decorative. The leading constant evaluates to the figure you'll see quoted in the literature, and running the formula across key sizes reproduces the table below: ``` (64/9)^(1/3) = 1.922999 (literature constant ~1.9229) key bits log2(GNFS ops) vs 512-bit 512 63.9 1x 768 76.5 6.13e+03x 1024 86.8 7.49e+06x 2048 116.9 8.73e+15x 4096 156.5 7.34e+27x ``` **A 2048-bit modulus is roughly nine quadrillion times harder to factor than the 512-bit one that costs $75.** That is what "adding bits" buys, and it's why the jump from 1024 to 2048 was worth the performance cost. One honesty note on those numbers: the raw heuristic runs slightly *above* the standardised security equivalents — it predicts about 117 bits for a 2048-bit key where NIST publishes 112\. The formula is an asymptotic estimate that ignores constant factors and assumes an idealised implementation, so the standards bodies quote the more conservative figure. Use the published equivalents for decisions; use the formula to understand the shape. | Key size | Security equivalent | Status | | -------- | ------------------- | ----------------------------------------------------------- | | 512-bit | \~60-bit | Factored 1999 — **now $75 and four hours** | | 768-bit | \~76-bit | Factored December 2009 | | 1024-bit | \~80-bit | Deprecated by NIST in 2010 | | 2048-bit | \~112-bit | Current minimum — **NIST deprecates this strength in 2030** | | 3072-bit | \~128-bit | Recommended for new systems | | 4096-bit | \~140-bit | Long-term, real performance cost | Those first two rows are worth expanding, because "broken in 1999" understates the situation badly. **RSA-155**, the 512-bit challenge modulus, fell on **22 August 1999**. It cost roughly 8,400 MIPS-years: seven calendar months end to end, with the sieving alone consuming 35.7 CPU-years spread across about 300 workstations in six countries. That was 1999\. Valenta et al. later optimised the number field sieve for Amazon EC2 and reported factoring 512-bit RSA keys **in under four hours for about $75**. Not a nation-state. A credit card and an afternoon. The part that should genuinely worry you is what the same paper found when it went looking: hundreds or thousands of **deployed** 512-bit keys across DNSSEC, HTTPS, IMAP, POP3, SMTP, DKIM, SSH and PGP. The math has been dead for twenty-five years and the deployments haven't caught up. **RSA-768** fell in **December 2009**, and the published figure is that it would have taken **more than 1,700 years on a single standard core** — done in roughly two and a half calendar years across a heterogeneous mix of clusters and grid computing. Extrapolate that curve to 2048 bits and you get a number with no physical meaning. That gap — trivial to multiply, infeasible to factor — is the entire trapdoor. Against classical computers, anyway. That 112-bit row has an expiry date attached to it now: NIST IR 8547 proposes deprecating 112-bit-strength algorithms in **2030** and disallowing them in **2035**, and the post-quantum replacements were standardised in August 2024\. Part 3 covers what that means and why it matters before a quantum computer exists. ## Why Build It If You Shouldn't Ship It You should use `cryptography` or `pycryptodome` for anything real. They're audited, maintained, and handle every gap listed above. But understanding the implementation changes how you use them. When you call `rsa.generate_private_key(public_exponent=65537, key_size=2048)` you now know why 65537 and not something else, that 2048 bits describes `n` rather than the key material, that generation means finding random primes rather than random bytes, and that the private key stores `p`, `q`, `d` and CRT parameters — not just `d`. That's what stops people picking a 512-bit key because "it's probably fine," or encrypting a file directly with RSA instead of using RSA to wrap an AES key. Understanding the math doesn't replace the library. It makes you competent to use it. [Part 2](https://sudosecurity.org/implementing-rsa-from-scratch-in-python-part-2/) replaces the hand-picked primes with a real generator — a Fermat and Lucas-Fibonacci pair drawing from `secrets`, audited against Miller-Rabin — and adds byte-level encryption so this handles actual data. It also inherits `e = 35537` into a real key, which turns out to matter. [Part 3](https://sudosecurity.org/implementing-rsa-from-scratch-in-python-part-3/) covers the attacks that break a mathematically correct implementation: timing, blinding, and constant-time exponentiation. Part 4 covers the 2023 attack that showed those defenses were insufficient, and Part 5 covers the deprecation timeline RSA now has.