Lesson 6 of 7 · about 10 minutes

Verifying

The verifier recombines the signature into a point and checks one coordinate. Get it wrong and forgeries walk straight through.

Verification gets the public key Q, the message hash z and the pair (r, s), and nothing else. It has to decide whether whoever produced those numbers knew d. It does so by rebuilding the signer’s nonce point out of the pieces and checking that it lands where r says it should.

the verification algorithm, in full

reject unless 1 <= r <= n-1 and 1 <= s <= n-1

u1 = z * inv(s) mod n
u2 = r * inv(s) mod n
R  = u1*G + u2*Q

reject if R is the point at infinity
valid if R.x mod n == r

The reason it works is a single substitution. The signer set s = inv(k)·(z + r·d), so inv(s) = k·inv(z + r·d). Feed that into u1·G + u2·Q, remember that Q = d·G, and the whole expression collapses to k·G — the exact point the signer generated and then discarded. The verifier holds it without ever having learned k or d, and compares its x-coordinate with r.

What a valid signature does and does not tell you

It tells you the signer held the private key matching this public key, and that the message hash was this z. Both, together, or the check fails.
It tells you nothing about whether that public key belongs to anyone you trust. Binding a key to an identity is what certificates, JWKS endpoints and trust stores are for; the signature check is one link in that chain and never the whole of it.
It does not make the signature bytes unique. Given a valid (r, s), the pair (r, n − s) is also valid — no private key required. Systems that use signature bytes as an identifier have to normalise to one of the two forms, which is what the “low-s” rule is about.

The range checks in the first line matter too. A verifier that accepts r = 0 or s = 0, or that forgets to confirm the public key is a point on the curve at all, opens the door to forgeries that have nothing to do with breaking the discrete logarithm. Every serious library performs these checks; several historical CVEs exist because one of them did not.

Your turn

Take the signature apart

Here is the signature you built in the previous lesson, together with the public key it belongs to. Verification starts by splitting it into two scalars. Compute them.

given

n = 19          G = (5, 1)
Q = (0, 6)      the signer's public key
z = 11          the hash of the message being checked
(r, s) = (10, 8)  the signature

the rule

u1 = z * inv(s) mod n
u2 = r * inv(s) mod n
valid  <=>  (u1*G + u2*Q).x mod n == r

u1 =u2 =

Why does this reconstruct kG?

Substitute. The signer set s = inv(k)·(z + r·d), so inv(s) = k · inv(z + r·d). Then:

u1*G + u2*Q = (z * inv(s))*G + (r * inv(s))*Q
            = (z * inv(s))*G + (r * inv(s))*(d*G)      because Q = d*G
            = ((z + r*d) * inv(s)) * G
            = ((z + r*d) * k * inv(z + r*d)) * G
            = k*G

The verifier ends up holding the signer's nonce point without ever knowing k or d. It then checks that its x-coordinate is the r that came with the signature. Every term the signer kept secret cancels — that cancellation is the whole trick.

Your turn

Find the one signature that verifies

Three candidate signatures arrive for the same message, z = 11, claiming to come from the same public key Q = (0, 6). All three are well-formed: both components are in range and neither is zero. Only one of them passes the check. Run the verification on each and pick it.

Candidate A — (r, s) = (10, 8)Candidate B — (r, s) = (6, 9)Candidate C — (r, s) = (10, 12)

Inverses modulo 19, 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

multiples of G:
 1G=(5,1)   2G=(6,3)   3G=(10,6)  4G=(3,1)   5G=(9,16)
 6G=(16,13) 7G=(0,6)   8G=(13,7)  9G=(7,6)  10G=(7,11)
11G=(13,10) 12G=(0,11) 13G=(16,4) 14G=(9,1) 15G=(3,16)
16G=(10,11) 17G=(6,14) 18G=(5,16) 19G=O

With the table above, Q = 7G, so u2·Q = (7·u2)G and the whole check collapses to arithmetic on scalars modulo 19: compute u1 + 7·u2 mod 19, look up that multiple of G, and compare its x-coordinate with r.

A curiosity worth knowing

If (r, s) verifies, so does (r, n − s) — the same message, a second valid signature, and no private key needed to produce it from the first. Here that means (10, 8) and (10, 11) both pass. This is signature malleability, and it is why Bitcoin and many libraries insist on the smaller of the two values, the “low-s” form. A system that treats the signature bytes as a unique identifier for a transaction gets bitten by this; a system that only asks “is this valid?” does not.

What you now know

Verification computes u1 = z·s⁻¹, u2 = r·s⁻¹ and checks (u1G + u2Q).x mod n == r.
It works because u1G + u2Q reconstructs exactly kG when the signature is genuine.
A perfectly valid signature of a different message is still a failed verification here.