Step 228. Full RSA Implementation: From Key Generation to Encryption/Decryption — The Textbook, by My Own Hands
Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★★★☆ | Estimated time: 5 hours
Prerequisites: Step 227 (modular arithmetic, the Euclidean algorithm, Euler’s theorem) — all of today’s math was built in the last chapter.
⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.
- What you need: Python 3 (measured: 3.12.14). Standard library only — nothing to install.
- Caution: one rule today — no production crypto libraries like
cryptography. Implementing everything from prime generation to signing yourself is this chapter’s learning goal. And the "textbook RSA" you build today has no padding, so it’s vulnerable if used in production — it’s an implementation for learning.
In Step 227 you built the parts (inverses, Euler’s theorem); today is assembly. RSA is a cipher standing on a single fact — "factoring large numbers is hard." You may publish n, the product of two primes, but nobody who can’t split n back apart learns the private key. Today you’ll generate 512-bit primes yourself to make a 1024-bit key, encrypt and decrypt a sentence, and measure the full process through signing and tamper detection. When it’s over, RSA is no longer a cipher you "believe in" — it’s a cipher you "made."
1. Learning Objectives
By the end of this chapter, you will be able to:
- Generate 512-bit primes yourself with Miller-Rabin primality testing
- Compute the
n, φ(n), e, drelationships and explain each variable’s role - Convert message ↔ integer correctly (
int.from_bytes/to_bytes) - Encrypt/decrypt with
pow(m, e, n)/pow(c, d, n), and apply the same keys in reverse for sign/verify - Explain the limits of padding-free textbook RSA (the m < n restriction, deterministic encryption)
2. Background Knowledge — Today’s Tools and Concepts
Today’s Tools at a Glance
| Category | Details |
|---|---|
| Language/environment | Python 3 (measured: 3.12.14), secrets (randomness), hashlib (hashing for signatures) |
| Today’s commands | secrets.randbits(), pow(a, b, n), pow(e, -1, phi), int.from_bytes(), int.to_bytes() |
| Concepts needed | All of Step 227 + Miller-Rabin primality testing, public/private keys, digital signatures |
| Today’s deliverable | rsa.py — a complete working implementation of key generation, encryption/decryption, sign/verify + verification experiment output |
2-1. Anatomy of an RSA Key
p, q : two large primes you generate yourself — secret
n = p × q : public. "A number that's hard to split" is the foundation of everything
φ(n) = (p-1)(q-1) : secret. Computable only by someone who knows p, q
e = 65537 : public exponent. Customarily chosen as a prime coprime with φ(n)
d : private exponent. e's inverse mod φ(n) — pow(e, -1, phi)
Only (n, e) is public. For an attacker to get d, they need φ(n); to get φ(n), they must split n into p, q — practically impossible at 1024 bits and above.
2-2. Why Encryption/Decryption Works — A One-Line Proof
Encryption: c = m^e mod n; decryption: m = c^d mod n. Chained together: m^(e·d) mod n. Since d is the inverse with e·d ≡ 1 (mod φ(n)), we have e·d = k·φ(n) + 1, and by Euler’s theorem (Step 227) m^(k·φ(n)) ≡ 1, so finally m^(e·d) ≡ m (mod n). Last chapter’s theorem is today’s decryption guarantee.
2-3. Miller-Rabin — How to Find Large Primes
How do you make a prime? "Pick a large odd number at random, test whether it’s prime, retry if not." The test uses the Miller-Rabin probabilistic primality test — it applies Fermat’s little theorem (Step 227: for prime p, a^(p-1) ≡ 1) with several random a values, and if every trial passes, it judges the number prime with overwhelming probability. Even for 512-bit numbers, it finishes within a second.
2-4. Digital Signatures — Using the Keys in Reverse
RSA’s beautiful symmetry: encryption is "lock with the public key, open with the private key," and signing is "lock with the private key, open with the public key." Raise the document’s hash to the private key (s = h^d mod n) and you have a signature; anyone can compute s^e mod n with the public key and check it against the document’s hash. Since only the private-key holder can produce it, "I wrote this" and "it wasn’t tampered with" are proven at once.
3. Follow Along
All output in this chapter was measured 2026-09-09 on Python 3.12.14. Primes are generated at random every run, so your numbers will differ — just verify the structure.
3-1. Building a Prime Generator
import secrets
def is_probable_prime(n, rounds=20):
if n < 2: return False
for p in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
if n % p == 0: return n == p # handle small primes directly
d, r = n - 1, 0
while d % 2 == 0:
d //= 2; r += 1 # n-1 = 2^r × d
for _ in range(rounds):
a = secrets.randbelow(n - 3) + 2
x = pow(a, d, n)
if x in (1, n - 1): continue
for _ in range(r - 1):
x = pow(x, 2, n)
if x == n - 1: break
else:
return False # definitely composite
return True # overwhelmingly likely prime
def gen_prime(bits):
while True:
c = secrets.randbits(bits) | (1 << (bits - 1)) | 1 # pin the top and bottom bits
if is_probable_prime(c):
return c
Draw a random number with secrets.randbits(bits), pin the top bit to 1 (so it’s exactly bits long) and the bottom bit to 1 (so it’s odd), then test. In measurement, one 512-bit prime came out in under a second.
3-2. Key Generation
p = gen_prime(512)
q = gen_prime(512)
print(str(p)[:20], "...", p.bit_length(), "bits")
print("p != q:", p != q)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = pow(e, -1, phi) # Step 227's inverse
print("n bits:", n.bit_length())
print("(e * d) % phi =", (e * d) % phi)
12570016984684578139 ... 512 bits
p != q: True
n bits: 1024
(e * d) % phi = 1
How to read the output: two 512-bit primes were made, and their product is 1024 bits. (e·d) mod φ(n) = 1 — exactly Step 227’s inverse cross-check. These six variables are everything in one RSA keypair.
3-3. Encryption and Decryption — With a Real Sentence
Messages must be integers, so convert with int.from_bytes.
msg = "Meet at dawn. Keys built by hand!"
m = int.from_bytes(msg.encode(), "big")
print("m < n:", m < n, "(m bits:", m.bit_length(), ")")
c = pow(m, e, n) # encrypt
m2 = pow(c, d, n) # decrypt
recovered = m2.to_bytes((m2.bit_length() + 7) // 8, "big").decode()
print("decrypted:", recovered)
print("matches original:", recovered == msg)
m < n: True (m bits: 281 )
decrypted: Meet at dawn. Keys built by hand!
matches original: True
How to read the output: a full sentence made the round trip through a 1024-bit n exactly. (m2.bit_length() + 7) // 8 computes the byte count needed to turn the integer back into bytes. Textbook RSA complete — but you’ll see its limits right away in 3-5.
3-4. Signing and Tamper Detection
import hashlib
doc = "This contract was written by me."
h = int.from_bytes(hashlib.sha256(doc.encode()).digest(), "big") % n
sig = pow(h, d, n) # sign with the private key
h_check = pow(sig, e, n) # verify with the public key
print("signature verifies:", h_check == h)
h_fake = int.from_bytes(hashlib.sha256("This contract was written by you.".encode()).digest(), "big") % n
print("tampered doc verifies:", h_check == h_fake)
signature verifies: True
tampered doc verifies: False
How to read the output: you ran the same keypair in the reverse direction. The original document passes verification; the tampered document — one word changed — fails. The signature is bound to the document’s hash, so change the document and verification breaks. This is the simultaneous achievement of non-repudiation (only the signer could make it) and integrity (tampering detected).
3-5. Verification Experiment — The Limits, by My Own Hands
big_m = n + 12345 # deliberately an m larger than n
big_c = pow(big_m, e, n)
big_m2 = pow(big_c, d, n)
print("large m restored:", big_m2 == big_m)
print("restored = m mod n:", big_m2 == big_m % n)
large m restored: False
restored = m mod n: True
How to read the output: when m exceeds n, the decryption result is truncated to m mod n — the mod world can’t remember anything beyond n. That’s the first limit: RSA can’t directly encrypt data larger than n. Which is why practice is hybrid — long data gets encrypted with AES (symmetric key), and only the short AES key gets encrypted with RSA.
The second limit hides out of sight. The same m always becomes the same c (deterministic) — an attacker can "encrypt every candidate plaintext and compare." This is why production RSA uses padding like OAEP to produce a different c every time, and why today’s padding-free implementation must not be used in production. These weaknesses are exactly the attack material of the coming chapters.
4. Missions & Exercises
Mission — Completing rsa.py and Self-Verification
- Organize today’s code into a single file
rsa.py— functionsgen_prime,generate_keys(bits)(returns(n, e), d),encrypt(m, e, n),decrypt(c, d, n),sign(doc, d, n),verify(doc, sig, e, n)(returns True/False) - With a 256-bit key (two 128-bit primes), write an
if __name__ == "__main__":demo that encrypts/decrypts a short English sentence and runs sign, verify, and tamper detection all in one go - In a comment at the top of the file, write each variable’s role in one line — all six: p, q, n, φ(n), e, d
- (Optional) Give a friend or colleague only the public key
(n, e), receive a ciphertext, and decrypt it with your private key — working without any key exchange is the whole point of public-key cryptography
Exercises
Exercise 1. An attacker has the public key (n, e) and a ciphertext c. What must they do to get d, and why is it hard? Explain via φ(n).
Exercise 2. Why is 65537 used for e? Explain using e’s two conditions (coprime with φ(n), preference for small numbers).
Exercise 3. In signature verification, why do we sign the "hash" rather than the document body? Give two reasons (length restriction, efficiency).
Exercise 4. In experiment 3-5, what was the decryption result of big_m = n + 12345? Explain how this limit leads to the industry’s "hybrid encryption" design.
5. Model Answers & Completion Criteria
Mission Model Answer
Here’s the skeleton of generate_keys — the remaining functions are the one-liners from the main text, transcribed as-is.
def generate_keys(bits=1024):
half = bits // 2
p, q = gen_prime(half), gen_prime(half)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
if phi % e == 0: # coprimality check — rare but necessary
return generate_keys(bits)
d = pow(e, -1, phi)
return (n, e), d
The demo’s grading criteria: ① the decrypted sentence equals the original under == ② signature verify True, tampered document False ③ the comments’ variable descriptions state "roles" (e.g., "d — private key. e’s inverse mod φ(n), used for decryption and signing"), not "values."
How to verify: run the demo twice — the primes change every time (random generation), yet the result judgments must be identically true. That the math holds on top of randomness is RSA’s essence.
Exercise Answers
Answer 1. Since d is e’s inverse mod φ(n), the attacker needs φ(n). φ(n) = (p-1)(q-1) can only be computed by factoring n into p and q. But no efficient method is known for splitting n of 1024 bits or more — factoring is hard, so φ(n) stays unknown; φ(n) unknown, so d stays unknown. RSA’s entire security hangs on this chain’s first link (the hardness of factoring).
Answer 2. First, e must be coprime with φ(n) for the inverse d to exist — picking a prime satisfies this condition almost automatically. Second, e is the exponent of public-key operations (encryption, verification), so smaller is faster. 65537 = 2¹⁶ + 1 has only two 1s in binary, making exponentiation especially fast, while being large enough to avoid the attacks against too-small values like 3 (next chapter’s material).
Answer 3. First, the signed object must be smaller than n (the 3-5 limit), but documents can be arbitrarily long — a hash compresses any length of document to a fixed size. Second, modular exponentiation at n’s scale is slow if applied to an entire document — doing it once on a hash is fast. Thanks to the hash’s tamper-detection property (change one character and the hash changes), document integrity is inherited as-is.
Answer 4. The decryption result was m mod n = 12345 (measured: restored = m mod n: True). Since the mod world can’t express anything at or above n, data RSA can directly encrypt is limited to n bits or less. Practice sidesteps this limit by encrypting long data with a fast symmetric cipher (AES) and sending only that AES key (a few hundred bits, smaller than n) encrypted with RSA — TLS is exactly this structure.
Completion Criteria Checklist
- [ ] I generated a 512-bit prime myself with Miller-Rabin
- [ ] I computed n, φ(n), e, d and confirmed
(e·d) mod φ(n) == 1 - [ ] I encrypted and decrypted a sentence and saw it match the original
- [ ] I measured all three: sign, verify, tamper detection
- [ ] I confirmed by experiment that m > n gets truncated
- [ ] I can explain each variable’s role in one line
- [ ] I can give two reasons padding-free RSA must not be used in production
- [ ] Mission: I completed rsa.py and confirmed every demo judgment is true
6. Common Pitfalls & Fixes
Wall 1. OverflowError: int too big to convert
Symptom: OverflowError: int too big to convert at to_bytes after decryption (measured 2026-09-09, when the byte count was set too small).
Cause: the length in m2.to_bytes(length, "big") is too short to hold m2.
Fix: compute the needed byte count with (m2.bit_length() + 7) // 8 as in 3-3. Hardcoding breaks when m grows.
Wall 2. pow(e, -1, phi) raises ValueError: base is not invertible
Symptom: ValueError: base is not invertible for the given modulus (the same error measured in Step 227).
Cause: e and φ(n) aren’t coprime — you drew a prime combination where φ(n) is a multiple of 65537. Rare, but it happens.
Fix: as in the mission model answer, regenerate the key if phi % e == 0.
Wall 3. Prime generation never finishes
Symptom: gen_prime spins for minutes.
Cause: two possibilities — you wrote pow(a, d) instead of pow(a, d, n) inside is_probable_prime, creating giant numbers (three-argument pow is mandatory; Step 227 Wall 3), or you forgot the top-bit pinning and keep drawing small numbers.
Fix: verify every exponentiation uses three-argument pow, and check the two bit-pinnings in | (1 << (bits-1)) | 1. When correct, 512 bits takes under a second (measured 2026-09-09).
Wall 4. Decryption differs from the original, but there’s no error
Symptom: matches original: False with no exception.
Cause: mostly m ≥ n — the 3-5 truncation happened silently. Reproducible by putting a long sentence through a 256-bit key.
Fix: add assert m < n before encryption. For long messages, split into multiple blocks (textbook style) or just keep messages short — today is about learning principles.
Wall 5. The "it’s done, let’s use this" temptation
Symptom: you want to drop today’s rsa.py into a real project.
Cause: the joy of completion. But today’s implementation has no padding, no timing-attack defenses, and none of the tens of thousands of audits a vetted library has survived.
Fix: this file’s purpose is learning. In production you use vetted libraries — except now you’re someone who knows what happens inside that library. That’s today’s harvest.
7. Summary
Today’s Concepts
| Concept | One-line explanation |
|---|---|
| RSA key | p, q (secret primes) → n (public), φ(n) (secret), e (public exponent), d (e’s inverse, secret) |
| Encryption/decryption | c = m^e mod n, m = c^d mod n — Euler’s theorem guarantees the round trip |
| Digital signature | Raise a hash to the private key — anyone verifies with the public key; breaks on tampering |
| Miller-Rabin | Probabilistic primality test based on Fermat’s little theorem — the engine of large-prime generation |
| m < n restriction | The mod world can’t hold beyond n — the reason hybrid encryption exists |
| Textbook RSA | Pure implementation without padding — for learning; production use forbidden (deterministic, vulnerable) |
Today’s Commands & Code
| Command | What it does |
|---|---|
secrets.randbits(bits) |
Generate cryptographic randomness |
pow(a, b, n) |
Modular exponentiation — encryption, decryption, and signing are all this |
pow(e, -1, phi) |
Compute the private key d |
int.from_bytes(b, "big") |
Bytes → integer (message preparation) |
m.to_bytes((m.bit_length()+7)//8, "big") |
Integer → bytes (restoration) |
hashlib.sha256(doc).digest() |
Make the hash to be signed |
An Instinct More Important Than Commands
All of RSA was six variables and two lines of exponentiation. The hard part isn’t the formulas but the chain of "why it’s safe" — hardness of factoring → φ(n) hidden → d hidden — and the moments that chain’s first link snaps (small n, small e, key reuse) are the attacks starting next chapter. Today you built the castle yourself. Someone who has built the castle knows where its weak stones are — the attack chapters ahead will click much faster.
Once every box is checked, Step 228 is complete. Click the checkbox in the sidebar to save your progress.