RSA in Python From Scratch: Math, Keys, and Real Code

Every HTTPS connection you've ever made ran through math published in a 1978 paper by Ron Rivest, Adi Shamir, and Len Adleman. Not a variant of it. Not a descendant. The same core algorithm, scaled up and hardened, but structurally identical to what you're about to build from scratch in about 50 lines of Python.

Most articles that cover RSA stop at the concept. They explain that RSA is "asymmetric" and that one key encrypts while the other decrypts, and then they hand you a diagram with padlocks and tell you to go use the cryptography library. That approach teaches you nothing about what's actually happening. You end up using cryptographic primitives you don't understand, which means you make decisions about key sizes, padding schemes, and usage patterns without any foundation.

This article goes all the way down. We're going to cover the number theory, build each component from scratch, trace through the algorithms by hand, test the result, and then honestly assess what this implementation can and cannot do. Part 2 adds cryptographically secure random prime generation and text encryption. Part 3 covers the side-channel attacks that can break a mathematically correct implementation.

By the end of this article you will have a working RSA implementation and a genuine understanding of why it works. That understanding is what lets you use production cryptography intelligently instead of copying boilerplate and hoping for the best.

We recommend reading A Small Introduction to RSA Encryption & the Mathematics to continue reading our selection of content. If the number theory in this section moved fast, this piece slows down and builds the same intuition from the ground up before you touch any code.

A Small Introduction to RSA Encryption & the Mathematics

RSA Encryption has always been amazing to me. It allows you to publish an encryption key – also known as e – without having to compromise your decryption key – known as d. One amazing feat that I find the most interesting is that generally in practice that e is usually always the

CoderOasisTraven

What Is the Math Behind RSA Encryption?

RSA is an asymmetric cryptosystem. You get two keys: one to encrypt, one to decrypt. The same key cannot do both. Publish the encryption key to the world, keep the decryption key private, and anyone can send you a message that only you can read.

That sounds contradictory at first. If someone knows the encryption key, can't they just work backwards and figure out the decryption key? This is the question RSA answers with number theory.

The encryption and decryption operations are:

ciphertext = m^e mod n
plaintext  = c^d mod n

Where m is the message as a number, e is the public exponent, d is the private exponent, and n is the modulus. The relationship between e and d is carefully constructed so that applying both operations returns you to the original message:

(m^e)^d ≡ m (mod n)

The security of RSA rests on a single asymmetry: computing n = p * q from two large primes is trivial, but factoring n back into p and q when n is 2048 bits is computationally infeasible with current hardware and known algorithms.

Before you can understand why the math works, you need three number theory concepts that most tutorials skip or underexplain.

What Number Theory Concepts Does RSA Require?

Modular arithmetic. The notation a ≡ b (mod n) means a and b leave the same remainder when divided by n. Equivalently, a - b is divisible by n. So 17 ≡ 5 (mod 12) because both leave a remainder of 5 when divided by 12. This is clock arithmetic: 17 hours after midnight is 5 AM. The modulo operation keeps numbers bounded, which is what makes RSA practical -- without it, the intermediate values in encryption would have millions of digits.

Greatest common divisor. gcd(a, b) is the largest integer that divides both a and b. Two numbers are coprime when gcd(a, b) = 1 -- they share no factors. This matters for RSA because we need the public exponent e to be coprime with the key generation parameter λ(n). If they shared a factor, the decryption key derivation breaks.

The Carmichael function. λ(n) is the smallest positive integer m such that x^m ≡ 1 (mod n) for every x coprime to n. The critical property: if a ≡ b (mod λ(n)), then x^a ≡ x^b (mod n) for any x coprime to n. This is the property that makes decryption work. If we construct e and d so that e * d ≡ 1 (mod λ(n)), then:

(m^e)^d = m^(e*d) ≡ m^1 = m (mod n)

Decryption perfectly undoes encryption. The math is not approximate or probabilistic. Given the right keys, it is exact.

How Are RSA Public and Private Keys Generated Mathematically?

Start with two distinct primes p and q. Their product n = p * q is the modulus.

For a prime p, the Carmichael function is λ(p) = p - 1, because every integer from 1 to p - 1 is coprime to p (Fermat's Little Theorem). For the product n = p * q:

λ(n) = lcm(p - 1, q - 1)

Some older implementations use φ(n) = (p-1)(q-1) instead, which is Euler's totient function. Both work because λ(n) always divides φ(n). The Carmichael function produces smaller, more efficient keys. Modern implementations use it. This implementation uses a simplified version where lambda_n = (p - 1) * (q - 1) for clarity -- the math is equivalent when gcd(p-1, q-1) is small.

Next, choose the public exponent e. The standard value is 65537, which is 2^16 + 1. It's prime, it's coprime with virtually all λ(n) values you'll encounter, and its binary representation (10000000000000001) makes modular exponentiation fast because it has only two set bits. This implementation uses 35537 instead of 65537 so the example numbers stay small enough to verify by hand.

To find the private exponent d, solve:

e * d ≡ 1 (mod λ(n))

Or equivalently, find integers d and x such that:

e * d + x * λ(n) = 1

The Extended Euclidean Algorithm finds d and x from this equation. It works because gcd(e, λ(n)) = 1 by construction -- we specifically chose e to be coprime with λ(n).

Once you have d, discard p and q. The public key is (e, n). The private key is (d, n). An attacker who wants to find d from (e, n) would need to compute λ(n), which requires factoring n into p and q. That's the hard problem RSA rests on.

How Do You Implement RSA Encryption in Python?

Now that you know what we're building toward, let's build it. Three components: the Extended Euclidean Algorithm to find d, fast modular exponentiation to perform encryption and decryption, and the key generation function that ties everything together.

How Does the Extended Euclidean Algorithm Work in Python?

The Extended Euclidean Algorithm finds (x, y) such that a*x + b*y = gcd(a, b). For RSA, we call it with a = e and b = λ(n). Since gcd(e, λ(n)) = 1, the equation becomes e*x + λ(n)*y = 1, which gives us x = d, the modular inverse of e we need.

The regular Euclidean Algorithm computes gcd(a, b) by repeatedly applying gcd(a, b) = gcd(b, a mod b) until b = 0. The extended version does the same thing but tracks how each reduction relates back to the original a and b, so it can reconstruct d at the end.

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
    # current_b = cb[0]*original_a + cb[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

Walk through a concrete example to make this tangible. Find d such that 35537 * d ≡ 1 (mod 3120). Call eucalg(35537, 3120).

The algorithm begins with a = 35537, b = 3120, ca = (1, 0), cb = (0, 1).

First iteration: k = 35537 // 3120 = 11. New a = 3120, new b = 35537 - 3120*11 = 35537 - 34320 = 1217. New ca = (0, 1), new cb = (1 - 11*0, 0 - 11*1) = (1, -11).

Verify: 1*35537 + (-11)*3120 = 35537 - 34320 = 1217. Correct. The coefficients track the current remainder as a combination of the inputs.

Continue this process until b = 0. The final ca gives (x, y) where 35537*x + 3120*y = 1. If x is negative, add λ(n) to it -- a negative d is equivalent to d + λ(n) in modular arithmetic, since -k ≡ λ(n) - k (mod λ(n)).

The algorithm runs in O(log max(a, b)) steps because each iteration reduces the problem by at least half. For 2048-bit keys, that's around 1400 iterations maximum. Fast.

One thing that surprises people: the coefficients oscillate positive and negative throughout the computation. This is normal and correct. The final coefficient is what matters, and the negative-to-positive correction handles the rest.

Why Do You Need Fast Modular Exponentiation and How Does It Work?

Computing m^e mod n where e = 65537 and n is a 2048-bit number looks straightforward until you think about what m^e actually is. A number with roughly 65537 * log10(m) digits. That's millions of digits before the modulo operation. Python handles arbitrary-precision integers, so it won't crash. It will just grind for a very long time.

Binary exponentiation solves this by taking the modulo at every multiplication step, keeping intermediate values bounded by n throughout the entire computation.

The algorithm reads the bits of the exponent e from the most significant bit to the least significant. At each step it squares the running result. If the current bit is 1, it also multiplies by the base. After each multiplication, reduce modulo 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

After each (r * r) % n, the value of r is less than n. After each (r * b) % n, same thing. The largest intermediate value is (n-1)^2, which is about 4096 bits for a 2048-bit key. That's manageable. Compare this to the naive approach, where you'd have a number growing by log2(b) bits at each of e multiplication steps -- unbounded and impractical.

The number of multiplications is 2 * floor(log2(e)). For e = 65537, that's at most 32 multiplications. Not 65537 multiplications. That's the entire point of binary exponentiation.

Verify this works:

assert modpow(2, 10, 10000) == 1024   # 2^10 = 1024
assert modpow(2, 10, 7) == 2          # 1024 mod 7 = 2
assert modpow(3, 4, 5) == 1           # 81 mod 5 = 1

One note before moving on: Python's built-in pow(b, e, n) does exactly this, implemented in C. It's dramatically faster than this Python version. Build it from scratch to understand it, then use pow(b, e, n) in anything that needs to run at speed.

How Do You Generate Keys and Encrypt/Decrypt with RSA in Python?

With eucalg and modpow in place, the key generation function is a direct translation of the math:

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])

