InfoSec 3001 — Information Security from the Offensive Perspective

Step 227. Math Foundations: Modular Arithmetic, the Euclidean Algorithm, Euler’s Theorem — Crypto’s Minimum Armament

Step 227. Math Foundations: Modular Arithmetic, the Euclidean Algorithm, Euler’s Theorem — Crypto’s Minimum Armament

Level 3 — Real-World CTF & Advanced Offensive Skills | Difficulty ★★☆☆☆ | Estimated time: 3 hours

Prerequisites: basic Python at the level of Step 90 (encoding and XOR). For math, middle-school division is enough — you’ll build the rest today.

⚠️ All exercises in this chapter are for your own lab and legal platforms only. Applying them to unauthorized systems is a crime.

  • What you need: Python 3 (measured: 3.12.14), paper and pen (for hand calculations).
  • Caution: today’s exercises are 100% safe. You only compute.

Day one of the Crypto track. All of modern cryptography is "arithmetic in the mod n world" — multiplying, exponentiating, and even "dividing" in a world where only remainders remain. The three things you learn today — modular arithmetic, the Euclidean algorithm, Euler’s theorem — are every component that makes up next chapter’s RSA. If it feels hard, that’s normal. In return, you’ll verify every formula today twice: once by hand, once in Python.

1. Learning Objectives

By the end of this chapter, you will be able to:

  • Understand modular arithmetic as "clock arithmetic" and compute with Python’s % and pow(a, b, n)
  • Find greatest common divisors with the Euclidean algorithm, by hand and in code
  • Find the x, y of ax + by = gcd(a,b) with the extended Euclidean algorithm
  • Explain that a modular inverse is "division in the mod world," and cross-check pow(a, -1, n) against your own implementation
  • Internalize Euler’s theorem a^φ(n) ≡ 1 (mod n) through experiment

2. Background Knowledge — Today’s Tools and Concepts

Today’s Tools at a Glance

Category Details
Language/environment Python 3 (measured: 3.12.14) — standard library only, nothing to install
Today’s commands %, pow(a, b, n), pow(a, -1, n), hand-rolled gcd() / egcd()
Concepts needed mod operation, greatest common divisor (gcd), coprimality, modular inverse, Euler’s φ(n), Euler’s theorem
Today’s deliverables Hand-calculation notes + an inverse calculator (your implementation) + Euler’s theorem experiment output

2-1. The mod Operation — Clock Arithmetic

a mod n is "the remainder when a is divided by n." A clock is a good example — 13:00 plus 2 hours is not 15:00 but 3:00. (13 + 2) mod 12 = 3. In the mod world, addition, subtraction, and multiplication all mean "do it, then take the remainder after dividing by n."

Why does crypto use it? Two properties. ① Results are trapped in 0 to n-1, so numbers never explode. ② It enables operations that are hard to reverse — a^k mod n is fast to compute, but finding k from the result (the discrete logarithm) is practically impossible for large numbers.

2-2. The Euclidean Algorithm — A Highway to the GCD

The greatest common divisor (gcd) is the largest number that divides both. The Euclidean algorithm finds it through repeated division alone:

gcd(a, b) = gcd(b, a mod b)  — when b becomes 0, a is the answer

A 2,300-year-old algorithm still runs inside every RSA key generation today. Because it’s fast (numbers shrink exponentially) and it always terminates.

2-3. Modular Inverse — Division in the mod World

In ordinary arithmetic, "divide by 3" is "multiply by 1/3." The mod world has this too. A modular inverse is the x such that a × x ≡ 1 (mod n) — the partner that multiplies to 1. The inverse of 3 mod 11 is 4 (3 × 4 = 12 ≡ 1).

An inverse exists only when a and n are coprime (gcd is 1). And the tool for finding it is the extended Euclidean algorithm — while computing the gcd, it finds as a bonus the x, y satisfying ax + by = gcd(a, b). If they’re coprime, gcd=1, so ax + ny = 1, i.e., ax ≡ 1 (mod n) — x is the inverse itself. RSA’s private key d is made with exactly this inverse.

2-4. Euler’s Theorem — The Cycle of Exponentiation

