RSA in Python From Scratch: The Math, the Code, and What Breaks It

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.

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.

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.

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.

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

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

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:

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.

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.

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 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 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.