OpenCyber AcademyLesson map
Lesson 01 published. Map, example, EX001.
flowchart TD
N0["Learning outcomes"]
N1["1.1 Why security students need proofs"]
N2["1.2 Growth rates"]
N3["1.4 Practical activity — Lab G"]
N4["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4
N4 --> EX["Worked example"]
EX --> Q["Exercise EX001"]
Logical drawing
flowchart LR
N0["Learning outcomes"]
N1["1.1 Why security students need proofs"]
N2["1.2 Growth rates"]
N3["1.4 Practical activity — Lab G"]
N4["Synthesis"]
N0 --> N1 --> N2 --> N3 --> N4 --> Q["EX001"]
[Learning outcomes]
|
v
[1.1 Why security students need proofs]
|
v
[1.2 Growth rates]
|
v
[1.4 Practical activity — Lab G]
|
v
[Synthesis]
|
v
[Worked example] --> [Exercise EX001]
Learning outcomes
You will (1) read and write a short proof by direct argument, contradiction and induction; (2) compare growth rates using logarithms and big-O notation; (3) explain why "how fast does the attack cost grow?" is the central question in cryptography; and (4) distinguish a mathematical claim from an empirical estimate. The chapter prepares discrete structures (Chapter 6) and probability (Chapter 12).
1.1 Why security students need proofs
A security claim is a statement about every attacker within a model, not about the attackers we happened to test. Testing a lock with ten picks shows it resisted ten picks; it does not show it resists the eleventh. Mathematics is the only tool that lets us make "for all" statements, and it does so by stating assumptions precisely. When a standard says a scheme is secure "if the Module-LWE problem is hard", that sentence is a conditional theorem: the conclusion is only as strong as the assumption, and the assumption is supported by decades of failed attacks rather than by proof. Learning to separate the proved part from the assumed part is the most useful mathematical habit in this book.
Three proof shapes recur. A direct proof chains true statements to the conclusion. A proof by contradiction assumes the opposite and derives something impossible; Euclid's proof that there are infinitely many primes is the classic example and underpins why RSA moduli can be chosen freely. Induction proves a base case and a step from n to n+1; it is how we reason about loops, hash chains and the counters inside stateful signatures.
1.2 Growth rates
Cryptographers measure security in bits: a "128-bit" problem needs about 2^128 basic operations. Logarithms convert between scales: log₂(10^30) ≈ 100, so 10^30 operations is about 2^100. Big-O notation keeps only the dominant term: an algorithm doing 3n³ + 50n steps is O(n³). The quantum threat is, at heart, a change in growth rate. Classically, the best known factoring algorithm grows sub-exponentially in the bit length of the number; Shor's algorithm (Shor, 1997) grows polynomially, roughly like n³ logical operations. For brute-force key search, Grover's algorithm (Grover, 1996) only reduces 2^k trials to about 2^(k/2) sequential iterations. One change is a collapse; the other is a square root that longer keys absorb.
1.3 Worked example
HCU's IT manager reads a headline saying quantum computers will "break all encryption". Using growth rates, we sort HCU's cryptography. RSA-2048 and elliptic-curve keys protect logins and VPN key exchange: a polynomial-time attack exists on a large fault-tolerant quantum computer, so these must be replaced. AES-256 encrypts the database: Grover leaves roughly 2^128 sequential work, still far beyond reach, so it stays. The headline is wrong in its scope, and the correction comes from a comparison of growth, not from an opinion.
1.4 Practical activity — Lab G
# Lab G (ch 1): growth rates that decide what quantum computers threaten.
import math
print("Symmetric key search: classical 2^k trials vs Grover ~2^(k/2) sequential iterations")
for k in (128, 192, 256):
print(f" k={k}: classical 2^{k}, Grover ~2^{k//2}")
def gnfs_bits(n_bits): # heuristic L_N[1/3, (64/9)^(1/3)] work, expressed in bits
ln_n = n_bits * math.log(2)
work = (64/9) ** (1/3) * ln_n ** (1/3) * math.log(ln_n) ** (2/3)
return work / math.log(2)
print("Factoring an n-bit RSA modulus: classical GNFS (heuristic) vs Shor gate count ~n^3")
for n in (1024, 2048, 3072):
print(f" n={n}: GNFS ~2^{gnfs_bits(n):.0f} operations; Shor ~n^3 = 2^{math.log2(n**3):.0f} logical gates")
Expected output:
Symmetric key search: classical 2^k trials vs Grover ~2^(k/2) sequential iterations
k=128: classical 2^128, Grover ~2^64
k=192: classical 2^192, Grover ~2^96
k=256: classical 2^256, Grover ~2^128
Factoring an n-bit RSA modulus: classical GNFS (heuristic) vs Shor gate count ~n^3
n=1024: GNFS ~2^87 operations; Shor ~n^3 = 2^30 logical gates
n=2048: GNFS ~2^117 operations; Shor ~n^3 = 2^33 logical gates
n=3072: GNFS ~2^139 operations; Shor ~n^3 = 2^35 logical gates
Read the output as a table of growth rates, not as predicted run times: the numbers ignore constants, error correction and hardware speed, which Chapter 19 treats as explicit assumptions.
Two contrasts stand out. For symmetric keys, Grover's search halves the exponent, so a 256-bit key still leaves a very large problem. For RSA, the gap is far wider: the classical cost grows faster than any polynomial in the key size, while Shor's cost grows only as the cube of it. Doubling the key from 1024 to 2048 bits adds a lot of classical work but only a few bits of quantum work. That difference is why RSA must be replaced rather than lengthened.
1.5 Common errors and limits
- Treating "secure if problem X is hard" as an unconditional proof.
- Comparing operation counts across machines as if a quantum gate and a classical instruction cost the same.
- Reading the heuristic factoring estimates as exact; they are order-of-magnitude guides.
Each error comes from forgetting what the calculation leaves out. Security proofs are conditional, so the condition must be stated beside the result. Operation counts compare growth, not wall-clock time, since a single error-corrected quantum operation may take far longer than a classical one. Heuristic estimates are useful for deciding which algorithms are in danger, not for predicting a date. A careful student writes the assumption next to every number.
Exercises
- EX001 — Bits of work. Express 10^24 operations and 10^24 × 2^20 operations in bits of work. Rubric: 3 = both correct with the logarithm shown.
- EX002 — Proof shape. Prove by induction that a hash chain of length n built as h₁ = H(s), h_{k+1} = H(h_k) requires exactly n hash evaluations. Rubric: 3 = base case, step and conclusion stated.
Synthesis
Security arguments combine proved implications with assumed hard problems. The quantum threat is a change in growth rate: polynomial-time Shor collapses factoring and discrete logarithms, while Grover only halves the exponent of key search.