Elliptic Curve Digital Signature Algorithm tools
Elliptic curves are defined as (y^2) % p = (x^3 + ax + b) % p
For which (4a^3 + 27b^2) % p != 0 (to exclude singular curves)
Domain parameters
- a and b are the equation constants above
- G is the generator point, a point on the curve above
- p is the (prime) congruence modulo above, ie lhs % p = rhs % p
- n is the number of possible points on the curve, note that n < p
Note that n * G = O (point at infinity)
This implies that n * pubkey = O
Because n * (privkey * G) = O
- https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
- https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
a = -a % n
The identity element, adding it to any point results in that point
This including adding the identity element to itself
Adding a point and its negation results in the point at infinity
Negated points have the same x coordinate and negated y coordinate
Adding (the x, y components of) one point P to another point Q results in a point S
If a line is drawn from P to Q it will result in a point R where R = -S
P + Q = R
(xp, yp) + (xq, yq) = (xr, yr)
lambda = ((yq - yp) / (xq - xp)) % p
"Division" is via modular inverse
Modular inverse: Find b such that (a * b) % m = 1
lambda = ((yq - yp) * modinv(xq - xp, p)) % p
xr = (lambda^2 - xp - xq) % p
yr = (lambda * (xp - xr) - yp) % p
As above but with
lambda = ((3 * xp^2 + a) / (2 * yp)) % p
lambda = ((3 * xp^2 + a) * modinv(2 * yp, p)) % p
If P is added to P the result is 2P, similarly 2P + P is 3P
Given R = kP where R and P are known, k cannot be determined
This is the basis for ECDSA use in public-key cryptography
Ie pubkey = privkey * G
- Let L be the bit length of n
- Let z be the leftmost L bits of hash(message)
- Select a random integer k in the range [1, n - 1]
- Calculate (x, y) = k * G
- Calculte r = x % n
- If r = 0 then choose a different k
- Calculate s = (k^-1 * (z + r * privkey)) % n = (modinv(k, n) * (z + r * privkey)) % n
- If s = 0 then choose a different k
- The signature is (r, s)
- If r or s is negative make positive with a = -a % n
- Verify the pubkey != O (point at infinity)
- Verify the pubkey lies on the curve
- Verify n * pubkey = O
- Verify r and s are in the range [1, n - 1]
- Let L be the bit length of n
- Let z be the leftmost L bits of hash(message)
- Calculate u = (z * s^-1) % n = (z * modinv(s, n)) % n
- Calculate v = (r * s^-1) % n = (r * modinv(s, n)) % n
- Calculate (x, y) = u * G + v * pubkey
- If the point (x, y) = O then the signature is invalid
- Verify r = x % n
package ecdsa_tools // import "github.com/jo-makar/ecdsa-tools"
TYPES
type Curve struct {
P, A, B *big.Int // Elliptic curve definition: (y^2) % p = (x^3 + ax + b) % p
Gx, Gy *big.Int // Generator point (a point on the curve above)
N *big.Int // Number of possible points on the curve
}
func (c *Curve) Equals(d *Curve) bool
type Point struct {
X, Y *big.Int
AtInf bool
Curve *Curve
}
func NewPoint(x, y *big.Int, curve *Curve) (*Point, error)
func (p *Point) Add(q *Point) *Point
func (p *Point) Double() *Point
func (p *Point) Equals(q *Point) bool
func (p *Point) IsNegation(q *Point) bool
func (p *Point) Multiply(k *big.Int) *Point
func (p *Point) Negate() *Point
func (p *Point) OnCurve() bool
type PrivKey struct {
D *big.Int // Private key
Curve *Curve
}
func NewPrivKeyBitcoin(privKey string) (*PrivKey, error)
func NewPrivKeyEthereum(privKey string) (*PrivKey, error)
func NewPrivKeyViaOpenSSLFile(privKeyPath string) (*PrivKey, error)
func NewRandomPrivKeyBitcoin() (*PrivKey, error)
func NewRandomPrivKeyEthereum() (*PrivKey, error)
func NewRandomPrivKeyViaOpenSSL(curve string) (*PrivKey, error)
func NewRandomPrivKeyViaStdLib(curve string) (*PrivKey, error)
func (p *PrivKey) CalcPubKey() *PubKey
type PubKey struct {
E *Point // Public key
Curve *Curve
}
func NewPubKeyBitcoin(address string) (*PubKey, error)
func NewPubKeyEthereum(address string) (*PubKey, error)
func NewPubKeyViaOpenSSLFile(pubKeyPath string) (*PubKey, error)
OpenSSL signature verification demo
OpenSSL signature (generation) demo