Why Private-Key Crypto Isn't Enough
Traditional private/secret/single-key cryptography (everything in Chapter 3 — DES, AES) uses one key, shared by both the sender and the receiver. It is symmetric — both parties are equal. That equality is exactly its weak point: if the key is disclosed, all communications using it are compromised, and because both sides hold the identical key, the scheme cannot stop the receiver from forging a message and claiming it came from the sender (or vice versa).
Challenges To Be Considered
Imagine Bob wants to send secret Message A to Alice, while an eavesdropper/attacker named Darth sits on the channel in between. A secure system needs to answer:
How to keep message A a secret from Darth?
How does Alice know the message was not modified in transit?
How does Alice know the message really comes from Bob?
How can Bob ensure Alice cannot deny receiving the message?
How to avoid a replay attack (Darth resending an old, valid message)?
How to keep the message fresh (and more…)?
Symmetric Cipher: The Confidentiality Cost
With a shared secret key, 2 users need only 1 key between them. But scale that up to n users who all want to talk securely to each other, and the number of keys needed explodes:
Number of keys required for n users = 0 + 1 + 2 + … + (n-1) = n(n-1)/2. The real challenge: how do you securely distribute that many keys in the first place?
Symmetric Cipher: The Authentication Problem
One fix for authentication is to create a signature for the message — but doing this with symmetric keys depends on a trusted third party, e.g. a Key Distribution Center (KDC). Even then, it still does not protect the sender from the receiver forging a message and falsely claiming it was sent by the sender, since both sides hold the same key.
Mnemonic — "Same Key, Same Blame"
"If you both hold the same key, neither can prove who's to blame." — symmetric crypto's core weakness in one line: because sender and receiver share an identical key, either one could have created any given message, so you can never definitively pin authorship on one party (no nonrepudiation) without bringing in a trusted third party like a KDC.
Public-Key Cryptography
Public-key cryptography is arguably the most significant advance in the 3,000-year history of cryptography. It uses two keys — a public key and a private key — and is called asymmetric because the two parties are not equal: what one key does, only the other key can undo. It relies on a clever application of number-theoretic concepts, and it complements — rather than replaces — private-key cryptography (both are still used together in practice, e.g. RSA to exchange a symmetric session key, then AES to encrypt the bulk data).
Why Public-Key Cryptography Was Developed
It was developed specifically to address two problems symmetric crypto struggles with:
How can two parties have secure communications without having to trust a KDC with their key? Public-key crypto lets Alice publish a public key that anyone can use — no shared secret needs to be pre-arranged or held by a third party.
How do you verify that a message comes intact from the claimed sender? A private key can "sign" a message in a way only the matching public key can verify — something symmetric keys cannot do cleanly.
A Bit of History
Public invention of public-key cryptography is credited to Whitfield Diffie & Martin Hellman at Stanford University in 1976. It was later revealed in 1997 that James H. Ellis, Clifford Cocks, and Malcolm J. Williamson of GCHQ (the British signals intelligence agency) had secretly discovered the same idea back in 1969 — but it stayed classified for decades.
Mnemonic — "Diffie-Hellman Went Public, GCHQ Went Quiet"
"'76 told the world, '69 kept the secret." Diffie & Hellman published the idea in 1976. GCHQ's Ellis, Cocks & Williamson had it first in 1969 but stayed classified until 1997 — remember it as "69 before 76, but 76 got the credit" (public discovery order vs. actual discovery order don't match — a classic exam trick question).
How Public-Key Cryptography Works
Public-key / two-key / asymmetric cryptography involves two keys:
It is infeasible to determine the private key from the public key. The system is asymmetric because whoever encrypts messages or verifies signatures cannot decrypt messages or create signatures — those abilities belong exclusively to the private-key holder.
Mnemonic — "Public Locks, Private Unlocks"
"Anyone can lock the box (public key encrypts), only the owner can unlock it (private key decrypts)." Think of the public key as an open padlock anyone can snap shut, but only the person holding the matching private key can open it. This is the single most tested direction fact in this chapter.
Requirements, Applications & Security Basis
Public-Key Applications — 3 Categories
Public-key algorithms can be classified into three broad uses. Some algorithms are suitable for all three; others are specific to just one.
Encryption / Decryption
Provides secrecy — hides the content of a message from anyone but the intended recipient.
Digital Signatures
Provides authentication — proves who created/sent a message and that it wasn't altered.
Key Exchange
Used to securely exchange a session key that will then be used for fast symmetric encryption of the actual bulk data.
Mnemonic — "E-D-K" (Encrypt, Digitally-sign, Key-swap)
"EDK: Envelope, Doodle, Key." Encryption/decryption = sealing an envelope (secrecy). Digital signatures = your unique doodle/signature (authentication). Key exchange = handing over a key to a lockbox (session-key setup) so you can switch to faster symmetric crypto.
Public-Key Requirements
Public-key algorithms rely on two keys where:
Infeasible to derive the decryption key
It is computationally infeasible to find the decryption key knowing only the algorithm and the encryption key.
Easy to encrypt / decrypt when key is known
It is computationally easy to encrypt or decrypt messages when the relevant (encrypt/decrypt) key is known.
Either key can play either role (for some algorithms)
Either of the two related keys can be used for encryption, with the other used for decryption.
These are formidable requirements which only a few algorithms have ever satisfied (RSA being the most famous).
The Trapdoor One-Way Function
The mathematical engine underneath all of this is a trapdoor one-way function.
Y = f(X) is easy to compute.
X = f⁻¹(Y) is infeasible to compute
(you can't easily go backwards).
Y = fₖ(X) is easy, if k and X are known.
X = fₖ⁻¹(Y) is easy, if
k and Y are known.
X = fₖ⁻¹(Y) is infeasible, if Y is known but k is not.
A practical public-key scheme depends on finding a suitable trapdoor one-way function — for RSA, that function is built from modular exponentiation, and the "trapdoor" (the secret k) is knowledge of the prime factors of n.
Mnemonic — "Trapdoor = Secret Shortcut"
"A trapdoor function is a one-way street — unless you know the secret alley." Forward is always easy. Backward is impossible for a stranger, but trivial for whoever holds the secret key k (the "trapdoor"). For RSA, that secret is the pair of prime factors p and q.
Security of Public-Key Schemes
- Like private-key schemes, a brute-force exhaustive key search is always theoretically possible
- But the keys used are far too large (> 512 bits, typically 1024–2048+ today) for brute force to be practical
- Security relies on a large enough gap in difficulty between the easy problem (encrypt/decrypt with the right key) and the hard problem (cryptanalyze without it)
- More generally, the hard problem is publicly known — it's just made hard enough to be impractical to break with current computing power
- Requires the use of very large numbers, which is why public-key crypto is slow compared to private-key schemes
RSA — The Best-Known Public-Key Scheme
RSA was designed by Ron Rivest, Adi Shamir, and Leonard Adleman of MIT in 1977 — the initials of their surnames give the algorithm its name. It is the best-known and most widely used public-key scheme in the world.
Easy forward, hard backward — the whole point
Multiplying two primes together (p × q = n) is fast even for huge numbers. Factoring that product n back into p and q, without already knowing them, is what's believed to be computationally infeasible for large enough n. That asymmetry in difficulty is RSA's trapdoor.
RSA Encryption, Decryption & Key Setup
RSA Encryption / Decryption
To encrypt a message M, the sender:
- Obtains the recipient's public key PU = {e, n}
- Computes: C = Mᵉ mod n, where 0 ≤ M < n
To decrypt the ciphertext C, the owner:
- Uses their private key PR = {d, n}
- Computes: M = C^d mod n
Note: the message M must be smaller than the modulus n — if the real message is bigger, it must be broken into blocks first.
Mnemonic — "C Comes from e, M comes back with d"
"e for Encrypt (public), d for Decrypt (private)." C = Mᵉ mod n — raise message to the exponent from the public key. M = C^d mod n — raise ciphertext to the decryption exponent from the private key. Same shape, different exponent, same modulus n both times.
RSA Key Setup — The Full Recipe
Each user generates their public/private key pair as follows:
Select two large primes at random: p, q
Kept secret — never published.
Compute the modulus n = p · q
n becomes part of both the public and private key.
Compute Euler's totient φ(n) = (p − 1)(q − 1)
Counts integers less than n that are coprime to n. Kept secret.
Select e at random: 1 < e < φ(n), gcd(e, φ(n)) = 1
e must share no common factors with φ(n) — this is the public encryption exponent.
Solve for d: e · d ≡ 1 (mod φ(n)), 0 ≤ d ≤ n
d is the modular multiplicative inverse of e mod φ(n) — the private decryption exponent.
Publish the public key PU = {e, n}
Anyone can use this to encrypt a message to you.
Keep secret the private key PR = {d, n}
Only you can decrypt messages sent to you, using this.
Mnemonic — "P-Q-N-Phi-E-D-Publish" (the 7-Step Ladder)
"Pick Primes, Multiply for N, Phi it, pick E, Derive D, then Publish/Protect." Pick two primes p, q → compute N = pq → compute Phi(n) = (p-1)(q-1) → choose E coprime to φ(n) → Derive d as e's inverse mod φ(n) → Publish {e,n}, Protect {d,n}. Seven words for seven steps, in order.
Why RSA Works — Euler's Theorem
The mathematics behind why decryption correctly recovers the original message rests on Euler's Theorem:
In RSA we have n = p·q, φ(n) = (p−1)(q−1), and e & d are carefully chosen to be inverses mod φ(n) — so e·d = 1 + k·φ(n) for some integer k. This means:
In other words: because e and d were built to "cancel out" mod φ(n), raising a message to the e-th power and then to the d-th power lands you right back where you started.
RSA By Hand — A Small Numeric Example
This is the classic textbook toy example (Alice/Bob/Darth scenario) — small enough to compute by hand, just to see every step of the RSA machinery in action. Never use numbers this small in real life — real RSA uses 1024+ bit primes.
Step-by-Step Key Setup
| Step | Action | Result |
|---|---|---|
| 1 | Select primes p, q | p = 17, q = 11 |
| 2 | Calculate n = p · q | n = 17 × 11 = 187 |
| 3 | Calculate φ(n) = (p−1)(q−1) | φ(n) = 16 × 10 = 160 |
| 4 | Select e: gcd(e, 160) = 1 | choose e = 7 |
| 5 | Determine d: d·e ≡ 1 mod 160, d < 160 | d = 23, since 23×7 = 161 = 1×160 + 1 |
| 6 | Publish public key | PU = {7, 187} |
| 7 | Keep secret private key | PR = {23, 187} |
The Scenario
Alice generates the key pair above and publishes PU = {7, 187} — anyone, including an eavesdropper Darth, can see this public key. Alice keeps PR = {23, 187} secret. Bob wants to send Alice the message M = 88 (note 88 < 187, satisfying the requirement that M < n).
Encryption (Bob → Alice)
C = 88⁷ mod 187 = 11
Bob sends the ciphertext x = 11 across the channel instead of the plaintext 88. Even if Darth intercepts x = 11, without the private key d = 23, Darth cannot recover 88.
Decryption (Alice recovers M)
M = 11²³ mod 187 = 88
Alice uses her private key d = 23 (known only to her) to recover the original message — 88, exactly what Bob sent.
Mnemonic — "17 & 11 make 187, 7 & 23 make 161"
"Small primes, small e, and de is one more than a multiple of φ(n)." Remember the check: d·e mod φ(n) must equal 1. Here 23 × 7 = 161, and 161 = (1 × 160) + 1 — one more than exactly one φ(n). That "+1 leftover" pattern is how you verify any (e,d) pair by hand.
Why this example is toy-sized only
n = 187 = 17 × 11 can be factored by trial division in seconds. Real RSA keys use primes hundreds of digits long specifically so factoring n back into p and q is computationally infeasible — that gap between "toy" and "real" security is entirely about the size of p and q.
Efficient Exponentiation — Square & Multiply
Computing something like 88²³ mod 187 by literally multiplying 88 by itself 23 times would be wasteful. RSA instead uses the Square and Multiply Algorithm — a fast, efficient method for modular exponentiation.
7⁵ = 7⁴ · 7¹ = 3 · 7 = 10 mod 11
3¹²⁹ = 3¹²⁸ · 3¹ = 5 · 3 = 4 mod 11
The Algorithm for Computing aᵇ mod n
The integer exponent b is expressed in binary as bₖbₖ₋₁…b₀:
560 in binary = 1000110000. Starting c=0, f=1, the algorithm walks bit by bit, squaring f (mod n) every step, and multiplying in an extra factor of a whenever the current bit is 1:
f = 1 → f = 1×7 mod 561 = 7 → f = 7×7 mod 561 = 49 → f = 49×49 mod 561 = … and so on until all bits of b are consumed.
Mnemonic — "Square Every Step, Multiply on a 1-Bit"
"Always square. Only multiply when you see a 1." Walk the exponent's binary digits left to right. Every single bit: square your running result. Whenever that bit is a 1: also multiply in one more copy of the base. That's the entire algorithm — no bit ever skips the square step, only some bits trigger the extra multiply.
Efficient Encryption — Choosing e
Encryption uses exponentiation to the power e, so a small e makes encryption faster. Common choices:
- Often choose e = 65537 (which is 2¹⁶ + 1) — small enough to be fast, large enough to be safe
- Also sometimes see e = 3 or e = 17
- But if e is too small (e.g. e = 3), the scheme can be attacked using the Chinese Remainder Theorem combined with 3 messages sent under different moduli
- If e is fixed, must always ensure gcd(e, φ(n)) = 1 — i.e. reject any candidate p or q that isn't relatively prime to e
Efficient Decryption — Using the CRT
Decryption uses exponentiation to the power d, which is typically large — this makes naive decryption slow (and, done carelessly, insecure). Instead, decryption can use the Chinese Remainder Theorem (CRT) to compute the result modulo p and modulo q separately, then combine the two partial results — this is roughly 4× faster than computing C^d mod n directly. Only the owner of the private key, who knows the values of p and q, can use this speed-up.
RSA Key Generation — the practical checklist
Users of RSA must: (1) determine two random primes p, q that are large enough that n = p·q cannot be feasibly factored, and typically found via a probabilistic primality test (guess-and-check); (2) select either e or d and compute the other, since e and d are modular inverses of each other mod φ(n) — an inverse-computing algorithm derives whichever one wasn't chosen.
RSA Security — Attacks & Countermeasures
There are four broad classes of possible attack against RSA:
Brute Force Key Search
Infeasible given the size of the numbers involved — trying every possible private key is impractical for keys of 1024+ bits.
Mathematical Attacks
Based on the difficulty of computing φ(n) by factoring the modulus n. This is the headline attack — see the Factoring Problem below.
Timing Attacks
Attacks based on how long the decryption operation takes to run — timing can leak information about the private key.
Chosen Ciphertext Attacks (CCA)
Exploits mathematical properties of the RSA algorithm itself, using specially chosen ciphertexts.
The Factoring Problem
The mathematical approach to breaking RSA takes three equivalent forms:
- Factor n = p·q directly, hence compute φ(n) and then d
- Determine φ(n) directly and compute d from it
- Find d directly, without going through φ(n) or factoring at all
Currently, all three are believed to be roughly equivalent in difficulty to factoring. There have been slow improvements in factoring algorithms over the years (as of May 2005, the best result was a 200-decimal-digit / 663-bit number, factored using the Lattice Sieve). The biggest jumps in progress have come from improved algorithms (going from QS, the Quadratic Sieve, to GNFS, the General Number Field Sieve, to LS, the Lattice Sieve) rather than raw hardware speed. Current guidance assumes 1024–2048 bit RSA is secure, provided p and q are chosen to be of similar size and satisfy the other standard constraints.
Progress in factoring
Factoring records are measured in "MIPS-years" — the number of instructions executed during one year of computing at one million instructions per second. Progress has been steady but slow, driven mostly by smarter algorithms, not just faster computers — which is why doubling key sizes (rather than waiting for hardware to catch up) keeps RSA ahead of factoring advances.
Timing Attacks
Developed by Paul Kocher in the mid-1990s. These exploit small timing variations in operations — e.g. multiplying by a small number vs. a large number, or conditional branches (IF statements) that execute different instructions depending on secret bits. By carefully measuring how long an operation takes, an attacker can infer operand size and, bit by bit, reconstruct the private key. RSA is vulnerable because the time taken during exponentiation can vary with the exponent's bits.
- Use constant exponentiation time, regardless of the key bits
- Add random delays to obscure timing patterns
- Blind the values used in calculations so the attacker can't correlate timing with the real private data
Chosen Ciphertext Attacks (CCA)
RSA is vulnerable to a chosen ciphertext attack: the attacker chooses ciphertexts and gets the corresponding decrypted plaintext back (e.g. tricking a system into decrypting things for them), then chooses the ciphertext specifically to exploit mathematical properties of RSA and leak information useful for cryptanalysis.
Counter with a random pad added to the plaintext before encryption, or use a formal padding scheme such as Optimal Asymmetric Encryption Padding (OAEP).
Mnemonic — "B-M-T-C" (Brute, Math, Timing, Chosen)
"Break it Brute-force (fails), break it with Math (factoring — the real threat), break it with Time (side channel), break it by Choosing ciphertexts (protocol abuse)." Four attack families, four very different defenses: bigger keys defeat brute force, bigger keys + good primes defeat math attacks, constant-time code + blinding defeats timing attacks, and padding schemes (OAEP) defeat chosen-ciphertext attacks.
Exam Tips & Tricks
Remember the formulas both ways
Encrypt: C = Mᵉ mod n (public key). Decrypt: M = C^d mod n (private key). Same n both times — only the exponent changes.
Public encrypts, private decrypts — never the reverse
This directionality is the single most commonly tested fact about asymmetric crypto. Public key = for everyone, encrypts. Private key = for the owner only, decrypts.
φ(n) uses (p−1)(q−1), NOT p·q
A very common mix-up: n = p·q, but φ(n) = (p−1)(q−1). Don't confuse the modulus with the totient.
e·d ≡ 1 mod φ(n) — the inverse check
To verify any (e,d) pair, multiply them and check the result is exactly one more than a multiple of φ(n): e·d = 1 + k·φ(n).
RSA security = factoring hardness, not key secrecy tricks
RSA's entire security rests on: multiplying two large primes is easy, but factoring the product back apart is (believed) infeasible for large enough numbers.
Know the 3 public-key use categories
Encryption/decryption (secrecy), digital signatures (authentication), key exchange (session keys) — not every algorithm supports all three.
Know all 4 RSA attack types
Brute force (infeasible), mathematical/factoring (the real long-term threat), timing (Kocher, mid-90s), chosen ciphertext (countered with OAEP padding).
Square and Multiply = O(log₂ n), not O(n)
Never multiply out an exponent step by step — the algorithm only needs a number of steps proportional to the number of bits in the exponent.
Quick Reference — Everything at a Glance
| Topic | Key Point |
|---|---|
| Private-key crypto weakness | Single shared key; symmetric so can't stop receiver forging a message & claiming sender sent it |
| Key distribution problem | n users need n(n-1)/2 keys total — securely distributing them is hard |
| Public-key crypto significance | "Most significant advance in the 3000-year history of cryptography" |
| Symmetric vs asymmetric | Symmetric: 1 shared key, parties equal. Asymmetric: 2 keys (public/private), parties unequal |
| Public-key invented by | Diffie & Hellman, Stanford, 1976 (publicly); Ellis/Cocks/Williamson at GCHQ discovered it in 1969 (classified, revealed 1997) |
| Two problems public-key crypto solves | Key distribution (no KDC needed) and digital signatures (verify sender) |
| Public key role | Known by anybody; encrypts messages, verifies signatures |
| Private key role | Known only to recipient; decrypts messages, creates/signs signatures |
| 3 public-key application categories | Encryption/decryption (secrecy), digital signatures (authentication), key exchange (session keys) |
| Public-key requirements | Infeasible to derive decrypt key from encrypt key; easy en/decrypt when key known; either key can encrypt (some algorithms) |
| One-way function | Y=f(X) easy; X=f⁻¹(Y) infeasible |
| Trapdoor one-way function | Y=fk(X) easy if k,X known; X=fk⁻¹(Y) easy if k,Y known; infeasible if only Y known |
| Public-key scheme security | Relies on gap between easy (en/decrypt) and hard (cryptanalyze) problems; keys > 512 bits; slower than private-key crypto |
| RSA creators | Rivest, Shamir, Adleman — MIT, 1977 |
| RSA mathematical basis | Exponentiation in a finite (Galois) field over integers modulo a prime |
| RSA key size in practice | Large integers, e.g. 1024 bits (1024–2048 bit range considered secure today) |
| RSA security basis | Cost of factoring large numbers (factoring is hard: O(e^(log n·log log n)); exponentiation is easy: O((log n)³)) |
| RSA encryption formula | C = Mᵉ mod n, using public key PU={e,n}, 0≤M<n |
| RSA decryption formula | M = C^d mod n, using private key PR={d,n} |
| RSA key setup steps | Pick p,q → n=pq → φ(n)=(p-1)(q-1) → choose e (gcd(e,φ(n))=1) → find d (e·d≡1 mod φ(n)) → publish {e,n}, keep {d,n} secret |
| Why RSA works | Euler's Theorem: a^φ(n) mod n = 1 when gcd(a,n)=1; e,d chosen as inverses mod φ(n) so C^d = M mod n |
| Worked example primes | p=17, q=11 → n=187 → φ(n)=160 → e=7 → d=23 (23×7=161=1×160+1) |
| Worked example keys | PU={7,187} (public), PR={23,187} (private) |
| Worked example encryption | M=88 → C = 88⁷ mod 187 = 11 |
| Worked example decryption | C=11 → M = 11²³ mod 187 = 88 (recovers original message) |
| Square and Multiply algorithm | Computes aᵇ mod n by squaring at every bit of b and multiplying in a on 1-bits; O(log₂ n) steps |
| Efficient encryption (choice of e) | Small e = faster; common choice e=65537 (2¹⁶+1); e=3 or 17 also seen but e=3 riskier (CRT attack with 3 messages) |
| Efficient decryption | Chinese Remainder Theorem (CRT) computes mod p & mod q separately then combines — ~4× faster; requires knowing p,q |
| RSA key generation practicalities | p,q found via probabilistic primality testing (guess & check); e,d are inverses — compute one from the other |
| RSA attack #1 — Brute force | Infeasible given key sizes used |
| RSA attack #2 — Mathematical | Based on difficulty of computing φ(n) by factoring n; 3 equivalent approaches: factor n, find φ(n) directly, or find d directly |
| RSA attack #3 — Timing | Paul Kocher, mid-1990s; exploits timing variation in exponentiation; countered with constant time, random delays, blinding |
| RSA attack #4 — Chosen ciphertext (CCA) | Attacker chooses ciphertexts to exploit RSA math properties; countered with random padding or OAEP |
| Factoring progress | As of May 2005, best result ~200 decimal digits (663 bits) via Lattice Sieve; biggest gains from better algorithms (QS → GNFS → LS), not just faster hardware |
| Currently assumed secure | 1024–2048 bit RSA, with p and q of similar size and meeting standard constraints |