Public-Key Math Essentials

• Invertible really means "division works"
• Extended GCD -> inverse -> linear congruence
• CRT combine step with numbers
• Euler/Fermat/Carmichael -> RSA
• Pitfalls + big.Int

Invertible (no heavy formalism)

• a is invertible mod n if there exists b: a*b \equiv 1 (mod n)
• Invertible values are exactly the coprimes
• These are the units \(\mathbb{Z}_n^*\), count = \(\varphi(n)\)

Extended GCD -> inverse

If gcd = 1, then:

So x mod b is the inverse.

Worked inverse (negative normalize)

56^{-1} mod 15:

• Extended GCD gives 56(-4) + 1515 = 1
• x = -4, normalize: -4 mod 15 = 11
• 11*11 = 121 \equiv 1 (mod 15)

Linear congruence example

Solve 14 x \equiv 30 (mod 100):

• g = gcd(14,100) = 2 divides 30
• 7 x \equiv 15 (mod 50)
• 7^{-1} mod 50 = 43
• x \equiv 45 (mod 50)
• Two solutions mod 100: x = 45, 70

CRT combine step (numbers)

Solve:

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

Compute M=105, M1=35, M2=21, M3=15, (t1,t2,t3)=(2,1,1).

Euler/Fermat/Carmichael

If gcd(a,n)=1:

For RSA n = p*q:

RSA correctness (sketch)

Then m^{ed} \equiv m (mod p, q) and CRT gives (mod n).

RSA parameters

• Need gcd(e, phi) = 1 so d exists
• e commonly 65537
• lambda(n) is tighter than phi(n)
• Toy RSA is insecure without padding

Pitfalls + big.Int

• Non-coprime inputs break inverses/CRT
• Normalize negatives: (x % m + m) % m
• Use big.Int when products overflow 64-bit

What you will build

• Extended GCD
• Modular inverse
• CRT solver
• Toy RSA math