Cryptography, from one-time pads to authenticated encryption and zero knowledge

Why this subject matters now

Three things changed in the last several years, and each one moved work from "specialists only" to "any engineer shipping a system." The first is that the protocol layer finally simplified. TLS 1.3, standardized in RFC 8446 in 2018 and now the overwhelming majority of new connections, deleted static RSA key transport, deleted CBC modes, deleted renegotiation, deleted compression, and left exactly one shape, ephemeral Diffie-Hellman for the key, an AEAD for the data, and a signature for identity. A generation of attacks, BEAST, CRIME, Lucky 13, POODLE, DROWN, ROBOT, targeted constructions that no longer exist in the protocol. Knowing why each was removed is still the fastest way to understand what a modern protocol is protecting against.

The second is that post-quantum cryptography stopped being a research topic and became a migration project. NIST published FIPS 203, 204, and 205 in August 2024, standardizing ML-KEM (from CRYSTALS-Kyber), ML-DSA (from CRYSTALS-Dilithium), and SLH-DSA (from SPHINCS+). Browsers and CDNs shipped hybrid X25519 + ML-KEM-768 key agreement in production well before that, because the harvest-now-decrypt-later threat applies to traffic recorded today and decrypted whenever a cryptographically relevant quantum computer exists. A practitioner in 2026 is expected to know what Shor's algorithm actually breaks (factoring and discrete log, completely), what Grover's algorithm actually costs (a square root, so AES-256 is fine and AES-128 is merely uncomfortable), and why hybrid deployment is the answer for key exchange but not for signatures.

The third is that cryptography moved from "protect the channel" to "prove things about data you cannot see." Zero-knowledge proof systems went from a 1985 definition to a deployed technology with proofs of a few hundred bytes verifiable in milliseconds. Secure multi-party computation runs private-set-intersection at advertising scale. Fully homomorphic encryption, impossible until Gentry's 2009 construction, now runs bootstrapped binary gates in the tens of milliseconds. None of these are drop-in, and all of them are routinely oversold, but the gap between what the literature can do and what a product can ship narrowed enough that engineers are asked about them.

Underneath all three is one discipline that does not change. State the game, state the assumption, write the reduction. The recurring failure in applied cryptography is not a broken cipher. AES has stood since 2001. The failures are a nonce reused, a MAC checked with a non-constant-time comparison, a padding error distinguishable from a MAC error, an RNG that was not seeded, a signature nonce that was a counter. Every one of those is a violation of a stated precondition of a security definition, which is why the definitions come first here.

Core theory

Kerckhoffs's principle and what a definition must contain

Auguste Kerckhoffs wrote in 1883 that a military cipher must remain secure even if everything about the system except the key becomes public. This is not a moral preference for openness. It is a statement about what can be repaired. Keys can be rotated, algorithms cannot. A design whose security rests on the adversary not knowing the algorithm has a single point of failure that fails permanently. Modern practice takes the principle further. The algorithm should be public, specified, and attacked by many people for years before deployment, because the only evidence available for a symmetric primitive is failed cryptanalysis.

A security definition has three parts, and a claim missing any of them is not a claim. First, the adversary's power, meaning what it can see, what it can ask for, and how much computation it gets. Second, the goal, meaning what counts as breaking the scheme, stated as an event whose probability is measured. Third, the quantification, which says that for all adversaries in some class, the probability of the break is bounded. "The ciphertext looks random" names no adversary, no goal, and no bound, so it is not a security definition, and a construction justified that way has been justified by nothing. This page will return to that point repeatedly, because almost every deployed cryptographic failure is a case where someone reasoned about appearance instead of about a game.

Perfect secrecy, defined