Euler’s φ(n) (the phi function) is "the count of numbers from 1 to n that are coprime with n." For a prime p, φ(p) = p – 1 (all of 1 to p-1 are coprime with it); for a product of two primes n = pq, φ(n) = (p-1)(q-1).

Euler’s theorem: if a and n are coprime, a^φ(n) ≡ 1 (mod n). It means exponentiation always cycles back to 1 after φ(n) turns. The special case for a prime p, a^(p-1) ≡ 1 (mod p), is Fermat’s little theorem. This theorem is exactly why RSA decryption works — you’ll use it precisely in the next chapter.

3. Follow Along

All output in this chapter was measured 2026-09-09 on Python 3.12.14.

3-1. Getting a Feel for Modular Arithmetic

print(17 % 5)          # remainder of 17 divided by 5
print((-7) % 5)        # Python gives positive remainders even for negatives
print((13 + 9) % 12)   # clock arithmetic: 13:00 + 9 hours
print(pow(7, 3, 11))   # 7^3 mod 11 — the three-argument pow
print(7**3, 343 % 11)  # cross-check: exponentiating first gives the same result

2
3
10
2
343 2

How to read the output: you confirmed three things. ① The remainder always lands in 0 to n-1. ② Python gives the positive value 3 for -7 % 5 (this differs across languages, so we standardize on Python). ③ pow(7, 3, 11) equals 7<strong>3 % 11, but for large numbers only the former is possible — because it keeps taking remainders along the way instead of materializing 7³ = 343 first. A hundred-digit exponentiation will exhaust memory via 7</strong>e. In crypto, it’s always the three-argument pow.

3-2. The Euclidean Algorithm — Once by Hand, Once in Code

By hand first. Find gcd(1071, 462):

1071 = 462 × 2 + 147
 462 = 147 × 3 + 21
 147 =  21 × 7 + 0    ← remainder 0 → the answer is 21

Now in code:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(1071, 462))

21

How to read it: the three hand divisions correspond exactly to three turns of the while loop. The single line a, b = b, a % b is all there is to "the larger number’s slot gets the smaller one; the smaller’s slot gets the remainder," repeated. The paper calculation transcribed verbatim — watch the moment math becomes code with your own eyes.

3-3. Extended Euclidean — The Source of Inverses

Now the version that also finds the x, y of ax + by = gcd(a, b).

def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

g, x, y = egcd(1071, 462)
print(f"g={g}, x={x}, y={y}")
print("check:", 1071 * x + 462 * y)

g=21, x=-3, y=7
check: 21

How to read the output: 1071 × (-3) + 462 × 7 = 21 holds. The recursion "descends until the remainder hits 0, then assembles x and y on the way back up." It’s fine if the mechanics don’t click yet — what you need now is the fact that "this function manufactures inverses," and you’ll verify that in the next step.

3-4. Modular Inverse — My Implementation vs the Built-in

Let’s find the inverse of 3 mod 11. The x that egcd(3, 11) returns is the inverse (3 and 11 are coprime).

g, x, _ = egcd(3, 11)
inv = x % 11                    # x can come out negative, so normalize to positive
print("mine:", inv)
print("check: 3 ×", inv, "mod 11 =", (3 * inv) % 11)
print("built-in:", pow(3, -1, 11))  # built-in inverse, Python 3.8+

mine: 4
check: 3 × 4 mod 11 = 1
built-in: 4

How to read the output: the answer from your egcd (4) matches Python’s built-in pow(3, -1, 11), and the cross-check 3 × 4 = 12 ≡ 1 (mod 11) passes too. You now own "division in the mod world." The computation that creates RSA’s private key d is exactly this one line.

3-5. Euler’s Theorem Experiment

Don’t believe the theorem — experiment. Check the Fermat’s-little-theorem form (a^(p-1) ≡ 1) at prime p = 11, and the general form at composite n = 15 (φ = 8).

p = 11
for a in [2, 5, 7, 10]:
    print(f"pow({a}, 10, 11) =", pow(a, p - 1, p))

def gcd(a, b):
    while b: a, b = b, a % b
    return a

