Skip to content
Tutorials Center
My learning

Topics

Lesson 61 of 68 ยท Projects

Project: Modular Arithmetic and Toy RSA

Build a modular arithmetic library with extended gcd, inverses and the Chinese remainder theorem, test it, then use it to run a toy RSA demonstration.

Modular arithmetic is the quiet engine under hash tables, checksums, random number generators and public-key cryptography. In this project you will build a small modular calculator from first principles: the extended Euclidean algorithm, modular inverses, solving linear congruences, the Chinese remainder theorem (CRT), and fast exponentiation. Then you will stack a toy RSA demonstration on top of it, so you can see how much of RSA is just these four functions.

This project is educational only. The RSA here uses tiny primes, no padding and no randomness, so it can be broken instantly. Real systems must use a vetted cryptography library. Python's built-in pow(a, -1, m) exists and is what you should use in real code; we write our own to understand it.

Read GCD, LCM and the Euclidean Algorithm, Modular Arithmetic and Number Theory in Cryptography first.

The calculator's parts

Extended gcd Finds x and y with ax + by = gcd.
Inverses Solve a * x = 1 mod m.
CRT Combine congruences with coprime moduli.
Fast power Square and multiply in log steps.
1 / 2

Step 1: extended gcd

The Euclidean algorithm replaces the pair (a, b) with (b, a mod b) until the second number is 0; the first number left is the gcd. The extended version also tracks coefficients x and y such that

aยทx + bยทy = gcd(a, b)

This is Bรฉzout's identity, and the coefficients are what we need for inverses. The recursive form is short. Suppose we know the answer for (b, a mod b): bยทxโ€ฒ + (a mod b)ยทyโ€ฒ = g. Since a mod b = a โˆ’ (a // b)ยทb, substituting gives aยทyโ€ฒ + bยท(xโ€ฒ โˆ’ (a // b)ยทyโ€ฒ) = g. So the new coefficients are x = yโ€ฒ and y = xโ€ฒ โˆ’ (a // b)ยทyโ€ฒ.

We will write the function iteratively, which avoids Python's recursion limit and is no harder to read. A good test of any new function is comparing it with a trusted one, so we check the gcd against math.gcd on many pairs, and we check the identity aยทx + bยทy = g itself.

Python Extended Euclid with built-in 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.

For (240, 46) the gcd is 2 and one valid pair of coefficients is x = โˆ’9 and y = 47, because 240ยท(โˆ’9) + 46ยท47 = โˆ’2160 + 2162 = 2. The test loop verifies 22,201 pairs. Coefficients are not unique (you can always shift x by 46/2 and y by 240/2 in opposite directions), so we test the identity, not specific numbers.

Step 2: inverses and linear congruences

A modular inverse of a modulo m is a number x with aยทx โ‰ก 1 (mod m). It exists exactly when gcd(a, m) = 1. If aยทx + mยทy = 1, then reducing modulo m kills the mยทy term, leaving aยทx โ‰ก 1. So the inverse is just x mod m from the extended gcd.

An inverse lets you divide. To solve the linear congruence aยทx โ‰ก b (mod m) with gcd(a, m) = g:

  • if g does not divide b, there is no solution;
  • otherwise divide everything by g, getting (a/g)ยทx โ‰ก (b/g) (mod m/g), which has a unique solution modulo m/g, and the original has g solutions modulo m, spaced m/g apart.
Python Inverses and linear congruences

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 inverse of 7 modulo 40 is 23, since 7 ยท 23 = 161 = 4 ยท 40 + 1, and the inverse of 3 modulo 11 is 4. The attempt to invert 6 modulo 15 raises an error that mentions gcd = 3. The congruence 7x โ‰ก 3 (mod 40) has the single solution [29]. The congruence 6x โ‰ก 9 (mod 15) has g = 3 and therefore three solutions, [4, 9, 14], while 6x โ‰ก 8 (mod 15) has none because 3 does not divide 8. The final loop compares every answer with direct trial of all residues, which is the definition and cannot be wrong.

Step 3: the Chinese remainder theorem

For pairwise coprime moduli, the system x โ‰ก rโ‚ (mod mโ‚), x โ‰ก rโ‚‚ (mod mโ‚‚), ... has one solution modulo the product M. We solve it by merging two congruences at a time. Suppose we have x โ‰ก r (mod M) and want to add x โ‰ก s (mod m) with gcd(M, m) = 1. Look for x + Mยทt:

Mยทt โ‰ก s โˆ’ r (mod m), so t = (s โˆ’ r) ยท Mโปยน mod m.

Then the merged answer is (r + Mยทt) modulo Mยทm. We reuse mod_inverse from step 2.

We can go beyond the textbook case cheaply. If the moduli share factors the system may still be solvable, but only if the two congruences agree on the shared part. We handle that by checking g = gcd(M, m): the system is consistent only when (s โˆ’ r) is divisible by g, and the merged modulus is the lcm. The function below does this general merge and returns None for impossible systems.

