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// Order returns smallest n where nG = O (point at zero)
 53func (ec *EC) Order(g Point) (int, error) {
 54	for i := 1; i < int(ec.Q.Int64())+1; i++ {
 55		mPoint, err := ec.Mul(g, i)
 56		if err != nil {
 57			return i, err
 58		}
 59		if mPoint.Equal(zeroPoint) {
 60			return i, nil
 61		}
 62	}
 63	return -1, errors.New("invalid order")
 64}
 65
 66// Add adds two points p1 and p2 and gets q, returns the negate of q
 67func (ec *EC) Add(p1, p2 Point) (Point, error) {
 68	if p1.Equal(zeroPoint) {
 69		return p2, nil
 70	}
 71	if p2.Equal(zeroPoint) {
 72		return p1, nil
 73	}
 74
 75	var numerator, denominator, sRaw, s *big.Int
 76	if bytes.Equal(p1.X.Bytes(), p2.X.Bytes()) && (!bytes.Equal(p1.Y.Bytes(), p2.Y.Bytes()) || bytes.Equal(p1.Y.Bytes(), bigZero.Bytes())) {
 77		return zeroPoint, nil
 78	} else if bytes.Equal(p1.X.Bytes(), p2.X.Bytes()) {
 79		// use tangent as slope
 80		// x^2
 81		x2 := new(big.Int).Mul(p1.X, p1.X)
 82		// 3 * x^2
 83		x23 := new(big.Int).Mul(big.NewInt(int64(3)), x2)
 84		// 3 * x^2 + a
 85		numerator = new(big.Int).Add(x23, ec.A)
 86		// 2 * y
 87		denominator = new(big.Int).Mul(big.NewInt(int64(2)), p1.Y)
 88		// s = (3 * x^2 + a) / (2 * y) mod ec.Q
 89		denInv := new(big.Int).ModInverse(denominator, ec.Q)
 90		sRaw = new(big.Int).Mul(numerator, denInv)
 91		s = new(big.Int).Mod(sRaw, ec.Q)
 92	} else {
 93		// slope
 94		// y0-y1
 95		numerator = new(big.Int).Sub(p1.Y, p2.Y)
 96		// x0-x1
 97		denominator = new(big.Int).Sub(p1.X, p2.X)
 98		// s = (y0-y1) / (x0-x1) mod ec.Q
 99		denInv := new(big.Int).ModInverse(denominator, ec.Q)
100		sRaw = new(big.Int).Mul(numerator, denInv)
101		s = new(big.Int).Mod(sRaw, ec.Q)
102	}
103
104	// q: new point
105	var q Point
106	// s^2
107	s2 := new(big.Int).Exp(s, big.NewInt(int64(2)), nil)
108	// s^2 - p1.X
109	x2Xo := new(big.Int).Sub(s2, p1.X)
110	// s^2 - p1.X - p2.X
111	x2XoX2 := new(big.Int).Sub(x2Xo, p2.X)
112	q.X = new(big.Int).Mod(x2XoX2, ec.Q)
113
114	// p1.X - q.X
115	xoX2 := new(big.Int).Sub(p1.X, q.X)
116	// s(p1.X - q.X)
117	sXoX2 := new(big.Int).Mul(s, xoX2)
118	// s(p1.X - q.X) - p1.Y
119	sXoX2Y := new(big.Int).Sub(sXoX2, p1.Y)
120	// q.Y = (s(p1.X - q.X) - p1.Y) mod ec.Q
121	q.Y = new(big.Int).Mod(sXoX2Y, ec.Q)
122
123	// negate q
124	// q = ec.Neg(q)
125	return q, nil
126}
127
128// Mul multiplies a point n times on the elliptic curve
129func (ec *EC) Mul(p Point, n int) (Point, error) {
130	var err error
131	p2 := p
132	r := zeroPoint
133	for 0 < n {
134		if n&1 == 1 {
135			r, err = ec.Add(r, p2)
136			if err != nil {
137				return p, err
138			}
139		}
140		n = n >> 1
141		p2, err = ec.Add(p2, p2)
142		if err != nil {
143			return p, err
144		}
145
146	}
147	return r, nil
148}