Numbers
RSA encryption
Multiply two big primes — easy. Factor the result back — practically impossible.
RSA is public-key encryption: anyone can encrypt with your public key; only you can decrypt with the private key.
Setup
- Pick two large primes p and q.
- n = p·q is your public modulus.
- Compute φ(n) = (p−1)(q−1).
- Pick e coprime to φ(n); find d with ed ≡ 1 mod φ(n).
- Public key: (n, e). Private key: d.