Digital Signatures

A signature proves that whoever holds a specific private key saw a specific message — authenticity, integrity, and non-repudiation in one primitive. Unlike a MAC, verification requires no secret, so anyone can check it: that asymmetry is what makes certificates, code signing, and software update channels possible. The scheme mechanics are straightforward; the operational story is dominated by one value, the per-signature nonce.

What actually gets signed #

Never the message — always its hash. Signing $H(m)$ rather than $m$ makes signatures constant-size and fast regardless of input length, but it means the signature is only as strong as the hash: a collision $H(m_1) = H(m_2)$ yields one signature valid for two different documents. This is precisely how the 2008 rogue-CA and 2012 Flame attacks worked — they attacked the hash, not the signature algorithm (see Merkle–Damgård).

DSA #

Descended from ElGamal and Schnorr, standardized in 1994 — and no longer approved. FIPS 186-5 (February 2023) removed DSA as an approved algorithm for signature generation, retaining it only to verify signatures that already exist; NIST cited lack of industry use and analyses showing DSA implementations are vulnerable when domain parameters are not properly generated. The current standard approves exactly three schemes: RSA, ECDSA and EdDSA. DSA is worth understanding anyway, because ECDSA is DSA with the group swapped and inherits its defining hazard.

It works in a prime-order subgroup: a large prime $p$, a 160-bit (now 224/256-bit) prime $q$ dividing $p-1$, and $g$ of order $q$. Private key $x < q$; public key $y = g^x \bmod p$.

Sign message $m$ with a random per-signature secret $k$:

$$r = \left(g^k \bmod p\right) \bmod q, \qquad s = k^{-1}\left(H(m) + xr\right) \bmod q$$

Verify with $(r, s)$ and $y$:

$$w = s^{-1} \bmod q, \quad u_1 = H(m)\,w \bmod q, \quad u_2 = r\,w \bmod q$$

$$v = \left(g^{u_1} y^{u_2} \bmod p\right) \bmod q \;\overset{?}{=}\; r$$

ECDSA is the same algebra with the multiplicative group replaced by an elliptic curve: $r$ becomes the x-coordinate of $kG$. Same equations, same nonce requirement, far smaller keys — which is why it took over TLS certificates, Bitcoin and Ethereum.

The nonce is the whole ballgame #

$k$ must be secret, unique, and unpredictable for every signature. Each property fails differently, and all three failures are total:

Reuse the same $k$ for two messages and the private key falls out algebraically. Two signatures $(r, s_1)$, $(r, s_2)$ share $r$ — visibly, on the wire:

$$k = \frac{H(m_1) - H(m_2)}{s_1 - s_2} \bmod q, \qquad x = \frac{sk - H(m)}{r} \bmod q$$

Leak a few bits of $k$ across many signatures and lattice reduction recovers $x$ — biased nonces need only ~100 signatures with a handful of known bits. Predict $k$ from a weak RNG and $x$ follows from a single signature.

1. 2010 Sony ships the PS3 with a constant ECDSA nonce; fail0verflow extracts the console's master signing key at 27C3. Every "signed" firmware after that is forgeable.
2. 2013 Android's SecureRandom flaw repeats nonces in Bitcoin wallet signatures; thieves scan the public blockchain for repeated r values and drain the affected wallets.
3. 2013+ Repeated-r scanning becomes standing practice on public chains — every reuse is permanently visible to anyone.
4. 2022 CVE-2022-21449 ("Psychic Signatures"): Java 15–18 accepted r = s = 0 as valid for any message — a missing range check, not a nonce bug, but the same class of catastrophic verification failure.

The structural fix: deterministic and Edwards signatures #

RFC 6979 derives $k$ deterministically as HMAC-DRBG(private_key, H(m)). Same message and key always produce the same signature, no RNG is consulted at signing time, and the nonce is unpredictable to anyone without the private key. It is a drop-in change — the signatures remain standard ECDSA and verify with unmodified verifiers.

Ed25519 (RFC 8032) goes further, redesigning the scheme around the failure modes:

Comparing signature performance correctly #

ECDSA signing computes one fixed-base scalar multiplication plus modular arithmetic; verification combines two scalar multiplications. ECKCDSA and ECGDSA rearrange that algebra, so operation-count comparisons depend on whether inversion is performed in the scalar field or curve field, whether fixed-base tables are precomputed, and which coordinates avoid inversions during point multiplication.

That makes a symbolic count useful for explaining an implementation, but insufficient for choosing a scheme. Measure the exact curve, library, CPU, constant-time mode, precomputation memory, batch size, key/signature encoding, and verification workload. A faster formula with variable-time secret-dependent code is not an acceptable signing implementation.

The current NIST portfolio also extends beyond the classical schemes in FIPS 186-5: FIPS 204 standardizes ML-DSA and FIPS 205 standardizes SLH-DSA for post-quantum signatures. That is a migration choice with different key/signature sizes and deployment constraints, not an interchangeable “faster ECDSA.”

Source claims audit #

Seeded from a university lab manual (DSA/SSL lab, following Applied Cryptography). Status of its load-bearing claims: