Difficulty: Intermediate to Advanced | Prerequisites: Modular arithmetic basics, NP-completeness concepts
This material covers how to build secure communication from number theory. You start with the one-time pad (perfect secrecy, impractical key management), move to Diffie-Hellman (two people agree on a shared secret over a public channel), then to RSA (public-key encryption and digital signatures built on the hardness of factoring). Zero-knowledge proofs round it out: proving you know something without revealing what it is.
One-Time Pad (OTP)
An encryption scheme where a uniformly random secret key (as long as the message) is added to the plaintext character by character, modulo the alphabet size. In simple terms: unbreakable encryption, but only if the key is truly random, as long as the message, and never reused.
Information-Theoretic Security
Security that holds even against an adversary with unlimited computational power. The ciphertext reveals nothing about the plaintext. Think of it as: even a computer that could try every possible approach would learn nothing.
Computational Security
Security that relies on the assumption that certain problems (factoring, discrete log) cannot be solved efficiently. Breakable in theory with infinite compute, but safe in practice. Think of it as: secure enough because nobody can do the maths fast enough.
Generator (of Z*p)
An integer g in Zp such that every non-zero element of Zp can be written as a power of g modulo p. Equivalently, the set {g^0, g^1, ..., g^(p-2)} mod p equals all of Z*p. In simple terms: a number whose repeated powers cycle through every element of the group.
Diffie-Hellman Key Exchange
A protocol that lets two parties (Alice and Bob) agree on a shared secret key over a public channel, using modular exponentiation. Neither party's secret exponent is ever transmitted. Think of it as: mixing colours in public so that only you and your partner know the final shade.
DH Assumption
The assumption that there is no efficient algorithm that, given p, g, g^a mod p, and g^b mod p, can compute g^(ab) mod p. In simple terms: even seeing both public values, an eavesdropper cannot figure out the shared secret.
RSA (Rivest-Shamir-Adleman)
A public-key cryptosystem where the public key (n, e) encrypts and the private key d decrypts. Security rests on the assumption that factoring n = p × q (a product of two large primes) is computationally hard. Think of it as: everyone can lock a box with your public padlock, but only you hold the key to open it.
Euler's Totient Function, phi(n)
The count of integers from 1 to n that are coprime to n. For n = p × q with p, q prime: phi(n) = (p-1)(q-1). In simple terms: how many numbers less than n have no common factor with n.
Fermat's Little Theorem
If p is prime, then for any integer a with gcd(a, p) = 1: a^(p-1) ≡ 1 (mod p). Think of it as: raising any non-zero element to the power (p-1) always gives 1, modulo a prime.
Euler's Theorem
If n = p × q (product of two distinct primes), then for any a coprime to n: a^(phi(n)) ≡ 1 (mod n). Generalises Fermat's Little Theorem.
Extended Euclidean Algorithm
An algorithm that, given integers x and y, returns (g, a, b) such that g = gcd(x, y) and ax + by = g. Used to compute modular multiplicative inverses. In simple terms: the tool for finding d in RSA, given e and phi(n).
Zero-Knowledge Proof (ZKP)
An interactive protocol where a prover convinces a verifier that a statement is true without revealing any information beyond the truth of the statement. Think of it as: proving you know the password to a vault without ever saying the password.
Completeness (ZKP property)
If x ∈ L (the statement is true), the honest prover can always convince the verifier to accept.
Soundness (ZKP property)
If x ∉ L (the statement is false), no cheating prover can convince the verifier to accept, except with negligible probability.
Zero Knowledge (ZKP property)
The verifier learns nothing from the interaction beyond the fact that x ∈ L. Formally: whatever the verifier sees could have been generated by the verifier alone, without the prover.
Alice and Bob share a uniformly random secret key k = k₁, k₂, k₃, ... (as long as the message).
Encrypt: ciphertext c = m + k (mod 26), character by character.
Decrypt: message m = c - k (mod 26).
Security properties:
Provides information-theoretic security: Eve cannot learn anything about the message, even with unbounded computation.
The key must be truly random, at least as long as the message, and used only once.
Con 1: insecure if the key is reused. Reusing a key lets an attacker XOR two ciphertexts to cancel the key and recover information about both plaintexts.
Con 2: Alice and Bob must privately agree on the key beforehand, which is the key-distribution problem that public-key cryptography solves.
Allows two parties to establish a shared secret over a public channel.
Setup: agree on a public prime modulus p and a generator g of Z*p.
Alice picks a secret random a, sends A = g^a mod p to Bob.
Bob picks a secret random b, sends B = g^b mod p to Alice.
Alice computes the shared key: k = B^a mod p = g^(ab) mod p.
Bob computes the shared key: k = A^b mod p = g^(ab) mod p.
An eavesdropper sees p, g, g^a mod p, and g^b mod p, but (under the DH assumption) cannot efficiently compute g^(ab) mod p.
Why generators matter: generators produce the full range of elements in Z*p through exponentiation. This forces an attacker to search a larger space when brute-forcing the secret exponent.
Worked example (from the cheatsheet): p = 23, g = 5. Alice picks a = 4, sends 5^4 mod 23 = 4. Bob picks b = 3, sends 5^3 mod 23 = 10. Alice computes 10^4 mod 23 = 18. Bob computes 4^3 mod 23 = 18. Shared secret: 18.
Fast modular exponentiation: square the base and halve the exponent repeatedly.
Example: 3^9 mod 5. Rewrite as 3^8 × 3^1. Then 3^8 = (3^4)^2, 3^4 = (3^2)^2 = 81 mod 5 = 1. So 3^8 = 1, and 3^9 = 1 × 3 = 3 mod 5.
Computing modular multiplicative inverse: given n and m with gcd(n, m) > 0, find z such that n × z ≡ 1 (mod m).
Run the Extended Euclidean Algorithm on (n, m) to get (a, b) with an + bm = 1.
Then a ≡ n^(-1) (mod m).
Extended Euclidean Algorithm:
Input: integers x ≥ y ≥ 0, not both zero. Output: (g, a, b) where g = gcd(x, y) and ax + by = g.
Base case: if y = 0, return (x, 1, 0). Recursive step: compute (g, a', b') = ExtendedEuclid(y, x mod y). Then return (g, b', a' - floor(x/y) × b').
Key generation:
Pick two large random primes p, q.
Set n = p × q.
Compute phi(n) = (p-1)(q-1).
Pick e coprime to phi(n), and compute d such that e × d ≡ 1 (mod phi(n)) using the Extended Euclidean Algorithm.
Public key: (n, e). Private key: d.
Encrypt: c = m^e (mod n).
Decrypt: m = c^d (mod n).
Why it works: by Euler's theorem, m^(phi(n)) ≡ 1 (mod n) for m coprime to n. Since e × d ≡ 1 (mod phi(n)), we have c^d = m^(ed) = m^(1 + k × phi(n)) = m × (m^(phi(n)))^k = m × 1 = m (mod n).
Worked example: p = 3, q = 17, so n = 51. phi(51) = 2 × 16 = 32. Choose e = 5. Compute d: 5d ≡ 1 (mod 32), so d = 13. Encrypt m = 4: c = 4^5 = 1024 mod 51 = 13. Decrypt: 13^13 mod 51 = 4.
Sign: given message m and private key d, compute signature s = m^d (mod n).
Verify: given (m, s) and public key (n, e), check that s^e ≡ m (mod n).
The RSA assumption guarantees that for a randomly chosen m, no efficient algorithm can produce a valid signature without knowing d.
A zero-knowledge proof for a language L is an interactive protocol between a prover (who wants to convince) and a verifier (who wants to be convinced) that satisfies three properties:
Completeness: if x ∈ L, the prover can always make the verifier accept.
Soundness: if x ∉ L, no cheating prover can fool the verifier (except with negligible probability).
Zero knowledge: the verifier learns nothing beyond the fact that x ∈ L. Formally, whatever the verifier saw from interacting with the prover could have been generated by the verifier on its own.
Example from the cheatsheet: a ZKP for Hamiltonian Cycle. The prover knows a Ham Cycle in graph G. Each round:
Prover randomly shuffles the vertices, writes an adjacency matrix, covers each cell with a post-it note.
Verifier randomly challenges: "reveal all" or "reveal cycle."
If "reveal all," the prover uncovers everything; the verifier checks it matches G (up to relabelling). If "reveal cycle," the prover reveals only the cycle edges; the verifier checks they form a valid Hamiltonian cycle.
The verifier's efficiency is polynomial time. After many rounds, a cheating prover (who does not know a cycle) gets caught with overwhelming probability.
\text{OTP Encrypt: } c = m + k \pmod{26}, \quad \text{Decrypt: } m = c - k \pmod{26}\text{DH shared key: } k = g^{ab} \bmod p\text{RSA: } n = pq, \quad \phi(n) = (p-1)(q-1), \quad ed \equiv 1 \pmod{\phi(n)}\text{RSA Encrypt: } c = m^e \bmod n, \quad \text{Decrypt: } m = c^d \bmod n\text{RSA Sign: } s = m^d \bmod n, \quad \text{Verify: } s^e \equiv m \pmod{n}\text{Fermat's Little Theorem: } a^{p-1} \equiv 1 \pmod{p} \text{ for prime } p,\; \gcd(a,p) = 1\text{Euler's Theorem: } a^{\phi(n)} \equiv 1 \pmod{n} \text{ for } \gcd(a,n) = 1\text{Extended Euclidean: given } x, y, \text{ find } (g, a, b) \text{ s.t. } g = \gcd(x,y),\; ax + by = gStudents often think the one-time pad is impractical "because it's old." The real limitation is key management: the key must be as long as the message, truly random, and never reused. If any of these conditions fails, security collapses.
A frequent confusion: thinking RSA's public key encrypts and the private key decrypts, full stop. In RSA signatures, the roles reverse: the private key signs (encrypts the hash) and the public key verifies. Same maths, different direction.
Students sometimes assume Diffie-Hellman provides authentication. It does not. A man-in-the-middle can impersonate both sides. DH gives you a shared secret; you need something else (certificates, signatures) to confirm who you are sharing it with.
When computing modular inverses, students sometimes forget to check that gcd(e, phi(n)) = 1. If this condition is not met, the inverse does not exist and RSA key generation fails.
⚠️ You will almost certainly be asked to perform an RSA encryption or decryption by hand with small numbers. Practise the full pipeline: pick p, q, compute n, phi(n), choose e, find d via Extended Euclidean, encrypt, decrypt.
⚠️ The Extended Euclidean Algorithm table is a common exam computation. Be fluent with the recursive version and the tabular version. The worked example in the cheatsheet (n = 77, e = 7) is representative of exam difficulty.
⚠️ Know the three properties of zero-knowledge proofs (completeness, soundness, zero knowledge) and be able to explain each in one sentence. The Hamiltonian Cycle ZKP is the standard example.
⚠️ Understand why generators are preferred in Diffie-Hellman: they produce the full group Z*p, maximising the search space for an attacker.
⚠️ Be ready to explain the difference between information-theoretic security (OTP) and computational security (RSA, DH). The distinction often appears as a short-answer or true/false question.
True or False: The one-time pad provides computational security. Answer: False. It provides information-theoretic security.
Fill in the blank: In Diffie-Hellman, the shared secret is g^______ mod p. Answer: ab (the product of both secret exponents).
True or False: In RSA, if you know n and e, you can efficiently compute d. Answer: False. You would need to factor n to find p and q, which is assumed to be hard.
Fill in the blank: Euler's totient of n = pq (distinct primes) is ______. Answer: (p-1)(q-1).
True or False: In a zero-knowledge proof, the verifier learns the prover's secret. Answer: False. The verifier learns only that the statement is true.
Q: Let n = 77 and e = 7 be an RSA public key. Compute the private key d.
A: Factor n: 77 = 7 × 11. Compute phi(77) = 6 × 10 = 60. Find d such that 7d ≡ 1 (mod 60). Using the Extended Euclidean Algorithm: 60 = 8 × 7 + 4, then 7 = 1 × 4 + 3, then 4 = 1 × 3 + 1. Back-substituting: 1 = 4 - 1 × 3 = 4 - 1 × (7 - 4) = 2 × 4 - 7 = 2 × (60 - 8 × 7) - 7 = 2 × 60 - 17 × 7. So d = -17 ≡ 43 (mod 60).
Q: In Diffie-Hellman with p = 23 and g = 5, Alice sends A = 4 and Bob sends B = 10. Eve intercepts both values. Explain why Eve cannot (efficiently) compute the shared secret.
A: Eve sees p = 23, g = 5, A = 4 = 5^a mod 23, and B = 10 = 5^b mod 23. To find the shared secret g^(ab) mod 23, she would need to recover a or b from A or B, which requires solving the discrete logarithm problem. Under the DH assumption, no efficient algorithm can do this.
Q: Explain why reusing a one-time pad key is insecure.
A: If Alice encrypts messages m₁ and m₂ with the same key k, the ciphertexts are c₁ = m₁ + k and c₂ = m₂ + k (mod 26). An attacker who computes c₁ - c₂ = m₁ - m₂ (mod 26) obtains the difference of the two plaintexts, which leaks substantial information about both messages. The key cancels out entirely.
Q: State and explain the three properties a zero-knowledge proof must satisfy.
A: Completeness: if the statement is true, the honest prover always convinces the verifier. Soundness: if the statement is false, no cheating prover can convince the verifier except with negligible probability. Zero knowledge: the verifier gains no information beyond the truth of the statement; formally, the verifier could have generated the transcript on its own without interacting with the prover.
Q: In RSA, why does m^(ed) ≡ m (mod n)?
A: Since ed ≡ 1 (mod phi(n)), we can write ed = 1 + k × phi(n) for some integer k. Then m^(ed) = m^(1 + k × phi(n)) = m × (m^(phi(n)))^k. By Euler's theorem (for m coprime to n), m^(phi(n)) ≡ 1 (mod n), so m^(ed) ≡ m × 1^k = m (mod n).
RSA's security depends on the assumption that factoring is hard, which connects to the NP-completeness material: if P = NP, factoring could be done in polynomial time and RSA would break. The entire cryptography unit assumes that certain problems sit outside P.
Zero-knowledge proofs for Hamiltonian Cycle tie back to the NP-completeness of Hamiltonian Cycle. The prover's ability to convince the verifier relies on the problem being in NP (a short certificate exists).
The probability material (Markov, Chernoff) underpins the analysis of cryptographic protocols: the "negligible probability" in soundness is made precise using these tools.
RSA, Rivest-Shamir-Adleman, public key encryption, private key, digital signature, one-time pad, OTP, Vernam cipher, Diffie-Hellman, DH key exchange, discrete logarithm, modular exponentiation, Extended Euclidean Algorithm, modular inverse, Euler's totient, phi function, Fermat's little theorem, Euler's theorem, zero-knowledge proof, ZKP, completeness, soundness, zero knowledge, Hamiltonian cycle ZKP, information-theoretic security, computational security, EECS 376, University of Michigan, foundations of computer science