Look at numencrypt and numdecrypt. They're identical. Both call modpow(m, key[0], key[1]). The only difference is which key you pass. This symmetry is intentional -- RSA's math doesn't distinguish encryption from decryption at the algorithmic level. Asymmetry comes from which key is secret, not from different operations.

The negative d check matters. The Extended Euclidean Algorithm produces Bezout coefficients that can be negative. If eucalg(35537, lambda_n) returns d = -7, that's equivalent to lambda_n - 7 in modular arithmetic -- adding lambda_n gives the correct positive representative. Skip this check and your implementation silently fails for certain prime pairs.

How Do You Test the RSA Python Implementation?

Fire up a Python interactive session and verify the round-trip:

>>> import rsa
>>> keys = rsa.keysgen(31337, 31357)
>>> keys
{'priv': (720926705, 982634309), 'pub': (35537, 982634309)}
>>> priv = keys['priv']
>>> pub = keys['pub']
>>> msg = 80087
>>> enc = rsa.numencrypt(msg, pub)
>>> enc
34604568
>>> dec = rsa.numdecrypt(enc, priv)
>>> dec
80087

Message 80087 encrypts to 34604568 and decrypts back to 80087. The round-trip works.

Now verify the mathematical relationship directly:

p, q = 31337, 31357
lambda_n = (p - 1) * (q - 1)   # 982571616
e, d = 35537, 720926705
print((e * d) % lambda_n)       # Should print 1

It prints 1. The modular inverse relationship e * d ≡ 1 (mod λ(n)) holds.

Now verify that n = p * q:

print(31337 * 31357)   # 982634309

This matches n from the key pair. The math checks out completely.

What Does the Complete RSA Implementation Look Like?

Here is the complete rsa.py file with full documentation:

"""
RSA from Scratch -- Part 1
Mathematical primitives: Extended Euclidean Algorithm,
modular exponentiation, key generation, integer encryption.
 
For educational use. Do not use in production.
"""
 
 
def eucalg(a, b):
    """
    Extended Euclidean Algorithm.
    Returns (x, y) such that a*x + b*y = gcd(a, b).
    Used to find the modular inverse of e mod lambda_n.
    """
    swapped = False
    if a < b:
        a, b = b, a
        swapped = True
    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
 
 
