Public-Key Math Essentials

Why this module exists

Public-key crypto is built on modular arithmetic, not magic. If you cannot compute inverses, solve congruences, or reason about Euler's totient, you will struggle to review or implement RSA, Diffie-Hellman, or elliptic-curve systems. This module builds the math toolkit every serious crypto engineer needs.

We keep formalism light but precise: you should be able to derive every step from extended GCD to RSA correctness and recognize when the math breaks.

1) Invertible really means "division works"

In \(\mathbb{Z}_n\), we say a is invertible modulo n if there exists b such that:

That b is the modular inverse. The invertible values are exactly the numbers coprime to n. These invertible values are called units and form a multiplicative group \(\mathbb{Z}_n^*\). The count of units is \(\varphi(n)\).

Takeaway: "invertible" is not a vibe; it means you can multiply by b to undo a.

2) Extended GCD -> inverse (full derivation)

The extended Euclidean algorithm returns x, y such that:

If gcd(a, b) = 1, then:

Reducing mod b gives:

So x mod b is the inverse of a mod b.

Worked example (includes negative normalization)

Find 56^{-1} mod 15.

Run extended GCD:

• 56 = 3*15 + 11
• 15 = 1*11 + 4
• 11 = 2*4 + 3
• 4 = 1*3 + 1

Back-substitute:

So x = -4. Normalize:

Check: 56 \equiv 11 (mod 15), and 11*11 = 121 \equiv 1 (mod 15).

3) Linear congruences -> solvability and solutions

We want to solve:

Let g = gcd(a, m). Then:

• If g does NOT divide b: no solutions.
• If g divides b: divide through by g and solve with an inverse.

When solutions exist, there are exactly g distinct solutions modulo m:

Worked example

Solve 14 x \equiv 30 (mod 100).

• gcd(14, 100) = 2 divides 30
• Divide by 2: 7 x \equiv 15 (mod 50)
• 7^{-1} mod 50 = 43 (since 7*43 = 301 \equiv 1)
• x \equiv 15*43 = 645 \equiv 45 (mod 50)

Two solutions mod 100:

So x \equiv 45 or 95 (mod 100). Check: 1445 = 630 and 1495 = 1330, both congruent to 30. Using 70 would give 80, so dividing the reduced modulus by g a second time is incorrect.

4) CRT combination (full combine step)

Given pairwise-coprime moduli:

Let M = m1m2...*mk. Define:

• Mi = M / mi
• ti = Mi^{-1} mod mi

Then a solution is:

Worked example

Solve:

• x \equiv 2 (mod 3)
• x \equiv 3 (mod 5)
• x \equiv 2 (mod 7)

Compute:

• M = 105
• M1=35, t1 = 35^{-1} mod 3 = 2
• M2=21, t2 = 21^{-1} mod 5 = 1
• M3=15, t3 = 15^{-1} mod 7 = 1

Then:

Normalize:

So x \equiv 23 (mod 105). If you ever compute a negative value, normalize with:

Non-coprime moduli

If gcd(m1, m2) = g, a solution exists only when r1 \equiv r2 (mod g). When it exists, the solution is modulo lcm(m1, m2).

5) Euler, Fermat, Carmichael -> why RSA works

Euler's totient counts units. For distinct primes p, q:

Euler's theorem (units only):

Fermat is the prime special case: \(a^{p-1} \equiv 1 \pmod{p}\).

The Carmichael function \(\lambda(n)\) is the exponent of \(\mathbb{Z}_n^*\). For RSA with n = p*q:

RSA correctness sketch

RSA chooses e and d such that:

For any message m < n:

• Work mod p and mod q separately.
• If m \equiv 0 (mod p), the statement is trivial.
• Otherwise Euler/Fermat gives m^{ed} \equiv m (mod p).
• Same for q.
• CRT combines the two into m^{ed} \equiv m (mod n).

6) RSA parameter choices (what matters)

• e must be coprime to \(\varphi(n)\) (or \(\lambda(n)\)) so the inverse d exists. If gcd(e, phi) != 1, you do not have a private key.
• In practice, e is often 65537 for efficiency and security balance.
• \(\lambda(n)\) is tighter than \(\varphi(n)\) and is commonly used in proofs.

Toy security caveats

• Tiny primes are trivially factorable.
• "Textbook RSA" (no padding) is malleable and deterministic.
• Small e without padding can leak plaintext (low-exponent attacks).
• Real RSA uses randomized padding (e.g., OAEP) and large primes.

7) Modular exponentiation (square-and-multiply)

Public-key crypto is dominated by modular exponentiation. The standard algorithm:

result = 1
while exp > 0:
  if exp is odd: result = (result * base) mod n
  base = (base * base) mod n
  exp >>= 1

This runs in O(log exp) multiplications. For large moduli, use big integers and constant-time variants to avoid side-channels.

8) Practical pitfalls (and when to use big.Int)

• Non-coprime inputs: inverses and CRT fail silently if gcd != 1.
• Negative residues: normalize with (x % m + m) % m.
• Overflow: a*b can overflow even if a and b fit 64-bit.
  • Switch to big.Int when m or intermediate products can exceed 2^63-1.
  • Use big.Int for RSA/DH-sized moduli (hundreds to thousands of bits).
• Wrong modulus for inverses: RSA uses phi(n) or lambda(n), not n.

What you will build

1. Extended GCD: compute Bezout coefficients and gcd.
2. Modular inverse: find inverses or detect failure.
3. CRT solver: combine congruences into one solution.
4. Toy RSA math: compute n and d from p, q, e.

Key takeaways

• "Invertible" means there exists b with ab \equiv 1 (mod n).
• Extended GCD gives inverses; inverses solve linear congruences.
• CRT is the combine step that stitches congruences together.
• RSA correctness follows from Euler/Fermat plus CRT.
• Use big.Int before you overflow.