Chapter 2 — Discrete mathematics | Engineering Cryptography and trust services

Open, free learning for anyone who wants to protect people and technology. No account is required to read this text or its worked answers.

Chapter 2 — Discrete mathematics

Lesson map

Lesson 02 published. Map, example, EX004.

flowchart TD
  N0["Learning outcomes"]
  N1["2.1 Clock arithmetic"]
  N2["2.2 Inverses and Fermat"]
  N3["Lab — Toy modular arithmetic"]
  N4["2.3 Reading the toy"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5
  N5 --> EX["Worked example"]
  EX --> Q["Exercise EX004"]

Logical drawing

flowchart LR
  N0["Learning outcomes"]
  N1["2.1 Clock arithmetic"]
  N2["2.2 Inverses and Fermat"]
  N3["Lab — Toy modular arithmetic"]
  N4["2.3 Reading the toy"]
  N5["Synthesis"]
  N0 --> N1 --> N2 --> N3 --> N4 --> N5 --> Q["EX004"]

[Learning outcomes]
    |
    v
[2.1 Clock arithmetic]
    |
    v
[2.2 Inverses and Fermat]
    |
    v
[Lab — Toy modular arithmetic]
    |
    v
[2.3 Reading the toy]
    |
    v
[Synthesis]
    |
    v
[Worked example] --> [Exercise EX004]

Learning outcomes

You will (1) compute with modular arithmetic; (2) explain why modular inverses and Fermat's little theorem matter to public-key systems; (3) recognise why toy examples must never become real keys.

2.1 Clock arithmetic

Modular arithmetic works like a clock: numbers wrap around after reaching the modulus. Seventeen hours after 9 o'clock is 2 o'clock because 26 mod 24 equals 2. Public-key cryptography lives in this world. Aiyana practises addition, multiplication and exponentiation modulo n, and learns that Python's three-argument pow(b, e, n) computes b^e mod n efficiently by repeated squaring, without ever building the huge intermediate number. The Handbook of Applied Cryptography, chapter 2, collects these number-theoretic tools and is free online, which makes it her reference for definitions such as greatest common divisor and multiplicative inverse.

2.2 Inverses and Fermat

A number e has an inverse modulo m when gcd(e, m) = 1; the inverse d satisfies e × d mod m = 1, and the extended Euclidean algorithm finds it. Fermat's little theorem says that for a prime p and a not divisible by p, a^(p-1) mod p = 1. Together with Euler's generalisation, these facts explain why the textbook RSA construction can reverse an exponentiation with a second exponent. Aiyana treats this as understanding, not engineering: RFC 8017 shows that real RSA needs padding schemes such as OAEP and PSS, because the bare textbook operation leaks structure and is insecure.

Lab — Toy modular arithmetic

"""Modular arithmetic facts behind public-key cryptography, on toy numbers (never a real key)."""
from math import gcd
p, q = 61, 53            # textbook-sized primes, far too small for any real use
n, phi = p * q, (p - 1) * (q - 1)
e = 17

def main():
    d = pow(e, -1, phi)  # modular inverse (Python 3.8+)
    print(f"n={n} phi={phi} gcd(e,phi)={gcd(e, phi)} d={d} (e*d mod phi = {e * d % phi})")
    m = 65
    c = pow(m, e, n)
    print(f"toy m={m} -> c={c} -> back {pow(c, d, n)}")
    print(f"Fermat check: 7^(61-1) mod 61 = {pow(7, 60, 61)}")

if __name__ == "__main__":
    main()

Run with python3 lab_modular.py. Verified output:

n=3233 phi=3120 gcd(e,phi)=1 d=2753 (e*d mod phi = 1)
toy m=65 -> c=2790 -> back 65
Fermat check: 7^(61-1) mod 61 = 1

2.3 Reading the toy

With primes 61 and 53 the modulus is 3233 and phi is 3120. The exponent 17 shares no factor with 3120, so its inverse exists and equals 2753, and 17 × 2753 mod 3120 is 1. Raising 65 to the 17th power gives 2790, and raising 2790 to 2753 returns 65. Fermat's check prints 1 for 7^60 mod 61. Aiyana writes in red in her notes that these numbers can be factored instantly by hand, there is no padding and no randomness, and that Ridgeway will use vetted libraries implementing FIPS 186-5 or RFC 8032 signatures instead. Real RSA moduli today are at least 2048 bits, and key generation is left to audited libraries.

Worked example

Aiyana computes the inverse of 17 modulo 3120, verifies Fermat's theorem for 7 and 61, and explains why the same arithmetic with real-sized numbers still needs standard padding.

Synthetic case. The primes and message are textbook toys; RFC 8017 and FIPS 186-5 are the real standards.

Errors and limits

Toy RSA is a teaching device. Copying it into software, even with large primes, produces an insecure system without padding, side-channel care and vetted key generation.

Exercises

EX004 — Inverse condition. When does an inverse of e modulo m exist? Rubric: 3 = when gcd(e, m) = 1;; 2 = coprime stated loosely;; 1 = always;; 0 = none.
EX005 — Toy values. From the lab, give d and the ciphertext of 65. Rubric: 3 = d = 2753, c = 2790;; 2 = one;; 1 = other numbers;; 0 = none.
EX006 — Why padding. Why is textbook RSA unsafe even with large primes? Rubric: 3 = no padding or randomness leaks structure; RFC 8017 requires OAEP/PSS;; 2 = "too simple";; 1 = it is safe;; 0 = none.

Synthesis

Modular arithmetic, inverses and Fermat's theorem explain public-key mathematics, but real systems rely on standardised schemes and vetted libraries.

Continue studying — chapter 02 of 50

← Chapter 01 (draft) · Course chapter index · Chapter 03 (draft) →