RSA — The Algorithm That Changed Cryptography
Everything we’ve covered so far — DES, 3DES, AES — is symmetric cryptography. Both parties share the same secret key. The sender encrypts with the key, the receiver decrypts with the same key.
But there’s a fundamental problem: how do you share the key in the first place?
If Alice and Bob have never met, and every communication channel between them could be intercepted by Eve, how do they agree on a secret key? You can’t encrypt the key — you’d need another key to encrypt it. It’s a chicken-and-egg problem that plagued cryptography for centuries.
In 1976, Whitfield Diffie and Martin Hellman proposed a revolutionary idea: public-key cryptography. A system where you have two keys — a public key (which everyone can see) and a private key (which only you know). Anyone can encrypt a message with your public key, but only you can decrypt it with your private key.
In 1977, Ron Rivest, Adi Shamir, and Leonard Adleman at MIT turned this idea into a working algorithm: RSA. It was the first practical public-key cryptosystem, and nearly 50 years later, it still underpins much of internet security.
The Key Insight — Trapdoor Functions
RSA is built on a simple but powerful idea: there exist mathematical operations that are easy to do in one direction but extremely hard to reverse — unless you know a secret.
The specific trapdoor in RSA is prime factorization:
- Easy: Multiply two large prime numbers.
p × q = n. A computer can do this in microseconds, even for 1000-digit primes. - Hard: Given
n, findpandq. For sufficiently large numbers (2048+ bits), this is computationally infeasible with current technology.
That asymmetry is the entire foundation of RSA.
The Math We Need
Before we build RSA, we need a few mathematical tools.
Modular Arithmetic
You already know modular arithmetic — it’s clock math. On a 12-hour clock, 10 + 5 = 3 (not 15). We write this as:
15 mod 12 = 3
The mod operation gives the remainder after division. Some examples:
17 mod 5 = 2 (17 = 3×5 + 2)
25 mod 7 = 4 (25 = 3×7 + 4)
100 mod 10 = 0 (100 = 10×10 + 0)
All of RSA’s computations happen modulo some number n. This means we never deal with infinitely large results — everything wraps around.
Prime Numbers
A prime number is divisible only by 1 and itself: 2, 3, 5, 7, 11, 13, …
RSA uses very large primes — typically 1024 bits each (about 309 decimal digits). These are generated randomly and tested for primality using probabilistic tests like Miller-Rabin.
Two numbers are coprime (or relatively prime) if their greatest common divisor is 1. For example, 8 and 15 are coprime (GCD = 1), even though neither is prime.
Euler’s Totient Function
For a positive integer n, Euler’s totient function phi(n) counts how many integers from 1 to n-1 are coprime with n.
For a prime p:
phi(p) = p - 1
Because every number from 1 to p-1 is coprime with a prime.
For the product of two distinct primes n = p × q:
phi(n) = (p - 1)(q - 1)
This is the key formula in RSA. If you know the factorization of n, computing phi(n) is trivial. If you don’t know the factors, computing phi(n) is as hard as factoring n.
Euler’s Theorem
For any integer a that is coprime with n:
a^phi(n) mod n = 1
This leads directly to:
a^(k × phi(n) + 1) mod n = a
In other words, if we raise a to a power that is 1 mod phi(n), we get a back. This is the mathematical foundation of RSA — it’s why encryption and decryption work.
Modular Multiplicative Inverse
The number d is the modular inverse of e modulo phi(n) if:
e × d mod phi(n) = 1
We write this as d = e^(-1) mod phi(n).
This can be computed using the Extended Euclidean Algorithm. The inverse exists if and only if e and phi(n) are coprime (GCD = 1).
RSA Key Generation
Now we have all the math we need. Let’s generate an RSA key pair.
Step 1: Choose Two Large Primes
Pick two large, distinct prime numbers p and q. In practice, each is typically 1024 bits (for RSA-2048) or 2048 bits (for RSA-4096).
For our example, let’s use small primes:
p = 61
q = 53
Step 2: Compute n
n = p × q = 61 × 53 = 3233
This n is the modulus — it appears in both the public and private keys.
Step 3: Compute phi(n)
phi(n) = (p - 1)(q - 1) = 60 × 52 = 3120
Step 4: Choose the Public Exponent e
Choose e such that:
1 < e < phi(n)GCD(e, phi(n)) = 1(e and phi(n) are coprime)
The most common choice is e = 65537 (which is 2^16 + 1). This value is used in nearly all RSA implementations because:
- It’s prime (so it’s coprime with most phi(n) values)
- In binary, it’s
10000000000000001— only two 1-bits, making modular exponentiation fast
For our small example:
e = 17 (GCD(17, 3120) = 1 ✓)
Step 5: Compute the Private Exponent d
Find d such that:
e × d mod phi(n) = 1
17 × d mod 3120 = 1
Using the Extended Euclidean Algorithm:
d = 2753 (because 17 × 2753 = 46801, and 46801 mod 3120 = 1)
The Key Pair
Public Key: (e, n) = (17, 3233) ← Share with everyone
Private Key: (d, n) = (2753, 3233) ← Keep secret!
The security depends on keeping d secret. And d can only be computed if you know phi(n), which requires knowing p and q. Since factoring n into p and q is hard for large numbers, the private key is safe.
After key generation, p and q should be securely deleted. You only need n, e, and d going forward.
RSA Encryption and Decryption
Encryption
To encrypt a message m (where 0 <= m < n):
c = m^e mod n
That’s it. Raise the message to the power e, take the result modulo n. The ciphertext is c.
Decryption
To decrypt ciphertext c:
m = c^d mod n
Raise the ciphertext to the power d, take the result modulo n. You get the original message back.
Why Does This Work?
Decrypt(Encrypt(m)) = (m^e)^d mod n
= m^(e×d) mod n
Since e × d = 1 mod phi(n), we can write e × d = k × phi(n) + 1 for some integer k.
By Euler’s theorem:
m^(k × phi(n) + 1) mod n = m^(k × phi(n)) × m mod n
= (m^phi(n))^k × m mod n
= 1^k × m mod n
= m
The math guarantees that encryption followed by decryption gives back the original message.
Worked Example
Using our keys: public (17, 3233), private (2753, 3233).
Encrypt the message m = 65:
c = 65^17 mod 3233
Computing 65^17 mod 3233 using repeated squaring:
65^1 mod 3233 = 65
65^2 mod 3233 = 4225 mod 3233 = 992
65^4 mod 3233 = 992^2 mod 3233 = 984064 mod 3233 = 2149
65^8 mod 3233 = 2149^2 mod 3233 = 4618201 mod 3233 = 2452
65^16 mod 3233 = 2452^2 mod 3233 = 6012304 mod 3233 = 2195
65^17 = 65^16 × 65^1 mod 3233
= 2195 × 65 mod 3233
= 142675 mod 3233
= 2790
Ciphertext: c = 2790
Decrypt:
m = 2790^2753 mod 3233
This is a massive exponentiation, but the repeated squaring algorithm handles it efficiently. The result:
m = 65 ✓
We get our original message back.
RSA Digital Signatures
RSA isn’t just for encryption — it also enables digital signatures. The operations are reversed:
- Sign:
signature = m^d mod n(use private key) - Verify:
m = signature^e mod n(use public key)
Only the holder of the private key can create a valid signature, but anyone with the public key can verify it. This provides:
- Authentication — The signature proves the message came from the key owner
- Integrity — Any modification to the message invalidates the signature
- Non-repudiation — The signer can’t deny they signed it
In practice, you don’t sign the message directly — you sign a hash of the message:
1. Compute hash: h = SHA-256(message)
2. Sign the hash: signature = h^d mod n
3. Send: message + signature
Verification:
1. Compute hash: h = SHA-256(message)
2. Recover hash from signature: h' = signature^e mod n
3. Compare: h == h'? If yes, signature is valid
Signing the hash instead of the message is both more efficient (the hash is small, fixed-size) and more secure (it avoids mathematical attacks against raw RSA signatures).
Padding — Why Raw RSA is Dangerous
Everything we’ve described so far is called textbook RSA or raw RSA. It’s mathematically correct but insecure in practice. Here’s why:
Problem 1: Deterministic Encryption
Raw RSA is deterministic — the same plaintext always produces the same ciphertext. An attacker who knows you’re encrypting one of a small set of messages (say, “yes” or “no”) can encrypt both, compare with the ciphertext, and determine the message.
Problem 2: Malleability
If an attacker has ciphertext c = m^e mod n, they can compute:
c' = c × 2^e mod n = (m × 2)^e mod n
This produces a valid ciphertext for the message 2m — without knowing m or d. The attacker can manipulate ciphertexts without decrypting them.
Problem 3: Small Message Attacks
If the message m is small and e = 3, then m^3 might be less than n. In that case, the attacker can just compute the regular (non-modular) cube root of the ciphertext to recover m.
The Solution: Padding Schemes
Modern RSA always uses a padding scheme that adds randomness and structure to the message before encryption:
OAEP (Optimal Asymmetric Encryption Padding) — For encryption. Adds randomness and a hash-based mask. Defined in PKCS#1 v2.
Padded message = OAEP_Encode(message, random_seed)
Ciphertext = (Padded message)^e mod n
PSS (Probabilistic Signature Scheme) — For signatures. Adds randomness to make signatures non-deterministic.
PKCS#1 v1.5 — An older padding scheme still widely used. Simpler than OAEP but vulnerable to Bleichenbacher’s attack (a padding oracle attack discovered in 1998). Avoid for new implementations.
The rule: never use raw RSA. Always use OAEP for encryption and PSS for signatures.
Key Sizes and Security
RSA’s security depends on the difficulty of factoring n. As factoring algorithms improve and computers get faster, larger keys are needed.
| RSA Key Size | Security Level (bits) | Status |
|---|---|---|
| 512 bits | ~30 bits | Broken in 1999 |
| 768 bits | ~60 bits | Broken in 2009 (took 2 years) |
| 1024 bits | ~80 bits | Deprecated — factorable with resources |
| 2048 bits | ~112 bits | Current minimum standard |
| 3072 bits | ~128 bits | Recommended for new systems |
| 4096 bits | ~140 bits | High security |
Notice the asymmetry: a 2048-bit RSA key provides only ~112 bits of security, while a 128-bit AES key provides 128 bits. RSA keys need to be much larger than symmetric keys for equivalent security. This is because factoring is easier than brute-force key search.
Comparison with AES
| Symmetric (AES) | Asymmetric (RSA) | Security Level |
|---|---|---|
| 80 bits | 1024 bits | Legacy (broken) |
| 112 bits | 2048 bits | Current minimum |
| 128 bits | 3072 bits | Strong |
| 192 bits | 7680 bits | Very strong |
| 256 bits | 15360 bits | Maximum |
This is why we don’t encrypt large data with RSA — the keys and operations are enormous compared to AES. Instead, RSA is used to encrypt a symmetric key, and AES encrypts the actual data. This is called hybrid encryption.
Hybrid Encryption — How RSA is Actually Used
In practice, nobody encrypts data directly with RSA. It’s too slow and has size limitations (the message must be smaller than n). Instead:
Sender:
1. Generate a random AES key (e.g., 256 bits)
2. Encrypt the data with AES: ciphertext = AES_Encrypt(data, aes_key)
3. Encrypt the AES key with RSA: encrypted_key = aes_key^e mod n
4. Send: encrypted_key + ciphertext
Receiver:
1. Decrypt the AES key with RSA: aes_key = encrypted_key^d mod n
2. Decrypt the data with AES: data = AES_Decrypt(ciphertext, aes_key)
This gives you the best of both worlds:
- RSA’s key distribution advantage (no need to pre-share a secret key)
- AES’s performance (fast bulk encryption)
This is exactly how TLS (HTTPS) worked before TLS 1.3 — the RSA key exchange encrypted a pre-master secret, which was used to derive AES session keys.
RSA in the Real World
TLS/HTTPS
RSA certificates are everywhere. When you visit a website over HTTPS, the server presents an RSA (or ECDSA) certificate. The certificate contains the server’s public key, signed by a Certificate Authority.
# View a website's RSA certificate
$ openssl s_client -connect example.com:443 2>/dev/null | openssl x509 -text | head -20
Certificate:
Data:
...
Subject Public Key Info:
Public Key Algorithm: rsaEncryption
RSA Public-Key: (2048 bit)
Modulus:
00:c3:5b:...
Exponent: 65537 (0x10001)
Note the exponent: 65537 (0x10001). This is e — the standard public exponent we discussed.
SSH
SSH keys can be RSA:
# Generate a 4096-bit RSA key pair
$ ssh-keygen -t rsa -b 4096
# View the public key
$ cat ~/.ssh/id_rsa.pub
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQ... user@host
Code Signing, PGP/GPG, JWT
RSA signatures are used to sign software packages, emails (PGP/GPG), and JSON Web Tokens (JWT with RS256 algorithm).
Generating RSA Keys with OpenSSL
# Generate a 2048-bit RSA private key
$ openssl genpkey -algorithm RSA -out private.pem -pkeyopt rsa_keygen_bits:2048
# Extract the public key
$ openssl rsa -in private.pem -pubout -out public.pem
# View the key components (n, e, d, p, q, etc.)
$ openssl rsa -in private.pem -text -noout
RSA Private-Key: (2048 bit, 2 primes)
modulus: (n)
00:c3:5b:a7:...
publicExponent: 65537 (0x10001) (e)
privateExponent: (d)
37:1e:c4:...
prime1: (p)
00:f5:2e:...
prime2: (q)
00:cc:7e:...
exponent1: (d mod p-1) (CRT optimization)
exponent2: (d mod q-1) (CRT optimization)
coefficient: (q^-1 mod p) (CRT optimization)
Notice the extra fields: exponent1, exponent2, and coefficient. These are for the Chinese Remainder Theorem (CRT) optimization, which makes private key operations about 4x faster by computing m^d mod p and m^d mod q separately and combining the results.
Attacks on RSA
Factoring the Modulus
The most direct attack: factor n into p and q, compute phi(n), and derive d. The best known algorithm is the General Number Field Sieve (GNFS).
Current records:
- RSA-250 (829 bits) was factored in 2020 using 2700 CPU-years
- RSA-2048 is estimated to require billions of CPU-years with current algorithms
Wiener’s Attack (Small d)
If the private exponent d is too small (roughly d < n^0.25 / 3), it can be recovered using continued fraction expansion of e/n. The fix: always use a full-size d — which happens naturally when e = 65537.
Bleichenbacher’s Attack (PKCS#1 v1.5 Padding Oracle)
If a server reveals whether PKCS#1 v1.5 padding is valid or not (through error messages or timing), an attacker can decrypt RSA ciphertexts with about a million adaptive queries. This was a devastating attack against SSL/TLS.
The fix: use OAEP padding, or implement PKCS#1 v1.5 with constant-time error handling.
Common Modulus Attack
If two users share the same n but have different (e, d) pairs, each can compute the other’s private key. Never share moduli between different key pairs.
Small e with Small Message
If e = 3 and the message is small enough that m^3 < n, the ciphertext is just the cube of the message — no modular reduction happens, and the attacker can take the regular cube root. The fix: always use padding (OAEP), which makes the padded message close to n in size.
Quantum Computing (Shor’s Algorithm)
This is the existential threat to RSA. In 1994, Peter Shor showed that a quantum computer can factor integers in polynomial time. A sufficiently large quantum computer could factor RSA-2048 in hours.
Current quantum computers are far too small and noisy to run Shor’s algorithm on meaningful key sizes. But the threat is real enough that NIST is standardizing post-quantum cryptographic algorithms (based on lattices, codes, and other structures resistant to quantum attacks).
If you’re designing systems that need to be secure for 20+ years, consider post-quantum alternatives or hybrid approaches that combine RSA with quantum-resistant algorithms.
RSA vs Elliptic Curve Cryptography (ECC)
ECC is the modern alternative to RSA for public-key cryptography. It provides the same security with much smaller keys:
| Security Level | RSA Key Size | ECC Key Size |
|---|---|---|
| 128 bits | 3072 bits | 256 bits |
| 192 bits | 7680 bits | 384 bits |
| 256 bits | 15360 bits | 521 bits |
ECC advantages:
- Much smaller keys and signatures
- Faster key generation
- Faster operations (at equivalent security levels)
RSA advantages:
- Simpler to understand
- Faster signature verification (with small
e) - Wider legacy support
The trend is clear — ECC is replacing RSA in new protocols. TLS 1.3 defaults to ECDHE key exchange with ECDSA signatures. SSH recommends Ed25519 (an ECC algorithm) over RSA. But RSA will remain in use for years due to its massive installed base.
Final Thoughts
RSA changed the world. Before public-key cryptography, secure communication required a pre-shared secret — a physical meeting, a trusted courier, a secure channel that somehow already existed. RSA eliminated that requirement. Two strangers on opposite sides of the internet could communicate securely, and that single breakthrough enabled e-commerce, online banking, secure messaging, and the modern internet.
The math is elegant: two large primes, multiplied together, create a trapdoor that’s easy to walk through in one direction and nearly impossible to reverse. Euler’s theorem ties encryption and decryption together with a mathematical guarantee. And the whole thing fits on a napkin.
But RSA also teaches us that elegance isn’t enough. Raw RSA is insecure — you need padding. Small keys are breakable — you need 2048+ bits. And quantum computers threaten to make the entire factoring-based approach obsolete. Cryptography is a moving target, and the algorithms that protect us today may not protect us tomorrow.
For now, RSA remains a foundational piece of internet security. Understanding it gives you insight into how public-key cryptography works, why key sizes matter, and why the field is constantly evolving.
Thanks for reading!
