Project 10: RSA Cryptosystem from Scratch

A self-contained deep-dive from the canonical Math from Foundations to Machine Learning curriculum.

  • Difficulty: Intermediate
  • Time: 1-2 weeks
  • Language: Python (alternatives: C++, Rust)
  • Prerequisites: Projects 1-2
  • Source: Prog P03

What You Will Build

Build a deliberately small educational RSA system without using a cryptography library for the number-theory operations. Generate candidate primes, test primality at an appropriate toy scale, compute n and Euler’s totient, choose a public exponent coprime to the totient, and find the private exponent with the extended Euclidean algorithm. Implement square-and-multiply modular exponentiation, encode short byte messages into integers smaller than n, and demonstrate key generation, encryption, and decryption. Clearly label the result unsafe for real secrets because it lacks secure key sizes, vetted randomness, padding, and side-channel defenses.

Real World Outcome

The CLI creates a public/private toy keypair, prints the mathematical invariants, encrypts a short message into integer blocks, and recovers the exact original bytes. A property-test run checks many messages and prime pairs. Invalid public exponents, oversized blocks, non-primes, and corrupt ciphertext produce useful diagnostics rather than silent nonsense.

Core Question

How do modular arithmetic and multiplicative inverses create a transformation that is easy to apply publicly but reversible only with a private exponent?

Concepts You Must Understand First

  1. Divisibility, primes, and greatest common divisors: Euclid’s algorithm exposes coprimality.
  2. Congruences: numbers can be equivalent modulo n; arithmetic wraps within residue classes.
  3. Euler’s totient and theorem: for coprime values, exponentiation cycles modulo n.
  4. Modular inverses: extended Euclid finds d such that ed ≡ 1 (mod φ(n)).
  5. Fast modular exponentiation: square-and-multiply avoids constructing enormous intermediate powers. See Hardy and Wright, An Introduction to the Theory of Numbers.

Build Milestones

  1. Implement and test gcd, extended gcd, modular inverse, and modular exponentiation.
  2. Add toy prime generation/testing with deterministic test fixtures and optional seeded randomness.
  3. Generate keys and assert p != q, gcd(e, φ)=1, and (e*d) mod φ = 1.
  4. Encode messages into safe-size blocks; encrypt, decrypt, and reconstruct bytes exactly.
  5. Add property tests, tampering/error cases, serialization, and an explicit security disclaimer.

Hints in Layers

  1. Build the arithmetic primitives first and compare each with Python’s three-argument pow or hand-worked examples.
  2. Keep byte encoding separate from RSA math; assert every message integer is in [0, n).
  3. Use tiny known primes for readable tests, then larger toy primes only after all invariants pass.

Common Pitfalls and Debugging

  • Symptom: decryption returns unrelated integers. Cause: d was computed modulo the wrong value or e is not coprime to the totient. Fix: print and assert the key invariants.
  • Symptom: part of a message cannot be recovered. Cause: its encoded integer is at least n. Fix: reduce block size based on modulus bit length.
  • Symptom: implementation seems secure because examples work. Cause: mathematical correctness was confused with production cryptographic safety. Fix: document missing OAEP padding, CSPRNG, key size, and side-channel protections.

Definition of Done

  • Core number-theory functions pass hand-calculated and randomized property tests.
  • Key generation enforces prime, distinctness, and coprimality invariants.
  • Short messages round-trip exactly through block encoding, encryption, and decryption.
  • Invalid keys, blocks, and ciphertext paths fail deterministically.
  • Documentation prominently states that the system is educational and unsafe for real secrets.

Previous: Project 9 · Complete learning path · Next: Project 11