Information Theory, Cryptography & Cybernetics (Part 13): Digital Signatures, DSA & The ECDSA Nonce Catastrophe

While encryption guarantees confidentiality (ensuring that unauthorized eavesdroppers cannot read a private transmission), modern human civilization and legal contracts require two equally vital guarantees: Integrity (proving the message was not modified in transit) and Non-Repudiation (proving that the author cannot subsequently deny having authored the document). Handcrafted wax seals and handwritten ink signatures satisfied this role for thousands of years. In the digital realm, where every bit can be effortlessly duplicated, authenticity is established through Digital Signature Algorithms (RSA-PSS, DSA, and ECDSA). However, this mathematical power comes with extreme architectural fragility: a failure of true randomness in a single ephemeral parameter collapses the entire cryptosystem.

1. The Mechanics of the Elliptic Curve Digital Signature Algorithm (ECDSA)

ECDSA operates over an elliptic curve group $E(mathbb{F}_p)$ with generator base point $G$ of prime order $n$. The private signing key is an integer $d in [1, n-1]$, and the public verification key is the curve point $Q = d cdot G$.

Signature Generation Protocol:

1. Compute the cryptographic hash of message $m$, truncated to the bit-length of $n$:
   [
   e = text{Hash}(m)
   ]
2. Select an ephemeral nonce $k in [1, n-1]$ uniformly at random.
3. Compute the curve point $R = (x_1, y_1) = k cdot G$.
4. Compute the signature component $r$:
   [
   r = x_1 bmod n
   ]
   (If $r = 0$, pick another random $k$).
5. Compute the signature component $s$:
   [
   s = k^{-1} (e + r cdot d) bmod n
   ]
   (If $s = 0$, pick another random $k$).
6. The digital signature is the pair of integers:
   [
   sigma = (r, s)
   ]

Public Signature Verification Protocol:

Given message $m$, public key $Q$, and signature $(r, s)$, any verifier confirms authenticity:

1. Verify that $r, s in [1, n-1]$.
2. Compute $e = text{Hash}(m)$ and modular inverse $w = s^{-1} bmod n$.
3. Compute coefficients $u_1 = e cdot w bmod n$ and $u_2 = r cdot w bmod n$.
4. Compute the verification curve point:
   [
   (x_2, y_2) = u_1 cdot G + u_2 cdot Q = left( frac{e}{s} right) G + left( frac{r}{s} right) d G = frac{e + r d}{s} G = k cdot G = (x_1, y_1)
   ]
5. Accept the signature if and only if $x_2 equiv r pmod n$.

2. The Ephemeral Nonce Reuse Catastrophe

Notice the parameter $k$: it is called an ephemeral nonce (“number used once”) because it must be generated anew with fresh cryptographic entropy for every single signature.

Suppose an engineering team implements ECDSA using a faulty random number generator (such as a hardcoded seed, an uninitialized pointer, or a predictable pseudo-random sequence) such that the same nonce $k$ is used to sign two distinct messages $m_1$ and $m_2$.

An adversary intercepts both signatures $sigma_1 = (r, s_1)$ and $sigma_2 = (r, s_2)$. Notice that because $k$ was identical, the first component $r = (kG)_x bmod n$ is identical across both signatures! The adversary now has a system of two modular linear equations with two unknowns ($k$ and private key $d$):

[
s_1 equiv k^{-1} (e_1 + r cdot d) pmod n, quad s_2 equiv k^{-1} (e_2 + r cdot d) pmod n
]

Subtracting the two equations eliminates the private key $d$ completely:

[
s_1 – s_2 equiv k^{-1} (e_1 – e_2) pmod n
]

Multiplying by $k$ and dividing by $(s_1 – s_2)$ immediately solves for the secret nonce $k$:

[
k equiv frac{e_1 – e_2}{s_1 – s_2} pmod n
]

Once $k$ is known, the private key $d$ is trivially calculated via elementary arithmetic:

[
d equiv r^{-1} (s_1 k – e_1) pmod n
]

3. Deterministic Nonce Generation: RFC 6979 & Ed25519

To eliminate reliance on fragile physical random number generators, modern cryptography mandates Deterministic Nonce Generation (RFC 6979). Instead of picking $k$ via hardware entropy, $k$ is computed deterministically as an HMAC hash of the message and the private key: $k = text{HMAC-SHA256}(d, m)$. The nonce is uniquely pseudorandom for every message, but 100% deterministic, completely preventing nonce reuse.

Furthermore, modern systems increasingly adopt Ed25519 (EdDSA), which incorporates deterministic nonces natively over Edwards curves, providing immune performance against side-channel and timing attacks.

Shakil Mahmud Shazal

Senior Software Engineer based in Dhaka, Bangladesh. Building scalable web architectures and writing at the intersection of computer science, physical systems, history, and ideas.