Step 1: Key Generation
Choose two large primes p and q, compute n = p×q and φ(n) = (p-1)(q-1)
Step 2: Choose e
Select e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
Step 3: Calculate d
Compute d as the modular inverse of e modulo φ(n)
Step 4: Encrypt
C ≡ M^e (mod n) using public key (e, n)
Step 5: Decrypt
M ≡ C^d (mod n) using private key (d, n)
Trapdoor Function
Easy to compute e and n, but hard to factorize n without knowing p and q
Key Strength
Security depends on the difficulty of factoring large numbers (2048+ bit keys recommended)
Public Distribution
Public key can be shared openly; only private key must be kept secret
Padding Required
Textbook RSA is vulnerable to attacks; OAEP padding is recommended
The RSA Trap Door
For Encryption: C ≡ M^e (mod n)
Easy to compute with public key (e, n)
For Decryption: M ≡ C^d (mod n)
Easy if you know d, but hard without factoring n
Why it works: M^(ed) ≡ M (mod n) by Euler's theorem
Since ed ≡ 1 (mod φ(n)), we have M^(ed) ≡ M^(1) ≡ M (mod n)
Public Information
• n (modulus)
• e (public exponent)
• Anyone can use (e, n) to encrypt
Secret Information
• p, q (primes)
• d (private exponent)
• Only owner can decrypt with (d, n)
Important Notes
• In practice, p and q are extremely large (512+ bits each)
• Messages are padded with OAEP (Optimal Asymmetric Encryption Padding)
• This prevents chosen plaintext attacks
• The example uses small primes for educational purposes
HTTPS/TLS
Used for secure web communication and certificate authentication
Email Security
PGP and S/MIME use RSA for encryption and digital signatures
Digital Signatures
Authenticates documents and ensures non-repudiation
Blockchain
Bitcoin and other cryptocurrencies use RSA variants for key derivation
1024-bit (Deprecated)
No longer considered secure; factored in 2009
2048-bit (Current Standard)
Secure until 2030; widely used for HTTPS
4096-bit (Future-Proof)
Recommended for long-term security
Post-Quantum Alternatives
NIST standardizing quantum-resistant algorithms