Breakthroughs in Cryptography#

blockchainkit.crypto hub · History · Examples · API reference

“We stand today on the brink of a revolution in cryptography.” – Whitfield Diffie and Martin Hellman, New Directions in Cryptography, 1976

Cryptography is the study of keeping and checking secrets when other people can read, copy or change your messages. A blockchain is a shared record, like a list of blocks of transactions. Many computers keep copies of it in step, without trusting each other. Every later idea in a blockchain rests on three things that cryptography provides:

a way to agree on a secret in public;
a way to prove who authorized a message;
a way to commit to data without revealing it: to fix a value now, keep it hidden, and be unable to change it later.

This chronology traces the ideas behind blockchainkit.crypto, from the one-time pad to Schnorr multi-signatures. Each entry follows the same order. It states the problem. It gives the idea in plain words. It lists the steps of the mechanism. Then it says why the mechanism works and where it stops working. The parameters are deliberately small, so you can print and inspect every value. Exact conventions and model boundaries lists exactly where the package departs from deployed systems.

The page uses a few conventions throughout:

Alice and Bob are the honest parties. An attacker is anyone trying to read, forge or change what they send.
$a \bmod p$ is a % p. $g^x \bmod p$ is pow(g, x, p), which takes only about $\log_2 x$ multiplications because it squares repeatedly. $a \equiv b \pmod p$ means a % p == b % p.
$a^{-1} \bmod p$ is the inverse of $a$: the number that undoes multiplication by $a$, so that $a \cdot a^{-1} \equiv 1$. In Python it is pow(a, -1, p).
$\oplus$ is bitwise XOR (^ in Python), $\|$ joins two byte strings (a + b), and $|r|$ is the length len(r).

Cryptographers measure strength in bits. A system has b-bit security if the best known attack needs about $2^b$ basic operations. Each extra bit doubles the attacker’s work.

$2^{64} \approx 1.8 \times 10^{19}$ operations is within reach: 100,000 computers doing $10^9$ operations a second finish in about two days.
$2^{128} \approx 3.4 \times 10^{38}$ operations is not. One such computer would need about $10^{22}$ years. The whole Bitcoin mining network, the largest computation on Earth at around $10^{21}$ hashes a second in the mid-2020s, would need about $10^{10}$ years. That is close to the age of the universe.

1917-1949 – The One-Time Pad and Perfect Secrecy #

Alice wants to send Bob a message that nobody else can read. This should hold even against an attacker with unlimited computing power.

A cipher is a method for scrambling (encrypting) and unscrambling (decrypting) a message with a key, a secret value. The scrambled message is the ciphertext. Gilbert Vernam built a teleprinter in 1917 that combined each character of a message with a character of a key tape. Joseph Mauborgne added the rule that the tape must be random and never reused. In modern terms the key is a random bit string as long as the message, and the two are XORed.

Alice and Bob meet in advance and share a random key $k$.
Alice computes the ciphertext $c = m \oplus k$ (bytes(a ^ b for a, b in zip(m, k))) and sends $c$.
Bob computes $c \oplus k$. XORing with the same key twice cancels out, because $k \oplus k = 0$, so he gets $m$ back.
Both destroy the part of the key they used.

Claude Shannon’s 1949 theory of secrecy systems proved why this is unbreakable. Fix a ciphertext $c$. For every candidate message $m$ of the same length there is exactly one key, $k = c \oplus m$, that produces it. A uniformly random key is one where every bit string of that length is equally likely. Such a key makes all of those candidate keys equally likely. The ciphertext therefore gives no reason to prefer one message over another:

\[c = m \oplus k, \qquad m = c \oplus k, \qquad \Pr[M = m \mid C = c] = \Pr[M = m].\]

The first two equations are encryption and decryption. The third says that seeing $c$ does not change the probability of any message $m$. This is called perfect secrecy.

The pad is secure only if both rules hold:

The key is random. Otherwise some messages become more likely than others.
The key is never reused. Reusing it gives $c_1 \oplus c_2 = m_1 \oplus m_2$, in which the key has cancelled out. The attacker then holds the XOR of two messages, which guesses about the language can unpick. Soviet reuse of pads let the US Venona project read thousands of messages.

Shannon also showed that every perfectly secret cipher needs at least as much key as message. That makes the pad impractical for exactly the reason it works. The two parties must already share a secret as long as everything they will ever say. Getting such a secret to both parties is the key-distribution problem. Public-key cryptography, where part of each key can be published openly, would solve it.

Implementation: blockchainkit.crypto.systems.one_time_pad.one_time_pad() refuses a key of the wrong length; blockchainkit.crypto.systems.one_time_pad.xor_bytes() is the underlying operation.

References: G. S. Vernam, Cipher Printing Telegraph Systems for Secret Wire and Radio Telegraphic Communications, Journal of the American Institute of Electrical Engineers 45, 109–115 (1926). C. E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal 28(4), 656–715 (1949). DOI.

The one-time pad and perfect secrecy (Vernam 1917, Shannon 1949)

1971 – Baby-Step Giant-Step: Square-Root Discrete Logs #

Most public-key systems on this page are secure only because one particular calculation is hard to reverse. So the first question is how hard it really is.

Take a prime $p$ and a number $g$. The powers $g, g^2, g^3, \dots \bmod p$ eventually return to 1 and then repeat in a loop. The values in that loop form a cyclic group. $g$ is its generator, and the length $n$ of the loop is its order. (In general a group is any set with one operation that can be combined and undone, like multiplication modulo $p$. The 1985 entry builds another one from elliptic curves.) Computing $h = g^x$ from $x$ is fast with pow. The reverse, finding $x$ from $h$, is the discrete logarithm of $h$. It has no obvious shortcut. Brute force, which means trying every possibility, takes up to $n$ steps.

Daniel Shanks, while working on a problem in number theory, traded memory for time to need only about $\sqrt n$ steps. The trick is the same one that makes a Python dict fast: store values once, then look them up in $O(1)$.

