ECDSA Signature Tool

A signature that verifies in one program and fails in another has usually not been forged, damaged or made with the wrong key. It has been written down differently. The numbers were right and the spelling was not.

ECDSA is the elliptic curve member of the family of signature schemes in the United States Digital Signature Standard. A private key is a single number. The public key is a point on a named curve, reached by adding the curve’s fixed base point to itself that many times. Going forward is quick. Going back, from the point to the number, is the problem nobody knows how to solve at these sizes.

The appeal is size. NIST’s key management guidance puts a curve of 256 to 383 bits at the same 128-bit security strength as an RSA modulus of 3072 bits, a 384-bit curve beside 7680 bits of RSA, and curves of 512 bits and more beside 15360. An RSA signature is as long as its modulus, so 384 bytes at that first level. The matching ECDSA signature is 64 bytes.

Keys shrink in step. On P-256 the private value is 32 bytes, and the public point in its uncompressed form is one marker byte, 04, followed by the x and y coordinates: 65 bytes in all.

What r and s are

To sign, the signer hashes the message, picks a secret number k for this one signature, and multiplies the base point by k. The x coordinate of that new point, reduced modulo the curve order, is r. The second number folds everything together: s is the hash plus the private key times r, all divided by k, again modulo the order. The pair (r, s) is the signature. A verifier with the public point and the same hash can test that the pair fits, without learning the private key or k.

Multiplying a point means adding it to itself, and adding points is geometry. Draw the line through two points of the curve. It meets the curve in one more place. Mirror that third point in the x axis, and the mirror image is the sum. To double a point, use the tangent there.

A worked case can be checked by hand. On the curve y^2 = x^3 - 7x + 10, take P = (1, 2) and Q = (3, 4). The line through them has slope 1. The standard formulas give x = 1 - 1 - 3 = -3 for the third point, and the line passes through (-3, -2) there. Mirrored, P + Q = (-3, 2), and indeed 2 squared is 4 while -27 + 21 + 10 is also 4. Set the two beads of the tool to those points and it draws the same line and prints the same sum.

That picture lives over the real numbers and is only a picture. The curves used for signing keep the equation and the formulas but do the arithmetic modulo a large prime, where the points are scattered and there is no smooth line to look at.

Two ways to write two numbers

A browser’s Web Crypto interface returns r and s as fixed-width fields glued end to end. Each number is padded on the left to the size of the curve, so a P-256 signature is always 64 bytes and a P-384 signature always 96. JSON Web Signature uses the same layout. For P-521 the JOSE specification notes that each 521-bit number is written in 66 octets, which makes 132 bytes.

Certificates took another road. The X.509 algorithm profile says the two values must be ASN.1 encoded as a SEQUENCE of two INTEGERs, and TLS 1.3 represents an ECDSA signature as that same DER-encoded structure. Software built around certificates therefore expects this form.

DER has opinions about integers. They are two’s complement and must use the fewest bytes possible, so leading zero bytes are dropped. The top bit of the first byte is the sign, which means a positive number whose first byte is 128 or more needs one extra zero byte in front to stay positive. The result is a signature whose length changes from one signing to the next.

The example in the JSON Web Signature specification shows it. Its R begins with the byte 14 and its S with 197. Raw, the signature is 64 bytes, or 86 characters of Base64url. In DER, R is written as it stands in 32 bytes, S gains a zero byte and takes 33, each number carries a two-byte header, and two more bytes open the SEQUENCE: 71 bytes. Paste that published signature into the tool and it reports exactly this.

Neither form announces itself. A verifier that is handed the wrong one simply answers no, and the caller concludes that the key or the message is wrong. The cure is mechanical, but it needs the curve, because going from DER to raw means padding each number back to full width.

A converter should also be strict. Trailing bytes, a length that is not minimal, a negative number or a value wider than the curve are signs that something upstream is broken, and a tool that guesses hides the fault.

The number that must never repeat

Sign the same message twice with ECDSA and the two signatures differ, though both are valid. The standard requires it: a new secret random number k shall be generated before each signature, and it must be protected from disclosure like the private key itself.

The reason is plain algebra. Two signatures made with the same k have the same r. Subtract one s from the other and the private key drops out, leaving k as the difference of the two hashes divided by the difference of the two s values. With k known, the private key follows from either signature.

This has happened to real products. At the 27th Chaos Communication Congress in 2010, a team presenting its work on a games console put the formulas on screen with the remark that from a pair of signatures that use the same random number one can compute both it and the private key. Their slide about the vendor’s signing code was a cartoon of a random number function that always returns 4.

In August 2013 the Android security team reported that applications using the platform’s Java cryptography interface for key generation, signing or random numbers might not receive cryptographically strong values, because the underlying generator was improperly initialized. Bitcoin.org had warned days earlier that the weakness left every Android wallet generated to date vulnerable to theft, and told users to move their funds to new keys.

Repetition is the loud failure. The quiet one is bias: the specification for deterministic signatures warns that even slight biases in choosing k may be turned into attacks. Its answer is to derive k from the private key and the message, so that no randomness is needed at signing time. The current standard approves that variant, noting that it protects against signatures made with insufficient randomness.

Curves, hashes and where they turn up

The three curves a browser offers have two names each: secp256r1, secp384r1 and secp521r1 in the certificate world, P-256, P-384 and P-521 at NIST. P-256 is the one that two major protocols single out. A TLS 1.3 implementation must support ECDSA on that curve with SHA-256, and the JSON Web Token specification recommends supporting ES256, which is the same pairing.

The pairing is a habit before it is a rule. JOSE defines exactly three combinations, ES256, ES384 and ES512, and the last uses the 521-bit curve despite its name. The signature standard recommends that hash and curve have the same security strength and says a weaker hash shall not be used. When the hash is longer than the curve order, only its leftmost bits enter the calculation.

Key files add their own vocabulary. A public key normally travels under a -----BEGIN PUBLIC KEY----- line, a private key under -----BEGIN PRIVATE KEY-----, and an older private format under -----BEGIN EC PRIVATE KEY-----. Inside, the curve is supposed to be named by its identifier. Keys that spell out the curve’s parameters in full are forbidden in certificates.

What a valid signature does not tell you

A valid signature proves that these exact bytes met one private key. It says nothing about who held the key, when, or whether they read what they signed. The private value is 32 bytes on P-256, small enough to leak in a screenshot, and an exported key file is plain text unless something else encrypts it.

The method cannot rescue a signer with a poor random source, and it cannot outlast its mathematics. NIST’s own strength table carries a note that the estimates will be significantly affected when quantum computing becomes practical. Until then, the work is modest: keep the key private, let a trusted library choose k, and know which of the two spellings the other side expects.