def modpow(b, e, n):
    """
    Fast modular exponentiation: b^e mod n.
    Uses binary exponentiation for O(log e) multiplications.
    Intermediate values stay bounded by n throughout.
    """
    tst = 1
    siz = 0
    while e >= tst:
        tst <<= 1
        siz += 1
    siz -= 1
    r = 1
    for i in range(siz, -1, -1):
        r = (r * r) % n
        if (e >> i) & 1:
            r = (r * b) % n
    return r
 
 
def keysgen(p, q):
    """
    Generate RSA key pair from two primes p and q.
    Returns {'pub': (e, n), 'priv': (d, n)}.
    In production: p and q must be randomly generated
    1024-bit primes, not hand-picked small numbers.
    """
    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):
    """
    Encrypt integer m with public key pub = (e, n).
    Requires m < n. Larger messages need chunking -- see Part 2.
    """
    return modpow(m, pub[0], pub[1])
 
 
def numdecrypt(m, priv):
    """
    Decrypt integer m with private key priv = (d, n).
    """
    return modpow(m, priv[0], priv[1])
 
 
if __name__ == '__main__':
    keys = keysgen(31337, 31357)
    print("Keys:", keys)
 
    priv = keys['priv']
    pub  = keys['pub']
    msg  = 80087
 
    enc = numencrypt(msg, pub)
    dec = numdecrypt(enc, priv)
 
    print(f"Message:   {msg}")
    print(f"Encrypted: {enc}")
    print(f"Decrypted: {dec}")
    assert msg == dec, "Round-trip failed"
    print("Round-trip: OK")
 
    e, d = pub[0], priv[0]
    p, q = 31337, 31357
    lambda_n = (p - 1) * (q - 1)
    assert (e * d) % lambda_n == 1, "Key derivation error"
    print(f"e*d ≡ 1 (mod lambda_n): OK")

Running this produces:

Keys: {'priv': (720926705, 982634309), 'pub': (35537, 982634309)}
Message:   80087
Encrypted: 34604568
Decrypted: 80087
Round-trip: OK
e*d ≡ 1 (mod lambda_n): OK

What Are the Limitations of This Python RSA Implementation?

This is where most articles get dishonest. They show you a working implementation and imply it's close to production-ready. It's not. Here's what's missing and why each gap matters.

Message size restriction. numencrypt only works for integers m < n. Our n = 982634309, which is 30 bits. Any message larger than that wraps around modulo n and produces garbage on decryption. Real RSA uses 2048-bit keys, but even then the raw message must be padded and split into chunks no larger than n. Part 2 covers byte-level chunking.

Toy prime generation. We passed p = 31337 and q = 31357 manually. These are 15-bit primes. A modern laptop factors a 15-bit product in microseconds. Real RSA requires primes around 1024 bits each, generated from a cryptographically secure random source. Part 2 builds the prime generator.

No padding scheme. Textbook RSA (this implementation) is deterministic: the same message always produces the same ciphertext. An attacker who can observe two encryptions of the same message knows they're identical. OAEP (Optimal Asymmetric Encryption Padding) adds randomness to break this determinism. The Python cryptography library uses OAEP by default. You should never use raw RSA for message encryption in production.

No side-channel protection. Our modpow implementation takes different amounts of time depending on which bits of the private key d are set. An attacker measuring decryption times across thousands of requests can recover individual bits of d using Kocher's timing attack (1996). Part 3 covers constant-time implementations and blinding.

No CRT optimization. The Chinese Remainder Theorem lets you compute decryption roughly four times faster by working modulo p and q separately and combining the results. Real RSA implementations (including OpenSSL) use CRT for private key operations. This implementation does not.

The table below summarizes where this implementation stands:

Why Not Just Use the Python Cryptography Library?