Set $m = \lceil\sqrt n\,\rceil$. Every exponent below $n$ can be written as $x = im + j$ with $0 \le i, j < m$. This is like writing a number as tens and units: i, j = divmod(x, m).
Baby steps. Compute $g^0, g^1, \dots, g^{m-1}$ and store them in a table, table[pow(g, j, p)] = j.
Giant steps. Compute $h, hg^{-m}, hg^{-2m}, \dots$. Each step multiplies by $g^{-m}$, the inverse of $g^m$.
Stop when the giant step $h\,(g^{-m})^{i}$ is in the table, at some $j$. Then $x = im + j$.

Step 4 works because multiplying $g^{im + j} = h$ by $g^{-im}$ separates the two unknowns:

\[g^{x} = h \iff g^{j} = h\,(g^{-m})^{i}, \qquad \text{cost} \approx 2\sqrt{n}.\]

In words: $x$ is found when some giant step lands on some baby step. There are only $m$ of each, so the cost is about $2\sqrt n$ multiplications, plus a table of $m$ entries.

For $n \approx 10^{12}$ this is about two million steps instead of a trillion.
Generic algorithms cannot do fundamentally better. A generic algorithm uses only the group operations (multiply, invert, compare) and never looks at how the elements are written down. Shoup proved in 1997 that any such algorithm needs about $\sqrt n$ steps.
For well-chosen elliptic curves no attack better than these generic ones is known. That is why a group of about $2^{256}$ elements gives about 128-bit security: $\sqrt{2^{256}} = 2^{128}$.

Implementation: blockchainkit.crypto.systems.discrete_log.baby_step_giant_step() returns the exponent and the number of table multiplications.

References: D. Shanks, Class Number, a Theory of Factorization, and Genera, Proceedings of Symposia in Pure Mathematics 20, American Mathematical Society, 415–440 (1971).

Baby-step giant-step: square-root discrete logs (Shanks 1971)

1974-1978 – Merkle’s Puzzles: Key Agreement in Public #

Can two people agree on a secret when every message between them is public? That would solve the key-distribution problem left by the one-time pad.

As an undergraduate in 1974, Ralph Merkle proposed the first scheme that does this. The idea: Alice hides many secrets in locked boxes that are each slow, but possible, to open. Bob opens one box. An eavesdropper, who reads everything sent but changes nothing, does not know which box Bob opened. So they must open about half of them.

Alice makes $N$ puzzles. Each one seals a random identifier and a random session key (a fresh key for one conversation). The seal is a deliberately weak key, so one puzzle can be opened by brute force in about $N$ trials.
Alice keeps a private table, a dict from identifiers to session keys. She sends all $N$ puzzles to Bob in public.
Bob opens one puzzle chosen at random, which costs about $N$ trials.
Bob announces only its identifier.
Alice looks the identifier up in her table. Both now hold the same session key.

The eavesdropper hears the identifier but does not know which puzzle contains it. So they must open puzzles until they find it, about $N/2$ of them on average:

\[W_{\text{honest}} = O(N), \qquad W_{\text{attacker}} \approx \tfrac{N}{2} \cdot N = O(N^2).\]

In words: the honest work grows like $N$ and the attacker’s work like $N^2$.

The idea was hard to publish, and the paper appeared in 1978, after Diffie and Hellman’s. Its limits and legacy:

A quadratic gap is not practical security. The attacker’s work is only about $N/2$ times Bob’s. An attacker with a thousand times Bob’s computing power can still keep up with a thousand-fold larger $N$.
Diffie-Hellman replaced it with a gap that grows exponentially in the key size: under the generic attacks, doubling the key length squares the attacker’s work.
The puzzles showed that public key agreement was possible at all.
Barak and Mahmoody later proved (2009) that the quadratic gap is the best any scheme built only from a random function can achieve. A random function is one whose every output is an independent random value, like a dict filled by coin flips.

Implementation: blockchainkit.crypto.systems.puzzles.merkle_puzzles() creates the puzzles and Alice’s table; blockchainkit.crypto.systems.puzzles.solve_puzzle() opens one by brute force.

References: R. C. Merkle, Secure Communications over Insecure Channels, Communications of the ACM 21(4), 294–299 (1978). DOI.

Merkle’s puzzles: the first public-key exchange (1974-1978)

Merkle's puzzles: the first public-key exchange (1974-1978)

1976 – Diffie-Hellman: Agreeing on a Secret over a Public Channel #

Sharing an encryption key used to require a secret channel in advance. Diffie and Hellman asked whether two people could reach the same secret by exchanging only public values.

Their idea uses a one-way street: pow is fast forwards, but the discrete log (1971 entry) is slow backwards. Each party keeps a private exponent and publishes only a power of $g$.

Everyone agrees on public numbers: a prime $p$ and a generator $g$.
Alice picks a private $a$ and sends $A = g^a \bmod p$.
Bob picks a private $b$ and sends $B = g^b \bmod p$.
Alice computes pow(B, a, p). Bob computes pow(A, b, p).
Because exponents multiply in either order, both arrive at the same element:

\[A=g^a\bmod p,\qquad B=g^b\bmod p,\qquad B^a=(g^b)^a=g^{ab}=(g^a)^b=A^b \pmod p.\]

In words: Alice raises Bob’s public value to her secret, Bob raises Alice’s to his, and both get $g^{ab}$.

Why it is secure, and what it does not do:

An observer sees $g, p, A, B$. The only known general way to compute $g^{ab}$ from them is to recover $a$ or $b$. That is a discrete logarithm, and the 1971 entry shows its generic cost is about $\sqrt n$.
The honest parties do one exponentiation each, about $\log_2 n$ multiplications. So the gap between them and the attacker grows exponentially with the key size. For $n \approx 2^{256}$ it is a few hundred multiplications against $2^{128}$.
The exchange does not say who is at the other end. This allows a man-in-the-middle attack:
1. The attacker intercepts $A$ and sends Bob their own public value instead.
2. The attacker intercepts $B$ and sends Alice their own public value instead.
3. The attacker now shares one secret with each party, and can decrypt, read and re-encrypt everything relayed between them.
Deployed protocols therefore authenticate the exchange: they sign the public values, so each side can check who sent them. They also pass the shared element through a key derivation function. This feeds it to a hash function, which is like Python’s hash() but with a long output, built so that nobody can find two inputs with the same output or work back from an output to an input. The result is uniformly random key bytes.

