Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 40 ยท Projects

Project: A Mini Crypto Library

Build a small cryptography library from scratch in Python: modular math, Miller-Rabin primes, RSA keys, padded encryption and signatures, checked by a test suite.

In this project you assemble everything from the math and public-key chapters into one small library: extended Euclid, modular inverses, Miller-Rabin primality testing, random prime generation, RSA key pairs, padded encryption and hash-then-sign signatures. Then you write a test suite that proves the pieces fit together.

Writing the library yourself is the best way to understand why each part exists. It is also the best way to see why you must never ship it. The code you will write is a teaching toolkit: it has no side-channel protection, uses a seeded random generator so the lesson is repeatable, and uses simplified padding. In real software you call a vetted library and use OAEP and PSS. The final section lists exactly what is missing.

The plan

The toolkit has three layers. Each layer only uses the one below it, which keeps the tests small and the bugs easy to find.

flowchart TD
    A["Layer 3: sign, verify, encrypt, decrypt"] --> B["Layer 2: RSA key generation"]
    B --> C["Layer 1: egcd, modinv, Miller-Rabin, random_prime"]
    C --> D["Python: pow(a, b, m), hashlib, random"]

Every function in the top layer depends on the layers beneath it, so test from the bottom up.

You met the ingredients earlier: modular arithmetic, the extended Euclidean algorithm, Miller-Rabin, RSA from scratch and digital signatures. Skim them first if any step below feels new.

Layer 1: number theory

Start with the pieces that have no cryptography in them at all. egcd returns the gcd and the Bezout coefficients; modinv turns that into an inverse and refuses to answer when none exists; is_probable_prime is Miller-Rabin; random_prime keeps drawing odd numbers with the top bit set until one passes.

Two details matter. First, we pass the random generator in as an argument. That makes every function deterministic when you give it a seeded random.Random, which is what lets the tests assert exact results. Second, we try a short list of small primes first. It is cheap and removes most composite candidates before the expensive modular exponentiations.

Python Layer 1: number theory with tests

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

If every line says PASS, layer 1 is trustworthy. Notice that 561 is a Carmichael number: it fools the plain Fermat test but not Miller-Rabin, so including it as a test case guards against the most common mistake in a primality implementation.

Layer 2 and 3: RSA keys, encryption and signatures

Key generation picks two distinct primes p and q of half the modulus size, computes phi = (p - 1)(q - 1), and requires gcd(e, phi) = 1 for the public exponent e = 65537. If that fails, draw new primes. The private exponent is d = e^-1 mod phi.

For signatures the toolkit uses hash-then-sign: hash the message with SHA-256, treat the digest as a number, and raise it to the private exponent. Verification raises the signature to e and compares with the digest. Signing the hash instead of the message lets you sign messages of any length and avoids the multiplicative tricks that work on raw RSA.

For encryption the toolkit adds a simplified random padding, in the shape of the old PKCS#1 v1.5 scheme: 00 02 <random non-zero bytes> 00 <message>. The random bytes mean that encrypting the same message twice gives two different ciphertexts, which closes the deterministic-encryption hole of textbook RSA (RSA padding and pitfalls).

Python The complete toolkit with a test suite

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The test list checks three kinds of properties: round trips (decrypting an encryption returns the message), negative cases (tampering must fail) and randomness effects (two encryptions of the same text differ). A good crypto test suite always contains negative tests, because a verifier that accepts everything passes every positive test.

Extending the project

Try these in the editor above, one at a time, and add a test for each:

  1. Speed up decryption with the CRT. Keep p and q in the private key and compute m1 = c^(d mod p-1) mod p, m2 = c^(d mod q-1) mod q, then combine them (see Euler's theorem and the CRT). Assert that it equals the plain result.
  2. Add key serialization. Write export_key(key) and import_key(text) using hex and a header line, and test the round trip.
  3. Make the padding check constant-time-ish. Replace the early raise statements in unpad with a single failure path, so an attacker cannot tell which check failed. This is the idea behind defenses against Bleichenbacher-style oracle attacks.
  4. Hash with a context string. Sign b"toolkit-v1:" + message so that a signature made for one purpose cannot be replayed in another.

What this library is missing

A short, honest list of why you must not use it in production:

  • No PSS or OAEP. The signature uses the full-domain-hash idea without a proper encoding, and the encryption padding is the older v1.5 style that is known to be fragile.
  • Not constant time. Python integers and pow leak timing information about the secret exponent.
  • A seeded PRNG. random.Random is not a secure source. Real key generation uses secrets or the operating system's randomness (randomness and entropy).
  • No blinding, no fault protection, no key storage, and only the minimum validation of inputs.

Writing it was still worth it. You now know exactly what a key pair, a signature and a padded ciphertext are made of.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the toolkit pass the random generator into each function instead of using a global one?

    Passing the generator in lets tests use a fixed seed. For real keys you would use the operating system's secure randomness instead.
  2. 2. Which test input exposes a primality test that relies only on Fermat's little theorem?

    561 = 3 x 11 x 17 satisfies the Fermat condition for every base coprime to it, yet it is composite. Miller-Rabin catches it.
  3. 3. Why should the test suite include cases where verification is expected to fail?

    Positive tests alone cannot tell a correct verifier from one that always returns true.
  4. 4. What does the random padding add to RSA encryption?

    The random filler bytes make encryption non-deterministic, which stops an attacker from confirming a guessed plaintext by encrypting it.
  5. 5. Which is a real reason not to ship this toolkit?

    The math is right, but real-world security depends on side-channel resistance, secure randomness and modern padding schemes.

Summary

  • A crypto library is built in layers: number theory, key generation, then encryption and signatures. Test each layer from the bottom up.
  • Miller-Rabin plus a seeded random generator gives deterministic, testable prime generation.
  • Hash-then-sign lets RSA sign messages of any length; random padding makes encryption non-deterministic.
  • Good test suites include round trips, negative cases and tamper checks.
  • Educational code is not production code: use vetted libraries, OAEP/PSS, secure randomness and constant-time operations.

Next: Project: A Tiny Blockchain and Merkle Proofs.