mimoo

Elliptic Curve Cryptography (ECC)

Abstract

ECC is about a group created via:

• a 2-dimension elliptic curve: an equation with unknowns x and y
  • every Elliptic Curve follows this formula: y² + a₁ x y + a₃ y = x³ + a₂ x² + a₄ x + a₆ (for some specified a₁, a₂, a₃, a₄, a₆)
  • actually, it can be shorten to this y² = x³ + a x + b (short weierstrass form) in practice because the characteristic (order of a prime field) 2 and 3 points in prime fields (except for binary (GF(2^x)) and GF(3^x) curves)

• a curve of characteristic 2 (defined over GF(2^x)) can be simplified to y² + xy = x³ + ax² + b

paulmillr

Hal Finney's explanation of secp256k1 "efficiently computable endomorphism" parameters used secp256k1 libraries, archived from source.

The same optimization could be applied to any Koblitz curve (e.g. Short Weistrass curve with a=0).

---

I implemented an optimized ECDSA verify for the secp256k1 curve, based on pages 125-129 of the Guide to Elliptic Curve Cryptography, by Hankerson, Menezes and Vanstone. I own the book but I also found a PDF on a Russian site which is more convenient.

secp256k1 uses the following prime for its x and y coordinates:

nlitsme

Demonstrate how to calculate the messagehash for the two signatures in this transaction

See ecdsa_demo.py for code showing how to use this to crack the bitcoin secret key.

These are the values extracted from the example transaction below:

pk="04 db d0 c6 15 32 27 9c f7 29 81 c3 58 4f c3 22 16 e0 12 76 99 63 5c 27 89 f5 49 e0 73 0c 05 9b 81 ae 13 30 16 a6 9c 21 e2 3f 18 59 a9 5f 06 d5 2b 7b f1 49 a8 f2 fe 4e 85 35 c8 a8 29 b4 49 c5 ff"
r="d4 7c e4 c0 25 c3 5e c4 40 bc 81 d9 98 34 a6 24 87 51 61 a2 6b f5 6e f7 fd c0 f5 d5 2f 84 3a d1"
s1="44 e1 ff 2d fd 81 02 cf 7a 47 c2 1d 5c 9f d5 70 16 10 d0 49 53 c6 83 65 96 b4 fe 9d d2 f5 3e 3e"