1package ecc
  2
  3import (
  4	"bytes"
  5	"errors"
  6	"math/big"
  7)
  8
  9// EC is the data structure for the elliptic curve parameters
 10type EC struct {
 11	A *big.Int
 12	B *big.Int
 13	Q *big.Int
 14}
 15
 16// NewEC (y^2 = x^3 + ax + b) mod q, where q is a prime number
 17func NewEC(a, b, q int) (ec EC) {
 18	ec.A = big.NewInt(int64(a))
 19	ec.B = big.NewInt(int64(b))
 20	ec.Q = big.NewInt(int64(q))
 21	return ec
 22}
 23
 24// At gets a point x in the curve
 25func (ec *EC) At(x *big.Int) (Point, Point, error) {
 26	if x.Cmp(ec.Q) > 0 {
 27		return Point{}, Point{}, errors.New("x<ec.Q")
 28	}
 29	// y^2 = (x^3 + ax + b) mod q
 30	// y = sqrt (x^3 + ax + b) mod q
 31	// x^3
 32	x3 := new(big.Int).Exp(x, big.NewInt(int64(3)), nil)
 33	// a^x
 34	aX := new(big.Int).Mul(ec.A, x)
 35	// x^3 + a^x
 36	x3aX := new(big.Int).Add(x3, aX)
 37	// x^3 + a^x + b
 38	x3aXb := new(big.Int).Add(x3aX, ec.B)
 39	// y = sqrt (x^3 + ax + b) mod q
 40	y := new(big.Int).ModSqrt(x3aXb, ec.Q)
 41	return Point{x, y}, Point{x, new(big.Int).Sub(ec.Q, y)}, nil
 42}
 43
 44// TODO add valid checker point function Valid()
 45
 46// Neg returns the inverse of the P point on the elliptic curve
 47func (ec *EC) Neg(p Point) Point {
 48	// TODO get error when point not found on the ec
 49	return Point{p.X, new(big.Int).Sub(ec.Q, p.Y)}
 50}
 51
 52// Add adds two points p1 and p2 and gets q, returns the negate of q
 53func (ec *EC) Add(p1, p2 Point) (Point, error) {
 54	if p1.Equal(zeroPoint) {
 55		return p2, nil
 56	}
 57	if p2.Equal(zeroPoint) {
 58		return p1, nil
 59	}
 60
 61	var numerator, denominator, sRaw, s *big.Int
 62	if bytes.Equal(p1.X.Bytes(), p2.X.Bytes()) && (!bytes.Equal(p1.Y.Bytes(), p2.Y.Bytes()) || bytes.Equal(p1.Y.Bytes(), bigZero.Bytes())) {
 63		return zeroPoint, nil
 64	} else if bytes.Equal(p1.X.Bytes(), p2.X.Bytes()) {
 65		// use tangent as slope
 66		// x^2
 67		x2 := new(big.Int).Mul(p1.X, p1.X)
 68		// 3 * x^2
 69		x23 := new(big.Int).Mul(big.NewInt(int64(3)), x2)
 70		// 3 * x^2 + a
 71		numerator = new(big.Int).Add(x23, ec.A)
 72		// 2 * y
 73		denominator = new(big.Int).Mul(big.NewInt(int64(2)), p1.Y)
 74		// s = (3 * x^2 + a) / (2 * y) mod ec.Q
 75		denInv := new(big.Int).ModInverse(denominator, ec.Q)
 76		sRaw = new(big.Int).Mul(numerator, denInv)
 77		s = new(big.Int).Mod(sRaw, ec.Q)
 78	} else {
 79		// slope
 80		// y0-y1
 81		numerator = new(big.Int).Sub(p1.Y, p2.Y)
 82		// x0-x1
 83		denominator = new(big.Int).Sub(p1.X, p2.X)
 84		// s = (y0-y1) / (x0-x1) mod ec.Q
 85		denInv := new(big.Int).ModInverse(denominator, ec.Q)
 86		sRaw = new(big.Int).Mul(numerator, denInv)
 87		s = new(big.Int).Mod(sRaw, ec.Q)
 88	}
 89
 90	// q: new point
 91	var q Point
 92	// s^2
 93	s2 := new(big.Int).Exp(s, big.NewInt(int64(2)), nil)
 94	// s^2 - p1.X
 95	x2Xo := new(big.Int).Sub(s2, p1.X)
 96	// s^2 - p1.X - p2.X
 97	x2XoX2 := new(big.Int).Sub(x2Xo, p2.X)
 98	q.X = new(big.Int).Mod(x2XoX2, ec.Q)
 99
100	// p1.X - q.X
101	xoX2 := new(big.Int).Sub(p1.X, q.X)
102	// s(p1.X - q.X)
103	sXoX2 := new(big.Int).Mul(s, xoX2)
104	// s(p1.X - q.X) - p1.Y
105	sXoX2Y := new(big.Int).Sub(sXoX2, p1.Y)
106	// q.Y = (s(p1.X - q.X) - p1.Y) mod ec.Q
107	q.Y = new(big.Int).Mod(sXoX2Y, ec.Q)
108
109	// negate q
110	// q = ec.Neg(q)
111	return q, nil
112}
113
114// Mul multiplies a point n times on the elliptic curve
115func (ec *EC) Mul(p Point, n *big.Int) (Point, error) {
116	var err error
117	p2 := p
118	r := zeroPoint
119	for bigZero.Cmp(n) == -1 { // 0<n
120		z := new(big.Int).And(n, bigOne)            // n&1
121		if bytes.Equal(z.Bytes(), bigOne.Bytes()) { // n&1==1
122			r, err = ec.Add(r, p2)
123			if err != nil {
124				return p, err
125			}
126		}
127		n = n.Rsh(n, 1) // n = n>>1
128		p2, err = ec.Add(p2, p2)
129		if err != nil {
130			return p, err
131		}
132	}
133	return r, nil
134}
135
136// Order returns smallest n where nG = O (point at zero)
137func (ec *EC) Order(g Point) (*big.Int, error) {
138	// loop from i:=1 to i<ec.Q+1
139	start := big.NewInt(1)
140	end := new(big.Int).Add(ec.Q, bigOne)
141	for i := new(big.Int).Set(start); i.Cmp(end) <= 0; i.Add(i, bigOne) {
142		iCopy := new(big.Int).SetBytes(i.Bytes())
143		mPoint, err := ec.Mul(g, iCopy)
144		if err != nil {
145			return i, err
146		}
147		if mPoint.Equal(zeroPoint) {
148			return i, nil
149		}
150	}
151	return bigZero, errors.New("invalid order")
152}