Modular arithmetic and RSA

Congruence

a is congruent to b modulo m, written a ≡ b (mod m), when m divides a − b; that is, when a and b leave the same remainder after division by m. 17 ≡ 5 (mod 12): 5 o'clock and 17:00 are the same on a clock.

You can add, subtract and multiply before or after taking remainders and get the same answer:

(a + b) mod m = ((a mod m) + (b mod m)) mod m
(a × b) mod m = ((a mod m) × (b mod m)) mod m

That keeps numbers small: the last digit of 7¹⁰⁰ can be found mod 10 without ever writing 7¹⁰⁰ down. Hash tables, check digits on bank cards and the "mod 1000000007" of contest problems all use this.

Inverses

The inverse of a mod m is a number x with a × x ≡ 1 (mod m): the "division" of modular arithmetic. 3 × 5 = 15 ≡ 1 (mod 7), so 5 is the inverse of 3 mod 7.

An inverse exists exactly when gcd(a, m) = 1. The extended Euclidean algorithm finds it: besides the gcd, it finds x and y with a x + m y = gcd(a, m) (Bézout's identity). When the gcd is 1, a x ≡ 1 (mod m), so x is the inverse.

def extended_gcd(a, b):
    """Returns (g, x, y) with a*x + b*y == g == gcd(a, b)."""
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y

def inverse(a, m):
    g, x, _ = extended_gcd(a, m)
    return x % m if g == 1 else None

print("3⁻¹ mod 7 =", inverse(3, 7))
print("17⁻¹ mod 3120 =", inverse(17, 3120))
print("4⁻¹ mod 10 =", inverse(4, 10))
print("check:", 17 * inverse(17, 3120) % 3120)

Fast powers

To compute a^e mod m with a huge e, do not multiply e times. Square and multiply: write e in binary; square a once per bit, and multiply the squares that belong to the 1 bits. That takes about log₂ e steps: 2000 instead of 10⁶⁰⁰ for a 2048-bit e. Python's pow(a, e, m) does exactly this.

Fermat's little theorem: if p is prime and p does not divide a, then a^p−1 ≡ 1 (mod p). So pow(a, p − 2, p) is a's inverse mod p, a favourite trick in contests.

RSA

RSA (Rivest, Shamir and Adleman, 1977) lets anyone encrypt a message that only you can read.

1. Pick two big primes p and q, and let n = p q.
2. Let φ = (p − 1)(q − 1).
3. Pick e with gcd(e, φ) = 1. The public key is (n, e): publish it.
4. Let d = e⁻¹ mod φ. The private key is d: keep it secret.
5. To encrypt a number m < n: c = m^e mod n. To decrypt: m = c^d mod n.

Decryption works because e d ≡ 1 (mod φ), and a theorem of Euler (a generalization of Fermat's) then gives m^{e d} ≡ m (mod n).

p, q = 61, 53
n = p * q                      # 3233, public
phi = (p - 1) * (q - 1)        # 3120, secret
e = 17                         # public: gcd(17, 3120) = 1
d = pow(e, -1, phi)            # 2753, the private key

message = 65
cipher = pow(message, e, n)    # anyone can do this
back = pow(cipher, d, n)       # only the owner of d can do this

print("public key:", (n, e), " private key:", d)
print("message", message, "-> encrypted", cipher, "-> decrypted", back)

With p = 61 and q = 53, as in the textbooks, anyone could factor n = 3233. Real keys use primes of about 300 digits, and the best known methods would take longer than the age of the universe to factor n. RSA is safe only as long as factoring is hard.

Mark lesson complete