Python CRT, including non-coprime moduli

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 classic puzzle (remainders 2, 3, 2 modulo 3, 5, 7) gives (23, 105). The pair mod 4 and mod 9 gives (29, 36). When the moduli 6 and 10 share the factor 2 and the remainders agree on parity, the answer is (13, 30). With remainders 1 and 2 they disagree on parity (one is odd, one is even), so there is no solution and the function returns None. The final loops compare against a brute-force search over one full period for a few hundred systems.

Step 4: fast exponentiation

Computing a^e mod m by multiplying a together e times is hopeless when e has hundreds of digits. Square and multiply reads the bits of e: it keeps a running result and a running square of a; when the current bit is 1, multiply the result by the square; then square a and move to the next bit. Only about logโ‚‚(e) steps are needed. Reducing modulo m after every multiplication keeps all numbers small.

We write it and compare it with Python's built-in three-argument pow, which does the same thing in C.

Python Square and multiply

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 huge exponent 10ยนโธ needs just 60 loop iterations, and 7^128 mod 13 is computed in 8, giving 3. That efficiency is what makes RSA feasible: the exponents have hundreds of digits, yet each exponentiation takes only a few thousand multiplications.

Step 5: a toy RSA on top

We now have everything. A toy key pair needs two distinct primes, which we find by trial division, an exponent e coprime to ฯ† = (p โˆ’ 1)(q โˆ’ 1), and d = eโปยน mod ฯ† using our own inverse. Encrypting is power_mod(m, e, n), decrypting is power_mod(c, d, n).

Because our modulus will be small, we also include the attack that makes the toy nature plain: factor n by trial division, rebuild ฯ† and recover the private key from the public one. We then use CRT in decryption, as real implementations do, computing the result modulo p and modulo q separately and merging them. Both routes must produce the same plaintext.

Python Toy RSA with keys, CRT decryption and an attack

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 primes are 1009 and 1103, so n = 1,112,927 and ฯ† = 1,110,816. Since 65537 is already coprime to ฯ† it stays as the public exponent. Every message below n survives the round trip, both by the plain formula and by the CRT shortcut, and the attacker recovers the identical private exponent after trying about a thousand divisors. A message larger than n would wrap around and decrypt incorrectly, which is one reason real systems encode messages carefully.

Step 6: a tiny test harness

A project is not finished until its checks run together. Collect all the assertions into one function that reports how many passed. We can use random sampling with a fixed seed against Python's own pow(a, -1, m), math.gcd and brute-force residues. Keeping tests in a function means you can re-run them after every edit.

Python
import random

def run_tests(seed=1, rounds=500):
    rng = random.Random(seed)
    for _ in range(rounds):
        a, m = rng.randrange(1, 10_000), rng.randrange(2, 10_000)
        if math.gcd(a, m) == 1:
            assert mod_inverse(a, m) == pow(a, -1, m)
        else:
            try:
                mod_inverse(a, m)
            except ValueError:
                pass
            else:
                raise AssertionError("inverse should not exist")
    return "all tests passed"

This final snippet is read-only because it depends on the functions from the earlier steps; paste it under them in one editor to run it.

Ideas to extend the project

  • Add Euler's totient ฯ†(n) and check Euler's theorem a^ฯ†(n) โ‰ก 1 (mod n) for all coprime a with n up to 200.
  • Implement the Miller-Rabin primality test and use it to pick larger primes for the toy RSA.
  • Add a discrete logarithm finder by brute force (baby-step giant-step is a good upgrade) and attack a small Diffie-Hellman exchange.
  • Write a command-line style menu function that takes text such as inv 7 40 or crt 2 3 3 5 and prints the answer.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. When does a have a modular inverse modulo m?

    a * x = 1 (mod m) is solvable exactly when a and m are coprime. Otherwise every multiple of a shares a factor with m.
  2. 2. How does the extended gcd give the inverse?

    Reducing ax + my = 1 modulo m removes the my term and leaves ax = 1, so x mod m is the inverse.
  3. 3. How many solutions modulo 15 does 6x = 9 have?

    gcd(6, 15) = 3 divides 9, so there are 3 solutions modulo 15, spaced 15/3 = 5 apart: 4, 9 and 14.
  4. 4. Why is square-and-multiply fast?

    Each loop step handles one bit of the exponent, so even a huge exponent takes a number of steps proportional to its number of bits.
  5. 5. Why can the toy RSA in this project be broken at once?

    Once an attacker factors n into p and q, they can compute phi and the private exponent with the same inverse function used to make the keys.

Summary

  • Extended gcd returns x and y with ax + by = gcd(a, b); test the identity rather than specific coefficients.
  • An inverse of a modulo m exists exactly when gcd(a, m) = 1, and it comes straight from the extended gcd.
  • Linear congruences have either no solutions or gcd(a, m) of them; CRT merges congruences two at a time and can even detect inconsistent systems.
  • Square-and-multiply makes huge modular powers cheap, matching Python's three-argument pow.
  • Toy RSA is these four tools in a row; small moduli fall to trial division, so it is never for real security.

Next: Project: Exam Scheduler with Graph Coloring.