In practice $g$ is chosen so that its order is a large prime. Its loop of powers is then a prime-order subgroup of all the numbers modulo $p$; the 1978 Pohlig-Hellman entry explains why. X25519 is Diffie-Hellman on an elliptic curve (1985 entry).

Implementation: blockchainkit.crypto.systems.asymmetric.DHGroup validates the prime-order subgroup and peer elements. It runs in a 62-bit teaching group with no authentication; deployments use 2048-bit groups or X25519.

References: W. Diffie and M. E. Hellman, New Directions in Cryptography, IEEE Transactions on Information Theory 22(6), 644–654 (1976). DOI; author’s copy.

Diffie-Hellman: agreeing on a secret over a public channel (1976)

1978 – RSA and the Public Trapdoor #

Diffie-Hellman agrees on a key. It does not let anyone encrypt to a published key, so that only the key’s owner can decrypt. Nor does it give signatures. A digital signature is a value that only the key’s owner can compute, but that anyone can check with the published key. It is like a handwritten signature that cannot be copied onto another document.

Rivest, Shamir and Adleman gave the first concrete system with a trapdoor: a public operation that anyone can apply, and a private one that reverses it. It works like a padlock that anyone can snap shut but only the keyholder can open.

Bob chooses distinct primes $p, q$ and computes $n = pq$.
Bob picks an exponent $e$ and computes the inverse exponent $d$: d = pow(e, -1, (p - 1) * (q - 1)).
Bob publishes $n$ and $e$, his public key, and keeps $d$, his private key.
To send a number $m < n$, Alice computes c = pow(m, e, n).
Bob decrypts with m = pow(c, d, n).
To sign $m$, Bob instead computes s = pow(m, d, n). Anyone can check that pow(s, e, n) == m.

\[ed\equiv1\pmod{(p-1)(q-1)},\qquad c=m^e\bmod n,\qquad m=c^d\bmod n.\]

In words: raising to $e$ and then to $d$ brings back the original number modulo $n$.

Why decryption works:

$ed = 1 + k(p-1)(q-1)$ for some integer $k$, by the choice of $d$.
Euler’s theorem says $m^{(p-1)(q-1)} \equiv 1 \pmod n$ for every $m$ that shares no factor with $n$. (The final result below also holds for the rare $m$ that do.)
So $c^d = m^{ed} = m \cdot (m^{(p-1)(q-1)})^k \equiv m \pmod n$.

Why it is secure, as far as anyone knows:

Finding $d$ requires $(p-1)(q-1)$, which requires the factors of $n$. Computing $d$ from $e$ is in fact as hard as factoring.
Security therefore rests on factoring being hard, though no proof shows that decrypting without $d$ is equally hard.
Real systems add padding: random bytes and a fixed structure mixed into the message before exponentiating. Without it, RSA has the two weaknesses listed below.

Implementation: blockchainkit.crypto.systems.asymmetric.rsa_keypair() exposes the arithmetic, with the familiar $61\times53$ example. This is textbook RSA: tiny primes and no padding, so it is deterministic (equal messages give equal ciphertexts) and malleable (multiplying ciphertexts multiplies plaintexts). Real RSA uses moduli of 2048 bits or more with OAEP (encryption) or PSS (signatures) padding.

References: R. L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM 21(2), 120–126 (1978). DOI.

RSA: a public trapdoor (Rivest, Shamir and Adleman 1978)

1978 – Pohlig-Hellman: Why the Group Order Needs a Large Prime Factor #

The $\sqrt n$ cost of the 1971 entry assumes the group cannot be taken apart. Pohlig and Hellman showed that if the order $n$ has small prime factors, the discrete log splits into one small problem per factor.

The idea is like rebuilding a number from its remainders. If you know x % 4 and x % 9, you know x % 36. The Chinese Remainder Theorem says this always works when the moduli share no factor. So it is enough to find $x$ modulo each prime power in $n$.

Factor the order as $n = \prod p_i^{e_i}$, for example $36 = 2^2 \cdot 3^2$.
For each prime power, raise $g$ and $h$ to the power $n/p_i^{e_i}$. This lands them in a smaller loop, a subgroup of order $p_i^{e_i}$: since $g^n = 1$, the new $g_i$ returns to 1 after $p_i^{e_i}$ steps. There the same equation reveals $x$ modulo $p_i^{e_i}$.
Solve each of these one base-$p_i$ digit at a time. Each digit is a discrete log in a subgroup of order only $p_i$, found with baby-step giant-step.
Combine the remainders with the Chinese Remainder Theorem into $x \bmod n$.

\[g_i = g^{n/p_i^{e_i}},\quad h_i = h^{n/p_i^{e_i}} \;\Longrightarrow\; h_i = g_i^{\,x \bmod p_i^{e_i}}, \qquad \text{cost} \approx \sum_i e_i \sqrt{p_i}.\]

In words: after the change of base, only $x \bmod p_i^{e_i}$ matters, and the total cost adds up $\sqrt{p_i}$ for each digit of each prime.

Consequences:

The cost is governed by the largest prime factor of $n$, not by $n$ itself. A group of order $n = 2^{64}$ falls in about a hundred tiny steps.
That is why Diffie-Hellman and Schnorr run in a subgroup of large prime order.
It is also why blockchainkit.crypto.systems.asymmetric.TEACHING_GROUP uses a safe prime $p = 2q + 1$ with $q$ prime: the subgroup of order $q$ has no smaller pieces to split off.

Implementation: blockchainkit.crypto.systems.discrete_log.pohlig_hellman() factors the order by trial division, solves each prime-power part with baby-step giant-step, and combines the answers.