You should, for anything real. The cryptography library and pycryptodome handle all of the above correctly, have been audited, and are maintained by people who spend their careers on this. Rolling your own crypto in production is one of the most reliable ways to introduce subtle, catastrophic vulnerabilities.

But there's a case for understanding the implementation: it changes how you use production libraries.

When you call cryptography.hazmat.primitives.asymmetric.rsa.generate_private_key(public_exponent=65537, key_size=2048), you now understand every parameter. You know why 65537 and not some other prime. You know that 2048 bits means n is a 2048-bit number, not the key material itself. You know that key generation involves random prime generation, not random byte generation. You know that the private key stores p, q, d, and CRT parameters -- not just d.

That knowledge shapes better decisions. Developers who don't understand RSA make decisions like using a 512-bit key because "it's probably fine," or encrypting large files directly with RSA instead of using RSA to encrypt an AES key, or reusing key pairs across contexts where they shouldn't be reused.

Understanding the math doesn't replace the library. It makes you competent to use the library.

For the concept side of RSA -- the intuition for why it works -- the introduction to RSA encryption article on CoderOasis covers the conceptual model in depth. And if you want to go further with cryptography in Python, we've covered the foundations of cryptography across the site.

How Does the Extended Euclidean Algorithm Trace Through a Real Example?

Let's trace fully through eucalg(35537, 3120) so there's no mystery. We want d such that 35537 * d ≡ 1 (mod 3120).

Initial state: a = 35537, b = 3120, ca = (1, 0), cb = (0, 1).

Iteration 1: k = 35537 // 3120 = 11. New b = 35537 - 11 * 3120 = 35537 - 34320 = 1217. New cb = (1 - 11*0, 0 - 11*1) = (1, -11). New state: a=3120, b=1217, ca=(0,1), cb=(1,-11).

Iteration 2: k = 3120 // 1217 = 2. New b = 3120 - 2 * 1217 = 686. New cb = (0 - 2*1, 1 - 2*(-11)) = (-2, 23). New state: a=1217, b=686, ca=(1,-11), cb=(-2,23).

Iteration 3: k = 1217 // 686 = 1. New b = 1217 - 686 = 531. New cb = (1-(-2), -11-23) = (3, -34). New state: a=686, b=531, ca=(-2,23), cb=(3,-34).

This continues until b = 0, at which point ca holds the Bezout coefficients. Verify the final result with Python:

d, x = eucalg(35537, 3120)
print(f"d = {d}")
print(f"Verify: (35537 * {d}) % 3120 = {(35537 * d) % 3120}")

If d is negative, the correction is:

if d < 0:
    d += 3120
print(f"Corrected d = {d}")
print(f"Verify: (35537 * {d}) % 3120 = {(35537 * d) % 3120}")

Both should print 1 for the modular product. A negative Bezout coefficient is mathematically equivalent to its positive counterpart modulo λ(n) -- adding λ(n) shifts you to the positive representative without changing the modular value.

Why Does Naive Modular Exponentiation Fail at RSA Scale?

Run this and watch what happens:

import time
 
b, e, n = 65537, 10**100, 10**309 + 7  # enormous exponent
 
# Naive: compute b**e first, then take modulo
start = time.perf_counter()
result_naive = (b ** e) % n
t_naive = time.perf_counter() - start
 
# Binary exponentiation
start = time.perf_counter()
result_fast = modpow(b, e, n)
t_fast = time.perf_counter() - start
 
# Python's built-in (same algorithm, in C)
start = time.perf_counter()
result_builtin = pow(b, e, n)
t_builtin = time.perf_counter() - start
 
assert result_naive == result_fast == result_builtin
print(f"Naive:   {t_naive:.4f}s")
print(f"modpow:  {t_fast:.4f}s")
print(f"pow():   {t_builtin:.6f}s")

On a modern machine, the naive approach takes several seconds even with Python's arbitrary-precision integer library doing the heavy lifting. The binary exponentiation version runs in milliseconds. Python's pow(b, e, n) in C runs in microseconds.