n = 15            # φ(15) = (3-1)(5-1) = 8
for a in [2, 4, 7, 8]:
    if gcd(a, 15) == 1:
        print(f"pow({a}, 8, 15) =", pow(a, 8, 15))

pow(2, 10, 11) = 1
pow(5, 10, 11) = 1
pow(7, 10, 11) = 1
pow(10, 10, 11) = 1
pow(2, 8, 15) = 1
pow(4, 8, 15) = 1
pow(7, 8, 15) = 1
pow(8, 8, 15) = 1

How to read the output: change a all you want — it’s always 1. The data in front of you says exponentiation cycles at φ(n) as long as the coprimality condition holds. Add one thing and this becomes RSA: choose e and d so their product is a multiple of φ(n) plus 1 (e×d ≡ 1 (mod φ(n)) — in other words, d is e’s inverse), and m^(e×d) ≡ m (mod n). Encrypt (raise to e) and decrypt (raise to d), and you’re back at the original m. The next chapter turns this sentence into code.

4. Missions & Exercises

Mission — Your Own Inverse Calculator

  1. Using egcd(), complete an "inverse calculator" function modinv(a, n) — if an inverse exists, normalize it to positive and return it; if not (gcd ≠ 1), return "no inverse"
  2. Build a comparison table of your function’s results vs pow(a, -1, n) for these three pairs: (3, 11), (7, 26), (6, 15) — the third has no inverse
  3. On paper, rewrite the Euclidean process for gcd(1071, 462) by hand and match it line by line against the code’s output

Exercises

Exercise 1. Solve 38 mod 12 as clock arithmetic. Then predict and verify Python’s result for the negative -3 % 8.

Exercise 2. Find gcd(252, 105) by hand with the Euclidean algorithm. How many divisions does it take?

Exercise 3. Explain the sentence "a modular inverse is division in the mod world" by working through solving 7x ≡ 1 (mod 26).

Exercise 4. Verify φ(15) = 8 by counting directly (list the numbers from 1 to 15 coprime with 15), then compute φ(21). Hint: 21 = 3 × 7.

5. Model Answers & Completion Criteria

Mission Model Answer

