Signing — Signatures by Hand, lesson 5

Signing

r comes from a throwaway point, s ties the message hash and the private key together. Two lines of algebra, one fatal requirement.

A signature has to prove two things at once: that the signer holds the private key, and that the message is the one they meant. ECDSA does it with two numbers, r and s, and one throwaway secret.

First the message is hashed. ECDSA never sees your bytes; it sees an integer z derived from the digest — the leftmost bits of it, as many as the group order has, interpreted as a number. That is why the choice of hash is part of the signature scheme and not an implementation detail, and why ES256 means “P-256 with SHA-256” specifically.

the signing algorithm, in full

choose k    a nonce: random, secret, used exactly once
r = (k*G).x mod n
s = inv(k) * (z + r*d) mod n
signature = (r, s)

if r == 0 or s == 0, throw k away and choose another

Look at what each half carries. r is a fingerprint of a point nobody else can produce without knowing k. s mixes three things — the message hash z, the private key d, and the nonce k — in a way that can be checked against the public key but not unpicked. The private key appears exactly once, inside a product, wrapped in a modular inverse. That is the whole design.

The nonce is not a formality

k must be secret, and it must be different for every signature. If two signatures over different messages share a nonce, anyone holding both can recover the private key with school algebra:

what nonce reuse costs you

s1 = inv(k)*(z1 + r*d)      same k, so the same r appears twice
s2 = inv(k)*(z2 + r*d)

s1 - s2 = inv(k)*(z1 - z2)
      k = (z1 - z2) / (s1 - s2)          <- the nonce falls out
      d = (s1*k - z1) / r                <- and then the private key

This is not a theoretical concern. It is how the PlayStation 3 code-signing key was recovered in 2010, how thousands of Bitcoin wallets have been emptied, and how a long list of embedded devices with weak entropy at boot have leaked their keys. The failure is invisible from the outside — the signatures are perfectly valid — until someone notices two of them sharing an r.

Your turn

Sign a message by hand

Everything you need is fixed for you, so the only work is the algebra. Note that the signature scalars live modulo n = 19, the number of points — not modulo the field prime 17, which governs coordinates only.

given

n = 19          the group order (how many points the curve has)
G = (5, 1)      the generator
d = 7           your private key
k = 3           the nonce for this one signature
z = 11          the message hash, already reduced mod n

the rule

r = (kG).x mod n
s = inv(k) * (z + r*d) mod n

r =s =

I need the inverses again

  a   |  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18
inv a |  1 10 13  5  4 16 11 12 17  2  7  8  3 15 14  6  9 18
                                             (all mod n = 19)

Check one if you like: 3 · 13 = 39 = 2·19 + 1, so inv(3) = 13 modulo 19. This is the same extended-Euclid inverse you used in lesson 2, only modulo n instead of modulo p.

One rule with no exceptions

Sign two different messages with the same k and the private key falls out of the two signatures by school algebra: subtract the two s equations, the d terms cancel into something you can solve for k, and then d follows immediately. This is not theoretical — it is how a PlayStation 3 signing key and thousands of Bitcoin wallets were recovered. In lesson 7 you will meet the tool on this site that scans for exactly that pattern.

What you now know

r = (kG).x mod n and s = k⁻¹(z + r·d) mod n — that is the entire signing algorithm.
The nonce k must be secret and fresh; reusing it exposes the private key outright.
Both halves are integers modulo the group order n, not modulo the field prime p.