ECDSA implementation using Go's provided curves

ecdsa.go

package ecdsa

import (
	"io"
	"os"
	"big"
	"crypto/elliptic"
	"sync"
)

type Curve struct {
	elliptic.Curve
	N *big.Int // order of base point
}

type PublicKey struct {
	C      *Curve
	Qx, Qy *big.Int // public key
}

type PrivateKey struct {
	PublicKey
	D *big.Int // private key
}

// randomNumber returns a uniform random value in [1, max).
// https://github.com/zaker/EcDSA--EcDH-in-Go/blob/master/ecc/eccdsa.go
func randomNumber(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) {
	k := (max.BitLen() + 7) / 8
	// r is the number of bits in the used in the most significant byte of
	// max.
	r := uint(max.BitLen() % 8)
	if r == 0 {
		r = 8
	}
	bytes := make([]byte, k)
	n = new(big.Int)

	for {
		_, err = io.ReadFull(rand, bytes)
		if err != nil {
			return
		}
		// Clear bits in the first byte to increase the probability
		// that the candidate is < max.
		bytes[0] &= uint8(int(1<<r) - 1)
		n.SetBytes(bytes)
		if n.Sign() > 0 && n.Cmp(max) < 0 {
			return
		}
	}
	return
}

func GenerateKey(rand io.Reader, c *Curve) (priv *PrivateKey, err os.Error) {
	priv = new(PrivateKey)
	priv.C = c
	var db []byte
	db, priv.Qx, priv.Qy, err = priv.C.GenerateKey(rand)
	priv.D = new(big.Int).SetBytes(db)
	return
}

// Supposed to return maxBits leftmost bits from hash, but currently works only
// with multiples of 8, which is good for current curves and hash <= 512 bits 
func hashBits(hash []byte, maxBits int) *big.Int {
	maxBytes := (maxBits + 7) / 8
	if maxBytes > len(hash) {
		maxBytes = len(hash)
	}
	return new(big.Int).SetBytes(hash[:maxBytes])
}

func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err os.Error) {
	r = new(big.Int)
	s = new(big.Int)
	for {
		k, _ := randomNumber(rand, priv.C.P)
		x, _ := priv.C.ScalarBaseMult(k.Bytes())
		r.Mod(x, priv.C.P)
		if r.Sign() == 0 {
			continue
		}
		z := hashBits(hash, priv.C.BitSize)
		s.Mul(r, priv.D)
		s.Mod(s, priv.C.N)
		s.Add(s, z)
		s.Mod(s, priv.C.N)
		k.ModInverse(k, priv.C.N)
		s.Mul(s, k)
		s.Mod(s, priv.C.N)
		if s.Sign() != 0 {
			break
		}
	}
	return
}

func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
	if r.Sign() < 1 || r.Cmp(pub.C.P) >= 0 {
		return false
	}
	if s.Sign() < 1 || s.Cmp(pub.C.P) >= 0 {
		return false
	}
	w := new(big.Int).ModInverse(s, pub.C.N)

	u1 := new(big.Int).Mul(w, hashBits(hash, pub.C.BitSize))
	u1.Mod(u1, pub.C.N)

	u2 := new(big.Int).Mul(w, r)
	u2.Mod(u2, pub.C.N)

	Gvx, Gvy := pub.C.ScalarBaseMult(u1.Bytes())
	Qvx, Qvy := pub.C.ScalarMult(pub.Qx, pub.Qy, u2.Bytes())
	x, _ := pub.C.Add(Gvx, Gvy, Qvx, Qvy)
	x.Mod(x, pub.C.N)

	return r.Cmp(x) == 0
}

// Curves

var initonce sync.Once
var p192 *Curve
var p224 *Curve
var p256 *Curve
var p384 *Curve
var p521 *Curve

func initAll() {
	initP192()
	initP224()
	initP256()
	initP384()
	initP521()
}

// N constants from http://csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf

func initP192() {
	p192 = new(Curve)
	p192.P, _ = new(big.Int).SetString("627710173538668076383578942320766641608390870039032496127", 10)
	p192.N, _ = new(big.Int).SetString("627710173538668076383578942317605901376719477318284228408", 10)
	p192.B, _ = new(big.Int).SetString("64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", 16)
	p192.Gx, _ = new(big.Int).SetString("188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", 16)
	p192.Gy, _ = new(big.Int).SetString("07192b95ffc8da78631011ed6b24cdd573f977a11e794811", 16)
	p192.BitSize = 192
}

func initP224() {
	n, _ := new(big.Int).SetString("26959946667150639794667015087019625940457807714424391721682722368061", 10)
	p224 = &Curve{*elliptic.P224(), n}
}

func initP256() {
	n, _ := new(big.Int).SetString("115792089210356248762697446949407573529996955224135760342422259061068512044369", 10)
	p256 = &Curve{*elliptic.P256(), n}
}

func initP384() {
	n, _ := new(big.Int).SetString("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643", 10)
	p384 = &Curve{*elliptic.P384(), n}
}

func initP521() {
	n, _ := new(big.Int).SetString("6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449", 10)
	p521 = &Curve{*elliptic.P521(), n}
}

func P192() *Curve {
	initonce.Do(initAll)
	return p192
}

func P224() *Curve {
	initonce.Do(initAll)
	return p224
}

func P256() *Curve {
	initonce.Do(initAll)
	return p256
}

func P384() *Curve {
	initonce.Do(initAll)
	return p384
}

func P521() *Curve {
	initonce.Do(initAll)
	return p521
}

Rev. 640e72, 2011-02-20: Added "x.Mod(x, pub.C.N)" -- previous version might not be able to verify signature correctly if x was > pub.C.N.

New version of Go now already includes crypto/ecdsa package. Use it!