def egcd(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = egcd(b, a % b)
    return (g, y1, x1 - (a // b) * y1)

def modinv(a, n):
    g, x, _ = egcd(a % n, n)
    if g != 1:
        return "no inverse"
    return x % n

The comparison table’s results (measured 2026-09-09): (3, 11) → 4 / 4 match, (7, 26) → 15 / 15 match, (6, 15) → "no inverse" / the built-in raises ValueError: base is not invertible for the given modulus. 6 and 15 have gcd 3, so no inverse exists — the moment the coprimality condition actually bites.

How to verify: ① do your function and the built-in reach the same conclusion on all three pairs? ② did you explain the "none" for (6, 15) via the gcd? ③ do the hand divisions correspond one-to-one with the code’s while iterations?

Exercise Answers

Answer 1. 38:00 goes around 12 twice (24) to 14, and one more lap back gives 2 — 38 mod 12 = 2. -3 % 8 is 5 in Python (Python always gives remainders as positive values in 0 to n-1; -3 + 8 = 5).

Answer 2. 252 = 105×2 + 42 → 105 = 42×2 + 21 → 42 = 21×2 + 0. Three divisions; the gcd is 21. Check it in code with gcd(252, 105) — the same 21 comes out.

Answer 3. In ordinary arithmetic, if 7x = 1 then x = 1/7. In mod 26, instead of 1/7 you look for "the number that multiplies with 7 to give 1" — that’s the inverse. egcd(7, 26) gives 7×15 + 26×(-4) = 1, so x = 15. Cross-check: 7×15 = 105 = 26×4 + 1 ≡ 1 (mod 26). So in the mod-26 world, dividing by 7 is multiplying by 15.

Answer 4. Numbers coprime with 15 (from 1 to 15): 1, 2, 4, 7, 8, 11, 13, 14 — 8 of them, matching φ(15) = 8 = (3-1)(5-1). φ(21) = (3-1)(7-1) = 2 × 6 = 12.

Completion Criteria Checklist

  • [ ] I can explain mod as clock arithmetic and use pow(a, b, n)
  • [ ] I know negative mods come out positive in Python
  • [ ] I found gcd(1071, 462) by hand and matched it against the code
  • [ ] I found an inverse with egcd and confirmed it matches pow(a, -1, n)
  • [ ] I can state the condition for an inverse to exist (coprimality)
  • [ ] I confirmed Euler’s theorem through experiment output
  • [ ] Mission: I completed modinv and built the three-pair comparison table

6. Common Pitfalls & Fixes

Wall 1. ValueError: base is not invertible from pow(a, -1, n)

Symptom: ValueError: base is not invertible for the given modulus (measured 2026-09-09, pow(3, -1, 15)).
Cause: a and n aren’t coprime (gcd(3, 15) = 3). An inverse exists only for coprime pairs.
Fix: the error is correct behavior — you’ve confirmed "no inverse exists." If that wasn’t intended, you picked a wrong a or n; print the gcd first and check.

Wall 2. egcd’s x comes out negative

Symptom: depending on the implementation, egcd(7, 26) may give x = -11.
Cause: ax + by = 1 has infinitely many solutions, and the recursion may find a negative one first. -11 is also correct (7 × (-11) + 26 × 3 = -77 + 78 = 1, and -77 ≡ 1 (mod 26)).
Fix: normalize into the positive range with % n — -11 % 26 = 15; any solution is the same inverse mod n. The only thing that matters is passing the cross-check (a * x) % n == 1.

Wall 3. Computing with 7</strong>e % n hangs**

Symptom: with a big exponent, it doesn’t finish for minutes or throws a memory error.
Cause: 7**e gets computed in full first — with a large e, the intermediate result explodes to tens of thousands of digits.
Fix: use only pow(7, e, n) from the start. The three-argument pow takes the remainder at every multiplication, keeping numbers below n.

Wall 4. Mistaking φ(n) for "the count of numbers below n"

Symptom: you answer φ(15) = 14.
Cause: you dropped the "coprime" condition. 3, 5, 6, 9, 10, 12, and 15 share factors with 15 and are excluded.
Fix: if n = pq (a product of two primes), don’t count — use the formula: φ(n) = (p-1)(q-1). Counting in code with gcd, as in the Euler experiment, works as a cross-check.

Wall 5. Giving up trying to memorize the formulas

Symptom: Euler’s theorem as a sentence won’t go in.
Cause: theorems aren’t for memorizing — they’re for internalizing through use.
Fix: run the 3-5 experiment five more times with different a and n. See "it’s always 1" five times with your own eyes, and the theorem stops being a sentence and becomes a fact.

7. Summary

Today’s Concepts

Concept One-line explanation
mod operation Arithmetic that keeps only remainders — results trapped in 0 to n-1
Greatest common divisor (gcd) The largest number dividing both — computed fast via the Euclidean algorithm
Coprime Two numbers with gcd = 1 — the condition for an inverse to exist
Modular inverse The x with a × x ≡ 1 (mod n) — division in the mod world
Extended Euclidean Finds the x, y of ax + by = gcd alongside the gcd — the source of inverses
Euler’s φ(n) Count of numbers in 1 to n coprime with n — (p-1)(q-1) for pq
Euler’s theorem If coprime, a^φ(n) ≡ 1 (mod n) — the basis of RSA decryption

Today’s Commands & Code

Command What it does
a % n Remainder — positive even for negatives in Python
pow(a, b, n) Modular exponentiation — the only option for big numbers
pow(a, -1, n) Modular inverse (built-in)
gcd(a, b) (your implementation) The Euclidean algorithm
egcd(a, b) (your implementation) Extended Euclidean — the heart of inverse computation

An Instinct More Important Than Commands

Today’s parts — remainders, gcd, inverses, φ(n) — each look humble, but combined they become the RSA that guards the modern internet. Two instincts in particular are everything for the next chapter: "division in the mod world = multiplication by the inverse" and "exponentiation cycles at φ(n)." Whenever the math feels abstract, experiment with one line of Python — as today, a theorem becomes yours only when confirmed by experiment.

Once every box is checked, Step 227 is complete.

← 이전 스텝
다음 스텝 →