2017-06-16 Friday-night tweet-size crypto: ECDSA over secp256k1
(Permalink: https://mumble.net/~campbell/2017/06/16/fntsc-ecdsa-secp256k1)
(Twitter: https://twitter.com/Riastradh_/status/875921073409282048)
(For amusement purposes only!)
- Parameters: Let p = 2^256 - 2^32 - 978, a prime; E, the Weierstrass
curve y^2 = x^3 + 7 over Z/pZ of order l; B, a point; H, SHA256.
- Keygen: Pick a uniformly in Z/lZ; publish A = a B.
- Verify: Given message m, coordinate x(R) in Z/pZ, and scalar s in
Z/lZ, test x(H(m) s^-1 B + x(R) s^-1 A) = x(R).
- Sign: Pick r uniformly in Z/lZ; compute R = r B, s = r^-1 [H(m) +
x(R) a] (mod l), reveal (x(R), s).
- Correctness: x(H(m) s^-1 B + x(R) s^-1 A) = x([H(m) + x(R) a]
s^-1 B) = x(r B) = x(R).
- Nwice attack: If (m, x(R), s) and (m', x(R), s') are signatures
under public key A = a B, then a = [s (H(m) - H(m'))/(s - s') -
H(m)]/x(R).
- Signature malleability: If (m, x(R), s) is a valid signature,
then so is (m, x(R), -s), since x(-R) = x(R).
[Update, 2017-10-09: Fix confusion of field size and curve order.
Correct the format: a signature contains only the x coordinate of
R, not a full encoding of R. Unfortunately, I cannot fix these
small but critical mistakes on Twitter.]
--
Copyright (c) 2006--2017, Taylor R. Campbell.
Verbatim copying and distribution of this entire article are permitted
worldwide, without royalty, in any medium, provided this notice, and
the copyright notice, are preserved.