The reason: b ** e with e = 10^100 produces a number with roughly 10^100 * log10(b) digits before the modulo operation. That intermediate value is not just large -- it's astronomically large. Allocating and operating on it costs time proportional to its size. Binary exponentiation avoids this entirely by never letting the running value exceed n^2.

For reference: with n as a 2048-bit number, n^2 is 4096 bits. That's large in human terms but trivially manageable for a computer. The number b^e without modular reduction for a real RSA exponent would have more digits than there are atoms in the observable universe.

How Does RSA Key Size Affect Security?

The security of RSA is the difficulty of factoring n into p and q. The best known general-purpose factoring algorithm is the General Number Field Sieve (GNFS). Its running time is sub-exponential in the number of bits in n:

exp( (64/9)^(1/3) * (ln n)^(1/3) * (ln ln n)^(2/3) )

This grows much slower than pure exponential time but much faster than polynomial time. The practical consequence: adding bits to n makes factoring harder, but not at a linear rate. Doubling the key size more than doubles the security.

Our example uses n = 982634309, which is 30 bits. A 30-bit number factors in microseconds on any modern machine:

import math
 
n = 982634309
# Trial division is enough for 30-bit numbers
for p in range(2, int(math.sqrt(n)) + 1):
    if n % p == 0:
        print(f"n = {p} * {n // p}")
        break

This finds p = 31337 and q = 31357 in milliseconds. Our toy implementation is not just slow or impractical -- it's trivially breakable. That's fine for learning the algorithm. It's not fine for anything else.

The 2009 factorization of a 768-bit RSA key required hundreds of machines running for nearly two years. A 2048-bit number at current hardware and algorithmic capabilities would require more computational resources than exist on Earth. That gap between "trivial to multiply" and "infeasible to factor" is the trapdoor RSA is built on.

We recommend reading Creating RSA Digital Signatures to continue reading our selection of content. The same numencrypt/numdecrypt symmetry this article ends on is exactly what makes RSA signatures possible, and that piece picks up the thread from here.

Understanding & Creating RSA Digital Signatures

In this article, I am going to show you what to learn from the first articles to turn it into real world, production safe usage. This article is going to cover one last major concept before we get into the real world usage of RSA: create unforgeable digital signatures. The

CoderOasisTraven

Frequently Asked Questions

Is it safe to use this RSA implementation in production?

No. This implementation lacks secure prime generation, message padding, timing-attack resistance, and CRT optimization. For production cryptography, use the cryptography library or pycryptodome.

What is the Extended Euclidean Algorithm used for in RSA?

It finds the modular inverse of the public exponent e relative to λ(n). That inverse is the private key d. Given e and λ(n), it computes d such that e * d ≡ 1 (mod λ(n)).

What Python version does this RSA code require?

Python 3.x. No external dependencies. The code uses only built-in integer arithmetic.

What is modular exponentiation and why does RSA need it?

Modular exponentiation computes b^e mod n without materializing the full value of b^e. For real RSA parameters, b^e would have millions of digits and take longer to compute than the age of the universe. Binary exponentiation with modular reduction at each step keeps the computation fast and practical.

Can the same RSA implementation be used for digital signatures?

Yes. Encrypting with the private key and decrypting with the public key is how RSA signatures work mathematically. The functions numencrypt and numdecrypt are symmetric -- pass the private key to numencrypt and you've signed the message. Pass the public key to numdecrypt and anyone can verify the signature. We cover this in the RSA digital signatures article.

Part 2 builds a cryptographically sound prime generator using the Miller-Rabin test and Fibonacci-based Lucas sequences, adds byte-level encryption so this implementation can handle real text, and produces an end-to-end working system. Part 3 covers the attacks that break a mathematically correct implementation: timing attacks, blinding, and constant-time exponentiation.