🗝️ 07-04: Asymmetric Encryption and RSA¶

📌 The Problem This Solves¶

In 07-02: Symmetric Encryption Basics, we hit the key distribution problem: symmetric encryption needs both parties to already share a secret key, but getting that key to each other securely over an untrusted network is itself a hard problem.

Asymmetric encryption (public-key cryptography) solves this with a clever trick: instead of one shared key, every participant generates a pair of mathematically linked keys:

A public key — safe to give to literally anyone, including attackers
A private key — kept secret, never shared with anyone

Whatever one key encrypts, only the other key in the pair can decrypt.

📬 The Mailbox / Padlock Analogy¶

Imagine an open padlock that anyone can snap shut, but only one specific key can open.

You manufacture a padlock and its matching key.
You keep the key (private key) locked in your pocket forever.
You mail copies of the open padlock (public key) to anyone who might want to send you something.
Anyone who wants to send you a secret box puts their item inside, snaps your padlock shut, and mails it.
Only you can open it, because only you have the matching key.

💡 Notice what makes this different from symmetric encryption: the sender never needed a secret at all. They just needed a public, freely distributed padlock. Nobody watching the mail — not even someone who intercepts a hundred padlocks in transit — can open a box locked with one, because the padlock itself doesn't reveal how to open it.

In cryptographic terms: the public key encrypts, the private key decrypts. Anyone can encrypt a message to you using your public key, but only you (holding the private key) can decrypt it.

	Symmetric Encryption	Asymmetric Encryption
Keys	One shared secret key	A public/private key pair
Who needs the secret?	Both parties, in advance	Only the key pair's owner
Speed	Fast	Much slower (100-1000x)
Solves	Bulk data encryption	Key distribution / first contact

💡 Because asymmetric encryption is computationally expensive, real systems (including TLS, Module 09) rarely use it to encrypt the actual data. Instead, they use it just to safely exchange a symmetric key — then switch to fast AES (see 07-03: AES & Block Cipher Modes) for everything else. This combination is often called hybrid encryption.

🔢 RSA: The Math Behind the Padlock¶

RSA (named for its inventors Rivest, Shamir, and Adleman) is the most well-known asymmetric encryption algorithm. Its security rests on a simple asymmetry in difficulty: multiplying two large prime numbers together is easy, but factoring the resulting product back into its two primes is extremely hard — if the primes are large enough (real RSA uses primes hundreds of digits long).

Let's walk through RSA by hand using tiny numbers, small enough to verify with pencil and paper. (Real RSA keys use primes hundreds of digits long — these tiny numbers are for learning the mechanics only; they offer zero real security.)

Step 1: Pick Two Prime Numbers¶

p = 5
q = 11

Step 2: Compute n (the modulus)¶

n = p × q = 5 × 11 = 55

n becomes part of both the public and private key. Its size (in real RSA, thousands of bits) is what determines the key's strength — because breaking RSA means factoring n back into p and q.

Step 3: Compute φ(n) — Euler's Totient¶

φ(n) = (p - 1) × (q - 1) = 4 × 10 = 40

φ(n) counts how many numbers less than n share no common factors with n. It's only computable easily if you know p and q individually — which is why keeping them secret (and discarding them after key generation) matters.

Step 4: Choose the Public Exponent (e)¶

Pick a number e such that 1 < e < φ(n) and e shares no common factors with φ(n) (i.e., gcd(e, φ(n)) = 1).

e = 3
gcd(3, 40) = 1  ✓ valid choice

(n, e) = (55, 3) is now the public key.

Step 5: Compute the Private Exponent (d)¶

Find d such that (e × d) mod φ(n) = 1 — in other words, d is the modular multiplicative inverse of e.

We need: (3 × d) mod 40 = 1
Try d = 27:  3 × 27 = 81,  81 mod 40 = 1   ✓

(n, d) = (55, 27) is now the private key.

	Value
Public key	`(n=55, e=3)` — shared with everyone
Private key	`(n=55, d=27)` — kept secret

🔒 Encrypting a Message¶

Say Bob wants to send Alice the number m = 9 (in real systems, the plaintext is converted to numbers first — but the RSA math itself only ever operates on numbers).

Bob uses Alice's public key (n=55, e=3):

ciphertext = m^e mod n
           = 9^3 mod 55
           = 729 mod 55
           = 14

Bob sends c = 14 to Alice over the network. Anyone sniffing the traffic — even an active MITM attacker — only ever sees 14, plus the public key, neither of which reveals m without solving the hard factoring problem.

🔓 Decrypting the Message¶

Alice receives c = 14 and uses her own private key (n=55, d=27):

plaintext = c^d mod n
          = 14^27 mod 55
          = 9

Alice recovers m = 9 — the exact original number Bob started with. 🎉

💡 The magic is that whichever key encrypts, only the mathematically paired other key can undo it — this is a direct property of modular exponentiation combined with how e and d were constructed to be inverses of each other modulo φ(n). You don't need to prove this to yourself from number theory to use RSA safely — you just need to trust (correctly) that this relationship holds for any valid RSA key pair.

🛡️ Why Factoring n Is the Whole Ballgame¶

Everything about RSA's security rests on one fact: an attacker who only sees the public key (n, e) needs φ(n) to compute d, and computing φ(n) requires knowing p and q — which means factoring n.

With our toy example, n = 55 is trivial to factor by hand: 55 = 5 × 11.
Real RSA keys use n values that are 2048 or 4096 bits long (over 600 decimal digits) — products of two enormous random primes. Factoring numbers that large is believed to be computationally infeasible with classical computers, even with all of today's computing power combined, for centuries.

💥 This is why RSA key size matters so much in practice: a "1024-bit RSA key" is now considered too weak (feasible to eventually factor with enough resources), while 2048-bit and above remain secure for now.

📌 Key Takeaways¶

Asymmetric encryption (public-key cryptography) uses a mathematically linked key pair: a public key anyone can have, and a private key that never leaves its owner.
Whatever the public key encrypts, only the matching private key can decrypt — solving the key distribution problem from symmetric encryption without any prior shared secret.
The padlock analogy: anyone can snap a public padlock shut, but only the private key opens it.
RSA builds this using the difficulty of factoring: n = p × q is easy to compute forward, but recovering p and q from n alone is extremely hard for large enough primes.
Key generation: pick primes p, q → compute n = p×q and φ(n) = (p-1)(q-1) → choose public exponent e → derive private exponent d as the modular inverse of e mod φ(n).
Encryption: ciphertext = message^e mod n. Decryption: message = ciphertext^d mod n.
The toy example (p=5, q=11, e=3, d=27) encrypts 9 to 14 and decrypts 14 back to 9 — the exact same math real RSA uses, just with impractically small numbers.
Real-world RSA uses primes hundreds of digits long specifically because small n values (like our toy 55) are trivially factorable — security scales with key size.
Because asymmetric encryption is slow, real protocols use it only to establish a shared symmetric key, then switch to fast AES for bulk data — this hybrid approach is exactly what happens in TLS (Module 09).