References: S. Pohlig and M. Hellman, An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance, IEEE Transactions on Information Theory 24(1), 106–110 (1978). DOI.

Pohlig-Hellman: why the group order must have a large prime factor (1978)

1979 – Lamport’s One-Time Signatures from a Hash #

RSA signatures rest on number theory. Leslie Lamport showed that a one-way function alone suffices: a function that is easy to compute but practically impossible to reverse. A cryptographic hash $H$, such as SHA-256, is used as one.

The idea: publish the hashes of many secret strings. To sign, reveal the secrets that the message picks out. Anyone can hash them and compare.

Key generation. Pick 256 pairs of random strings $x_{i,0}, x_{i,1}$. They are the private key. Their hashes are the public key.
Signing. Compute the 256-bit hash $H(m)$, with bits $b_1, \dots, b_{256}$. For each bit $b_i$, reveal $x_{i,b_i}$: one string of each pair, chosen by the bit.
Verifying. For each $i$, check that $H(x_{i,b_i}) = y_{i,b_i}$.

\[\text{public key } y_{i,b} = H(x_{i,b}), \qquad \sigma = (x_{1,b_1}, \dots, x_{256,b_{256}}).\]

In words: the public key is the hashes of all 512 secrets, and a signature $\sigma$ is the 256 secrets that the message’s hash bits select.

Why it works, and its limits:

A forger needs, for every position, the preimage selected by the new message’s hash bit. A preimage of $y$ is an input that hashes to $y$. Producing an unrevealed one means inverting $H$.
Each signature, however, reveals half of the private key. After $k$ signatures on random messages, a given preimage has been revealed with probability $1 - 2^{-k}$. A fresh random message can then be forged with probability about $(1 - 2^{-k})^{256}$, which reaches 78% at $k = 10$.
An attacker who can try many messages does far better, so a key must sign only once.
Merkle’s trees, invented the same year, authenticate many one-time keys under one root. They hash the public keys in pairs, then hash those results in pairs, and so on up to a single root hash, which is published.
Because they rely only on hashing, these signatures resist quantum computers. A large quantum computer could quickly break RSA, Diffie-Hellman and elliptic curves, but it speeds up attacks on hashes only modestly. The standardized SPHINCS+ (SLH-DSA) descends from Lamport’s scheme.
Winternitz chains shrink the keys by hashing one secret many times over, so that one chain signs several bits at once.

Implementation: blockchainkit.crypto.systems.lamport.lamport_keypair(), blockchainkit.crypto.systems.lamport.lamport_sign(), and blockchainkit.crypto.systems.lamport.lamport_verify() use full Lamport pairs. Deployed hash-based signatures (XMSS, SPHINCS+) shrink them with Winternitz chains and many-time trees.

References: L. Lamport, Constructing Digital Signatures from a One Way Function, Technical Report CSL-98, SRI International (1979).

Lamport one-time signatures: signing with only a hash (1979)

1979 – Yuval’s Birthday Attack #

Finding two people with the same birthday in a room is much easier than finding someone with your birthday. Every pair of people is a chance for a match, and the number of pairs grows like the square of the room size. Gideon Yuval turned this into an attack on signatures. Signatures sign the hash of a message rather than the message itself. So two messages with the same hash, a collision, share every signature.

The attacker writes many harmless variants of a contract (extra spaces, swapped synonyms) and many harmful variants.
The attacker hashes them all, storing the harmless hashes in a dict.
The attacker stops when a harmful variant’s hash is already in the dict.
The victim signs the harmless variant.
The signature also fits the harmful one.

Among $q$ random $n$-bit values there are about $q^2/2$ pairs. Each pair is equal with probability $2^{-n}$. So a repeat appears with probability about $q^2/2^{n+1}$ while that is small:

\[\Pr[\text{collision}] \approx 1 - e^{-q^2 / 2^{n+1}}, \qquad E[q] \approx \sqrt{\tfrac{\pi}{2}\, 2^{n}}.\]

In words: the chance of a collision approaches 1 once $q$ passes about $2^{n/2}$, and $E[q]$ is the expected number of hashes before the first one.

Consequences:

A collision is expected after about $2^{n/2}$ hashes. So an $n$-bit hash gives only $n/2$ bits of collision resistance (the difficulty of finding any two inputs with the same hash).
A 64-bit hash collides after about four billion tries, minutes on a laptop.
That is why SHA-256’s 256-bit output is chosen for 128-bit collision security.

Implementation: blockchainkit.crypto.systems.hashing.find_collision() searches truncated SHA-256; blockchainkit.crypto.systems.hashing.truncated_hash() does the truncation.

References: G. Yuval, How to Swindle Rabin, Cryptologia 3(3), 187–191 (1979). DOI.

The birthday attack on hash functions (Yuval 1979)

1981 – Blum’s Coin Flipping by Telephone: Commitments #

Manuel Blum asked how two people who do not trust each other can flip a fair coin over the telephone. His answer uses a sealed envelope.

Alice seals her call, heads or tails, in an envelope and sends it.
Bob announces a coin flip.
Alice opens the envelope.
Alice wins if her call matches the flip.

Each property of the envelope stops one cheat:

It must be binding, so Alice cannot open it to the other call after hearing the flip.
It must be hiding, so Bob cannot read the call and announce the opposite.

Such an envelope is a commitment. It can be built from a hash and a salt $r$, a random byte string mixed into the input:

\[C = H(\text{domain} \,\|\, |r| \,\|\, r \,\|\, m), \qquad \text{open}: (m, r) \ \text{with}\ H(\dots) = C.\]

In words: the commitment $C$ is the hash of a label, the salt’s length, the salt and the message. To open it, Alice reveals $m$ and $r$, and Bob recomputes the hash.

Why each part is there:

Opening to a different value means finding a second input with the same hash, so binding rests on collision resistance.
Without the salt, hiding would fail. Bob could simply hash “heads” and “tails” and compare. A long random salt makes such guessing hopeless.
Encoding the salt’s length $|r|$ fixes where the salt ends and the message begins, so one input cannot be split two ways.
The domain label separates uses: a hash made for a commitment can never be mistaken for a hash made for something else. This is domain separation.
Checking should take constant time: the same time whether the first differing byte is early or late (like hmac.compare_digest). Otherwise timing leaks how much of a guess was right.

Commitments became a basic building block. A Schnorr prover commits to $R$ before seeing a challenge (1985 entry), and a block header commits to its transactions.

Implementation: blockchainkit.crypto.systems.commitments.commit() adds domain separation and explicit salt framing; blockchainkit.crypto.systems.commitments.verify_commitment() compares in constant time.

References: M. Blum, Coin Flipping by Telephone: A Protocol for Solving Impossible Problems, CRYPTO ‘81, 11–15 (1981); reprinted in ACM SIGACT News 15(1), 23–27 (1983). DOI.

Coin flipping by telephone: hash commitments (Blum 1981)

1985 – Elliptic Curves as a Cryptographic Group #

Diffie-Hellman needs only a group in which discrete logs are hard. It does not need the integers modulo $p$ specifically. Victor Miller proposed elliptic curves for this at CRYPTO ‘85, and Neal Koblitz independently developed elliptic-curve cryptosystems.

An elliptic curve here is the set of integer pairs $(x, y)$ that solve the equation below modulo $p$, plus one extra “point at infinity”. It is a finite set of curve points with a special addition rule, not a smooth curve over the real numbers. The rule comes from geometry over the reals: draw the line through two points, find where it meets the curve a third time, and reflect that point. The same formulas work modulo $p$. The point at infinity acts as zero. Because the operation is written as addition, $xG$ plays the role that pow(g, x, p) played before: the base point $G$ added to itself $x$ times.

Everyone agrees on a curve and a base point $G$.
A private key is an integer $x$.
The public key is $Q = xG$, computed by double-and-add, the addition version of pow’s repeated squaring:
1. Start with the point at infinity.
2. For each bit of $x$, from the top: double the running point, and if the bit is 1, add $G$.

\[y^2=x^3+ax+b\pmod p,\qquad Q=xG.\]

In words: points satisfy the curve equation, and a public key is the base point multiplied by the private integer.

Why curves allow short keys:

Double-and-add computes $Q$ in about $2\log_2 x$ additions. Recovering $x$ from $G, Q$ is the elliptic-curve discrete-log problem.
The integers modulo $p$ have extra structure, such as factorization into primes. Index-calculus algorithms exploit it to solve discrete logs (and factor RSA moduli) in subexponential time: much faster than $2^{c \cdot \text{bits}}$ for any fixed $c$, though still slower than any polynomial. So those keys must be thousands of bits long.
No such attack is known for well-chosen curves. That leaves only the $\sqrt n$ generic attacks, so a 256-bit curve key matches a roughly 3072-bit RSA key.
“Well-chosen” matters. A curve whose order has only small prime factors falls to Pohlig-Hellman, and some special families reduce to easier problems.
Production code must also run in constant time (the same time for every key), because timing differences can reveal the private key.

Implementation: blockchainkit.crypto.systems.curves.Curve, blockchainkit.crypto.systems.curves.add(), and blockchainkit.crypto.systems.curves.multiply() implement the group law, including infinity, inverse points, and doubling. TOY_CURVE has 19 points; SECP256K1 is Bitcoin’s curve. The arithmetic is variable-time Python; production libraries such as libsecp256k1 use constant-time code, because timing can leak private scalars.

References: V. S. Miller, Use of Elliptic Curves in Cryptography, CRYPTO ‘85, LNCS 218, 417–426 (proceedings 1986). DOI. N. Koblitz, Elliptic Curve Cryptosystems, Mathematics of Computation 48(177), 203–209 (1987). DOI.

Elliptic-curve cryptography: a finite group you can draw (Miller and Koblitz 1985)

1985 – Zero Knowledge: Proofs That Reveal Nothing #

Can you convince someone that you know a secret without revealing anything about it? Goldwasser, Micali and Rackoff formalized this striking possibility. An interaction between a prover and a verifier can convince the verifier that a statement is true while revealing nothing else.

The test for “revealing nothing” uses a simulator: a program that does not know the secret. A transcript is the record of every message exchanged. A proof is zero-knowledge if the simulator can produce transcripts indistinguishable from real ones, meaning no efficient test can tell them apart. The verifier could have generated such transcripts alone. So the real ones cannot have taught them anything.

Schnorr’s later identification protocol shows the idea concretely. The prover has a secret $x$ and public key $Q = xG$. A nonce is a random number used once.

The prover picks a random nonce $k$ and sends the commitment $R = kG$.
The verifier sends a random challenge $c$.
The prover answers $s = k + cx$.
The verifier checks $sG = R + cQ$.

The simulator fakes a transcript by working backwards:

Pick $c$ and $s$ at random.
Solve the check for a matching $R = sG - cQ$.
Output $(R, c, s)$, which passes the check without $x$.

\[R = kG,\quad c \xleftarrow{\$} \mathbb{Z}_n,\quad s = k + cx; \qquad \text{simulator: } R = sG - cQ.\]

In words: $c \xleftarrow{\$} \mathbb{Z}_n$ means $c$ is drawn uniformly from $0, \dots, n-1$. A real prover fixes $R$ first; the simulator fixes $c$ first.

Why the real proof still convinces:

A prover who could answer two different challenges $c_1 \ne c_2$ for the same $R$ would know $x = (s_1 - s_2)/(c_1 - c_2)$.
Without $x$, a cheating prover succeeds only by guessing $c$ before committing, with probability $1/n$.
So a real prover must commit to $R$ before seeing an unpredictable $c$. That order is the only thing separating a proof from a simulation.
Hence a recorded transcript proves nothing to a third party.
The simulation argument assumes the verifier picks $c$ at random, as an honest one does.