Fix a message space \(\mathcal{M}\), a key space \(\mathcal{K}\), a ciphertext space \(\mathcal{C}\), and an encryption scheme \((\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\) where \(\mathsf{Gen}\) samples a key, \(\mathsf{Enc}_k(m)\) produces a ciphertext, and \(\mathsf{Dec}_k(\mathsf{Enc}_k(m)) = m\) always. Shannon's 1949 definition of perfect secrecy is that the ciphertext carries no information about the plaintext.

The probability is over the key and over whatever distribution the message came from. An equivalent and more useful form drops the message distribution entirely. A scheme is perfectly secret if and only if for every pair of messages \(m_0, m_1\) of equal length and every ciphertext \(c\),

The equivalence is a two-line Bayes computation. Assume the second form and write \(\P[C=c] = \sum_{m'} \P[M=m'] \P[\mathsf{Enc}_k(m')=c]\). Since the inner probability is the same constant \(p_c\) for every \(m'\), the sum is \(p_c\), so \(\P[M=m \mid C=c] = \P[C=c \mid M=m]\P[M=m]/\P[C=c] = p_c \P[M=m]/p_c = \P[M=m]\). The converse runs the same computation backwards. The second form is preferable because it is a statement about the scheme alone, with no reference to how messages are distributed, and because it is the shape every later definition takes. An adversary cannot tell which of two messages was encrypted.

The one-time pad is perfectly secret

Let \(\mathcal{M} = \mathcal{K} = \mathcal{C} = \{0,1\}^n\), let \(\mathsf{Gen}\) sample \(k\) uniformly from \(\{0,1\}^n\), and let \(\mathsf{Enc}_k(m) = m \oplus k\), \(\mathsf{Dec}_k(c) = c \oplus k\). Correctness is immediate. \((m \oplus k) \oplus k = m\) because XOR is its own inverse. For secrecy, fix any \(m\) and any \(c\). Then

because \(m \oplus c\) is one specific string and \(k\) is uniform on \(2^n\) strings. The value \(2^{-n}\) does not depend on \(m\) at all, so the equal-probability condition holds for every pair \(m_0, m_1\), and the scheme is perfectly secret. The proof is three lines and it is worth noticing exactly which property of XOR did the work. For each fixed \(m\), the map \(k \mapsto m \oplus k\) is a bijection on the key space. Any group operation with that property works, and modular addition gives the same result. This is also precisely the property that fails when a pad is used twice, since \(c_1 \oplus c_2 = m_1 \oplus m_2\) eliminates the key and leaves a statement about plaintexts alone.

Shannon's theorem, that perfect secrecy needs \(|\mathcal{K}| \geq |\mathcal{M}|\)

The one-time pad's key is as long as its message, and that is not an artifact of the construction. It is forced.

Theorem (Shannon, 1949). If \((\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\) is perfectly secret over message space \(\mathcal{M}\) and key space \(\mathcal{K}\), then \(|\mathcal{K}| \geq |\mathcal{M}|\).

Proof. Suppose for contradiction that \(|\mathcal{K}| < |\mathcal{M}|\). Fix any message \(m_0 \in \mathcal{M}\) and any ciphertext \(c\) that occurs with positive probability when \(m_0\) is encrypted, so there is at least one key \(k\) with \(\mathsf{Enc}_k(m_0) = c\). Now consider the set

the set of messages that could possibly have produced \(c\) under some key. Because \(\mathsf{Dec}\) is a function, each key contributes at most one message, so \(|\mathcal{M}(c)| \leq |\mathcal{K}| < |\mathcal{M}|\). Therefore there exists a message \(m_1 \in \mathcal{M}\) with \(m_1 \notin \mathcal{M}(c)\). For that \(m_1\), no key encrypts it to \(c\). If some \(k\) had \(\mathsf{Enc}_k(m_1) = c\), then correctness would give \(\mathsf{Dec}_k(c) = m_1\) and \(m_1\) would be in \(\mathcal{M}(c)\). Hence

which contradicts perfect secrecy in the two-message form. Therefore \(|\mathcal{K}| \geq |\mathcal{M}|\). \(\blacksquare\)

Two consequences follow immediately and both are practical. An \(n\)-bit key cannot perfectly protect more than \(n\) bits of message, so a perfectly secret system needs key material at the rate of its traffic. This is why one-time pads survive only in niches where couriered key material is cheaper than the alternative. Second, the entropy version of the same statement, \(H(K) \geq H(M)\), shows the bound is about uncertainty rather than about literal key length. A 256-bit key file with 40 bits of real entropy buys 40 bits of secrecy. The theorem is what forces the rest of the subject to exist. If perfect secrecy is unaffordable, the escape is to weaken "no information" to "no information an efficient adversary can extract."

Computational security, with negligible functions, PPT, and the security parameter

The computational relaxation introduces a security parameter \(\lambda\) (in practice, the key length in bits) and quantifies over adversaries that run in probabilistic polynomial time in \(\lambda\). A function \(\nu: \N \to \R^{+}\) is negligible if it eventually shrinks faster than any inverse polynomial.

As examples, \(2^{-\lambda}\) and \(2^{-\sqrt{\lambda}}\) and \(\lambda^{-\log \lambda}\) are negligible, while \(1/\lambda^{100}\) is not. The definition is engineered so that negligible functions are closed under addition and under multiplication by any polynomial, which is exactly what proofs need. A reduction that loses a polynomial factor, or a hybrid argument that sums polynomially many negligible terms, still ends with something negligible. That closure is the entire reason the asymptotic framing is used at all.

A scheme is computationally secure if every probabilistic polynomial-time (PPT) adversary wins the relevant game with probability at most \(1/2 + \nu(\lambda)\) (for distinguishing games) or at most \(\nu(\lambda)\) (for forgery or inversion games). The asymptotic statement is a proof convenience and a terrible engineering guide, so applied work uses the concrete form instead. An adversary running in time \(t\) making \(q\) queries has advantage at most some explicit function \(\epsilon(t,q)\). "AES-128 is a secure PRP" becomes "no known attack does better than about \(2^{126}\) operations", and "SHA-256 is collision resistant" becomes "no collision is known and generic search costs \(2^{128}\)". Concrete bounds are what let an engineer answer the only question that matters in deployment, namely how much data may go under one key before the bound stops being comfortable.

Two more definitions used constantly below. An adversary's advantage in a game with a binary guess is \(\mathsf{Adv} = |\,2\P[\text{win}] - 1\,| = |\P[\text{output } 1 \mid b=1] - \P[\text{output } 1 \mid b=0]|\), the second form being the distinguishing formulation. And a reduction from problem \(P\) to scheme \(S\) is an explicit algorithm that, given black-box access to an adversary breaking \(S\) with advantage \(\epsilon\) in time \(t\), solves \(P\) with advantage roughly \(\epsilon\) in time roughly \(t\). The reduction is the proof. Its quality, how much advantage and time it loses, is what "tightness" means and it determines real key sizes.

Pseudorandom generators and the distinguishing game

A pseudorandom generator is a deterministic, efficiently computable function \(G: \{0,1\}^{\lambda} \to \{0,1\}^{\ell(\lambda)}\) with \(\ell(\lambda) > \lambda\) (it stretches) such that its output on a uniform seed is computationally indistinguishable from uniform. The game is simple. A challenger flips \(b\). If \(b = 0\) it hands the adversary \(G(s)\) for uniform \(s \in \{0,1\}^\lambda\), and if \(b = 1\) it hands a uniform string \(r \in \{0,1\}^{\ell}\). The adversary outputs a guess. \(G\) is a PRG if for all PPT \(D\),

Note what the definition does not say. It does not say the output passes statistical tests, though it implies that, since any test is a candidate distinguisher. It does not say the output is incompressible, though that is implied too. It says something stronger and cleaner, that no efficient procedure whatsoever separates the two distributions. That is why "it looks scrambled" is not a definition. Looking scrambled is the conclusion of passing the handful of tests someone happened to run, and the definition quantifies over all tests.

A PRG output is trivially distinguishable by an unbounded adversary. The image of \(G\) has at most \(2^{\lambda}\) points inside \(\{0,1\}^{\ell}\), a fraction \(2^{\lambda - \ell}\) of the space, so an exhaustive search over seeds decides membership perfectly. Computational security is therefore genuinely weaker than perfect secrecy, and the trade is worth it. A \(\lambda\)-bit seed protects \(\ell \gg \lambda\) bits of message, which Shannon's theorem forbids in the information-theoretic setting. The stream-cipher construction \(\mathsf{Enc}_k(m) = m \oplus G(k)\) is exactly this trade, and its security is exactly the PRG assumption. A distinguisher for the encryption becomes a distinguisher for \(G\) by a one-line reduction.

The hybrid argument, in full

The hybrid argument is the central proof technique in this subject. It is used so constantly that most texts introduce it once and then invoke it silently, which is why it is worked here from the start on a concrete case. The idea, to show two distributions are indistinguishable, is to build a sequence of intermediate distributions where consecutive ones differ in exactly one place, bound each neighboring gap by the assumption, and sum.

Claim. Let \(G: \{0,1\}^{\lambda} \to \{0,1\}^{2\lambda}\) be a PRG. Define the length-doubling iterate that produces \(n\) blocks. Set \(s_0 = s\), and for \(i = 1, \ldots, n\) write \(G(s_{i-1}) = (s_i, y_i)\) where \(s_i\) is the left \(\lambda\) bits (the next state) and \(y_i\) is the right \(\lambda\) bits (the output block). Let \(G^{n}(s) = (y_1, y_2, \ldots, y_n)\). Then \(G^n\) is a PRG, and for every distinguisher \(D\) running in time \(t\),

for a distinguisher \(D'\) running in time \(t + O(n \cdot t_G)\), where \(t_G\) is the cost of one evaluation of \(G\).

Proof. Define hybrid distributions \(H_0, H_1, \ldots, H_n\). In \(H_j\), the first \(j\) output blocks \(y_1, \ldots, y_j\) are drawn uniformly and independently, the state \(s_j\) is drawn uniformly, and the remaining blocks \(y_{j+1}, \ldots, y_n\) are produced by running the real iteration forward from \(s_j\).

H_0 : y1 y2 y3 ... yn      all real, from a uniform seed s0
H_1 : $1 y2 y3 ... yn      y1 uniform, s1 uniform, rest real from s1
H_2 : $1 $2 y3 ... yn      y1,y2 uniform, s2 uniform, rest real from s2
...
H_n : $1 $2 $3 ... $n      all uniform

\(H_0\) is exactly the output distribution of \(G^n\) on a uniform seed, and \(H_n\) is exactly the uniform distribution on \(n\lambda\) bits. By the triangle inequality,

It remains to bound one neighboring pair. Fix \(j\) and build \(D'_j\), a distinguisher for \(G\), as follows. \(D'_j\) receives a challenge string \(w \in \{0,1\}^{2\lambda}\), which is either \(G(s)\) for uniform \(s\) or uniform. It parses \(w = (\sigma, y)\) with \(\sigma, y \in \{0,1\}^{\lambda}\). It then constructs a candidate output vector. Blocks \(1\) through \(j-1\) are sampled uniformly by \(D'_j\) itself, block \(j\) is set to \(y\), and blocks \(j+1\) through \(n\) are computed by iterating the real \(G\) starting from state \(\sigma\). It hands the vector to \(D\) and echoes \(D\)'s output.

Now trace the two cases. If \(w = G(s)\) for uniform \(s\), then \((\sigma, y)\) is a real \(G\) output, so block \(j\) is real and the continuation runs from the real next state, which is precisely \(H_{j-1}\). If \(w\) is uniform, then \(y\) is uniform and independent, and \(\sigma\) is uniform and independent, so blocks \(1..j\) are uniform and the continuation runs from a uniform state, which is precisely \(H_j\). Therefore

Let \(D'\) be the \(D'_j\) achieving the largest such gap (or, to avoid non-uniformity, let \(D'\) pick \(j\) uniformly at random and lose a factor \(n\) that way instead). Summing the \(n\) terms gives the claim. \(D'\) runs \(D\) once and evaluates \(G\) at most \(n\) times, so the time overhead is \(O(n\, t_G)\). \(\blacksquare\)

Three things to take away, because they recur everywhere. The loss is linear in the number of hybrid steps. Stretching a PRG \(n\) times multiplies the adversary's advantage budget by \(n\), which is why concrete parameters care about how much output is drawn from one seed. The neighboring pair must differ in exactly one invocation of the assumption, otherwise the embedding does not work. And the reduction must be able to simulate everything around the embedded challenge. Here that meant \(D'_j\) sampling the earlier blocks itself and running \(G\) forward for the later ones. If a proof cannot simulate, it is not a proof.

A numeric feel for what the linear loss means. Suppose \(G\) has advantage at most \(2^{-60}\) against any adversary in the time budget of interest. Drawing \(n = 2^{20}\) blocks from a single seed gives \(2^{20} \cdot 2^{-60} = 2^{-40}\), still fine. Drawing \(n = 2^{40}\) blocks gives \(2^{-20}\), which is not fine at all. Rekeying exists because of arithmetic like this, not because of superstition.

Pseudorandom functions and permutations

A PRG produces one long string. A pseudorandom function produces an exponentially large table that the adversary may probe adaptively. A keyed function \(F: \{0,1\}^{\lambda} \times \{0,1\}^{n} \to \{0,1\}^{m}\) is a PRF if no efficient adversary with oracle access can tell \(F_k(\cdot)\) for a uniform key from a uniformly random function \(f: \{0,1\}^n \to \{0,1\}^m\).

The random function \(f\) is an object of size \(m2^{n}\) bits and cannot be written down, but it can be simulated lazily, answering each fresh query with fresh randomness and remembering it. That lazy-sampling view is how random functions appear inside proofs.

A pseudorandom permutation is the same game with a permutation. For each key, \(E_k: \{0,1\}^{n} \to \{0,1\}^{n}\) is a bijection, and the adversary must distinguish \(E_k\) from a uniformly random permutation. If the adversary also gets the inverse oracle the notion is a strong PRP. A block cipher is a family of permutations, and "AES is secure" means, formally, "AES is a strong PRP".

The two notions are close but not identical, and the gap is exactly the birthday term. A random function has collisions. A random permutation has none. That single difference is the whole content of the switching lemma.

PRP/PRF switching lemma. Let \(\pi\) be a uniformly random permutation on \(\{0,1\}^{n}\) and \(f\) a uniformly random function on the same domain. For any adversary \(A\) making at most \(q\) queries (without repeats),

Proof sketch with the term derived. Run \(A\) against a lazily-sampled random function. Define the "bad" event \(\mathsf{Coll}\), in which two distinct queries receive the same answer. Conditioned on \(\neg\mathsf{Coll}\), the answers from a random function are distinct and, for distinct inputs, uniformly distributed over distinct outputs, which is exactly the distribution a random permutation produces. So the two oracles are identical until \(\mathsf{Coll}\) occurs, and the identical-until-bad lemma bounds the distinguishing advantage by \(\P[\mathsf{Coll}]\). The \(i\)-th answer collides with one of the \(i-1\) previous answers with probability at most \((i-1)/2^{n}\), so by a union bound

The practical reading is that a block cipher may be treated as a random function for free until the number of blocks processed approaches \(2^{n/2}\). For AES with \(n = 128\), that is \(2^{64}\) blocks, or \(2^{68}\) bytes, comfortably beyond any real deployment. For a 64-bit block cipher such as 3DES or Blowfish, \(2^{32}\) blocks is 34 GB under a single key, which is why the Sweet32 attacks of 2016 were practical against long-lived HTTPS connections using 3DES, and why 64-bit block ciphers are gone. This is the same arithmetic that appears again in hash collisions, in GCM nonce collisions, and in CBC's security bound. The birthday bound is one calculation showing up in five places.

Semantic security and IND-CPA as games

Goldwasser and Micali introduced in 1984 the definition that replaced perfect secrecy as the working standard, and with it the entire game-based style. Semantic security says that whatever an efficient adversary can compute about the plaintext from the ciphertext, it could have computed without the ciphertext, given only the length. Formally, for every PPT \(A\) there is a PPT simulator \(S\) such that for every message distribution and every function \(h\) of the message, \(A\)'s probability of outputting \(h(m)\) from \(\mathsf{Enc}_k(m)\) exceeds \(S\)'s probability of outputting \(h(m)\) from \(|m|\) alone by at most a negligible amount. The definition captures the right intuition, and it is awkward to use in proofs. The equivalent indistinguishability form is what everyone actually works with.

The IND-CPA game. The challenger runs \(k \leftarrow \mathsf{Gen}(1^{\lambda})\) and flips a bit \(b\). The adversary \(A\) may query an encryption oracle \(\mathsf{Enc}_k(\cdot)\) as often as it likes, at any point. At some point it submits two equal-length messages \(m_0, m_1\) and receives the challenge \(c^{*} = \mathsf{Enc}_k(m_b)\). It may keep querying the oracle afterwards. Finally it outputs a guess \(b'\). Its advantage is

and the scheme is IND-CPA secure if this is negligible for all PPT \(A\). Notice what the chosen-plaintext oracle models, an adversary who can cause known data to be encrypted. That is not exotic. A web server encrypting a cookie that contains an attacker-chosen path, a VPN carrying attacker-generated packets, a database encrypting a field the attacker can write, all give the adversary exactly this oracle. The CRIME and BEAST attacks against TLS were mounted from precisely this position.

Deterministic encryption cannot be IND-CPA

Claim. If \(\mathsf{Enc}\) is deterministic and stateless, meaning \(\mathsf{Enc}_k(m)\) always yields the same ciphertext for the same \(k, m\), then there is an adversary with advantage \(1\) making two oracle queries.

Proof. The adversary picks any two distinct equal-length messages \(m_0 \neq m_1\), queries the oracle on \(m_0\), and stores the answer \(c_0 = \mathsf{Enc}_k(m_0)\). It then submits the pair \((m_0, m_1)\) and receives \(c^{*} = \mathsf{Enc}_k(m_b)\). It outputs \(b' = 0\) if \(c^{*} = c_0\) and \(b' = 1\) otherwise. If \(b = 0\), determinism forces \(c^{*} = c_0\), so \(b' = 0\) with probability 1. If \(b = 1\), then \(c^{*} = \mathsf{Enc}_k(m_1) \neq \mathsf{Enc}_k(m_0)\) because \(\mathsf{Dec}\) must recover distinct messages from them, so \(b' = 1\) with probability 1. Hence \(\P[b'=b] = 1\) and the advantage is 1. \(\blacksquare\)

Every IND-CPA secure scheme is therefore randomized or stateful. That single line explains a large fraction of practical cryptographic API design, the initialization vector in CBC, the nonce in CTR and GCM, the ephemeral key in ElGamal, the salt in OAEP and PSS. Each exists to make encryption non-deterministic. It also explains why deterministic encryption is sometimes still used deliberately, in searchable or order-preserving database encryption, and why those schemes leak equality patterns by construction. The leakage is not a bug in the implementation, it is what the definition says must happen.

Block ciphers, DES and AES and the absence of proofs

A block cipher is a keyed permutation on a fixed-width block. DES, standardized in 1977 with a 56-bit key and 64-bit block, is a 16-round Feistel network. Split the block into halves \((L_i, R_i)\), and set \(L_{i+1} = R_i,\ R_{i+1} = L_i \oplus F(R_i, k_i)\). The Feistel structure has a property worth stating because it is the reason the design was chosen. It is invertible regardless of whether \(F\) is invertible, since \(R_i = L_{i+1}\) and \(L_i = R_{i+1} \oplus F(L_{i+1}, k_i)\). That freedom lets the round function be an arbitrary nonlinear mess. DES fell to brute force, not to structure. The EFF's Deep Crack machine recovered a key in about 56 hours in 1998 for roughly a quarter of a million dollars in hardware. Its differential cryptanalysis resistance, discovered publicly by Biham and Shamir at the Weizmann Institute around 1990, turned out to have been known to the designers, which is a useful historical lesson about the value of open analysis.

AES (Rijndael, by Daemen and Rijmen, standardized 2001) is a substitution-permutation network on a 128-bit block with 10, 12, or 14 rounds for 128-, 192-, and 256-bit keys. Each round applies four transformations to a \(4\times4\) byte state, SubBytes (a fixed 8-bit S-box, algebraically the inverse in \(\mathrm{GF}(2^8)\) composed with an affine map, chosen for a flat difference distribution table), ShiftRows (cyclic row shifts), MixColumns (a fixed MDS matrix over \(\mathrm{GF}(2^8)\) applied to each column), and AddRoundKey (XOR with the round key). The design principle is explicit and worth knowing. SubBytes provides confusion, ShiftRows plus MixColumns provide diffusion, and the pair is chosen so the branch number of the linear layer guarantees a minimum number of active S-boxes over four rounds, which yields provable upper bounds on differential and linear trail probabilities.

AES round on the 4x4 state (128 bits, column-major)

  s00 s01 s02 s03      SubBytes      ShiftRows       MixColumns      AddRoundKey
  s10 s11 s12 s13   -> byte-wise  -> row i rotated -> column-wise -> XOR round key
  s20 s21 s22 s23      S-box          left by i       MDS matrix
  s30 s31 s32 s33

  confusion               diffusion (spreads one byte across a column,
                          then across the whole state in two rounds)

There is no proof that AES is a pseudorandom permutation, and there will not be one. A proof would imply \(\mathrm{P} \neq \mathrm{NP}\). What exists is the bound above on trail probabilities, which rules out the two classical attack families, plus twenty-five years of failed attacks by a large and motivated community. The best known key-recovery attacks on full AES-128 (biclique-style) improve on exhaustive search by roughly a factor of four, from \(2^{128}\) to about \(2^{126}\), which is cryptanalytically interesting and operationally irrelevant. This is the honest epistemic position for every symmetric primitive. Confidence comes from failed cryptanalysis, not from reduction. The reductions in this subject start one level up, where modes and protocols are proved secure assuming the block cipher is a PRP.

Modes of operation

A block cipher encrypts one block. A mode turns it into something that encrypts a message. The modes differ in exactly what they require of the caller, and every historical disaster in this area is a requirement that was not met.

ECB, and why "it looks scrambled" fails

Electronic codebook applies \(E_k\) to each block independently, so \(c_i = E_k(m_i)\). It is deterministic, so by the claim above it is not IND-CPA, with advantage 1 from two queries. The concrete leak is that equal plaintext blocks produce equal ciphertext blocks, so all block-level structure survives encryption. The canonical demonstration is an image whose outlines remain visible after ECB encryption. The measured version below is the same fact in numbers, where a plaintext with 5 blocks and 2 distinct values encrypts to a ciphertext with 5 blocks and 2 distinct values. Each individual ciphertext block is a perfectly good pseudorandom string. The scheme still fails, because security was never a property of individual blocks.

CBC and its IV requirement

Cipher block chaining sets \(c_0 = IV\) and \(c_i = E_k(m_i \oplus c_{i-1})\), decrypting as \(m_i = D_k(c_i) \oplus c_{i-1}\). The chaining destroys the equal-blocks leak, and the IV supplies the randomness IND-CPA requires. The IV must be unpredictable to the adversary, not merely unique. If the adversary can predict the next IV, it can mount a chosen-plaintext attack. To test whether an unknown block \(m^{*}\) (encrypted earlier under known \(c_{j-1}\)) equals a guess \(g\), submit the plaintext block \(g \oplus c_{j-1} \oplus IV_{\text{next}}\). The resulting ciphertext block equals \(c_j\) exactly when the guess is right. This is the BEAST attack against TLS 1.0, which used the last ciphertext block of the previous record as the next IV, making it perfectly predictable. TLS 1.1 fixed it by putting an explicit random IV in every record.

CBC's security proof, assuming \(E_k\) is a PRP and IVs are uniform, gives an IND-CPA advantage bounded by roughly \(\sigma^{2}/2^{n}\) where \(\sigma\) is the total number of blocks encrypted and \(n\) the block size. It is again a birthday bound, and it comes from the possibility that two inputs to \(E_k\) collide, after which the mode's outputs reveal a plaintext XOR. CBC is also not parallelizable for encryption (each block needs the previous ciphertext) though it is for decryption, and it requires padding, which is where the next problem comes from.

CTR mode and its reduction to a PRF

Counter mode turns a block cipher into a stream cipher, \(c_i = m_i \oplus E_k(\mathrm{nonce} \,\|\, i)\). Encryption and decryption are the same operation, both parallelize, no padding is needed, and only the forward direction of the cipher is used, so \(E_k\) need only be a PRF rather than a PRP. The security proof is the cleanest of any mode and worth writing out.

Claim. If \(F\) is a secure PRF, CTR mode is IND-CPA, with \(\mathsf{Adv}^{\mathrm{cpa}}_{\mathrm{CTR}}(A) \leq 2\,\mathsf{Adv}^{\mathrm{prf}}_{F}(B)\) for an adversary \(B\) with essentially the same running time, provided no counter value is ever repeated.

Proof sketch, with the steps. Game 0 is the real IND-CPA game. Game 1 replaces \(F_k\) with a truly random function \(f\). Any adversary whose behavior changes between Game 0 and Game 1 yields a PRF distinguisher directly. \(B\) runs the IND-CPA game using its own oracle wherever the mode calls \(F_k\), which it can do because the mode only ever evaluates \(F\) in the forward direction on inputs \(B\) knows. So \(|\P[\text{win}_0] - \P[\text{win}_1]| \leq \mathsf{Adv}^{\mathrm{prf}}_{F}(B)\). In Game 1, every counter input is distinct by assumption, so every keystream block \(f(\mathrm{nonce}\|i)\) is an independent uniform \(n\)-bit string never used elsewhere. The challenge ciphertext is therefore a one-time pad of \(m_b\) with fresh uniform bits, whose distribution is uniform and independent of \(b\), so \(\P[\text{win}_1] = 1/2\) exactly. Combining, the advantage is at most \(\mathsf{Adv}^{\mathrm{prf}}_{F}(B)\) in the distinguishing normalization (twice that in the \(2\P-1\) normalization). \(\blacksquare\)

Two clauses in that proof are load-bearing and both are the caller's responsibility. "No counter value is ever repeated" is a precondition, not a conclusion. Violate it and the keystream repeats. And when \(F\) is a block cipher rather than an ideal PRF, the switching lemma adds \(\sigma^{2}/2^{n+1}\) for \(\sigma\) blocks, because a permutation's keystream blocks are distinct where a random function's would sometimes collide. Both terms show up in the data limits that standards quote.

Stream ciphers and the nonce-reuse catastrophe, worked

Every stream cipher, whether CTR mode, ChaCha20, or a dedicated design, produces a keystream from a key and a nonce and XORs it into the plaintext. Reusing a (key, nonce) pair reproduces the keystream, and then

The key has vanished from the equation. What remains is a classical problem, recovering two plaintexts from their XOR, which is easy whenever the plaintexts have structure. English text has roughly one bit of entropy per character against seven or eight bits of representation. Protocol messages have fixed headers. JSON has known field names. If any part of \(m_1\) is known, the corresponding part of \(m_2\) follows by a single XOR, with no cryptanalysis at all. The measured demonstration below recovers a full second plaintext from a known first one under a repeated CTR nonce.

The same arithmetic makes CTR and every stream cipher malleable. Flipping bit \(j\) of the ciphertext flips bit \(j\) of the plaintext, exactly and predictably, with no knowledge of the key. In the run below, flipping one bit of the ciphertext turns the plaintext "attack" into "Attack". Confidentiality without integrity is not a coherent security goal for almost any real system, which is the entire argument for authenticated encryption.

Padding oracles, and why unauthenticated CBC is dangerous

CBC needs the plaintext padded to a block multiple, and PKCS#7 pads with \(p\) bytes each equal to \(p\). On decryption, a receiver that distinguishes "padding malformed" from "padding fine but something else failed", whether by error message, by response time, or by any other observable, hands the adversary a one-bit oracle. Vaudenay showed at EPFL in 2002 that this single bit is enough to decrypt arbitrary ciphertext.

To attack ciphertext block \(C_j\), the adversary submits a two-block ciphertext \((R, C_j)\) with \(R\) under its control. The receiver computes \(P = D_k(C_j) \oplus R\) and checks the padding of \(P\). Write \(I = D_k(C_j)\), the unknown intermediate. Setting the last byte of \(R\) to \(r_{15}\) makes the last plaintext byte \(I_{15} \oplus r_{15}\). The adversary sweeps \(r_{15}\) through all 256 values until the padding validates, which happens (almost always) exactly when that byte is \(\texttt{0x01}\), revealing \(I_{15} = r_{15} \oplus \texttt{0x01}\). Then it fixes \(r_{15} = I_{15} \oplus \texttt{0x02}\) and sweeps \(r_{14}\) for a valid \(\texttt{0x02 0x02}\), and so on up the block. Sixteen sweeps of at most 256 queries recover the entire intermediate, and the real plaintext is \(I \oplus C_{j-1}\). The measured run below recovers a 35-byte secret in 6,560 oracle queries, about 137 queries per byte against a theoretical average near 128.

The lesson generalizes past padding. Lucky 13 (AlFardan and Paterson, 2013) exploited a timing difference of a few microseconds in TLS's MAC-then-encrypt CBC construction, caused by how much data the HMAC had to process after padding removal. From this follows the general rule that decryption must not reveal any information about a failed decryption beyond the single fact that it failed, and the only reliable way to achieve that is to authenticate the ciphertext before decrypting it at all.

Message authentication codes

A MAC is a keyed tag \(t = \mathsf{Mac}_k(m)\), verified by \(\mathsf{Vrfy}_k(m, t) \in \{0,1\}\). The security notion is existential unforgeability under chosen-message attack.

EUF-CMA. The challenger picks \(k\). The adversary queries \(\mathsf{Mac}_k(\cdot)\) on messages of its choice, collecting a set \(Q\). It wins if it outputs a pair \((m^{*}, t^{*})\) with \(\mathsf{Vrfy}_k(m^{*}, t^{*}) = 1\) and \(m^{*} \notin Q\). The scheme is secure if every PPT adversary wins with negligible probability. Three details matter. "Existential" means any message counts, including nonsense. The adversary does not have to forge something meaningful, because meaningfulness is not something the cryptography can define. "Chosen-message" means the adversary sees tags on messages it picked, adaptively. And strong unforgeability (SUF-CMA) additionally forbids producing a new valid tag on an already-queried message, which matters when tags are used as identifiers or in AEAD composition.

Any secure PRF is a secure MAC, with a short proof worth keeping in mind. Set \(\mathsf{Mac}_k(m) = F_k(m)\) truncated to \(\ell\) bits. Replace \(F_k\) with a random function \(f\). The change costs \(\mathsf{Adv}^{\mathrm{prf}}\). Against \(f\), the tag on an unqueried \(m^{*}\) is a uniform \(\ell\)-bit string the adversary has never seen, so it guesses correctly with probability \(2^{-\ell}\). The total forgery probability is \(\mathsf{Adv}^{\mathrm{prf}}_{F} + 2^{-\ell}\). The \(2^{-\ell}\) term is why 128-bit tags are standard and why truncating a tag to 32 bits gives an attacker a one-in-four-billion forgery per attempt, which is not enough when attempts are free.

CBC-MAC and the length-extension pitfall

CBC-MAC computes the CBC chain with a zero IV and outputs only the last block, \(t = c_L\) where \(c_i = E_k(m_i \oplus c_{i-1})\), \(c_0 = 0^{n}\). It is a secure PRF on fixed-length messages and completely broken on variable-length ones.

The forgery. Query the tag on a one-block message \(m\), getting \(t = E_k(m)\). Query the tag on another one-block message \(m'\), getting \(t' = E_k(m')\). Now consider the two-block message \(M = m \,\|\, (m' \oplus t)\). Its CBC-MAC is

So \((M, t')\) is a valid forgery on a message never queried, with two queries and no computation. The fixes are all about binding the length. CMAC (NIST SP 800-38B, from Iwata and Kurosawa's OMAC) XORs a derived subkey into the last block, and ECBC-MAC encrypts the final block under a second key. Both destroy the algebraic identity above, and both are provably secure for variable-length inputs.

HMAC and why the construction is nested

Bellare, Canetti, and Krawczyk proposed HMAC in 1996 to build a MAC from an unkeyed Merkle-Damgård hash.

with \(\mathrm{ipad} = \texttt{0x36}\) repeated to the block length and \(\mathrm{opad} = \texttt{0x5c}\) repeated likewise, and \(k\) zero-padded to the hash's block size (or hashed first if longer). The obvious construction \(H(k \| m)\) is broken by length extension, which is a structural property of Merkle-Damgård covered below. An attacker who knows \(H(k\|m)\) and \(|k|\) computes \(H(k \| m \| \mathrm{pad} \| m')\) without knowing \(k\). The demonstration below carries out that forgery against \(H(\text{secret} \| \text{message})\) with SHA-256 and then shows the identical attempt failing against HMAC.

The outer hash is what stops it. The final output is \(H(\text{opad-key} \| \text{inner digest})\), and the inner digest is a complete, finalized hash value rather than an internal chaining state that an attacker can continue from. The reverse composition \(H(m \| k)\) is also unsuitable, since a collision in \(H\) on the message part transfers directly to a tag collision. The two distinct pads matter because they derive two different keys from one, so the inner and outer functions are keyed independently. The security proof treats the compression function as a PRF under both derived keys and shows HMAC is a PRF, with a bound that degrades at the birthday level in the number of queries.

Carter-Wegman MACs and polynomial universal hashing

Wegman and Carter showed in 1981 that a MAC does not need a cryptographic primitive over the whole message. It needs a fast universal hash of the message plus one cryptographic value per message. A family \(\{h_r\}\) is \(\epsilon\)-almost-XOR-universal if for all distinct \(m \neq m'\) and all \(\delta\), \(\P_r[h_r(m) \oplus h_r(m') = \delta] \leq \epsilon\). Given such a family and a per-message pseudorandom pad \(s\), set

Forging on a new message requires predicting \(h_r(m^{*}) \oplus h_r(m)\) for the message whose tag was seen, which the universality bound caps at \(\epsilon\). The pad must be fresh per message, produced by a PRF applied to a nonce.

The universal hash of choice is polynomial evaluation. Interpret the message blocks \(m_1, \ldots, m_L\) as coefficients of a polynomial and evaluate at the key \(r\) in a finite field.

For two distinct messages, the difference is a nonzero polynomial of degree at most \(L\) in \(r\), which has at most \(L\) roots in the field, so \(\epsilon \leq L/|\mathbb{F}|\). The collision probability grows linearly in message length and shrinks with field size. GMAC (the authentication half of GCM) does this in \(\mathrm{GF}(2^{128})\) with the reduction polynomial \(x^{128} + x^{7} + x^{2} + x + 1\), which is why GCM is fast on hardware with a carry-less multiply instruction. Poly1305 (Bernstein, 2005) does it modulo the prime \(2^{130} - 5\) with the key \(r\) partially clamped so that 32-bit-limb arithmetic never overflows, which is why it is fast in software without special instructions.

The catastrophic requirement is that \(s\) is never reused. Two tags under the same pad let the adversary subtract them, eliminating \(s\) and leaving a polynomial equation whose roots include the hash key \(r\). Solving it recovers \(r\), then \(s\), and then the adversary can forge any message. The demonstration below carries this out end to end in a 61-bit prime field, two tags under one pad, one quadratic solved, hash key recovered, pad recovered, arbitrary forgery produced. This is not a degradation, it is total authentication failure, and it is exactly what a repeated GCM nonce causes.

Authenticated encryption

Confidentiality and integrity are separate goals, and combining primitives that each achieve one does not automatically achieve both. Bellare and Namprempre (2000) settled which compositions work, and Krawczyk (2001) analyzed the same question in the setting TLS actually used. The table gives the three candidates, assuming an IND-CPA scheme and an EUF-CMA MAC with independent keys.

The failure of encrypt-and-MAC is immediate from a definition already proved. The MAC is deterministic, so equal plaintexts give equal tags, so the ciphertext-plus-tag pair is distinguishable exactly as deterministic encryption was, with advantage 1. The failure of MAC-then-encrypt is subtler and is the reason padding oracles were exploitable in TLS. The receiver must decrypt before it can check the MAC, so every malformed ciphertext gets processed by the decryption path, and every observable difference in that path is an oracle. Encrypt-then-MAC inverts the order, rejecting on a bad tag before touching the decryption routine, so a forged ciphertext never reaches code that could leak anything. The rule to remember is that encrypt-then-MAC is the only composition that is secure for all secure components, and that "verify the tag first, in constant time, then decrypt" is the shape every correct implementation has.

AEAD and associated data

Rogaway's nonce-based AEAD interface (2002) is the abstraction that won. Encryption takes a key, a nonce, associated data, and a plaintext, and returns a ciphertext. Decryption takes the same key, nonce, and associated data plus the ciphertext, and returns either the plaintext or a failure symbol.

  Enc(K, N, A, P) -> C          Dec(K, N, A, C) -> P or FAIL

  K  key            secret, long-lived
  N  nonce          unique per (K, message); public; NOT secret; NOT random-required
  A  associated     authenticated but not encrypted: routing headers, version tags,
     data           record sequence numbers, tenant ids
  P  plaintext      encrypted and authenticated
  C  ciphertext     includes the authentication tag

Associated data exists because real messages have parts that must travel in the clear and still must not be modifiable, such as an IP header a router has to read, a database row key, or a protocol version field. If those are not authenticated, an attacker can redirect or downgrade a message whose payload is perfectly protected. The AEAD security definition is a single game combining IND-CPA with ciphertext integrity. The adversary gets an encryption oracle and a decryption oracle, and it wins by distinguishing the challenge or by getting the decryption oracle to accept any \((N, A, C)\) it did not receive from encryption. Under that definition, a scheme's guarantee is exactly the guarantee the caller needs, which is why AEAD is the interface application code should see.

GCM, ChaCha20-Poly1305, and the exact cost of a repeated nonce

AES-GCM is CTR mode for confidentiality plus GMAC for integrity, sharing one key. The authentication key is \(H = E_k(0^{128})\), the block cipher applied to the all-zero block. GHASH evaluates the polynomial in \(H\) over the ciphertext and associated data, and the result is masked with \(E_k(N \| 1)\), the counter-zero keystream block for that nonce. ChaCha20-Poly1305 (RFC 8439) is the analogous construction from Bernstein's ChaCha20 stream cipher and Poly1305, with the one-time Poly1305 key derived as the first 32 bytes of the ChaCha20 keystream for that nonce.

Now the consequence of nonce reuse, precisely. Two encryptions under one \((K, N)\) do two kinds of damage.

• Confidentiality is gone for those two messages. The CTR keystream is identical, so \(C_1 \oplus C_2 = P_1 \oplus P_2\), verified in the measured run below with real AES-GCM.
• Authentication is gone for the entire key. Both tags used the same mask \(E_k(N\|1)\) and the same \(H\). Subtracting the two GHASH equations cancels the mask and leaves a polynomial equation over \(\mathrm{GF}(2^{128})\) whose unknown is \(H\). Its degree is the block length of the longer message, and factoring it (Berlekamp's algorithm, cheap at these degrees) yields a small candidate set containing \(H\). With \(H\) known, the adversary can compute GHASH itself, so it can forge a valid tag for any ciphertext under any nonce for which it can obtain or has obtained one mask value, and in particular can modify messages under the reused nonce at will. This is Joux's "forbidden attack", and it was found in the wild by Böck, Zauner, Devlin, Somorovsky, and Jovanovic (2016) against TLS servers with faulty nonce generation.

The asymmetry is what surprises people. The confidentiality loss is local to the two messages, the authentication loss is global to the key. That is why the correct response to a suspected nonce reuse is to rotate the key, not to re-send the messages.

Misuse-resistant AEAD

Rogaway and Shrimpton's SIV construction (2006) asks what the best possible behavior under nonce reuse is, and answers that the scheme should leak only whether two (nonce, associated data, plaintext) triples were identical, and nothing else. SIV achieves this by deriving the synthetic IV from the message itself as \(IV = \mathsf{PRF}_{k_1}(N, A, P)\), then encrypting with CTR under \(IV\) and \(k_2\), and shipping \(IV\) as the tag. Two identical messages under one nonce produce identical ciphertexts (unavoidable, since the scheme is deterministic given its inputs), but two different messages produce unrelated IVs and therefore unrelated keystreams, so the XOR leak never happens and the authentication key is never exposed. AES-GCM-SIV (RFC 8452, from Gueron, Langley, and Lindell) is the modern instantiation with performance close to GCM.

The cost is that SIV is two-pass. The whole plaintext must be read to compute the IV before encryption can start, which rules it out for streaming with bounded memory. The engineering decision is therefore explicit. If nonce uniqueness can be guaranteed by construction, use GCM or ChaCha20-Poly1305 and go fast in one pass. If nonce uniqueness depends on distributed state that might fail, pay for the second pass and get a scheme whose worst case is survivable.

Hash functions

A cryptographic hash \(H: \{0,1\}^{*} \to \{0,1\}^{n}\) compresses arbitrary input to a fixed digest. Three security properties are usually named, and they are genuinely different, so keeping them separate is not pedantry.

Collision resistance means it is infeasible to find \(x \neq x'\) with \(H(x) = H(x')\). Second-preimage resistance means that given \(x\), it is infeasible to find \(x' \neq x\) with \(H(x') = H(x)\). Preimage resistance means that given \(y\), it is infeasible to find any \(x\) with \(H(x) = y\).

Collision resistance implies second-preimage resistance (an algorithm for the latter, run on a random \(x\), produces a collision), and second-preimage resistance does not imply preimage resistance, nor the reverse, in general. A clean separation follows. Let \(H'\) be a collision-resistant hash on \(n\) bits and define \(G(x) = 0 \| x\) if \(|x| = n\), and \(G(x) = 1 \| H'(x)\) otherwise. \(G\) is collision resistant (a collision either collides \(H'\) or equates two identical short strings), but it is trivially not preimage resistant on the first branch, since a digest beginning with 0 reveals its preimage outright. The generic attack costs also differ. Preimage and second preimage take \(2^{n}\) work, collision takes \(2^{n/2}\), which is why SHA-256 is described as offering 128 bits of collision resistance and 256 bits of preimage resistance from the same 256-bit digest.

The birthday bound, derived and measured

Draw \(q\) values independently and uniformly from a set of size \(N = 2^{n}\). The probability that all are distinct is

Take logarithms and use \(\ln(1-x) \leq -x\).

In the other direction the union bound over the \(\binom{q}{2}\) pairs gives \(\P[\text{collision}] \leq q(q-1)/(2N)\), so the two bounds sandwich the truth and both say the same thing, that collisions appear when \(q \approx \sqrt{N}\). Setting the exponent to \(\ln 2\) gives the median at \(q \approx 1.177\sqrt{N}\), and the expected number of draws to the first collision is \(\sqrt{\pi N/2} \approx 1.253\sqrt{N}\), a standard computation from \(\E[T] = \sum_{q \geq 0}\P[T > q]\) with the product above approximated by \(e^{-q^{2}/2N}\).

The expected number of collisions among \(q\) draws is easier and exact. Define \(X_{ij} = 1\) when draws \(i\) and \(j\) match, so \(\E[X_{ij}] = 1/N\) and by linearity \(\E[\#\text{collisions}] = \binom{q}{2}/N = q(q-1)/2N\), with no independence assumption needed. Both predictions are checked against measurement in the implementation section. Truncated SHA-256 digests at 16, 20, 24, and 28 bits give mean first-collision times within a few percent of \(\sqrt{\pi N/2}\) over 400 trials each, and collision counts at \(N = 2^{32}\) match \(q(q-1)/2N\) to within sampling noise (4.90 measured against 4.66 predicted at \(q = 200{,}000\)).

The consequences are everywhere. A 128-bit digest gives 64-bit collision resistance, which is why MD5 (128 bits) and SHA-1 (160 bits) are dead. MD5 collisions cost seconds on a laptop after Wang and Yu's 2004 differential attack, and SHA-1 fell to the SHAttered collision from CWI and Google in 2017 at about \(2^{63.1}\) work, then to a chosen-prefix collision by Leurent and Peyrin in 2020. Note that SHA-1's preimage resistance is still intact. It is collision resistance that broke, which is why signatures over attacker-influenced documents fell while HMAC-SHA1, which does not rely on collision resistance, did not.

Merkle-Damgård and length extension

MD5, SHA-1, and the SHA-2 family are Merkle-Damgård constructions. Pad the message to a block multiple with a \(\texttt{0x80}\) byte, zeros, and the 64-bit message length, then iterate a compression function \(f: \{0,1\}^{n} \times \{0,1\}^{b} \to \{0,1\}^{n}\) over the blocks with a fixed initialization vector, \(h_i = f(h_{i-1}, m_i)\), and output \(h_L\). The Merkle-Damgård theorem says the construction is collision resistant if \(f\) is. The proof walks a collision on \(H\) backwards through the chain and finds a colliding pair of compression-function inputs, with the length in the padding ensuring the two messages have the same block count or produce a collision in the final block.

The structural weakness is that the output is the internal state. An attacker holding \(H(m)\) knows \(h_L\) exactly and can continue the iteration.

computable without knowing \(m\), let alone any secret prefix. That makes \(H(k \| m)\) a broken MAC, as demonstrated in the code below, where a valid tag on \(\texttt{user=guest\&role=viewer} \| \mathrm{pad} \| \texttt{\&role=admin}\) is forged from a legitimate tag without ever learning the key. It also motivates the SHA-512/256 truncation and the SHA-3 design. Truncating the output hides most of the state and blocks the attack. This is why SHA-384 and SHA-512/256 are not length-extendable, while SHA-256 and SHA-512 are.

Sponges and SHA-3

Keccak, selected as SHA-3 in 2012, uses the sponge construction of Bertoni, Daemen, Peeters, and Van Assche. State of \(b = r + c\) bits split into a rate \(r\) and a capacity \(c\). Absorbing XORs each \(r\)-bit message block into the rate portion and applies a fixed permutation \(f\) to the whole state. Squeezing reads \(r\) bits at a time from the rate, applying \(f\) between reads. The capacity is never touched directly by input or output.

  absorb                                   squeeze
  m1      m2      m3                        z1      z2
  |       |       |                         ^       ^
  v       v       v                         |       |
 [r]-+-> [r]-+-> [r]-+---------------------[r]-+---[r]
 [c] |   [c] |   [c] |                     [c] |   [c]
     f       f       f                         f
  capacity c is never read or written by the caller;
  generic security is min(c/2, output/2) for collisions

The sponge's security is governed by the capacity, giving collision resistance \(2^{c/2}\) and preimage resistance \(2^{c/2}\) in the indifferentiability framework (with the output length as the other constraint). SHA3-256 uses \(r = 1088, c = 512\) on a 1600-bit state. Because the output never exposes the full state, sponges are not length-extendable, so \(\mathsf{SHA3}(k \| m)\) is a sound MAC and KMAC is standardized on exactly that basis. The same permutation gives SHAKE128 and SHAKE256, extendable-output functions that emit as many bytes as asked, which is what lattice schemes use for deterministic matrix expansion.

Choosing among SHA-2, SHA-3, and BLAKE3. SHA-256 remains the default for interoperability and is fast on any CPU with the SHA extensions. Its only sharp edge is length extension, which matters exactly when someone builds a homemade prefix MAC. SHA-3 is the structurally different backup, valuable precisely because a break of the Merkle-Damgård family would not transfer to it, and it is the right choice when a sponge's flexibility (XOFs, KMAC, domain separation by suffix) is wanted. On general-purpose CPUs without acceleration it is typically slower than SHA-2. BLAKE3, from O'Connor, Aumasson, Neves, and Wilcox-O'Hearn, is a Merkle-tree construction over a reduced BLAKE2 compression function. Its internal tree structure means hashing parallelizes across cores and SIMD lanes, and it provides keyed hashing and a KDF mode natively. The team reports single-threaded throughput several times that of SHA-256 on machines without SHA hardware, with the gap widening further when multiple cores are used. The practical rule is SHA-256 if an external standard names it, BLAKE3 if throughput on large inputs dominates and the format is yours to choose, and SHA-3 if diversity of structure or an XOF is the requirement.

Merkle trees and inclusion proofs

A Merkle tree hashes \(n\) leaves pairwise up to a single root, so a proof that a particular leaf is in the set consists of the \(\lceil \log_2 n \rceil\) sibling hashes along the path. Verification recomputes the root from the leaf and the siblings and compares. Forging an inclusion proof for an element not in the set requires a collision in the hash, so the tree inherits the hash's security.

Two implementation details are security-relevant. Leaves and internal nodes must be hashed with different domain separators (\(H(\texttt{0x00} \| \text{leaf})\) versus \(H(\texttt{0x01} \| L \| R)\)). Without that, an attacker can present an internal node as if it were a leaf, which is the second-preimage attack that RFC 6962 explicitly defends against. And trees with a duplicated last node on odd levels, the convention Bitcoin uses, admit distinct leaf sequences with the same root, a malleability bug that has been exploited in practice. The worked example below builds an eight-leaf tree, prints every level, produces the three-hash proof for leaf 5, verifies it, and shows that the same proof rejects leaf 4.

Merkle trees are what make certificate transparency logs, content addressing, blockchain block headers, and BLAKE3's parallelism all work. The scaling is the point. An inclusion proof for one leaf among \(2^{20}\) is 20 hashes, 640 bytes, verified with 20 compression calls, independent of how large the underlying set is.

Password hashing and memory hardness

Passwords have far less entropy than keys, so a password hash must be deliberately slow. A fast hash such as SHA-256 lets an attacker with a GPU test billions of candidates per second against a stolen database. There are three generations of defense, PBKDF2 (iterate a PRF many times), bcrypt (Provos and Mazières, 1999, using a modified Blowfish key schedule with a tunable cost, so cost 12 means \(2^{12} = 4096\) iterations of the expensive setup), and the memory-hard functions scrypt (Percival, 2009) and Argon2 (Biryukov, Dinu, and Khovratovich, winner of the Password Hashing Competition in 2015, specified in RFC 9106).

The memory-hardness argument is an economic one and worth stating precisely. An attacker's advantage comes from parallel hardware. A GPU has thousands of cores, an ASIC can have far more, and iteration count alone scales the defender's cost and the attacker's cost by the same factor, leaving the ratio unchanged. Memory does not scale that way. If evaluating the function requires \(M\) bytes of fast memory held for the duration, then \(P\) parallel evaluations require \(P \cdot M\) bytes, and memory is the expensive, non-shrinking part of any chip. Formally these functions are analyzed by their time-memory product. A pebbling argument shows that reducing memory below the design point forces recomputation that raises time enough to keep \(T \times M\) roughly constant, so the attacker cannot trade away the cost. Argon2id at 64 MiB with one pass and one lane costs a server tens of milliseconds and costs an attacker 64 MiB of dedicated memory per parallel guess. At a million guesses in parallel that is 64 TB of RAM, which is the entire point.

Every password hash also needs a per-user random salt, which defeats precomputed rainbow tables and ensures that two users with the same password get different stored values, and modern deployments add a server-held secret "pepper" so that a database dump alone is not enough. None of this makes a weak password strong. It converts an instant break into an expensive one and buys time to rotate.

Number theory for public-key cryptography

Public-key cryptography needs a structure where some operation is easy and its inverse is not. Every deployed scheme gets that from one of two places, the difficulty of factoring or the difficulty of computing discrete logarithms in a well-chosen group.

Work in \(\Z_n = \{0, 1, \ldots, n-1\}\) with addition and multiplication mod \(n\). The multiplicative group \(\Z_n^{*}\) consists of the residues coprime to \(n\), and its size is Euler's totient \(\varphi(n)\), which is \(p - 1\) for prime \(p\) and \((p-1)(q-1)\) for \(n = pq\) with distinct primes. Lagrange's theorem gives the fact everything rests on. For any \(a \in \Z_n^{*}\),

with Fermat's little theorem \(a^{p-1} \equiv 1 \pmod p\) as the prime case. The proof is one line once the group structure is in view. The order of any element divides the order of the group, so \(a^{|G|} = (a^{\mathrm{ord}(a)})^{|G|/\mathrm{ord}(a)} = 1\). Exponents therefore live mod \(\varphi(n)\), which is exactly why RSA decryption works.

A group is cyclic if some element \(g\) generates it, so every element is \(g^{i}\). \(\Z_p^{*}\) is cyclic for prime \(p\), and \(g\) is called a generator or primitive root. The discrete logarithm problem is, given \(g\) and \(h = g^{x}\), to find \(x\). It is easy in \((\Z_n, +)\) (division), believed hard in \(\Z_p^{*}\) for large \(p\), and believed harder still, in the sense that only generic attacks are known, in a well-chosen elliptic curve group.

The Chinese remainder theorem states that for coprime \(m_1, m_2\), the map \(x \mapsto (x \bmod m_1, x \bmod m_2)\) is a ring isomorphism \(\Z_{m_1 m_2} \to \Z_{m_1} \times \Z_{m_2}\). Constructively, \(x = a_1 m_2 (m_2^{-1} \bmod m_1) + a_2 m_1 (m_1^{-1} \bmod m_2) \bmod m_1m_2\). RSA implementations use it to decrypt roughly four times faster. Compute \(m_p = c^{d \bmod (p-1)} \bmod p\) and \(m_q = c^{d \bmod (q-1)} \bmod q\) on half-size moduli, then recombine. Two exponentiations on \(k/2\)-bit numbers cost about \(2 \cdot (1/8)\) of one on \(k\)-bit numbers, since modular exponentiation is cubic in the bit length. The measured toy run below confirms CRT decryption agrees with the direct computation on every ciphertext in the space. The same trick is a liability. A single bit flip during one of the two half-computations lets an attacker factor \(n\) from one faulty signature by computing \(\gcd(\sigma^{e} - m, n)\), the Bellcore fault attack of Boneh, DeMillo, and Lipton (1997), which is why implementations verify signatures before releasing them.

The algorithms that set key sizes

Key sizes are not chosen by taste. They are chosen so that the best known algorithm costs more than an attacker can spend.

Pollard rho for generic discrete log. In a group of prime order \(N\) with no exploitable structure, the best known attack is a birthday search. Pollard's rho method walks a pseudorandom sequence in the group and detects a cycle. The expected number of steps is \(\sqrt{\pi N/4} \approx 0.886\sqrt{N}\), with constant memory using Floyd or Brent cycle finding, and it parallelizes with a linear speedup using distinguished points (van Oorschot and Wiener). For a curve of order \(2^{256}\) that is \(2^{127.8}\) group operations, so a 256-bit curve gives about 128 bits of security. Shanks's baby-step giant-step achieves the same time with \(\sqrt{N}\) memory and is therefore worse in practice. The Pohlig-Hellman algorithm reduces discrete log in a group of order \(\prod p_i^{e_i}\) to discrete logs in the prime-order subgroups, so the security is set by the largest prime factor of the group order, which is why curve standards specify prime order or a tiny cofactor.

Index calculus for discrete log in \(\Z_p^{*}\). The multiplicative group of a finite field has extra structure. Integers factor. Index calculus picks a factor base of small primes, collects relations \(g^{k} \equiv \prod p_i^{e_i}\) that factor completely over the base, solves the resulting linear system for the discrete logs of the base, and then computes any individual log by finding one more smooth relation. Its cost is subexponential, \(L_p[1/3, 1.923]\) for the number-field-sieve variant, in the standard notation \(L_n[\alpha, c] = \exp\big((c + o(1))(\ln n)^{\alpha}(\ln\ln n)^{1-\alpha}\big)\). This is why finite-field Diffie-Hellman needs a 2048- or 3072-bit modulus while an elliptic curve needs only 256 bits. Index calculus has no analogue on a general curve, so only the generic square-root attack applies. Logjam (2015) showed the practical consequence. The expensive precomputation in index calculus depends only on the modulus, so a handful of widely reused 512-bit and 1024-bit groups made individual connections breakable after a one-time cost.

Factoring and the general number field sieve. GNFS factors \(n\) in \(L_n[1/3, (64/9)^{1/3}] = L_n[1/3, 1.923]\). The arithmetic that follows sets RSA key sizes, and it is worth doing explicitly rather than quoting a table.

Public-key constructions

Diffie-Hellman, derived

Diffie and Hellman's 1976 paper posed and solved the problem of establishing a shared secret over a public channel. Fix a cyclic group \(G\) of prime order \(q\) with generator \(g\). Alice picks \(a\) uniformly in \(\Z_q\) and sends \(A = g^{a}\). Bob picks \(b\) and sends \(B = g^{b}\). Alice computes \(B^{a} = g^{ab}\), Bob computes \(A^{b} = g^{ab}\). The shared value is the same because exponentiation commutes, and an eavesdropper who sees \(g, g^{a}, g^{b}\) must compute \(g^{ab}\), which is the computational Diffie-Hellman problem.

Two assumptions, and the difference matters. CDH asks, given \((g, g^{a}, g^{b})\), to compute \(g^{ab}\). DDH asks, given \((g, g^{a}, g^{b}, Z)\), to decide whether \(Z = g^{ab}\) or a random group element. An algorithm that solves CDH immediately solves DDH, by computing \(g^{ab}\) and comparing, so DDH-hardness is the stronger assumption. The converse implication is not known. The distinction is not academic. In \(\Z_p^{*}\) with a generator of the full group, DDH is false, because the Legendre symbol of \(g^{ab}\) is computable from those of \(g^{a}\) and \(g^{b}\), leaking one bit and letting an adversary distinguish. That is exactly why protocols work in the prime-order subgroup of quadratic residues, where the leak disappears. Security proofs for ElGamal and for many key-exchange protocols need DDH, not merely CDH, so the group choice is part of the proof.

The raw protocol is completely broken by an active attacker. A man-in-the-middle runs two independent exchanges, one with each side, and relays. Alice shares \(g^{am}\) with the attacker, Bob shares \(g^{bm}\), and the attacker decrypts, reads, re-encrypts. Nothing in the mathematics prevents it, because nothing in the mathematics says who is at the other end. The fix is always authentication of the transcript, whether a signature over the exchanged values (TLS 1.3), a pre-shared key mixed into the derivation, or a password-authenticated variant. Anonymous Diffie-Hellman is secure against a passive adversary and worthless against an active one, and every real protocol therefore carries an authentication mechanism alongside it.

RSA, and why the textbook version is unusable

Rivest, Shamir, and Adleman published in 1978 the first practical public-key encryption and signature scheme. For key generation, pick distinct large primes \(p, q\), set \(n = pq\) and \(\varphi(n) = (p-1)(q-1)\), pick \(e\) coprime to \(\varphi(n)\) (65537 in practice, since its binary form \(10000000000000001\) makes exponentiation cheap), and compute \(d = e^{-1} \bmod \varphi(n)\) by the extended Euclidean algorithm. Encryption is \(c = m^{e} \bmod n\) and decryption is \(m = c^{d} \bmod n\).

For correctness, \(ed = 1 + k\varphi(n)\) for some integer \(k\), so \(c^{d} = m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^{k} \equiv m \pmod n\) by Euler's theorem when \(\gcd(m,n)=1\), and the CRT handles the measure-zero case where \(m\) shares a factor with \(n\). Security rests on the RSA assumption, that computing \(e\)-th roots mod \(n\) is hard without the factorization. That assumption is implied by hardness of factoring but not known to be equivalent to it.

Textbook RSA, meaning \(m^{e} \bmod n\) with no padding, fails in at least four independent ways, all demonstrated numerically below on the classic \(p = 61, q = 53\) key.

Determinism. It is deterministic, so by the earlier claim it is not IND-CPA, with advantage 1. When the message space is small (a vote, a bid, a credit-card number), an attacker simply encrypts every candidate and matches.

Malleability. \(\mathsf{Enc}(m_1)\cdot\mathsf{Enc}(m_2) = (m_1m_2)^{e} = \mathsf{Enc}(m_1m_2)\). An attacker who cannot read a ciphertext can still transform it into an encryption of a related message. The run below multiplies a ciphertext of 65 by an encryption of 2 and decrypts to 130. In the signature setting this is existential forgery, since from signatures on \(m_1\) and \(m_2\), the signature on \(m_1m_2\) is free.

Small exponent, no padding. With \(e = 3\) and \(m^{3} < n\), the modular reduction never happens, so the "ciphertext" is just \(m^{3}\) over the integers and an ordinary integer cube root recovers \(m\). Håstad's broadcast attack generalizes it. The same message sent to three recipients with \(e = 3\) is recoverable by CRT plus a cube root, and Coppersmith's lattice method extends the attack to partially known or slightly padded messages.

Chosen-ciphertext. Given a target \(c\), ask for the decryption of \(c' = c \cdot r^{e} \bmod n\) for random \(r\). The answer is \(mr\), and dividing by \(r\) gives \(m\). Even a decryption oracle that only reveals one bit suffices, by binary search.

OAEP (Bellare and Rogaway, 1994) is the fix for encryption. It is a two-round Feistel over the message using two hash functions modeled as random oracles. With random seed \(r\), compute \(X = (m \| 0^{k_1}) \oplus \mathcal{G}(r)\) and \(Y = r \oplus \mathcal{H}(X)\), and RSA-encrypt \(X \| Y\). Decryption inverts and checks the zero block, and a mismatch means reject. The construction makes the scheme randomized, makes any modification of the ciphertext produce garbage that fails the zero check, and admits a proof of IND-CCA2 security in the random oracle model under the RSA assumption. Shoup found in 2001 that the original proof was flawed for general trapdoor permutations, and Fujisaki, Okamoto, Pointcheval, and Stern repaired it specifically for RSA. The older PKCS#1 v1.5 padding has no such proof and is the target of Bleichenbacher's 1998 adaptive chosen-ciphertext attack, which recovers a session key from about a million oracle queries and keeps coming back (ROBOT, 2017) whenever an implementation leaks a distinguishable error.

ElGamal and the KEM/DEM paradigm

ElGamal (1985) turns Diffie-Hellman into encryption. The public key is \(h = g^{x}\). To encrypt \(m \in G\), pick \(y\) uniformly and send \((c_1, c_2) = (g^{y},\, m \cdot h^{y})\). To decrypt, compute \(c_2 \cdot c_1^{-x} = m h^{y} g^{-xy} = m g^{xy} g^{-xy} = m\). It is randomized (fresh \(y\) per message), it is IND-CPA under DDH, and it is multiplicatively homomorphic, since \((c_1c_1', c_2c_2')\) decrypts to \(mm'\). The homomorphism is a feature for voting protocols and a liability everywhere else, since it means the scheme is malleable and therefore not IND-CCA.

Public-key operations are expensive and constrained to a group, so nobody encrypts bulk data with them. The KEM/DEM paradigm, formalized by Cramer and Shoup, splits the job. A key encapsulation mechanism produces a random symmetric key together with an encapsulation of it under the recipient's public key, and a data encapsulation mechanism (an AEAD) encrypts the actual message under that key. For ElGamal the KEM picks \(y\), sends \(g^{y}\), and sets \(K = \mathsf{KDF}(h^{y})\). Note the KDF. The raw group element is not a key, since it lives in a structured set with recognizable encoding and non-uniform bits, and hashing it is what produces uniform key material. This is precisely the structure of TLS 1.3, of the ECIES/HPKE family, and of ML-KEM, and the composition theorem is clean. An IND-CCA KEM plus an IND-CCA (authenticated) DEM gives an IND-CCA hybrid scheme.

Signatures

A signature scheme is \((\mathsf{Gen}, \mathsf{Sign}, \mathsf{Vrfy})\) with EUF-CMA security defined exactly as for MACs, except verification uses a public key, so anyone can check and only the holder can produce. That asymmetry is what buys non-repudiation and what makes certificates possible.

RSA-PSS (Bellare and Rogaway, 1996) is the modern RSA signature. Hash the message with a random salt, encode with a mask generation function, and apply the RSA private exponent. The randomization gives a tight security reduction to the RSA problem in the random oracle model, unlike full-domain hash, and it avoids the structure that makes PKCS#1 v1.5 signatures vulnerable to Bleichenbacher's low-exponent forgery when verifiers parse the padding sloppily.

DSA and ECDSA sign with a per-signature random nonce \(k\). In ECDSA over a curve of prime order \(N\) with generator \(G\), private key \(d\), public key \(Q = dG\), and message hash \(z\), pick \(k\), compute \(R = kG\), set \(r = R_x \bmod N\), and

Verification computes \(u_1 = zs^{-1}\), \(u_2 = rs^{-1}\), and checks that \((u_1G + u_2Q)_x \bmod N = r\). The algebra works because \(u_1G + u_2Q = (zs^{-1} + rds^{-1})G = s^{-1}(z + rd)G = kG = R\).

If \(k\) repeats across two signatures under the same key, the private key falls out algebraically. Same \(k\) means same \(r\). Subtracting the two equations \(s_1 k = z_1 + rd\) and \(s_2 k = z_2 + rd\) eliminates \(rd\).

Two divisions and the key is gone. This is not hypothetical. It recovered the Sony PlayStation 3 code-signing key in 2010 (the nonce was a constant), and it has drained cryptocurrency wallets whose Android RNG returned repeated values in 2013. Worse, the attack degrades gracefully for the attacker. Even biased nonces leak, and lattice attacks recover the key from a few hundred signatures with a handful of known nonce bits.

EdDSA (Bernstein, Duif, Lange, Schwabe, and Yang, 2011) removes the failure mode by construction. It derives the nonce deterministically as \(k = H(\text{secret prefix} \,\|\, m)\), so two different messages give different nonces without any randomness at signing time, and the same message always gives the same signature. Ed25519 also fixes the curve (Curve25519 in Edwards form), the hash (SHA-512), and the encoding, which eliminates the parameter-choice errors that ECDSA implementations keep making. The measured run below confirms both properties. Deterministic nonces for two messages do not collide, and repeated signing of one message is stable.

Schnorr signatures (1991) are the cleanest of the family and are what EdDSA is. Commit \(R = kG\), challenge \(c = H(R \| P \| m)\), respond \(s = k + c\,d\), verify \(sG = R + cP\). The verification identity is one line of algebra, \(sG = (k + cd)G = kG + c(dG) = R + cP\). Schnorr signatures are linear in the secret, which makes them aggregate and threshold-sign naturally (MuSig, FROST), and they have a security proof from the discrete log assumption via the forking lemma of Pointcheval and Stern. Patent encumbrance until 2008 is the only reason DSA and ECDSA exist. Bitcoin's 2021 Taproot upgrade adopted Schnorr for exactly the aggregation properties.

Elliptic curves

An elliptic curve over a prime field \(\mathbb{F}_p\) (with \(p > 3\)) is the set of solutions to \(y^{2} = x^{3} + ax + b\) together with a point at infinity \(\mathcal{O}\), where the discriminant condition \(4a^{3} + 27b^{2} \neq 0\) rules out singular curves.

The group law, geometrically. Three points of the curve that lie on one line sum to \(\mathcal{O}\). To add \(P\) and \(Q\), draw the line through them, find the third intersection with the curve, and reflect it across the \(x\)-axis. To double \(P\), use the tangent at \(P\) instead of a chord. The point at infinity is the identity, and the inverse of \((x,y)\) is \((x,-y)\). Associativity is the non-obvious part, provable by a Bezout-style argument or by noting the group is isomorphic to the divisor class group of degree zero.

Algebraically. For \(P = (x_1,y_1)\), \(Q = (x_2,y_2)\) with \(P \neq \pm Q\), the chord slope is \(\lambda = (y_2-y_1)/(x_2-x_1)\). For \(P = Q\) the tangent slope comes from implicit differentiation of the curve equation, \(2y\,dy = (3x^{2}+a)\,dx\), giving \(\lambda = (3x_1^{2}+a)/(2y_1)\). In both cases

with all arithmetic in \(\mathbb{F}_p\), so the divisions are modular inverses. The \(x_3\) formula follows from Vieta. The cubic \((\lambda x + \nu)^{2} = x^{3} + ax + b\) has roots \(x_1, x_2, x_3\) and the coefficient of \(x^{2}\) is \(-\lambda^{2}\), so \(x_1 + x_2 + x_3 = \lambda^{2}\).

Why curves give smaller keys

The security of a discrete-log system is set by the best available algorithm. In \(\mathbb{F}_p^{*}\), index calculus exploits the fact that field elements are integers that factor into small primes, and its subexponential cost forces 3072-bit moduli for 128-bit security. On a general elliptic curve there is no factorization to exploit. The group elements are points, there is no notion of a "small" point, and no subexponential algorithm is known. Only the generic square-root attacks apply, so \(2n\) bits of group order gives \(n\) bits of security. That is the whole argument, and it is why 256-bit curves replaced 3072-bit finite fields, a factor of 12 in key size and far more in operation cost.

The exceptions matter and are the reason curve choice is not free. Anomalous curves with \(\#E(\mathbb{F}_p) = p\) admit a polynomial-time attack via the \(p\)-adic logarithm (Smart, Satoh-Araki, Semaev). Supersingular curves and other small-embedding-degree curves fall to the MOV and Frey-Rück reductions, which map the curve discrete log into a finite field where index calculus applies. Curves with small subgroups permit invalid-curve and small-subgroup confinement attacks when implementations skip point validation. Standard curves are chosen to avoid all of these, and the rigidity debate, whether a curve's parameters were generated by a transparent procedure or by unexplained constants, exists because those choices are where a backdoor would hide.

Curve25519 (Bernstein, 2006) is the design that took over. It is the Montgomery curve \(y^{2} = x^{3} + 486662x^{2} + x\) over \(\mathbb{F}_{2^{255}-19}\), with order \(8\ell\) for a 252-bit prime \(\ell\). Its properties are engineering choices as much as mathematical ones. The Montgomery ladder computes scalar multiplication using only \(x\)-coordinates with the same sequence of operations regardless of the scalar bits, so constant-time implementation is the natural one rather than a careful one. Every 32-byte string is a valid public key, so there is no invalid-curve attack surface and no validation to forget. The prime \(2^{255}-19\) admits fast reduction. And the parameters were chosen by a stated deterministic rule, addressing the rigidity concern. Its Edwards-form twin, Ed25519, provides signatures using the same field. The pair is now the default in SSH, Signal, WireGuard, TLS, and most new protocol designs.

Pairing-friendly curves support a bilinear map \(e: G_1 \times G_2 \to G_T\) with \(e(aP, bQ) = e(P,Q)^{ab}\). That single identity enables identity-based encryption (Boneh and Franklin, 2001), short BLS signatures that aggregate an arbitrary number of signers into one group element, and most efficient zk-SNARK verifiers. Pairings require a small embedding degree, which is exactly the property normal curves avoid, so pairing-friendly families (BN, BLS12) are constructed deliberately. The cost is a delicate security level. Kim and Barbulescu's 2016 improvement to the number field sieve in extension fields cut the security of BN254 from a claimed 128 bits to roughly 100, which is why BLS12-381 (from the Zcash team) replaced it as the default in proving systems.

Commitments and secret sharing

A commitment scheme is a digital envelope. The sender commits to a value now and opens it later, and neither party can cheat. Two properties stand in tension.

Hiding means the commitment reveals nothing about the committed value. Binding means the committer cannot open the same commitment to two different values. Each comes in a computational and a perfect (information-theoretic) flavor, and a scheme cannot be perfectly hiding and perfectly binding at once, because perfect hiding means the commitment's distribution is identical for all values, so for every commitment there exist openings to every value, and an unbounded committer can find them. The design choice is therefore which party gets the unconditional guarantee.

The hash commitment \(c = H(m \| r)\) with random \(r\) is computationally hiding (given a random oracle) and computationally binding (a double opening is a collision). Pedersen's 1991 scheme is the algebraic one. In a prime-order group with generators \(g, h\) whose relative discrete log \(\log_g h\) is unknown to anyone,

It is perfectly hiding. For any \(m\), as \(r\) ranges uniformly, \(g^{m}h^{r}\) is uniform over the group, so the commitment's distribution does not depend on \(m\) at all. It is computationally binding under discrete log. Opening one commitment as \((m, r)\) and \((m', r')\) gives \(g^{m}h^{r} = g^{m'}h^{r'}\), hence \(g^{m - m'} = h^{r' - r}\), hence \(\log_g h = (m - m')/(r' - r)\), so a double opening solves the discrete log the setup assumed hard. Pedersen commitments are also additively homomorphic, \(\mathsf{Com}(m_1;r_1)\cdot\mathsf{Com}(m_2;r_2) = \mathsf{Com}(m_1+m_2; r_1+r_2)\), which is what makes them the workhorse of confidential transactions, range proofs, and verifiable secret sharing.

Shamir secret sharing, derived

Shamir's 1979 scheme splits a secret \(s\) into \(n\) shares so that any \(t\) reconstruct it and any \(t-1\) learn nothing. The construction is polynomial interpolation over a finite field \(\mathbb{F}_p\). Choose a random polynomial of degree \(t-1\) with the secret as its constant term,

and hand participant \(i\) the share \((i, f(i))\) for \(i = 1, \ldots, n\), with \(x = 0\) reserved for the secret.

Reconstruction. A degree-\((t-1)\) polynomial is determined by \(t\) points, and Lagrange gives the formula explicitly. With points \((x_1,y_1),\ldots,(x_t,y_t)\),

The products are field elements, and the divisions are modular inverses, which exist because the \(x_i\) are distinct and \(p\) is prime.

Perfect privacy. Given any \(t-1\) shares and any candidate secret \(s'\), there is exactly one degree-\((t-1)\) polynomial passing through those \(t-1\) points with \(f(0) = s'\), because \(t\) points determine the polynomial uniquely. So every candidate secret is consistent with exactly one choice of the remaining randomness, and since the coefficients were uniform, every candidate is equally likely. The shares carry zero information, in the Shannon sense, not merely computationally. The run below verifies this by enumeration on a small field. Given two shares of a 3-of-6 sharing over \(\mathbb{F}_{1613}\), all 1613 candidate secrets remain consistent.

Shamir sharing underlies threshold signing (each party holds a share of the key and they sign without ever assembling it), key escrow with \(m\)-of-\(n\) recovery, DNSSEC root key ceremonies, and the secret-sharing branch of secure multi-party computation. Its homomorphism is the reason. Shares of \(s\) plus shares of \(s'\) are shares of \(s + s'\), so linear functions can be computed on shares directly, and multiplication needs one round of interaction to reduce the degree back down.

Zero-knowledge proofs

Goldwasser, Micali, and Rackoff asked in 1985 what it means to prove a statement while revealing nothing except that it is true. Their answer defines an interactive proof system for a language \(L\) between a prover \(P\) and a verifier \(V\) with three properties.

Completeness says that if \(x \in L\) and both parties follow the protocol, \(V\) accepts with probability 1 (or overwhelming probability). Soundness says that if \(x \notin L\), then no cheating prover, however powerful, makes \(V\) accept with more than negligible probability. Zero knowledge says there exists an efficient simulator \(S\) that, given only \(x\) and no witness, produces transcripts whose distribution is indistinguishable from real interactions. The simulator is the definition's whole content. If a transcript can be manufactured without the secret, then the transcript cannot contain the secret.

A proof of knowledge strengthens soundness. There must exist an efficient extractor that, given rewinding access to any prover that convinces the verifier, outputs the witness. Convincing the verifier therefore requires actually knowing the secret, not merely the truth of the statement.

The Schnorr identification protocol, worked

The statement is "I know \(x\) such that \(h = g^{x}\)" in a group of prime order \(q\). The protocol has three moves.

  Prover (knows x)                        Verifier (knows g, h)
  -----------------------------------------------------------------
  r <- random in Z_q
  t = g^r            --------- t ------->
                     <-------- c --------  c <- random in Z_q
  s = r + c*x mod q  --------- s ------->
                                           accept iff  g^s == t * h^c

Completeness. \(g^{s} = g^{r + cx} = g^{r}(g^{x})^{c} = t\,h^{c}\), so an honest prover always convinces the verifier.

Special soundness, giving knowledge extraction. Suppose a prover produces two accepting transcripts with the same commitment \(t\) and different challenges, \((t, c_1, s_1)\) and \((t, c_2, s_2)\) with \(c_1 \neq c_2\). Then \(g^{s_1} = t h^{c_1}\) and \(g^{s_2} = t h^{c_2}\). Dividing, \(g^{s_1 - s_2} = h^{c_1 - c_2}\), and since \(h = g^{x}\) and the group has prime order (so \(c_1 - c_2\) is invertible mod \(q\)),

The extractor rewinds the prover to just after it sent \(t\), feeds a fresh challenge, and computes \(x\) from the two responses. A prover that succeeds on two different challenges for one commitment therefore knows \(x\). A prover that does not know \(x\) can answer at most one challenge per commitment, so it succeeds with probability at most \(1/q\). The run below performs exactly this extraction and confirms the recovered witness equals the real one.

Honest-verifier zero knowledge, by explicit simulation. The simulator does not know \(x\). It picks the challenge \(c\) and the response \(s\) first, both uniform in \(\Z_q\), and then solves for the commitment that makes the check pass.

By construction \(g^{s} = t h^{c}\), so the transcript accepts. And its distribution is identical to a real one. In a real run, \(r\) is uniform so \(t\) is uniform, \(c\) is uniform and independent, and \(s\) is then determined. In the simulation, \(s\) and \(c\) are uniform and independent and \(t\) is determined, and the map between the two parameterizations is a bijection. The distributions are equal, not merely close, so the protocol is perfectly honest-verifier zero knowledge. The measured run below generates 200 simulated transcripts with no witness at all and all 200 pass verification. That is the point made concrete. A transcript proves nothing to a third party, because anyone can fabricate one.

The ordering is what makes simulation possible. The simulator gets to choose the challenge, which a real prover does not. Against a malicious verifier who chooses \(c\) as a function of \(t\), this simulator fails, and full zero knowledge needs either a trusted common reference string, a commitment to the challenge first, or sequential repetition with single-bit challenges.

Fiat-Shamir, with interaction removed

Fiat and Shamir observed in 1986 that the verifier's only job is to produce an unpredictable challenge, and a hash function can do that. Replace \(c\) with \(c = H(\text{public parameters} \| h \| t \| m)\). The protocol becomes a single message \((t, s)\) that anyone can check, which is to say a signature on \(m\). Schnorr signatures, EdDSA, and essentially every non-interactive proof system in deployment are Fiat-Shamir applied to some identification protocol. Security holds in the random oracle model, by the forking lemma. Rewind the adversary to the point of the hash query and answer differently, obtaining the two transcripts that special soundness needs.

The hash input must include everything. Omitting the public key \(h\) from the hash enables key-substitution attacks. Omitting the commitment \(t\) breaks soundness outright. Omitting domain separation lets a proof for one statement be replayed as a proof for another. This is not a theoretical concern. The "weak Fiat-Shamir" transform, which hashes only the commitment and not the statement, was found in multiple deployed proof libraries and documented by Dao, Miller, Wright, and Grubbs in 2023 as a live vulnerability class. The implementation below hashes the group parameters, the public key, the commitment, and the message, and the run confirms that a signature verifies only under the exact message and the exact public key it was made for.

SNARKs and STARKs, conceptually

A SNARK is a succinct non-interactive argument of knowledge, a proof that a computation was performed correctly, whose size and verification time are much smaller than the computation itself, often constant. "Argument" rather than "proof" because soundness holds only against computationally bounded provers, which is unavoidable for succinctness.

The pipeline is the same in every system. Express the computation as an arithmetic circuit over a finite field, convert it to a constraint system (R1CS, or a PLONK-style gate layout, or an AIR for STARKs), encode the constraint satisfaction as a polynomial identity that holds everywhere if and only if the computation was correct, commit to the polynomials, and have the verifier check the identity at a random point using the commitment's opening proofs. Correctness rests on the Schwartz-Zippel lemma. Two distinct polynomials of degree \(d\) over a field of size \(|\mathbb{F}|\) agree at a uniformly random point with probability at most \(d/|\mathbb{F}|\), so one random check catches a cheating prover with overwhelming probability.

The families differ in the commitment scheme, and that choice determines every practical property. Groth16 uses a pairing-based polynomial commitment (KZG) and produces the shortest proofs in practice, three group elements, verified in a few milliseconds, at the cost of a circuit-specific trusted setup whose toxic waste breaks soundness if retained. PLONK and its descendants keep pairings but make the setup universal and updatable. STARKs, from Ben-Sasson and collaborators at the Technion and StarkWare, replace the pairing commitment with a Merkle-tree-plus-FRI construction over a hash function, giving no trusted setup, plausible post-quantum security since only hash security is assumed, and proofs measured in tens to hundreds of kilobytes rather than hundreds of bytes. Bulletproofs (Bünz, Bootle, Boneh, Poelstra, Wuille, and Maxwell) sit in between, with no trusted setup, logarithmic proof size, and linear verification.

What they promise and what they do not is worth stating. They promise that a verifier with a small budget can be convinced of a large computation, which is genuinely new and is what rollups and verifiable-compute services sell. They do not promise privacy unless the circuit is designed for it. "Zero-knowledge" is an option in most of these systems, not an automatic property. And proving remains expensive, typically several orders of magnitude more work than running the computation directly, which is the real constraint on where they can be deployed.

Multi-party computation, homomorphic encryption, and private retrieval

Secure multi-party computation lets \(n\) parties compute \(f(x_1, \ldots, x_n)\) with each \(x_i\) private, learning the output and nothing else. Yao's 1986 garbled-circuit construction handles two parties. The garbler encrypts a Boolean circuit gate by gate, where each wire carries two random labels standing for 0 and 1 and each gate is a table of four ciphertexts, each decryptable only with the right pair of input labels. The evaluator obtains labels for its own inputs through oblivious transfer, which lets it choose one of two values without the sender learning which, and then evaluates the circuit knowing only meaningless labels until the final output mapping is revealed. Modern optimizations, free-XOR, half-gates, garbled row reduction, cut the communication per gate to roughly two ciphertexts.

The secret-sharing branch (BGW, GMW, SPDZ) scales to many parties. Inputs are Shamir-shared, addition is local because shares add, multiplication needs one interaction round using precomputed Beaver triples, and the whole computation runs in a number of rounds proportional to the circuit depth. The trade is the classic one. Garbled circuits are constant-round with high bandwidth, secret sharing is low-bandwidth with rounds proportional to depth, so wide shallow circuits favor one and deep narrow ones favor the other. Deployed uses are narrower than the theory, private set intersection for advertising conversion measurement, distributed key generation and threshold signing for custody systems, and privacy-preserving aggregate statistics such as the Prio system used for browser telemetry.

Homomorphic encryption computes on ciphertexts directly. Partially homomorphic schemes have been known since the beginning. Textbook RSA and ElGamal are multiplicative, Paillier (1999) is additive. Each supports one operation without limit. Fully homomorphic encryption supports both, hence arbitrary circuits, and was open for thirty years until Gentry's 2009 construction at IBM Research. Its structure is still the template. Ciphertexts carry noise. Each operation grows the noise, addition mildly and multiplication severely. Once noise exceeds a threshold, decryption fails. A scheme that tolerates a bounded number of multiplications is somewhat homomorphic. Bootstrapping makes it fully homomorphic. Run the decryption circuit itself homomorphically, using an encryption of the secret key, producing a fresh ciphertext of the same plaintext with reset noise. It is a fixed point argument, and it requires the scheme to be able to evaluate its own decryption, which is what "bootstrappable" means.

Practical status, with real numbers as reported by the implementers. Gentry's original bootstrapping took on the order of thirty minutes per operation. The TFHE line (Chillotti, Gama, Georgieva, Izabachène) brought programmable bootstrapping of a single binary gate to roughly ten milliseconds on a CPU core, and the Zama TFHE-rs implementation reports figures in that range today, with GPU and FPGA backends improving throughput further. The BGV and CKKS families, implemented in Microsoft Research's SEAL and in OpenFHE, take the opposite approach. Pack thousands of plaintext slots into one ciphertext and operate on all of them simultaneously, giving good amortized cost for SIMD-shaped workloads such as encrypted inference over a batch, with bootstrapping measured in seconds rather than milliseconds. The honest summary is that FHE is real, is deployed in narrow places (private set intersection, encrypted database lookups, some regulated-data analytics), and remains three to five orders of magnitude slower than plaintext computation, so the question for any application is whether the data is valuable enough to pay that.

Private information retrieval asks something narrower, to fetch record \(i\) from a public database without the server learning \(i\). The trivial solution, download everything, is perfectly private and usually unaffordable, so the goal is sublinear communication. Chor, Goldreich, Kushilevitz, and Sudan introduced the problem in 1995 with an information-theoretic solution requiring multiple non-colluding servers. Single-server computational PIR came later and rests on homomorphic encryption, the client sending an encrypted selection vector that the server folds over the database. The server must still touch every record, since skipping one would leak that it was not requested, so PIR's cost is inherently linear in database size per query. Recent systems (SimplePIR and DoublePIR from MIT, FrodoPIR, Spiral) push the online cost down by preprocessing a large client-side hint, reaching throughputs of hundreds of megabytes per second of database scanned per query, which is finally in the range where certificate-revocation checks and private DNS lookups are plausible.

Post-quantum cryptography

Two quantum algorithms matter, and conflating them is the most common error in this area.

Shor (1994) factors integers and computes discrete logarithms in polynomial time on a quantum computer, roughly \(O((\log n)^{2}(\log\log n))\) quantum gates plus classical post-processing. Its engine is quantum period-finding. Factoring reduces to finding the period \(r\) of \(a^{x} \bmod n\), and the quantum Fourier transform extracts that period from a superposition in one shot where classical methods need exponentially many evaluations. This breaks RSA, finite-field Diffie-Hellman, DSA, ECDH, and ECDSA completely, not partially. Doubling the key size does not help, because the algorithm is polynomial in the key size.

Grover (1996) searches an unstructured space of \(N\) items in \(O(\sqrt{N})\) queries. Against a symmetric cipher with a \(k\)-bit key that is a square root, \(2^{k/2}\) instead of \(2^{k}\). AES-128 drops to \(2^{64}\) quantum iterations and AES-256 to \(2^{128}\). Two things temper even that. Grover's iterations are inherently sequential, so unlike classical brute force it parallelizes poorly. Running \(p\) machines gives only a \(\sqrt{p}\) speedup, and \(2^{64}\) sequential quantum operations at a billion per second is about 585 years. And each iteration requires a coherent evaluation of AES inside the quantum computer, which is enormously more expensive than a classical AES evaluation. From this follows the practical guidance to double symmetric key sizes if you are worried (AES-256, SHA-512, 256-bit MACs), and replace public-key algorithms entirely. For hash functions, the Brassard-Høyer-Tapp collision algorithm gives \(2^{n/3}\) with large memory, which is why SHA-256's collision resistance is still considered adequate.

Lattices, LWE, and the NIST standards

The learning-with-errors problem, introduced by Regev in 2005, is the foundation of the standardized replacements. Fix a modulus \(q\) and a dimension \(n\). Sample a secret \(s \in \Z_q^{n}\), and produce samples \((a_i, b_i)\) with \(a_i\) uniform in \(\Z_q^{n}\) and

where \(\chi\) is a narrow error distribution (discrete Gaussian or a centered binomial). The search problem is to recover \(s\). The decision problem is to distinguish these samples from uniform. Without the errors this is Gaussian elimination and takes polynomial time. With them, elimination amplifies the noise catastrophically. Each row operation adds errors, and after \(n\) steps the accumulated error swamps the signal. That is the whole intuition for hardness, and Regev backed it with a quantum reduction from worst-case lattice problems (GapSVP, SIVP) to average-case LWE, which is a stronger foundation than most assumptions have, since breaking random instances implies solving the hardest instances of a well-studied geometric problem.

Plain LWE needs an \(n \times n\) public matrix, which is megabytes. Ring-LWE (Lyubashevsky, Peikert, Regev) and Module-LWE replace the matrix with structured elements of a polynomial ring \(\Z_q[x]/(x^{n}+1)\), so a whole row is described by \(n\) coefficients and multiplication runs in \(O(n \log n)\) by the number-theoretic transform. Module-LWE, which Kyber uses, sits between the two, using a small \(k \times k\) matrix of ring elements, so the security level is tuned by changing \(k\) rather than by changing the ring, which is why ML-KEM-512, 768, and 1024 share all their arithmetic.

The toy Regev encryption in the implementation section shows the mechanism concretely. Encrypt a bit by summing a random subset of the public samples and adding \(b \cdot \lfloor q/2 \rfloor\), decrypt by subtracting \(\langle u, s\rangle\) and testing which half of the modulus the result lands in. The measured run at \(n = 64\), \(q = 8192\), \(m = 256\), \(\sigma = 8\) records zero decryption failures in 2,000 trials, with accumulated noise of standard deviation 63.7 against a decryption margin of \(q/4 = 2048\), and failures appear (21 in 500) once \(\sigma\) is raised to 128. That is the parameter-selection problem in miniature. The modulus must be large enough that noise never crosses the boundary, and small enough that keys stay small and the problem stays hard.

NIST standardized three algorithms in August 2024, and their tradeoffs are best seen as numbers.

Reading the table is the point. ML-KEM's ciphertext is 34 times larger than X25519's public value, which costs a kilobyte in every handshake and is affordable. ML-DSA signatures are 38 times larger than Ed25519's, which is painful in a certificate chain where several signatures and several public keys appear, and is the reason signature migration is harder than key-exchange migration. SLH-DSA assumes nothing but hash-function security, making it the fallback if lattice cryptanalysis advances, and its signature sizes are the price of that conservatism. Falcon has the smallest signatures and the most treacherous implementation, since its Gaussian sampler needs floating-point arithmetic that must be constant-time.

Hybrid deployment is the current answer for key exchange. Derive the session key from both an X25519 shared secret and an ML-KEM shared secret, concatenated into the KDF, so the connection is secure if either primitive holds. That protects against both a quantum computer and a break of the newer, less-studied lattice scheme. The X25519MLKEM768 group is what browsers and major CDNs now negotiate by default. Signatures are not being hybridized as aggressively, for a defensible reason. A signature only needs to be unforgeable at the moment of verification, so a break years from now does not retroactively forge today's signatures, whereas an encrypted session recorded today can be decrypted whenever the attacker acquires the capability.

That asymmetry is the harvest-now-decrypt-later argument, and it is the reason migration cannot wait for quantum computers to exist. An adversary recording traffic today needs only patience. If data must stay confidential for \(y\) years, and migration takes \(m\) years, and a capable quantum computer arrives in \(z\) years, then data is exposed whenever \(y + m > z\). With medical or intelligence data where \(y\) is measured in decades, the inequality is satisfied for almost any plausible \(z\), which is Mosca's formulation of the deadline.

Worked problems

Problems 1 through 9 are distributed through the theory above, next to the material each one tests. Two more here, both of the kind that separates people who have used a library from people who understand what the library promises.

Implementation

Every block below was executed on the machine this repository is built on, and the output shown under each one is that program's real output. The Python is pedagogical throughout, with small parameters, Python bignums, no constant-time discipline, and no side-channel hardening. It is written to be read, which is exactly what makes it unsafe to ship. The Rust and TypeScript blocks at the end are the opposite. They implement nothing and only call vetted libraries, which is what production code should look like.

The birthday bound, measured against its prediction

This checks the two predictions derived earlier, that the expected number of draws before the first collision is \(\sqrt{\pi N/2}\), and that the expected number of colliding pairs among \(q\) draws is exactly \(q(q-1)/2N\). The values are SHA-256 digests truncated to 16, 20, 24, and 28 bits, so they come from a real hash rather than a PRNG.

"""Birthday bound: measured collisions against the predicted value."""
import hashlib
import math
import random

random.seed(20260724)


def truncated_hash(i, bits):
    """A real hash, truncated, so the inputs are not just a PRNG stream."""
    return int.from_bytes(hashlib.sha256(i.to_bytes(8, "big")).digest()[:8],
                          "big") >> (64 - bits)


def first_collision(bits, start):
    """Draw truncated hashes until one repeats; return the number of draws."""
    seen, i = set(), start
    while True:
        v = truncated_hash(i, bits)
        if v in seen:
            return len(seen) + 1
        seen.add(v)
        i += 1


print("first-collision search: mean draws vs sqrt(pi N / 2)")
print("%5s %14s %14s %14s" % ("bits", "N", "measured", "predicted"))
for bits in (16, 20, 24, 28):
    N, trials, start, tot = 1 << bits, 400, 0, 0
    for _ in range(trials):
        tot += first_collision(bits, start)
        start += 1 << 30                      # disjoint input range per trial
    mean, pred = tot / trials, math.sqrt(math.pi * N / 2)
    print("%5d %14d %14.1f %14.1f   ratio %.3f" % (bits, N, mean, pred, mean / pred))

print("\ncollision counts for q draws into N = 2^32 slots: measured vs q(q-1)/2N")
print("%10s %14s %14s" % ("q", "measured", "predicted"))
N = 1 << 32
for q in (10_000, 50_000, 100_000, 200_000):
    tot, base = 0, 1 << 40
    for _ in range(20):
        seen, c = {}, 0
        for i in range(q):
            v = truncated_hash(base + i, 32)
            c += seen.get(v, 0)               # each repeat is one colliding pair
            seen[v] = seen.get(v, 0) + 1
        tot += c
        base += 1 << 30
    print("%10d %14.2f %14.2f" % (q, tot / 20, q * (q - 1) / (2 * N)))

print("\nPRP/PRF switching: collisions in q random-function outputs"
      " (a permutation has none)")
N = 1 << 24
for q in (1000, 4000, 16000):
    tot = 0
    for _ in range(50):
        seen = set()
        for _ in range(q):
            v = random.randrange(N)
            tot += v in seen
            seen.add(v)
    print("q=%6d  mean distinguishing events %.3f   bound q^2/2N = %.3f"
          % (q, tot / 50, q * q / (2 * N)))

first-collision search: mean draws vs sqrt(pi N / 2)
 bits              N       measured      predicted
   16          65536          328.3          320.8   ratio 1.023
   20        1048576         1270.9         1283.4   ratio 0.990
   24       16777216         4902.9         5133.6   ratio 0.955
   28      268435456        20179.4        20534.3   ratio 0.983

collision counts for q draws into N = 2^32 slots: measured vs q(q-1)/2N
         q       measured      predicted
     10000           0.00           0.01
     50000           0.20           0.29
    100000           1.25           1.16
    200000           4.90           4.66

PRP/PRF switching: collisions in q random-function outputs (a permutation has none)
q=  1000  mean distinguishing events 0.080   bound q^2/2N = 0.030
q=  4000  mean distinguishing events 0.500   bound q^2/2N = 0.477
q= 16000  mean distinguishing events 7.520   bound q^2/2N = 7.629

The first-collision means land within 5 percent of \(\sqrt{\pi N/2}\) at every width, and the residual spread is explained by the statistic's own variance. Its standard deviation is about \(0.52\sqrt{N}\), so 400 trials leave roughly a 2.6 percent standard error, which brackets the observed ratios. The collision counts at \(N = 2^{32}\) track \(q(q-1)/2N\) closely, 4.90 measured against 4.66 predicted at \(q = 200{,}000\). The last group is the switching lemma made concrete. Repeated outputs from a random function, which is exactly the event a PRP/PRF distinguisher exploits, occur at close to the \(q^{2}/2N\) bound.

How modes fail, from ECB structure to keystream reuse to malleability

Real AES from a vetted library, deliberately misused, which is the only way to see that these failures are properties of the mode rather than of the cipher.

"""Why ECB fails and why a stream-cipher keystream must never repeat.
Pedagogical: a real AES from a vetted library, deliberately misused."""
import os
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

key, BS = os.urandom(16), 16
pt = (b"SAME BLOCK 16BY!" * 4) + b"different  block"


def run(mode, data):
    enc = Cipher(algorithms.AES(key), mode).encryptor()
    return enc.update(data) + enc.finalize()


def blocks(ct):
    return [ct[i:i + BS] for i in range(0, len(ct), BS)]


# ---- ECB leaks equality of plaintext blocks ----
ecb = blocks(run(modes.ECB(), pt))
print("plaintext blocks: %d, distinct: %d" % (len(pt) // BS, len(set(blocks(pt)))))
print("ECB ciphertext blocks: %d, distinct: %d  <- the structure survives"
      % (len(ecb), len(set(ecb))))

# ---- CBC hides it, as long as the IV is fresh and unpredictable ----
iv = os.urandom(BS)
cbc = blocks(run(modes.CBC(iv), pt))
print("CBC ciphertext blocks: %d, distinct: %d" % (len(cbc), len(set(cbc))))
print("CBC with a repeated IV on the same plaintext is identical:",
      run(modes.CBC(iv), pt) == run(modes.CBC(iv), pt))

# ---- CTR is a stream cipher: reuse the counter and the pad cancels ----
nonce = os.urandom(16)
p1, p2 = b"attack at dawn, bring the ladders", b"retreat at dusk, burn the letters"
c1, c2 = run(modes.CTR(nonce), p1), run(modes.CTR(nonce), p2)
xor = lambda a, b: bytes(u ^ v for u, v in zip(a, b))
print("CTR nonce reuse: C1 xor C2 == P1 xor P2 ->", xor(c1, c2) == xor(p1, p2))
print("  recovering P2 from P1 and the two ciphertexts:", xor(xor(c1, c2), p1) == p2)

# ---- CTR is malleable: a flipped ciphertext bit is a flipped plaintext bit ----
tamper = bytearray(c1)
tamper[0] ^= ord("a") ^ ord("A")
print("  bit-flipping attack turns 'attack' into:",
      run(modes.CTR(nonce), bytes(tamper))[:6])

plaintext blocks: 5, distinct: 2
ECB ciphertext blocks: 5, distinct: 2  <- the structure survives
CBC ciphertext blocks: 5, distinct: 5
CBC with a repeated IV on the same plaintext is identical: True
CTR nonce reuse: C1 xor C2 == P1 xor P2 -> True
  recovering P2 from P1 and the two ciphertexts: True
  bit-flipping attack turns 'attack' into: b'Attack'

Five plaintext blocks with two distinct values encrypt under ECB to five ciphertext blocks with two distinct values. The equality pattern survives intact. CBC with a fresh IV destroys it, but CBC with a repeated IV on the same plaintext produces byte-identical output, which is the determinism failure again. The CTR section recovers a complete second plaintext from a known first one under a repeated nonce, and the final line flips one ciphertext bit to turn "attack" into "Attack" with no key at all, which is what malleability means in practice.

A padding oracle decrypting CBC one byte at a time

The attacker in this program has no key and no plaintext. It has a function returning one bit, whether a submitted ciphertext had well-formed PKCS#7 padding. That is enough.

"""A CBC padding oracle recovering plaintext one byte at a time.
Pedagogical: this is why unauthenticated CBC must not be deployed."""
import hashlib
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

# The key is derived from a fixed string only so this run reproduces
# exactly; the attack below never uses it.
KEY = hashlib.sha256(b"padding oracle demo").digest()[:16]
BS, queries = 16, 0


def unpad(data):
    n = data[-1]
    if n == 0 or n > BS or data[-n:] != bytes([n]) * n:
        raise ValueError("bad padding")
    return data[:-n]


def encrypt(pt):
    n = BS - len(pt) % BS
    iv = hashlib.sha256(b"fixed IV, reproducibility only").digest()[:BS]
    enc = Cipher(algorithms.AES(KEY), modes.CBC(iv)).encryptor()
    return iv + enc.update(pt + bytes([n]) * n) + enc.finalize()


def oracle(ct):
    """The only thing the attacker can do: submit a ciphertext and learn whether
    the padding was well formed. One bit per query."""
    global queries
    queries += 1
    dec = Cipher(algorithms.AES(KEY), modes.CBC(ct[:BS])).decryptor()
    try:
        unpad(dec.update(ct[BS:]) + dec.finalize())
        return True
    except ValueError:
        return False


def crack_block(prev, block):
    """Recover D_k(block) byte by byte, then XOR with prev to get plaintext."""
    inter = bytearray(BS)
    for pos in range(BS - 1, -1, -1):
        pad = BS - pos
        for guess in range(256):
            forged = bytearray(BS)
            forged[pos] = guess
            for j in range(pos + 1, BS):
                forged[j] = inter[j] ^ pad            # force the tail to be valid
            if oracle(bytes(forged) + block):
                if pos == BS - 1:                     # rule out an accidental 0x02 0x02
                    probe = bytearray(forged)
                    probe[pos - 1] ^= 0xFF
                    if not oracle(bytes(probe) + block):
                        continue
                inter[pos] = guess ^ pad
                break
    return bytes(a ^ b for a, b in zip(inter, prev))


secret = b"the launch code is 0451, tell no one"
ct = encrypt(secret)
blocks = [ct[i:i + BS] for i in range(0, len(ct), BS)]
print("ciphertext is %d blocks (IV + %d data)" % (len(blocks), len(blocks) - 1))
recovered = b"".join(crack_block(blocks[i - 1], blocks[i])
                     for i in range(1, len(blocks)))
print("queries to the oracle:", queries)
print("recovered:", unpad(recovered))
print("matches the original:", unpad(recovered) == secret)
print("cost per byte: %.1f oracle queries" % (queries / len(recovered)))

ciphertext is 4 blocks (IV + 3 data)
queries to the oracle: 6816
recovered: b'the launch code is 0451, tell no one'
matches the original: True
cost per byte: 142.0 oracle queries

Full recovery of the 35-byte secret in 6,816 queries, 142 per byte, in a fraction of a second. The theoretical average for a linear sweep is 128 per byte. The surplus is the disambiguation probe that separates a genuine \(\texttt{0x01}\) from an accidental \(\texttt{0x02 0x02}\). Note what the attacker never needed, the key, any plaintext, any timing precision, or more than one bit per query. Rate limiting and other systems-level defenses slow this down. They do not fix it. Encrypt-then-MAC does, by rejecting a forged ciphertext before the decryption path ever runs.

Polynomial MAC key recovery from one repeated nonce

GMAC and Poly1305 both evaluate a polynomial in a secret key and mask the result with a per-nonce pad. This does the same arithmetic in a 61-bit prime field so the algebra is visible, recovers the hash key from two tags that shared a pad, and then shows the confidentiality half of the same failure against real AES-GCM.

"""Why a Carter-Wegman polynomial MAC dies on nonce reuse, and what AES-GCM
nonce reuse costs in practice. Pedagogical: small prime field, no constant time."""
import os
import random

from cryptography.hazmat.primitives.ciphers.aead import AESGCM

random.seed(5)
p = (1 << 61) - 1          # a Mersenne prime, small enough to root-find by hand


def poly_mac(blocks, r, s):
    """tag = (sum_i m_i r^(L-i+1)) + s mod p, the shape of GMAC and Poly1305."""
    acc = 0
    for m in blocks:
        acc = (acc + m) * r % p
    return (acc + s) % p


r_key = random.randrange(1, p)          # hash key, reused across messages
s1 = random.randrange(p)                # per-nonce pad, must never repeat
m_a, m_b = [123456789, 987654321], [111111111, 222222222]
t_a, t_b = poly_mac(m_a, r_key, s1), poly_mac(m_b, r_key, s1)   # SAME pad: the bug
print("tag(A) = %d\ntag(B) = %d (same nonce, so the same pad s)" % (t_a, t_b))

# Subtracting cancels s: (a1-b1) r^2 + (a2-b2) r - (t_a - t_b) = 0 mod p.
c2, c1, c0 = (m_a[0] - m_b[0]) % p, (m_a[1] - m_b[1]) % p, (t_b - t_a) % p
print("the difference polynomial vanishes at the true key:",
      (c2 * r_key % p * r_key + c1 * r_key + c0) % p == 0)
disc = (c1 * c1 - 4 * c2 * c0) % p
sq = pow(disc, (p + 1) // 4, p)                  # p = 3 mod 4, so this is the root
inv = pow(2 * c2, -1, p)
roots = [(-c1 + sq) * inv % p, (-c1 - sq) * inv % p]
print("roots recovered from the two tags:", roots)
print("the hash key is among them:", r_key in roots)
s_rec = (t_a - poly_mac(m_a, r_key, 0)) % p
print("recovered pad equals s:", s_rec == s1)
forged = [999999999, 424242424]
print("forged tag matches the real one:",
      poly_mac(forged, r_key, s_rec) == poly_mac(forged, r_key, s1))

# ---------- the same failure in real AES-GCM ----------
aead = AESGCM(AESGCM.generate_key(bit_length=256))
nonce = os.urandom(12)
pt1, pt2 = b"transfer  100 to alice", b"transfer 9999 to bob  "
x1 = aead.encrypt(nonce, pt1, None)[:-16]        # strip the 16-byte tag
x2 = aead.encrypt(nonce, pt2, None)[:-16]        # nonce reuse
xor = lambda a, b: bytes(u ^ v for u, v in zip(a, b))
print("AES-GCM nonce reuse: C1 xor C2 == P1 xor P2 ->", xor(x1, x2) == xor(pt1, pt2))
print("  so knowing P1 gives P2 for free:", xor(xor(x1, x2), pt1) == pt2)
print("  with distinct nonces the same equality fails:",
      xor(aead.encrypt(os.urandom(12), pt1, None)[:-16], x2) == xor(pt1, pt2))

tag(A) = 341330479213824651
tag(B) = 1383198642513917995 (same nonce, so the same pad s)
the difference polynomial vanishes at the true key: True
roots recovered from the two tags: [589016108321111110, 4777859841786623]
the hash key is among them: True
recovered pad equals s: True
forged tag matches the real one: True
AES-GCM nonce reuse: C1 xor C2 == P1 xor P2 -> True
  so knowing P1 gives P2 for free: True
  with distinct nonces the same equality fails: False

Two tags under one pad, one quadratic solved by a modular square root, and the authentication key is out. The pad follows from either tag, and after that any message can be tagged. In \(\mathrm{GF}(2^{128})\) the corresponding step is a polynomial factorization rather than a quadratic formula, and the degree is the message length in blocks, but the structure and the consequence are identical. The AES-GCM half confirms the confidentiality loss. \(C_1 \oplus C_2 = P_1 \oplus P_2\) holds exactly under a reused nonce and fails under a fresh one. The same script structure, run against a Merkle-Damgård hash, forges a valid tag for \(H(k \| \texttt{user=guest\&role=viewer} \| \mathrm{pad} \| \texttt{\&role=admin})\) from a legitimate tag without the key, and the identical attempt against HMAC-SHA-256 fails, which is the length-extension argument from the theory section reduced to an executed check.

Toy RSA and ElGamal, with the textbook failures

The RSA half uses the classic \(p = 61, q = 53\) key so every value can be checked by hand. The ElGamal half works in the prime-order subgroup where DDH is plausible.

"""Toy RSA and ElGamal, plus the attacks that make the textbook versions unusable.
Pedagogical: 12-bit and 256-bit moduli, no padding, no constant-time discipline."""
import random

random.seed(11)

# ---------- textbook RSA on the classic 61 x 53 key ----------
p, q = 61, 53
n, phi, e = p * q, (p - 1) * (q - 1), 17
d = pow(e, -1, phi)
enc, dec = lambda m: pow(m, e, n), lambda c: pow(c, d, n)
print("RSA toy: n = %d, phi(n) = %d, e = %d, d = %d, ed mod phi = %d"
      % (n, phi, e, d, e * d % phi))
print("  encrypt 65 -> %d, decrypt -> %d" % (enc(65), dec(enc(65))))
print("  correctness over the whole message space:",
      all(dec(enc(x)) == x for x in range(n)))
print("  malleability: dec(c * enc(2)) = %d = 2 * 65" % dec(enc(65) * enc(2) % n))
print("  determinism: enc(65) == enc(65) ->", enc(65) == enc(65))
print("  small exponent: m=14, e=3, m^3 = %d < n = %d, integer cube root = %d"
      % (14 ** 3, n, round(pow(14, 3, n) ** (1 / 3))))

# ---------- CRT decryption, four times faster and fault-sensitive ----------
dp, dq, qinv = d % (p - 1), d % (q - 1), pow(q, -1, p)


def dec_crt(c):
    m1, m2 = pow(c, dp, p), pow(c, dq, q)
    return m2 + ((qinv * (m1 - m2)) % p) * q


print("  CRT decryption agrees on all ciphertexts:",
      all(dec_crt(x) == dec(x) for x in range(n)))

# ---------- ElGamal in a prime-order subgroup, where DDH is plausible ----------
qq = 0x878BFAE2414C343C1027C4D1C386BBC4CD613E30D8F16ADF91B7584A2265DFF5
pp, g = 2 * qq + 1, pow(2, 2, 2 * qq + 1)
x = random.randrange(1, qq)
h = pow(g, x, pp)


def eg_enc(m):
    y = random.randrange(1, qq)
    return pow(g, y, pp), m * pow(h, y, pp) % pp


def eg_dec(ct):
    c1, c2 = ct
    return c2 * pow(c1, qq - x, pp) % pp        # c1^-x = c1^(q-x) in an order-q group


msgs = [pow(g, random.randrange(qq), pp) for _ in range(200)]
print("ElGamal: 200 encrypt/decrypt roundtrips:",
      all(eg_dec(eg_enc(m)) == m for m in msgs))
a, b = msgs[0], msgs[1]
ca, cb = eg_enc(a), eg_enc(b)
print("  multiplicatively homomorphic: dec(ca * cb) == a * b ->",
      eg_dec((ca[0] * cb[0] % pp, ca[1] * cb[1] % pp)) == a * b % pp)
print("  randomized: two encryptions of one message differ ->", eg_enc(a) != eg_enc(a))

RSA toy: n = 3233, phi(n) = 3120, e = 17, d = 2753, ed mod phi = 1
  encrypt 65 -> 2790, decrypt -> 65
  correctness over the whole message space: True
  malleability: dec(c * enc(2)) = 130 = 2 * 65
  determinism: enc(65) == enc(65) -> True
  small exponent: m=14, e=3, m^3 = 2744 < n = 3233, integer cube root = 14
  CRT decryption agrees on all ciphertexts: True
ElGamal: 200 encrypt/decrypt roundtrips: True
  multiplicatively homomorphic: dec(ca * cb) == a * b -> True
  randomized: two encryptions of one message differ -> True

Correctness is verified over the entire message space, and CRT decryption is checked against direct exponentiation on every ciphertext. The three textbook failures then appear in order. Multiplying a ciphertext by an encryption of 2 decrypts to twice the plaintext, encrypting the same value twice gives the same ciphertext, and with \(e = 3\) on a small message the modulus never wraps so an integer cube root recovers the plaintext. ElGamal's homomorphism and its randomization are both confirmed over 200 trials. The ECDSA nonce-reuse recovery of Problem 7 was verified the same way on real secp256k1 parameters with an affine-coordinate group law. Twenty honest signatures verify, twenty tampered messages are rejected, and two signatures sharing a nonce yield first the nonce and then the private key, after which an arbitrary message can be signed and verifies under the original public key.

Shamir secret sharing over a prime field

A 3-of-6 sharing with the polynomial fixed so the numbers match Problem 8, an exhaustive check that two shares leave every candidate secret possible, and a randomized check of 5-of-9 sharing over \(2^{127}-1\).

"""Shamir (t, n) secret sharing over a prime field. Pedagogical, not production."""
import random

P = 1613            # small prime so every intermediate value is checkable by hand


def poly_eval(coeffs, x, p=P):
    acc = 0
    for c in reversed(coeffs):               # Horner
        acc = (acc * x + c) % p
    return acc


def share(secret, t, n, p=P, coeffs=None):
    """Split secret into n shares, any t of which reconstruct it."""
    if coeffs is None:
        coeffs = [secret] + [random.randrange(p) for _ in range(t - 1)]
    return [(x, poly_eval(coeffs, x, p)) for x in range(1, n + 1)], coeffs


def lagrange_at_zero(shares, p=P):
    """Reconstruct f(0) by Lagrange interpolation over GF(p)."""
    total = 0
    for i, (xi, yi) in enumerate(shares):
        num = den = 1
        for j, (xj, _) in enumerate(shares):
            if i != j:
                num, den = num * (-xj) % p, den * (xi - xj) % p
        total = (total + yi * num * pow(den, -1, p)) % p
    return total


shares, coeffs = share(1234, t=3, n=6, coeffs=[1234, 166, 94])
print("polynomial  f(x) = %d + %d x + %d x^2  mod %d" % (*coeffs, P))
print("shares     ", shares)
for subset in ([0, 1, 2], [1, 3, 4], [0, 3, 5], [2, 4, 5]):
    rec = lagrange_at_zero([shares[i] for i in subset])
    print("recover from x=%s -> %d  %s" % ([shares[i][0] for i in subset], rec,
                                           "OK" if rec == 1234 else "FAIL"))

# Two shares carry no information: for every candidate secret s there is exactly
# one degree-2 polynomial through the two shares with f(0) = s.
two = shares[:2]
print("candidate secrets consistent with 2 shares:",
      sum(lagrange_at_zero([(0, s)] + two) == s for s in range(P)), "of", P)

big_p = (1 << 127) - 1
sec = random.randrange(big_p)
sh, _ = share(sec, t=5, n=9, p=big_p)
print("200 random 5-of-9 reconstructions over 2^127-1:",
      "all OK" if all(lagrange_at_zero(random.sample(sh, 5), big_p) == sec
                      for _ in range(200)) else "FAIL")
print("a 4-share attempt recovers the secret:",
      lagrange_at_zero(random.sample(sh, 4), big_p) == sec)

polynomial  f(x) = 1234 + 166 x + 94 x^2  mod 1613
shares      [(1, 1494), (2, 329), (3, 965), (4, 176), (5, 1188), (6, 775)]
recover from x=[1, 2, 3] -> 1234  OK
recover from x=[2, 4, 5] -> 1234  OK
recover from x=[1, 4, 6] -> 1234  OK
recover from x=[3, 5, 6] -> 1234  OK
candidate secrets consistent with 2 shares: 1613 of 1613
200 random 5-of-9 reconstructions over 2^127-1: all OK
a 4-share attempt recovers the secret: False

Every 3-subset reconstructs 1234, all 1613 candidate secrets remain consistent with any 2 shares, 200 random 5-of-9 reconstructions succeed over the large field, and a 4-share attempt does not recover the secret. The middle line is the one that matters. Privacy below the threshold is information-theoretic, so no amount of adversarial computation helps.

Merkle trees and inclusion proofs

Eight leaves, domain-separated leaf and node hashing, and the three-hash proof for one leaf, verified and then shown to reject a different leaf.

"""Merkle tree with domain-separated hashing and inclusion proofs. Pedagogical."""
import hashlib

H_leaf = lambda d: hashlib.sha256(b"\x00" + d).digest()      # domain separation:
H_node = lambda l, r: hashlib.sha256(b"\x01" + l + r).digest()  # leaf tag != node tag


def build(leaves):
    """Levels of the tree: level 0 the leaf hashes, last level the root."""
    level, levels = [H_leaf(x) for x in leaves], None
    levels = [level]
    while len(level) > 1:
        if len(level) % 2:
            level = level + [level[-1]]
        level = [H_node(level[i], level[i + 1]) for i in range(0, len(level), 2)]
        levels.append(level)
    return levels


def proof(levels, index):
    """Sibling path from a leaf up to the root: (hash, sibling_is_left) pairs."""
    path = []
    for level in levels[:-1]:
        nodes = level + ([level[-1]] if len(level) % 2 else [])
        sib = index ^ 1
        path.append((nodes[sib], sib < index))
        index //= 2
    return path


def verify(leaf, path, root):
    acc = H_leaf(leaf)
    for sib, sib_is_left in path:
        acc = H_node(sib, acc) if sib_is_left else H_node(acc, sib)
    return acc == root


leaves = [b"tx%d" % i for i in range(8)]
levels = build(leaves)
root = levels[-1][0]
for d, level in enumerate(levels):
    print("level %d: %s" % (d, [h.hex()[:8] for h in level]))
print("root       ", root.hex())

p = proof(levels, 5)
print("proof for leaf 5: %s" % [(h.hex()[:8], "L" if l else "R") for h, l in p])
print("verify(tx5, proof, root)      ->", verify(leaves[5], p, root))
print("verify(tx4, proof, root)      ->", verify(leaves[4], p, root))
print("all 8 inclusion proofs verify ->",
      all(verify(leaves[i], proof(levels, i), root) for i in range(8)))

tampered = list(leaves)
tampered[3] = b"tx3 "                                  # one byte changed
print("root after tampering leaf 3   ->", build(tampered)[-1][0].hex()[:16], "(differs)")
for n in (8, 1024, 1 << 20):
    depth = (n - 1).bit_length()
    print("n = %8d  proof length = %2d hashes = %4d bytes" % (n, depth, 32 * depth))

level 0: ['a91327b9', 'b535c0e4', '8f968b0e', 'dd92b235', '590b66ca', 'a98fc432', '44242c29', '643fe4d2']
level 1: ['e7f5de3c', 'fb92ff71', 'c2fdc5c0', 'aae42598']
level 2: ['f7ef01f2', '2b8a3d57']
level 3: ['807a99ec']
root        807a99ec8905538b7cb3ae8a446b76b0696bd98b06aabaf5b5cf56475451229c
proof for leaf 5: [('590b66ca', 'L'), ('aae42598', 'R'), ('f7ef01f2', 'L')]
verify(tx5, proof, root)      -> True
verify(tx4, proof, root)      -> False
all 8 inclusion proofs verify -> True
root after tampering leaf 3   -> b01f84efe7192d51 (differs)
n =        8  proof length =  3 hashes =   96 bytes
n =     1024  proof length = 10 hashes =  320 bytes
n =  1048576  proof length = 20 hashes =  640 bytes

The proof for leaf 5 carries three sibling hashes with their left/right positions, verifies against the root, and fails for leaf 4 with the same path. Changing one byte of any leaf changes the root. The last lines are the scaling argument. A proof for one leaf among a million is 20 hashes and 640 bytes, which is why certificate transparency logs, content-addressed stores, and BLAKE3's internal tree all use this structure.

Schnorr, with proof, simulation, extraction, and Fiat-Shamir

The same protocol in four modes, which together are the definition of zero knowledge made executable. Honest proofs accept. Proofs with the wrong witness fail. Simulated transcripts, produced with no witness at all by choosing the response first and solving for the commitment, also accept, so a transcript proves nothing to a third party. And two transcripts on one commitment reveal the witness, so convincing a live verifier does require knowing it.

"""Schnorr identification, its simulator, its extractor, and Fiat-Shamir.
Pedagogical: a real implementation uses a curve group and constant-time code."""
import hashlib
import random

random.seed(7)
# A prime-order subgroup of Z_p^*: p = 2q + 1 with both q and p prime.
q = 0x878BFAE2414C343C1027C4D1C386BBC4CD613E30D8F16ADF91B7584A2265DFF5
p = 2 * q + 1
g = pow(2, 2, p)                       # any nonzero square lies in the order-q group
assert pow(g, q, p) == 1 and g != 1

x = random.randrange(1, q)             # witness
h = pow(g, x, p)                       # statement: "I know x with h = g^x"


def prove(witness):
    """Commitment, challenge, response."""
    r = random.randrange(1, q)
    return pow(g, r, p), (c := random.randrange(q)), (r + c * witness) % q


def check(t, c, s):
    return pow(g, s, p) == t * pow(h, c, p) % p


def simulate():
    """Zero knowledge: an accepting transcript built without the witness, by
    choosing the response first and solving for the commitment."""
    c, s = random.randrange(q), random.randrange(q)
    return pow(g, s, p) * pow(h, -c % q, p) % p, c, s


def extract(c1, s1, c2, s2):
    """Special soundness: two responses to one commitment give the witness."""
    return (s1 - s2) * pow(c1 - c2, -1, q) % q


def challenge(t, msg):
    """Fiat-Shamir: the hash covers the group, the statement, the commitment,
    and the message. Omitting any of them breaks something."""
    material = b"schnorr" + b"|".join(str(v).encode() for v in (p, g, h, t)) + msg
    return int.from_bytes(hashlib.sha256(material).digest(), "big") % q


def fs_sign(msg):
    r = random.randrange(1, q)
    t = pow(g, r, p)
    return t, (r + challenge(t, msg) * x) % q


def fs_verify(pub, msg, t, s):
    c = int.from_bytes(hashlib.sha256(
        b"schnorr" + b"|".join(str(v).encode() for v in (p, g, pub, t)) + msg
    ).digest(), "big") % q
    return pow(g, s, p) == t * pow(pub, c, p) % p


print("200 honest interactive proofs accept:", all(check(*prove(x)) for _ in range(200)))
print("200 proofs with the wrong witness rejected:",
      not any(check(*prove(random.randrange(1, q))) for _ in range(200)))
print("200 simulated transcripts also accept:", all(check(*simulate()) for _ in range(200)))

r = random.randrange(1, q)                      # rewind the prover to one commitment
c1, c2 = random.randrange(q), random.randrange(q)
print("witness extracted from two transcripts equals x:",
      extract(c1, (r + c1 * x) % q, c2, (r + c2 * x) % q) == x)

msg = b"transfer 10 units to bob"
t, s = fs_sign(msg)
print("Fiat-Shamir signature verifies:      ", fs_verify(h, msg, t, s))
print("...on a modified message:            ", fs_verify(h, b"transfer 100 to bob", t, s))
print("...under a different public key:     ", fs_verify(pow(g, x + 1, p), msg, t, s))
print("200 Fiat-Shamir signatures verify:   ",
      all(fs_verify(h, b"m%d" % i, *fs_sign(b"m%d" % i)) for i in range(200)))

200 honest interactive proofs accept: True
200 proofs with the wrong witness rejected: True
200 simulated transcripts also accept: True
witness extracted from two transcripts equals x: True
Fiat-Shamir signature verifies:       True
...on a modified message:             False
...under a different public key:      False
200 Fiat-Shamir signatures verify:    True

All four properties hold over 200 trials each. The Fiat-Shamir section then turns the protocol into a signature and confirms it verifies only under the exact message and the exact public key that went into the challenge hash, which is precisely what including both in that hash buys.

Regev's LWE encryption, with the noise budget measured

The lattice scheme in its simplest form. Encrypt a bit by summing a random subset of the public samples and adding \(b\lfloor q/2 \rfloor\). Decrypt by subtracting \(\langle u, s\rangle\) and testing which half of the modulus the result falls in. At \(n = 64\), \(q = 8192\), \(m = 256\), \(\sigma = 8\) the run records zero decryption failures in 2,000 trials, with accumulated noise of standard deviation 63.7 against a decryption margin of \(q/4 = 2048\). Conditioned on a fixed key the only randomness is the subset choice, predicting \(\sigma\sqrt{m}/2 = 64.0\), which is what the measurement matches. Averaging over keys as well predicts \(\sigma\sqrt{m/2} = 90.5\). Raising \(\sigma\) to 128 pushes the noise into the decision boundary and 21 of 500 decryptions fail. That is parameter selection in miniature. ML-KEM's modulus \(q = 3329\) and its centered binomial noise are chosen so the failure probability is below \(2^{-138}\), because a decryption failure is not merely an outage, it leaks information about the secret key.

Using real libraries correctly

Both blocks do the same four things. They authenticate and encrypt with an AEAD including associated data, verify that tampering and wrong associated data fail closed, agree a key by elliptic-curve Diffie-Hellman and expand it through HKDF into independent directional subkeys, and sign. No primitive is implemented. The Rust version uses the RustCrypto crates (aes-gcm 0.10, chacha20poly1305 0.10, hkdf 0.12, ed25519-dalek 2, x25519-dalek 2) and was compiled and run. The TypeScript version uses WebCrypto, which is the same API in a browser and in Node.

// Applied crypto with RustCrypto: AEAD, HKDF, X25519, Ed25519.
// Nothing here implements a primitive; it only uses vetted ones correctly.
use aes_gcm::aead::{Aead, AeadCore, KeyInit, OsRng, Payload};
use aes_gcm::Aes256Gcm;
use chacha20poly1305::ChaCha20Poly1305;
use hkdf::Hkdf;
use hmac::{Hmac, Mac};
use sha2::Sha256;
use subtle::ConstantTimeEq;

fn aead_demo() {
    let key = Aes256Gcm::generate_key(&mut OsRng);
    let cipher = Aes256Gcm::new(&key);
    // A fresh 96-bit nonce per message. Reuse under one key is fatal for GCM.
    let nonce = Aes256Gcm::generate_nonce(&mut OsRng);
    let aad = b"v1:account-4711";
    let ct = cipher
        .encrypt(&nonce, Payload { msg: b"balance: 42.00", aad })
        .expect("encrypt");
    let pt = cipher
        .decrypt(&nonce, Payload { msg: ct.as_ref(), aad })
        .expect("decrypt");
    println!("AES-256-GCM roundtrip: {}", String::from_utf8_lossy(&pt));

    // Wrong associated data must fail, and so must a flipped ciphertext bit.
    let wrong = cipher.decrypt(&nonce, Payload { msg: ct.as_ref(), aad: b"v1:account-9999" });
    let mut tampered = ct.clone();
    tampered[0] ^= 1;
    let flipped = cipher.decrypt(&nonce, Payload { msg: tampered.as_ref(), aad });
    println!("  wrong AAD rejected: {}", wrong.is_err());
    println!("  tampered ciphertext rejected: {}", flipped.is_err());

    // ChaCha20-Poly1305 is the same interface; pick it where AES has no hardware.
    let ck = ChaCha20Poly1305::generate_key(&mut OsRng);
    let cc = ChaCha20Poly1305::new(&ck);
    let cn = ChaCha20Poly1305::generate_nonce(&mut OsRng);
    let cct = cc.encrypt(&cn, Payload { msg: b"balance: 42.00", aad }).unwrap();
    let cpt = cc.decrypt(&cn, Payload { msg: cct.as_ref(), aad }).unwrap();
    println!("ChaCha20-Poly1305 roundtrip: {}", String::from_utf8_lossy(&cpt));
}

fn hkdf_demo(ikm: &[u8]) {
    let salt = [0x0bu8; 32];
    let hk = Hkdf::<Sha256>::new(Some(&salt), ikm);
    let mut c2s = [0u8; 32];
    let mut s2c = [0u8; 32];
    hk.expand(b"client->server", &mut c2s).unwrap();
    hk.expand(b"server->client", &mut s2c).unwrap();
    println!("HKDF: distinct labels give distinct subkeys: {}", c2s != s2c);
}

fn x25519_demo() {
    use x25519_dalek::{EphemeralSecret, PublicKey};
    let a_sec = EphemeralSecret::random_from_rng(&mut OsRng);
    let a_pub = PublicKey::from(&a_sec);
    let b_sec = EphemeralSecret::random_from_rng(&mut OsRng);
    let b_pub = PublicKey::from(&b_sec);
    let ab = a_sec.diffie_hellman(&b_pub);
    let ba = b_sec.diffie_hellman(&a_pub);
    println!("X25519 shared secrets agree: {}", ab.as_bytes() == ba.as_bytes());
    // The raw shared secret is not a key. Expand it first.
    hkdf_demo(ab.as_bytes());
}

fn ed25519_demo() {
    use ed25519_dalek::{Signature, Signer, SigningKey, Verifier};
    let sk = SigningKey::generate(&mut OsRng);
    let vk = sk.verifying_key();
    let msg = b"transfer 10 units to bob";
    let sig: Signature = sk.sign(msg);
    println!("Ed25519 verify honest: {}", vk.verify(msg, &sig).is_ok());
    println!("Ed25519 verify tampered: {}",
             vk.verify(b"transfer 10 units to mallory", &sig).is_ok());
    // Deterministic nonces: signing the same message twice gives the same bytes,
    // which is exactly the property that removes the ECDSA nonce-reuse footgun.
    println!("Ed25519 is deterministic: {}", sk.sign(msg).to_bytes() == sig.to_bytes());
}

fn constant_time_demo() {
    let a = [7u8; 32];
    let b = [7u8; 32];
    let mut c = [7u8; 32];
    c[31] = 8;
    // ct_eq has no early exit, so its running time does not depend on where the
    // first difference is. Comparing secrets with == is a timing oracle.
    println!("constant-time compare equal: {}", bool::from(a.ct_eq(&b)));
    println!("constant-time compare differ: {}", bool::from(a.ct_eq(&c)));

    let mut mac = <Hmac<Sha256> as Mac>::new_from_slice(b"key material").unwrap();
    mac.update(b"message");
    let tag = mac.clone().finalize().into_bytes();
    // verify_slice is the constant-time comparison; never compare tags with ==.
    println!("HMAC verify: {}", mac.verify_slice(&tag).is_ok());
}

fn main() {
    aead_demo();
    x25519_demo();
    ed25519_demo();
    constant_time_demo();
}

// WebCrypto: AEAD, HKDF, ECDH, ECDSA. Runs unchanged in a browser or in Node.
// Keys are non-extractable CryptoKey handles, so the bytes never enter JS memory.
const enc = new TextEncoder();
const dec = new TextDecoder();

async function aead(): Promise<void> {
  const key = await crypto.subtle.generateKey(
    { name: "AES-GCM", length: 256 }, false, ["encrypt", "decrypt"]);
  const iv = crypto.getRandomValues(new Uint8Array(12));  // 96 bits, never reused
  const aad = enc.encode("v1:account-4711");              // authenticated, not encrypted
  const alg = { name: "AES-GCM", iv, additionalData: aad, tagLength: 128 };
  const ct = await crypto.subtle.encrypt(alg, key, enc.encode("balance: 42.00"));
  console.log("AES-GCM roundtrip:", dec.decode(await crypto.subtle.decrypt(alg, key, ct)));

  // Decryption fails closed on wrong associated data and on a flipped bit.
  const wrongAad = { ...alg, additionalData: enc.encode("v1:account-9999") };
  const flipped = new Uint8Array(ct); flipped[0] ^= 1;
  for (const [label, a, c] of [["AAD mismatch", wrongAad, ct],
                               ["tampered ciphertext", alg, flipped]] as const) {
    await crypto.subtle.decrypt(a, key, c)
      .then(() => console.log(`${label} accepted: BUG`))
      .catch(() => console.log(`${label} rejected: true`));
  }
}

async function subkeys(ikm: ArrayBuffer): Promise<void> {
  // The raw ECDH output is not a key: expand it, with a distinct label per use.
  const base = await crypto.subtle.importKey("raw", ikm, "HKDF", false, ["deriveBits"]);
  const salt = crypto.getRandomValues(new Uint8Array(32));
  const sub = async (label: string) => new Uint8Array(await crypto.subtle.deriveBits(
    { name: "HKDF", hash: "SHA-256", salt, info: enc.encode(label) }, base, 256));
  const [c2s, s2c] = [await sub("client->server"), await sub("server->client")];
  console.log("HKDF: two labels give different subkeys:",
              !c2s.every((b, i) => b === s2c[i]));
}

async function ecdh(): Promise<void> {
  const params = { name: "ECDH", namedCurve: "P-256" };
  const [a, b] = [await crypto.subtle.generateKey(params, false, ["deriveBits"]),
                  await crypto.subtle.generateKey(params, false, ["deriveBits"])];
  const ab = new Uint8Array(await crypto.subtle.deriveBits(
    { name: "ECDH", public: b.publicKey }, a.privateKey, 256));
  const ba = new Uint8Array(await crypto.subtle.deriveBits(
    { name: "ECDH", public: a.publicKey }, b.privateKey, 256));
  console.log("ECDH shared secrets agree:", ab.every((x, i) => x === ba[i]));
  await subkeys(ab.buffer);
}

async function signVerify(): Promise<void> {
  const kp = await crypto.subtle.generateKey(
    { name: "ECDSA", namedCurve: "P-256" }, false, ["sign", "verify"]);
  const alg = { name: "ECDSA", hash: "SHA-256" };
  const msg = enc.encode("transfer 10 units to bob");
  const sig = await crypto.subtle.sign(alg, kp.privateKey, msg);
  console.log("ECDSA verify (honest, tampered):",
              await crypto.subtle.verify(alg, kp.publicKey, sig, msg),
              await crypto.subtle.verify(alg, kp.publicKey, sig,
                                         enc.encode("transfer 10 units to mallory")));
}

await aead();
await ecdh();
await signVerify();

$ cargo run --quiet
AES-256-GCM roundtrip: balance: 42.00
  wrong AAD rejected: true
  tampered ciphertext rejected: true
ChaCha20-Poly1305 roundtrip: balance: 42.00
X25519 shared secrets agree: true
HKDF: distinct labels give distinct subkeys: true
Ed25519 verify honest: true
Ed25519 verify tampered: false
Ed25519 is deterministic: true
constant-time compare equal: true
constant-time compare differ: false
HMAC verify: true

$ node --experimental-strip-types webcrypto.mts
AES-GCM roundtrip: balance: 42.00
AAD mismatch rejected: true
tampered ciphertext rejected: true
ECDH shared secrets agree: true
HKDF: two labels give different subkeys: true
ECDSA verify (honest, tampered): true false

Three details in those blocks separate correct usage from plausible-looking usage. The nonce is generated fresh per message and never derived from the message or carried across messages. The associated data carries the context the ciphertext must be bound to, so a ciphertext moved to a different account or a different protocol version fails to authenticate instead of decrypting into the wrong place. And the raw Diffie-Hellman output is never used as a key. It goes through HKDF with a label, which both uniformizes the bits and produces independent subkeys per direction, so compromise of one direction's key says nothing about the other. The Rust block closes with the constant-time comparison and the constant-time MAC verification, which is the subject of the last measurement.

Why comparisons must be constant time

The smallest measurement here and the one most often skipped. An early-exit comparison of a MAC tag leaks, through its running time, how many leading bytes matched, which turns a \(2^{128}\) forgery search into 16 searches of 256 each.

"""An early-exit tag comparison is a timing oracle. Measured, not asserted."""
import hmac
import statistics
import time


def naive_equal(a, b):
    if len(a) != len(b):
        return False
    for x, y in zip(a, b):          # returns as soon as a byte differs
        if x != y:
            return False
    return True


def timeit(fn, a, b, reps=20000):
    samples = []
    for _ in range(15):
        t0 = time.perf_counter_ns()
        for _ in range(reps):
            fn(a, b)
        samples.append((time.perf_counter_ns() - t0) / reps)
    return statistics.median(samples)


tag = bytes(range(32))
early = bytearray(tag); early[0] ^= 1      # differs at byte 0
late = bytearray(tag); late[31] ^= 1       # differs at byte 31

print("naive early-exit compare:")
print("  differs at byte  0: %7.1f ns" % timeit(naive_equal, tag, bytes(early)))
print("  differs at byte 31: %7.1f ns" % timeit(naive_equal, tag, bytes(late)))
print("constant-time compare_digest:")
print("  differs at byte  0: %7.1f ns" % timeit(hmac.compare_digest, tag, bytes(early)))
print("  differs at byte 31: %7.1f ns" % timeit(hmac.compare_digest, tag, bytes(late)))

naive early-exit compare:
  differs at byte  0:   215.1 ns
  differs at byte 31:  1066.0 ns
constant-time compare_digest:
  differs at byte  0:    50.5 ns
  differs at byte 31:    50.4 ns

The naive comparison takes 215.1 ns when the first byte differs and 1066.0 ns when only the last byte differs, a 5.0x spread that is measurable across a network given enough samples. hmac.compare_digest takes 50.5 and 50.4 ns, a difference below the measurement noise. Every serious library exposes such a function, CRYPTO_memcmp in OpenSSL, sodium_memcmp in libsodium, subtle::ConstantTimeEq in RustCrypto, and the rule is simply that secrets are never compared with the language's equality operator.

How it is done in practice

TLS 1.3, message by message

TLS 1.3 (RFC 8446, Rescorla, 2018) is the best-analyzed protocol in deployment and the clearest example of every definition above being used for something. The full handshake is one round trip.

  Client                                              Server

  ClientHello                 -------->
    + key_share (X25519 / ML-KEM public value)
    + supported_versions, cipher_suites
    + signature_algorithms
    [+ pre_shared_key, early_data, + 0-RTT app data]
                                        ServerHello
                                          + key_share (server public value)
                              {EncryptedExtensions}
                              {CertificateRequest*}
                              {Certificate}          server's cert chain
                              {CertificateVerify}    signature over the transcript
                              {Finished}             MAC over the transcript
                              <--------  [Application Data*]
  {Certificate*}
  {Certificate Verify*}
  {Finished}                  -------->
  [Application Data]          <------->  [Application Data]

  {} encrypted with handshake keys      [] encrypted with application keys

ClientHello. The client sends its ephemeral Diffie-Hellman public value immediately, guessing the group rather than negotiating it first. That guess is what makes the handshake one round trip instead of two. It also sends the versions, cipher suites, and signature algorithms it supports. All of it is in the clear and all of it is covered by the transcript hash later, so tampering is detected even though it is not hidden.

ServerHello. The server picks the group and sends its own ephemeral public value. Both sides now compute the shared secret and immediately derive handshake keys through HKDF, so everything after this point is encrypted, including the server's certificate. That is a change from TLS 1.2, where the certificate travelled in the clear and leaked the identity of the service to any observer.

Certificate and CertificateVerify. The certificate asserts the binding between a name and a public key. CertificateVerify is a signature over the hash of the entire handshake transcript so far. This is the step that defeats the man-in-the-middle attack on raw Diffie-Hellman. An attacker can substitute its own key share, but it cannot produce a signature over a transcript containing that share without the certificate's private key. Note the separation of duties, which is the whole design. The long-term key authenticates, the ephemeral key encrypts.

Finished. Each side sends a MAC over the transcript under a key derived from the handshake secret. This proves both sides derived the same secret and saw the same messages, which closes downgrade attacks. If an attacker stripped a supported version or a cipher suite from the ClientHello, the transcripts differ and the MAC fails.

The key schedule is a chain of HKDF-Extract and HKDF-Expand calls producing separate secrets for handshake traffic, application traffic in each direction, exporters, and resumption. Every derivation is labeled, so no two keys are ever equal by accident and no key serves two purposes. The AEADs allowed are exactly three, AES-128-GCM, AES-256-GCM, and ChaCha20-Poly1305, with the record sequence number contributing to the nonce so nonce uniqueness is a protocol invariant rather than an implementation hope.

Forward secrecy, and what it does not cover

A protocol has forward secrecy when compromise of long-term keys does not expose past sessions. TLS 1.3 has it because the session key comes from ephemeral Diffie-Hellman values that both sides discard after the handshake. The server's certificate key signs, and a signature key cannot decrypt anything. TLS 1.2's RSA key transport did not have it. The client encrypted the premaster secret to the server's long-term RSA key, so an adversary who recorded traffic for years and later obtained that key decrypted everything retroactively. This is the single most important reason static RSA key exchange was removed.

Forward secrecy does not cover sessions in progress at the moment of compromise, future sessions, or anything the endpoints stored. It also depends on the ephemeral keys actually being erased, which is not automatic in a garbage-collected runtime and is defeated by session-ticket keys that live for weeks. Protocols that want more, such as the Signal double ratchet, add post-compromise security by re-running Diffie-Hellman continuously, so an attacker who steals state loses access again once a fresh exchange completes.

0-RTT and the replay caveat

With a pre-shared key from a previous session, TLS 1.3 lets a client send application data in its first flight, before any round trip. The data is encrypted under a key derived from the resumption secret alone. The catch follows directly. Nothing in that first flight depends on a fresh server contribution, so the server cannot distinguish a genuine 0-RTT message from a replayed recording of one, and forward secrecy does not hold for it either. The mitigations are all partial. Single-use tickets need cross-server state, and freshness windows narrow rather than close the hole. The correct rule is a protocol-level one. Only idempotent requests may be sent as 0-RTT data, which in HTTP terms means GET without side effects and never a POST.

PKI and certificate transparency

The web's trust model is a list of root certificate authorities shipped with the browser or operating system. Any of them can issue a certificate for any name, so the security of every site is the security of the weakest CA, a structural weakness demonstrated by the DigiNotar compromise in 2011 that produced valid certificates for Google domains. Certificate Transparency (RFC 6962, from Laurie, Langley, and Kasper at Google) does not prevent misissuance. It makes it detectable. Every certificate must be logged in append-only Merkle-tree logs, the CA obtains a signed timestamp proving submission, and browsers refuse certificates lacking one. Domain owners monitor logs for certificates they did not request, and auditors verify log consistency with the Merkle proofs from the implementation above. An inclusion proof shows a certificate is in the log, and a consistency proof shows the log only ever appended.

The rest of the modern PKI story is shortened lifetimes and automation. Certificate lifetimes have fallen from years to months and are heading shorter, because short expiry substitutes for revocation, which never worked. CRLs are too large and OCSP leaks browsing history to the CA while usually failing open. ACME automation is what makes short lifetimes tolerable. For internal systems the same reasoning leads to a private CA with hours-long certificates and workload identity, which is how service meshes do mutual TLS.

Randomness, and the failures that came from getting it wrong

Every construction on this page assumes uniform random bits at some point. The correct source is the operating system, getrandom(2) on Linux, arc4random_buf on the BSDs and macOS, BCryptGenRandom on Windows, crypto.getRandomValues in a browser. These are seeded from hardware entropy, they do not block after initial seeding, and they handle fork and VM-snapshot cases that user-space generators get wrong. Using a language's default PRNG is a bug. Python's random, Java's Random, and rand() in C are all predictable from a handful of outputs.

The historical failures are worth memorizing because each one maps to a precondition stated earlier. The Debian OpenSSL patch of 2006, discovered in 2008, removed the entropy sources and left the process ID as the only seed, so all keys generated on affected systems came from a set of about 32,768 possibilities. The Sony PlayStation 3 code-signing key fell in 2010 because the ECDSA nonce was a constant, which is the algebra of Problem 7 executed by other people. Android's SecureRandom bug in 2013 repeated nonces and drained Bitcoin wallets by the same mechanism. And Dual_EC_DRBG, a NIST-standardized generator with an unexplained pair of points, was shown by Shumow and Ferguson in 2007 to admit a back door for anyone knowing their discrete-log relationship, and was later reported to have been paid for. The lesson repeated across all four is that the randomness is not a detail of the implementation, it is a hypothesis of the theorem.

Key management, rotation, and reading an API safely

Key management is where most real systems are weakest, because it is the part with no clean theory. The working rules are these. Use one key per purpose, derived with a labeled KDF from a root rather than reused across purposes. Hold keys in a KMS or HSM where the application receives operations rather than key bytes. Use envelope encryption so that rotating a key encryption key does not require re-encrypting the data. Put explicit key identifiers in every ciphertext so that rotation and algorithm migration are possible at all. And drive rotation by data volume against the birthday bounds computed earlier, not by a calendar. Rotation without a key identifier in the ciphertext format is not rotation, it is an outage waiting for the first old record.

Reading a cryptographic API safely comes down to a few questions asked in order. What is the security notion, AEAD or plain encryption, and what does the type system force? Who supplies the nonce, and what happens if it repeats? Does decryption return a distinguishable error, or a single failure? Are comparisons constant time? What are the documented data limits per key? Libraries differ enormously in how much they answer for you. libsodium's crypto_secretbox and Tink's key handles are designed so the misuse is hard to express. ring encodes single-use nonces in the type system, so reusing one is a compile error. OpenSSL's EVP interface will happily let a caller reuse an IV, decrypt without checking a tag, or pick an unauthenticated mode. The single most reliable applied rule remains the same. Do not implement primitives, and choose the library whose default is the safe thing.

The current research frontier

The post-quantum migration. The standards exist and the work is now engineering. Hybrid X25519 with ML-KEM-768 is negotiated by default in major browsers and CDNs, so a large fraction of web key exchange is already quantum-resistant. SSH followed with hybrid sntrup761x25519 and ML-KEM variants. Signatures lag, and the reason is size. Certificate chains carrying ML-DSA signatures and public keys inflate handshakes by several kilobytes, which measurably hurts connection setup on lossy links. The competing directions are Falcon (small signatures, hard implementation), merkle-tree schemes for firmware where statefulness is acceptable (LMS and XMSS, already standardized in SP 800-208), and protocol-level tricks that omit intermediate certificates. NIST's additional-signature round, with MAYO, SQIsign, and others, is searching for a small non-lattice signature. A separate concern is structural diversity, since ML-KEM and ML-DSA rest on the same family of assumptions and a lattice advance would hit both.

Formally verified implementations. The most consequential practical line is the one that removes implementation bugs by proof rather than by review. HACL* and EverCrypt, from a collaboration involving Microsoft Research and INRIA, are verified in F* and compiled to C. Their code ships in Firefox, in the Linux kernel's WireGuard implementation, and in mozilla's NSS. Fiat-Crypto, from MIT, generates field arithmetic with machine-checked proofs of functional correctness, and its output is in BoringSSL. Jasmin and libjade extend the approach to assembly with constant-time guarantees verified at the instruction level. The trend line is clear. For the small set of primitives everyone uses, hand-written code is being replaced by generated, proved code.

Proof systems. zk-SNARK research is moving toward transparent setups, faster provers, and recursive composition. Folding schemes (Nova and its successors, from Microsoft Research and academic collaborators) reduce incremental verifiable computation to a cheap per-step folding operation instead of a full proof. Lookup arguments (Plookup, Halo2's variants) make otherwise-expensive operations such as range checks and bitwise logic tractable inside arithmetic circuits. Hash-based systems from the Technion-derived STARK line trade proof size for transparency and plausible post-quantum security. Hardware acceleration for multi-scalar multiplication and NTT, the two dominant costs, is an active industry.

Encrypted computation. FHE's practical frontier is bootstrapping cost and compiler tooling. Microsoft Research's SEAL, OpenFHE, and Zama's TFHE-rs each attack a different point on the latency-versus-throughput curve, and the interesting work is in transpilers that turn ordinary programs into circuits with sensible noise budgets. MPC's frontier is throughput for specific shapes. Private set intersection is fast enough for advertising measurement at scale, and threshold ECDSA and threshold Schnorr signing are now used in custody products. PIR has recently become plausible for real workloads through preprocessing-based schemes such as SimplePIR and Spiral, with certificate revocation checking and private DNS as the obvious targets. Across all three, the honest summary is the same. The asymptotics have been fine for years and the constants are what changed.

Attacks that matter. The productive attack surface is not the mathematics. Microarchitectural side channels keep producing practical key extraction, from cache timing against table-based AES to Hertzbleed's frequency-scaling leak (2022) and the GoFetch attack on Apple silicon's data memory-dependent prefetcher (2024), which extracts keys from constant-time code by exploiting a prefetcher that treats data as pointers. Fault injection continues to break signature implementations. And the largest category by volume remains protocol and implementation misuse of exactly the kinds demonstrated in this page's code. The companion page on systems and web security covers the surrounding attack surface in detail.

Open source to read

Repositories worth reading rather than merely importing, with the file to open first.

briansmith/ring is a Rust crypto library whose design philosophy is that misuse should be a compile error. Open src/aead/nonce.rs and read how a nonce is a move-only type consumed by a single sealing operation, so reusing one does not type-check. Then src/aead/less_safe_key.rs, whose name is itself the documentation for what you give up when you opt out.

jedisct1/libsodium is the reference for an API designed so the default is correct. Open src/libsodium/crypto_aead/xchacha20poly1305/aead_xchacha20poly1305.c to see the 192-bit-nonce construction that makes random nonces safe, and compare it with the aes256gcm directory, where the API forces a runtime check for hardware support before the function is even available.

tink-crypto/tink-cc (the C++ half of what was google/tink, now archived and split by language) organizes cryptography around key handles, keysets, and rotation rather than around algorithms. Open tink/aead/aes_gcm_key_manager.h to see how a key type carries its parameters and validation, then tink/aead/kms_envelope_aead.h for envelope encryption as a first-class primitive.

openssl/openssl is the code most of the internet actually runs, and the best place to see the gap between a specification and an implementation. Open ssl/tls13_enc.c and follow the key schedule from the shared secret through the handshake and application traffic secrets. It is RFC 8446 section 7.1 in C, label by label.

BLAKE3-team/BLAKE3 is the clearest modern hash design. Open reference_impl/reference_impl.rs, which is a few hundred readable lines covering the compression function, the chunk chaining, and the tree structure that makes the whole thing parallel. The SIMD implementations in c/ are the same algorithm with the tree exploited.

arkworks-rs/algebra is the algebraic foundation under most Rust zero-knowledge work. Open ec/src/models/short_weierstrass/affine.rs for the group law of this page implemented generically over a field, then ec/src/pairing.rs for the bilinear map that SNARK verifiers use.

microsoft/SEAL is homomorphic encryption you can actually run. Open native/examples/5_ckks_basics.cpp, which walks the encoding of real numbers, the scale management, and the noise budget. It teaches more about why FHE is hard to use than any survey.

open-quantum-safe/liboqs is the collection point for post-quantum implementations behind one API. Open src/kem/ml_kem/kem_ml_kem_768.c for the thin wrapper that fixes the parameter set, then docs/algorithms/kem/ml_kem.yml for the key and ciphertext sizes and the constant-time claims for each implementation, which is where the numbers in the table above come from.

Common misconceptions

"The ciphertext looks random, so the encryption is fine." Looking random is the conclusion of whatever tests someone ran. A security definition quantifies over all efficient tests. ECB output looks random block by block and leaks the entire structure of the plaintext. Every construction on this page that failed, failed while producing output that would pass a randomness test suite.

"Encryption protects integrity." It does not, and the separation is not subtle. CTR and every stream cipher are exactly malleable. Flipping a ciphertext bit flips the corresponding plaintext bit, as measured above. CBC lets an attacker control a whole block at the cost of randomizing another. Without a MAC or an AEAD, a ciphertext is a suggestion.

"A nonce is a random number, so nonce reuse just means slightly less randomness." Nonce means "number used once", and the requirement is uniqueness rather than randomness. Reuse in CTR or ChaCha20 exposes the XOR of two plaintexts. Reuse in GCM additionally exposes the authentication key and therefore permits arbitrary forgeries under that key. Reuse in ECDSA reveals the private key with two divisions. None of those is a gradual degradation.

"Longer keys mean more security, so 4096-bit RSA is much stronger than 2048." The scaling is subexponential, so doubling the modulus buys far less than doubling the exponent of work. A 2048-bit modulus is roughly \(2^{110}\)-ish, 3072 gives about \(2^{128}\), and reaching \(2^{256}\) needs about 15,360 bits. Meanwhile a 256-bit elliptic curve gives \(2^{128}\) with far cheaper operations. Key length is only comparable within one algorithm family.

"We hash passwords with SHA-256, so they are safe." SHA-256 is fast, and fast is the wrong property here. A GPU tests billions of candidates per second against a stolen hash. Password hashing needs a deliberately expensive, memory-hard function with a per-user salt, such as Argon2id, scrypt, or bcrypt. The iteration count and memory parameter are the security margin, and they need raising as hardware improves.

"Zero-knowledge proofs make a system private." A proof system proves what its circuit says and hides only what the circuit was designed to hide. Most SNARK deployments are used for succinctness, not privacy. And the surrounding metadata, transaction timing, amounts, network-level linkage, is untouched by any of it.

"Quantum computers break all cryptography." Shor breaks the public-key algorithms in deployment today, completely. Grover halves the effective key length of symmetric primitives, which AES-256 already accounts for, and its poor parallelization makes even AES-128 a stretch. Hash-based signatures, symmetric encryption, and MACs survive with parameter changes. The migration is a large engineering project, not a restart.

"Our system is secure because we use AES-256." Naming a primitive says nothing about the mode, the nonce discipline, the integrity protection, the key management, or the protocol. Almost every real failure in this field occurred in a system that used a perfectly good primitive incorrectly.

Self-check

References

1. Katz, J. and Lindell, Y. Introduction to Modern Cryptography, 3rd edition. CRC Press, 2020. The definition-first treatment this page follows.
2. Boneh, D. and Shoup, V. A Graduate Course in Applied Cryptography, draft, 2023. toc.cryptobook.us. The most complete free source for the concrete-security bounds quoted here.
3. Goldreich, O. Foundations of Cryptography, Volumes 1 and 2. Cambridge University Press, 2001 and 2004. The rigorous treatment of pseudorandomness, zero knowledge, and reductions.
4. Ferguson, N., Schneier, B., and Kohno, T. Cryptography Engineering. Wiley, 2010. The engineering-failure perspective.
5. Aumasson, J.-P. Serious Cryptography, 2nd edition. No Starch Press, 2024. The applied companion, with the modern primitives.
6. Shannon, C. E. "Communication Theory of Secrecy Systems." Bell System Technical Journal 28(4), 1949. DOI. Perfect secrecy and the key-length bound proved above.
7. Diffie, W. and Hellman, M. "New Directions in Cryptography." IEEE Transactions on Information Theory 22(6), 1976. DOI.
8. Rivest, R., Shamir, A., and Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." CACM 21(2), 1978. DOI. From MIT and, for Shamir, later the Weizmann Institute.
9. Goldwasser, S. and Micali, S. "Probabilistic Encryption." Journal of Computer and System Sciences 28(2), 1984. DOI. Semantic security, from MIT.
10. Goldwasser, S., Micali, S., and Rackoff, C. "The Knowledge Complexity of Interactive Proof Systems." STOC 1985; SIAM J. Computing 18(1), 1989. DOI.
11. ElGamal, T. "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms." IEEE Transactions on Information Theory 31(4), 1985. DOI.
12. Shamir, A. "How to Share a Secret." CACM 22(11), 1979. DOI. Weizmann Institute.
13. Wegman, M. N. and Carter, J. L. "New Hash Functions and Their Use in Authentication and Set Equality." JCSS 22(3), 1981. DOI. IBM Research. The universal-hash MAC behind GMAC and Poly1305.
14. Fiat, A. and Shamir, A. "How to Prove Yourself: Practical Solutions to Identification and Signature Problems." CRYPTO 1986. DOI. Weizmann Institute.
15. Schnorr, C. P. "Efficient Signature Generation by Smart Cards." Journal of Cryptology 4(3), 1991. DOI.
16. Pedersen, T. P. "Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing." CRYPTO 1991. DOI.
17. Yao, A. C.-C. "How to Generate and Exchange Secrets." FOCS 1986. DOI. Garbled circuits. Yao now leads the interdisciplinary information sciences institute at Tsinghua.
18. Bellare, M. and Rogaway, P. "Random Oracles are Practical: A Paradigm for Designing Efficient Protocols." CCS 1993. DOI. See also their "Optimal Asymmetric Encryption" (EUROCRYPT 1994) for OAEP.
19. Bellare, M., Canetti, R., and Krawczyk, H. "Keying Hash Functions for Message Authentication." CRYPTO 1996. DOI. HMAC, with Canetti and Krawczyk then at IBM Research and Krawczyk also at the Technion.
20. Bellare, M. and Namprempre, C. "Authenticated Encryption: Relations among Notions and Analysis of the Generic Composition Paradigm." ASIACRYPT 2000. DOI.
21. Krawczyk, H. "The Order of Encryption and Authentication for Protecting Communications." CRYPTO 2001. DOI.
22. Vaudenay, S. "Security Flaws Induced by CBC Padding." EUROCRYPT 2002. DOI. EPFL. The padding-oracle attack implemented above.
23. Rogaway, P. and Shrimpton, T. "A Provable-Security Treatment of the Key-Wrap Problem." EUROCRYPT 2006. DOI. SIV and misuse-resistant AEAD. See also Rogaway's nonce-based encryption work (2002-2004).
24. Bernstein, D. J. "Curve25519: New Diffie-Hellman Speed Records." PKC 2006. DOI. See also ChaCha20 (2008) and Poly1305 (2005), standardized together in RFC 8439.
25. Regev, O. "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography." STOC 2005; JACM 56(6), 2009. DOI.
26. Gentry, C. "Fully Homomorphic Encryption Using Ideal Lattices." STOC 2009. DOI. IBM Research. See also Brakerski (Weizmann), Gentry, and Vaikuntanathan (MIT) for BGV.
27. Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. "Private Information Retrieval." FOCS 1995. DOI. Technion, Weizmann, and MIT.
28. Shor, P. W. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." FOCS 1994; SIAM J. Computing 26(5), 1997. DOI.
29. Grover, L. K. "A Fast Quantum Mechanical Algorithm for Database Search." STOC 1996. DOI.
30. Ben-Sasson, E., Bentov, I., Horesh, Y., and Riabzev, M. "Scalable, Transparent, and Post-Quantum Secure Computational Integrity." IACR ePrint 2018/046. ePrint. STARKs, from the Technion.
31. Rescorla, E. "The Transport Layer Security (TLS) Protocol Version 1.3." RFC 8446, 2018. RFC.
32. Laurie, B., Langley, A., and Kasper, E. "Certificate Transparency." RFC 6962, 2013. RFC.
33. NIST. FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), and FIPS 205 (SLH-DSA), August 2024. FIPS 203, FIPS 204, FIPS 205.

Key takeaway