Key generation
Pick primes p, q. n = p·q. φ(n) = (p-1)(q-1). Pick e coprime to φ(n). d = e^(-1) mod φ(n).
Advertisement
Encryption/decryption
c = m^e mod n. m = c^d mod n. Works via Euler: m^(ed) = m^(1 + k·φ(n)) = m · m^(k·φ(n)) = m mod n.
Advertisement
Padding
Textbook RSA is broken. Use OAEP (encryption) or PSS (signing). Padding schemes prevent chosen-ciphertext attacks.
Security
Assumes integer factorization hard. Shor's algorithm breaks in polynomial time on quantum computer. Migrate to post-quantum.