Implementation: blockchainkit.crypto.systems.signatures.verify_transcript() checks the group equation; blockchainkit.crypto.systems.signatures.simulate_transcript() is the simulator.

References: S. Goldwasser, S. Micali, and C. Rackoff, The Knowledge Complexity of Interactive Proof-Systems, STOC ‘85, 291–304 (1985). DOI.

Zero-knowledge proofs: convincing without revealing (Goldwasser, Micali and Rackoff 1985)

1986 – The Fiat-Shamir Heuristic: From Interaction to Signatures #

An interactive proof convinces only the verifier who took part. Fiat and Shamir replaced the verifier’s random challenge with a hash of the transcript so far. The proof no longer needs a live conversation. Putting the message into the hash turns it into a signature.

The signer picks a nonce $k$ and computes $R = kG$.
The signer computes the challenge itself, $c = H(R, Q, m)$.
The signer computes $s = k + cx$. The signature is $(R, s)$.
A verifier recomputes $c$ from $R, Q, m$ and checks $sG = R + cQ$.

\[c = H(R, Q, m), \qquad \sigma = (R,\ s = k + cx).\]

In words: the hash plays the honest verifier, and the signature $\sigma$ is the prover’s commitment and answer.

Why it works, and what can go wrong:

The simulator’s trick was to pick $c$ first and then solve for $R$. Now $c$ is computed from $R$.
If $H$ behaves like a random function, any change to $R$ produces an unpredictable new $c$. The trick no longer works, and a valid $(R, s)$ again shows knowledge of $x$.
Pointcheval and Stern later proved such signatures secure in this random-oracle model: the analysis pretends $H$ is a truly random function that everyone can query.
Everything the verifier would have seen must go into the hash. Leaving out $Q$, for instance, lets an attacker choose the public key after the challenge.
Schnorr signatures, EdDSA, and most zero-knowledge proof systems used by blockchains (SNARKs, STARKs: short proofs that a computation was done correctly) rely on this transform. Such omissions have broken real implementations (the 2022 “Frozen Heart” disclosures).

Implementation: blockchainkit.crypto.systems.signatures.challenge() hashes the curve domain, public key, commitment, and message.

References: A. Fiat and A. Shamir, How To Prove Yourself: Practical Solutions to Identification and Signature Problems, CRYPTO ‘86, LNCS 263, 186–194 (proceedings 1987). DOI.

The Fiat-Shamir heuristic: from interaction to signatures (1986)

1989 – The Merkle-Damgård Construction and Length Extension #

A hash function must accept messages of any length. It is much easier to design and analyze a compression function $f$. This maps a fixed-size state and one fixed-size block of input to a new state. Ralph Merkle and Ivan Damgård independently showed at CRYPTO ‘89 how to chain one into a full hash. The idea is a loop: h = f(h, block) for each block.

Pad the message so that it ends with its own length and fills a whole number of blocks.
Split it into blocks $m_1, \dots, m_\ell$.
Start the state at a fixed constant, $h_0 = IV$ (the initial value).
Feed each block through $f$, updating the state.
The final state is the digest, the hash output.

\[h_0 = IV, \qquad h_i = f(h_{i-1}, m_i), \qquad H(m) = h_\ell.\]

In words: the digest is the state after the last block.

Why collision resistance carries over:

If $f$ is collision-resistant, so is $H$.
Trace two colliding messages backward from their equal digests. At the last step where the inputs to $f$ differ, the outputs are still equal. That is a collision in $f$.
The encoded length guarantees that such a step exists.
MD5, SHA-1 and SHA-256 all follow this design.

Its side effect is length extension. Since $H(m)$ is the chaining state, anyone can resume the chain from it. They can compute $H(m \,\|\, \text{pad} \,\|\, s)$ knowing only $H(m)$ and $|m|$. This breaks a naive MAC (message authentication code): a short tag, computed from a message and a shared key, that proves the message came from a key holder unchanged. A “MAC” computed as $H(k \,\|\, m)$ is therefore forgeable:

The attacker sees one valid tag $t = H(k \,\|\, m)$ and knows the length of $k \,\|\, m$.
The attacker sets the state to $t$ and works out the padding that followed $k \,\|\, m$.
The attacker continues the loop over any extra blocks $s$.
The result is a valid tag for the extended message $m \,\|\, \text{pad} \,\|\, s$, made without knowing $k$.

Implementation: blockchainkit.crypto.systems.merkle_damgard.merkle_damgard_sha256() reimplements SHA-256 block by block (checked against the standard library); blockchainkit.crypto.systems.merkle_damgard.length_extension() performs the attack.

References: R. C. Merkle, One Way Hash Functions and DES, CRYPTO ‘89, LNCS 435, 428–446 (1990). DOI. I. B. Damgård, A Design Principle for Hash Functions, CRYPTO ‘89, LNCS 435, 416–427 (1990). DOI.

The Merkle-Damgard construction and length extension (1989)

1989-1991 – Schnorr Identification and Compact Signatures #

Claus Schnorr made discrete-log proofs short and fast. This is the protocol already used in the 1985 entry. It is written in additive notation, where the group operation is + and repeated addition $xG$ replaces $g^x$, as on elliptic curves.

The prover, with secret $x$ and public key $Q = xG$, picks a fresh nonce $k$ and commits with $R = kG$.
The prover receives a challenge $c$.
The prover answers $s = k + cx \bmod n$.
The verifier checks $sG = R + cQ$. The check holds because $sG = (k + cx)G = kG + c(xG)$.

\[R=kG,\qquad s=k+cx\pmod n,\qquad sG=R+cQ.\]

In words: the answer $s$ mixes the nonce and the secret, and the check confirms the mix using only public points.

Properties:

The Fiat-Shamir transform with $c = H(R, Q, m)$ turns this into a signature $(R, s)$: one group element and one scalar (an integer modulo $n$).
The nonce must be fresh. Two signatures with the same $k$ give two linear equations in $k$ and $x$ (the 2010-2013 entry).
The equation is also linear in the keys. If two signers use the same $c$, their $R$ and $s$ values add to a valid signature for $Q_1 + Q_2$. This later enabled multi-signatures (the 2018 entry).
A patent kept Schnorr signatures out of standards until it expired in 2008. Bitcoin adopted them in 2021 as BIP-340 (Bitcoin Improvement Proposal 340). BIP-340 stores only the x-coordinate of a public key and hashes with a tagged hash, a hash prefixed by a label.

Implementation: blockchainkit.crypto.systems.signatures.sign(), blockchainkit.crypto.systems.signatures.verify(), and blockchainkit.crypto.systems.signatures.recover_reused_nonce_key() use a domain-separated scheme over a prime-order elliptic-curve group, an additive adaptation of the original multiplicative groups. The challenge encoding differs from BIP-340 (no x-only keys or tagged hash), so these signatures do not verify in Bitcoin.

References: C. P. Schnorr, Efficient Signature Generation by Smart Cards, Journal of Cryptology 4, 161–174 (1991); following the CRYPTO ‘89 work. DOI.

Schnorr signatures: short, fast, and linear (1989-1991)

1991 – Pedersen Commitments: Perfectly Hiding and Additive #

A hash commitment hides its contents only from an attacker who cannot invert the hash. Also, nothing useful can be computed on sealed values. Torben Pedersen introduced a commitment with two better properties:

it hides its contents even from an attacker with unlimited computing power;
multiplying sealed commitments adds the amounts inside them.

It uses two generators $g, h$ of a group of prime order $q$.

Setup: $h$ is derived by hashing, so that nobody knows the exponent $w$ with $h = g^w$.
Commit: to commit to a value $v$, pick a random blinding $r$ and publish $C = g^v h^r \bmod p$.
Open: reveal $v$ and $r$. Anyone recomputes $C$.

\[C(v, r) = g^{v} h^{r} \bmod p, \qquad C(a, r)\,C(b, s) = C(a + b,\ r + s).\]

In words: a commitment is $g$ to the value times $h$ to the blinding. Multiplying two commitments gives a commitment to the sum of the values, because exponents add.

Why it hides perfectly, and binds only computationally:

Write $h = g^{w}$. Then $C = g^{v + wr}$.
For any other value $v'$, the blinding $r' = r + (v - v')/w \bmod q$ gives the same $C$. Every value is equally consistent with $C$, so hiding is perfect.
Conversely, anyone who opens one commitment to two values $(v, r) \ne (v', r')$ has $v + wr = v' + wr'$. They can solve for $w = \log_g h$.
So binding is only as strong as that discrete log. That is why $h$ is derived by hashing, so that nobody knows $w$.
The additive property lets anyone check that hidden inputs equal hidden outputs. This is the basis of confidential transactions, whose amounts stay hidden, in Monero and Mimblewimble.

Implementation: blockchainkit.crypto.systems.commitments.pedersen_commit() and blockchainkit.crypto.systems.commitments.pedersen_generators() work in the teaching group, so binding holds only while its small discrete logarithm stays unknown; production uses 256-bit elliptic-curve groups.

References: T. P. Pedersen, Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing, CRYPTO ‘91, LNCS 576, 129–140 (1992). DOI.

Pedersen commitments: perfectly hiding and additive (1991)

1996 – HMAC: Keyed Hashing Done Right #

To prove that a message came from someone holding a shared key, the key must be mixed into the hash in a way that leaves an attacker nothing to extend. The 1989 entry shows that $H(k \,\|\, m)$ fails this test.

Bellare, Canetti and Krawczyk defined HMAC. It hashes twice, with two keys derived from $k$. They proved it secure under assumptions about the compression function. ipad and opad are two fixed byte patterns (0x36 and 0x5c repeated), XORed into the key after it is padded to one block.

Inner hash: compute $H((k \oplus ipad) \,\|\, m)$.
Outer hash: compute $H((k \oplus opad) \,\|\, \text{inner digest})$.
The outer digest is the tag.

\[\mathrm{HMAC}(k, m) = H\bigl((k \oplus opad) \,\|\, H((k \oplus ipad) \,\|\, m)\bigr).\]

In words: hash the message with one version of the key, then hash that result with another version of the key.

Why length extension now fails:

Resuming the outer hash from the tag only appends data after the inner digest.
A tag for $m \,\|\, s$ needs the inner digest of $m \,\|\, s$, which the attacker cannot compute without the key.

HMAC became RFC 2104 in 1997. (An RFC is an internet standards document.) It is everywhere: TLS (the protocol behind https), key derivation (HKDF), and the deterministic nonces of RFC 6979.

Implementation: blockchainkit.crypto.systems.mac.hmac_sha256(), contrasted with the broken blockchainkit.crypto.systems.mac.naive_mac().

References: M. Bellare, R. Canetti, and H. Krawczyk, Keying Hash Functions for Message Authentication, CRYPTO ‘96, LNCS 1109, 1–15 (1996). DOI.

HMAC: keyed hashing that resists length extension (1996)

2002 – SHA-256 as a Standardized Hash Primitive #

Different programs must compute the same fingerprint for the same data. Otherwise a signature made by one cannot be checked by another. NIST, the US standards agency, specified SHA-256 in FIPS 180-2 alongside other secure hash algorithms. The standard includes test vectors, known input-output pairs that independent implementations can check themselves against.

A good hash behaves like a random function, so related inputs must give unrelated outputs. Changing one input bit should flip each of the 256 output bits independently with probability one half. This is the avalanche effect. You can measure it:

Hash a message $m$.
Flip one bit to get $m'$, and hash it.
XOR the two digests and count the 1-bits (the popcount, int.bit_count()).

The number of flipped bits is then binomial, like the number of heads in 256 fair coin tosses:

\[d = \mathrm{popcount}\bigl(H(m) \oplus H(m')\bigr) \sim \mathrm{Binomial}\bigl(256, \tfrac12\bigr), \qquad E[d] = 128, \quad \sigma_d = 8.\]

In words: on average 128 bits change, with a standard deviation of 8 bits.

Why it matters, and what a hash is not:

If outputs clustered by input instead, an attacker could steer toward a target digest. That would beat the $2^{256}$ (preimage) or $2^{128}$ (collision, the 1979 entry) work that a random function forces.
A digest is a compact fingerprint. It does not encrypt the input.
A guessable input can be found by hashing candidates.

Implementation: blockchainkit.crypto.systems.hashing.sha256() delegates to Python’s standard library; blockchainkit.crypto.systems.merkle_damgard.merkle_damgard_sha256() is a readable reimplementation (the 1989 entry) that the tests check against it.

References: NIST, Secure Hash Standard, FIPS PUB 180-2 (2002). Historical standard record, cited for historical context rather than as current standards guidance.

SHA-256 and the avalanche effect (FIPS 180-2, 2002)

2010-2013 – Nonce Reuse in Practice, and Deterministic Nonces #

A signature hides the private key behind a fresh random nonce. If the nonce repeats, the key leaks. With $s_i = k + c_i x$, two signatures that share $k$ but sign different messages (so $c_1 \ne c_2$) are two linear equations in two unknowns.

The attacker finds two signatures with the same $R$, which means the same $k$.
The attacker recomputes both challenges $c_1, c_2$ from the public data.
Subtracting the equations eliminates $k$. Dividing by $c_1 - c_2$ (multiplying by pow(c1 - c2, -1, n)) gives $x$.

\[s_1 - s_2 = (c_1 - c_2)\,x \quad\Longrightarrow\quad x = \frac{s_1 - s_2}{c_1 - c_2} \bmod n.\]

In words: two answers to two challenges with the same nonce reveal the secret, just as in the 1985 soundness argument.

It happened in practice:

ECDSA, the elliptic-curve signature standard used by Bitcoin and Ethereum, has a different equation, $s = k^{-1}(z + rx)$. The same counting applies: a repeated nonce leaves two equations in $k$ and $x$.
In December 2010 the fail0verflow team showed that Sony’s PlayStation 3 signed software with a constant ECDSA nonce, and recovered Sony’s private key.
Weak random number generators in Android wallets led to Bitcoin thefts in 2013.

The fix was to stop needing randomness. Thomas Pornin’s RFC 6979 derives the nonce from an HMAC-based deterministic generator. It is seeded with the private key and the message hash.

Distinct messages get distinct nonces, so the equations above never arise.
The nonce is unpredictable without the key.
It does not stop fault attacks, which disturb the hardware (for example with a voltage glitch) so that it computes a wrong signature.

Implementation: blockchainkit.crypto.systems.signatures.recover_reused_nonce_key() performs the extraction; blockchainkit.crypto.systems.signatures.deterministic_nonce() implements RFC 6979 section 3.2 with SHA-256 and reproduces the RFC’s test vectors. It feeds this package’s Schnorr signatures rather than ECDSA, and adds no protection against fault attacks.

References: fail0verflow (bushing, marcan, sven), Console Hacking 2010: PS3 Epic Fail, 27th Chaos Communication Congress (2010). T. Pornin, Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), RFC 6979 (2013). DOI.

Nonce reuse in practice, and deterministic nonces (2010-2013)

2018 – MuSig: Schnorr Multi-Signatures and the Rogue-Key Attack #

A multi-signature is one signature, produced jointly by several key holders, that is valid for one combined public key. Schnorr signatures are linear, so this looks easy. With a shared challenge $c$, partial signatures $s_i = k_i + c x_i$ add up to one ordinary signature. It is valid for the aggregate key $\sum Q_i$ and nonce $\sum R_i$.

Done naively, this allows a rogue-key attack:

The honest signer announces $Q_{\text{honest}}$.
The last signer to announce a key waits for the others. They pick an $x$ they know and announce $Q_{\text{rogue}} = xG - Q_{\text{honest}}$.
The aggregate key is now $Q_{\text{honest}} + Q_{\text{rogue}} = xG$.
The attacker does not know the private key of $Q_{\text{rogue}}$, but does not need it. They know $x$, so they can sign alone.

Maxwell, Poelstra, Seurin and Wuille’s MuSig weights every key by a hash of the whole key list $L$:

Every signer computes the weight $a_i = H(L, Q_i)$ of each key.
The aggregate key is $Q_{\text{agg}} = \sum_i a_i Q_i$.
Each signer contributes a nonce point $R_i$, and the shared challenge $c$ is computed from their sum, the aggregate key and the message.
Each signer sends $k_i + c\, a_i x_i$. The sum $s$ completes the signature.

\[a_i = H(L, Q_i), \qquad Q_{\text{agg}} = \sum_i a_i Q_i, \qquad s = \sum_i (k_i + c\, a_i x_i).\]

In words: each key is scaled by a hash of the whole list before adding, and the partial signatures are scaled the same way.

Why the attack fails:

The cancellation needs a key chosen as a function of the others’ weighted keys.
But the weights depend on the attacker’s own key through $L$.
Changing the key changes every coefficient unpredictably, so the attacker is left guessing, as with any hash.

Bitcoin’s Taproot upgrade (2021) made such aggregate spends indistinguishable from single-signer spends.

Implementation: blockchainkit.crypto.systems.multisig.musig_coefficients(), blockchainkit.crypto.systems.multisig.aggregate_public_keys(), and blockchainkit.crypto.systems.multisig.musig_sign(). All signers run in one process; real MuSig needs a round of nonce commitments (or MuSig2’s two nonces per signer) to resist attacks across concurrent signing sessions.

References: G. Maxwell, A. Poelstra, Y. Seurin, and P. Wuille, Simple Schnorr Multi-Signatures with Applications to Bitcoin, Designs, Codes and Cryptography 87, 2139–2164 (2019); preprint IACR ePrint 2018/068. DOI.

MuSig: Schnorr multi-signatures and the rogue-key attack (2018)