Asymmetric Encryption: RSA & ECC
Asymmetric encryption solved one of the hardest problems in cryptography: how can two strangers securely exchange secrets over a channel that's being watched by everyone? The answer involves mathematical trapdoors — and it's one of the most elegant ideas in computer science.
The Key Distribution Problem
Symmetric encryption (AES) requires both parties to have the same key. But how do they agree on that key without a secure channel in the first place? It's a chicken-and-egg problem: you need encryption to share the key, but you need the key to encrypt.
This was considered an unsolvable problem until 1976, when Whitfield Diffie and Martin Hellman published their groundbreaking paper introducing public-key cryptography — an entirely new approach that made the key distribution problem disappear.
Public & Private Keys: The Mailbox Analogy
In asymmetric cryptography, each person has two mathematically linked keys:
- Public key: Share it with the world. Post it on your website. It's used to encrypt messages TO you.
- Private key: Guard it with your life. It's used to decrypt messages that were encrypted with your public key.
The critical mathematical property: what is encrypted with the public key can only be decrypted with the matching private key. Even the person who encrypted it can't decrypt it with just the public key.
RSA: The Classic Algorithm
RSA (Rivest–Shamir–Adleman, 1977) is the most famous asymmetric algorithm. Its security rests on one simple fact: it's easy to multiply two large prime numbers, but incredibly hard to factor the result back into its primes.
RSA uses primes with hundreds of digits. The product becomes your public key (simplified). The primes themselves are kept secret as the private key.
RSA in practice
- Key sizes: RSA-2048 is the current minimum. RSA-4096 for higher security. Larger keys mean slower operations.
- Speed: RSA is ~1000× slower than AES for the same data size — which is why it's only used to encrypt small things (like symmetric keys) rather than bulk data.
- Shor's algorithm threat: A quantum computer can factor large numbers in polynomial time, completely breaking RSA. This is why post-quantum cryptography matters.
Elliptic Curve Cryptography (ECC): Smaller, Faster, Stronger
ECC is a newer approach to public-key cryptography based on the mathematics of elliptic curves — not the ovals you might be imagining, but a specific type of algebraic curve.
The key insight: point multiplication on an elliptic curve is easy, but finding the original scalar (the "discrete logarithm") is hard.
RSA at 128-bit security
Requires a 3072-bit key
Large, slow, bandwidth-heavy
ECC at 128-bit security
Requires only a 256-bit key (12× smaller!)
Fast, efficient, ideal for mobile and IoT
ECC is now the preferred choice for TLS, SSH keys, and cryptocurrency wallets (Bitcoin uses secp256k1, a specific elliptic curve). The NSA's Suite B cryptography recommended ECC for government use.
Diffie-Hellman Key Exchange: Agreeing on a Secret Publicly
Diffie-Hellman (DH) is a key exchange protocol — it lets two parties establish a shared secret over a public channel without ever transmitting the secret itself. It's the mechanism that TLS uses to establish session keys.
The paint mixing analogy
- Alice and Bob publicly agree on a shared base color: yellow.
- Alice secretly mixes in some red to get orange. Bob secretly mixes in some blue to get green. They exchange these mixed colors publicly.
- Alice takes Bob's green and adds her secret red → olive. Bob takes Alice's orange and adds his secret blue → the same olive.
- Both have arrived at the same final color (olive) without ever revealing their secret colors. An eavesdropper who only saw yellow, orange, and green cannot determine the olive color.
Real DH uses modular exponentiation instead of paint, but the principle is identical. The "shared secret" becomes the symmetric encryption key for the session.
ECDH (Elliptic Curve Diffie-Hellman) does the same thing using elliptic curve math — smaller, faster, and more efficient than classic DH.
Frequently Asked Questions
Can I encrypt anything with a public key?
In principle, yes. In practice, asymmetric encryption is too slow for large data. The standard pattern is to use the public key to encrypt a symmetric key (like an AES key), then use the symmetric key to encrypt the actual data. This is called a "hybrid encryption" scheme — and it's exactly what TLS does.
What happens if my private key is compromised?
All past communications encrypted with the corresponding public key can now be decrypted — unless perfect forward secrecy (PFS) was used. PFS generates a new ephemeral key pair for each session, so even if the long-term private key is stolen, past sessions remain protected. TLS 1.3 mandates PFS. Always prefer TLS 1.3 over older versions.
Why can't we just use bigger RSA keys to defeat quantum computers?
It doesn't help. Shor's algorithm's quantum speedup is so dramatic that even RSA-100,000 would be broken — the algorithm scales polynomially, while breaking RSA classically scales exponentially. Making keys bigger just delays the classical attack; it doesn't help at all against Shor's. The mathematical problem RSA relies on needs to be replaced entirely, not just made "harder."
Frequently Asked Questions
What will I learn here?
This page covers the core concepts and techniques you need to understand the topic and progress confidently to the next lesson.
How should I use this page?
Start with the overview, then follow the section links to deepen your understanding. Use the table of contents on the right to jump to specific sections.
What should I read next?
Use the navigation below to continue to the next lesson or explore related topics.