ECDSA

A public key lets someone check a signature without learning the private key. ECDSA builds that check from elliptic-curve point arithmetic and a message hash. It signs a message; it does not encrypt it.

Agree on the group

The signer and verifier share the curve parameters ⁠, including base point $G$ and its prime order $n$. The signer holds a private scalar $d$ and publishes $Q=dG$. The verifier must obtain the right public key for the identity or account being checked.

Let $z$ be the integer derived from the message hash. If the hash is longer than the bit length of $n$, ECDSA takes its leftmost bits to that length. Coordinate arithmetic uses the field modulus $p$; signature scalars use $n$.

Make a signature

The signer chooses a secret scalar $k$ between $1$ and $n-1$, then computes:

$$R=kG,\qquad r=x_R\bmod n,$$ $$s=k^{-1}(z+rd)\bmod n.$$

The signature is $(r,s)$. If either value is zero, signing retries with another $k$. See FIPS 186-5, §6.4.

The example below uses the tiny curve $y^2=x^3+2x+2\pmod{17}$ with $G=(5,1)$ of order $19$. It exposes $d$ and $k$ for learning and takes $z=11$ directly, without hashing a message. Change $k$ or change the digest presented to the verifier.

These small numbers offer no security. Some choices of $k$ produce an invalid signature; the diagram leaves that failure visible instead of silently replacing the nonce.

Check the signature

After validating the public key and checking $1\le r,s<n$, the verifier computes:

$$u_1=zs^{-1}\bmod n,\qquad u_2=rs^{-1}\bmod n,$$

$V=u_1G+u_2Q.$

Reject if $V=O$. Otherwise accept when $x_V\bmod n=r$. The verifier uses the message, public key and signature; it does not need $d$ or $k$. Public-key validation checks the curve and subgroup as well as rejecting the point at infinity. See SEC 1, §§3.2.2 and 4.1.4.

Why it works

For an honestly generated signature, substitute $Q=dG$ and the signing equation:

$$\begin{aligned} V&=zs^{-1}G+rs^{-1}(dG)\\ &=s^{-1}(z+rd)G\\ &=kG=R. \end{aligned}$$

The reconstructed point has the same horizontal coordinate, so the check succeeds. This proves correctness of the calculation; resistance to forgery also relies on the chosen group, hash and implementation. Tiny teaching groups can have accidental matches after a digest change.

Protect the nonce

If an attacker learns $k$ from a valid signature, rearranging the equation reveals the private key:

$d=(sk-z)r^{-1}\bmod n.$

Reusing the same $k$ for two different digest values is also dangerous. Subtracting the two signing equations can reveal $k$, then $d$.

The two signatures below use the same teaching key. Switch off nonce reuse: the two equations no longer yield one shared $k$.

A nonce can come from a suitable cryptographic random generator or a specified deterministic construction. RFC 6979 derives it from the private key and message hash; deterministic does not mean publicly predictable. A timestamp is not a substitute.

Three different inputs

P-256 and secp256k1 can both be used with ECDSA. Passkeys ⁠ commonly use the former; Ethereum EOA transactions ⁠ use the latter. Their groups and encodings are not interchangeable.

Recovering a public curve seed's origin is therefore a different task from recovering a signing key. Curve Origins ⁠ follows that investigation.