First, we need to select two distinct prime numbers (p and q).
Compute n = p × q and φ(n) = (p-1) × (q-1)
Select e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
Find d such that d × e ≡ 1 mod φ(n)
(e, n)
(d, n)
Note: In real RSA, messages are converted to numbers first.
To encrypt message m, compute:
c ≡ me mod n
To decrypt ciphertext c, compute:
m ≡ cd mod n
Euler's theorem guarantees that for any message m:
mφ(n) ≡ 1 mod n
Since e × d ≡ 1 mod φ(n), we have:
(me)d ≡ me×d ≡ mkφ(n)+1 ≡ (mφ(n))k × m ≡ m mod n