Proof
p, q is prime numbern = pq
φ(n) = (p-1)(q-1)
aφ(n)+1 = a (mod n)
case 1) gcd(a,n) = 1
By euler theorem aφ(n)+1= a (mod n)
case 2) gcd(a,n) ≠ 1
a = p or q ( for n = pq )
let a = q
by fermat theorem qp-1 = 1 (mod p)
aφ(n)+1 = qφ(n)+1 = q(p-1)(q-1)+1 = q(p-1)(q-1) * q = 1(q-1) * q = q = a (mod p)
aφ(n)+1 = qφ(n)+1 = 0 = q = a (mod q)
By Chinese Remainder Theorem
gcd(p, q) = 1
aφ(n)+1 = a (mod p)
aφ(n)+1 = a (mod q)
then aφ(n)+1 = a (mod p * q) = a (mod n)
By euler theorem aφ(n)+1= a (mod n)
case 2) gcd(a,n) ≠ 1
a = p or q ( for n = pq )
let a = q
by fermat theorem qp-1 = 1 (mod p)
aφ(n)+1 = qφ(n)+1 = q(p-1)(q-1)+1 = q(p-1)(q-1) * q = 1(q-1) * q = q = a (mod p)
aφ(n)+1 = qφ(n)+1 = 0 = q = a (mod q)
By Chinese Remainder Theorem
gcd(p, q) = 1
aφ(n)+1 = a (mod p)
aφ(n)+1 = a (mod q)
then aφ(n)+1 = a (mod p * q) = a (mod n)
Generate Key
1. prime p,q2. n = p * q
3. select e (commonly 65537 = 0x10001)
4. calculate d
e * d = 1 (mod φ(n))
5. n, e is public key
6. d is private key
Encrypt
me = c (mod n)
Decrypt
cd = me*d = mkφ(n) + 1 = m (mod n)
Sign
md = s (mod n)
Verify
me = me*d = mkφ(n) + 1 = m (mod n)
