1package ecc
  2
  3import (
  4	"bytes"
  5	"errors"
  6	"math/big"
  7)
  8
  9type EC struct {
 10	A *big.Int
 11	B *big.Int
 12	Q *big.Int
 13}
 14
 15// NewEC (y^2 = x^3 + ax + b) mod q, where q is a prime number
 16func NewEC(a, b, q int) (ec EC) {
 17	ec.A = big.NewInt(int64(a))
 18	ec.B = big.NewInt(int64(b))
 19	ec.Q = big.NewInt(int64(q))
 20	return ec
 21}
 22
 23// At gets a point x in the curve
 24func (ec *EC) At(x *big.Int) (Point, Point, error) {
 25	if x.Cmp(ec.Q) > 0 {
 26		return Point{}, Point{}, errors.New("x<ec.Q")
 27	}
 28	// y^2 = (x^3 + ax + b) mod q
 29	// y = sqrt (x^3 + ax + b) mod q
 30	// x^3
 31	x3 := new(big.Int).Exp(x, big.NewInt(int64(3)), nil)
 32	// a^x
 33	aX := new(big.Int).Mul(ec.A, x)
 34	// x^3 + a^x
 35	x3aX := new(big.Int).Add(x3, aX)
 36	// x^3 + a^x + b
 37	x3aXb := new(big.Int).Add(x3aX, ec.B)
 38	// y = sqrt (x^3 + ax + b) mod q
 39	y := new(big.Int).ModSqrt(x3aXb, ec.Q)
 40	return Point{x, y}, Point{x, new(big.Int).Sub(ec.Q, y)}, nil
 41}
 42
 43// TODO add valid checker point function
 44
 45func (ec *EC) Neg(p Point) Point {
 46	// TODO get error when point not found on the ec
 47	return Point{p.X, new(big.Int).Sub(ec.Q, p.Y)}
 48}
 49
 50// Add adds two points p1 and p2 and gets q
 51func (ec *EC) Add(p1, p2 Point) (Point, error) {
 52	if p1.Equal(zeroPoint) {
 53		return p2, nil
 54	}
 55	if p2.Equal(zeroPoint) {
 56		return p1, nil
 57	}
 58
 59	var numerator, denominator, sRaw, s *big.Int
 60	if bytes.Equal(p1.X.Bytes(), p2.X.Bytes()) && (!bytes.Equal(p1.Y.Bytes(), p2.Y.Bytes()) || bytes.Equal(p1.Y.Bytes(), bigZero.Bytes())) {
 61		return zeroPoint, nil
 62	} else if bytes.Equal(p1.X.Bytes(), p2.X.Bytes()) {
 63		// use tangent as slope
 64		// x^2
 65		x2 := new(big.Int).Mul(p1.X, p1.X)
 66		// 3 * x^2
 67		x23 := new(big.Int).Mul(big.NewInt(int64(3)), x2)
 68		// 3 * x^2 + a
 69		numerator = new(big.Int).Add(x23, ec.A)
 70		// 2 * y
 71		denominator = new(big.Int).Mul(big.NewInt(int64(2)), p1.Y)
 72		// (3 * x^2 + a) / (2 * y) mod ec.Q
 73		denInv := new(big.Int).ModInverse(denominator, ec.Q)
 74		sRaw = new(big.Int).Mul(numerator, denInv)
 75		s = new(big.Int).Mod(sRaw, ec.Q)
 76	} else {
 77		// slope
 78		// y0-y1
 79		numerator = new(big.Int).Sub(p1.Y, p2.Y)
 80		// x0-x1
 81		denominator = new(big.Int).Sub(p1.X, p2.X)
 82		// (y0-y1) / (x0-x1) mod ec.Q
 83		denInv := new(big.Int).ModInverse(denominator, ec.Q)
 84		sRaw = new(big.Int).Mul(numerator, denInv)
 85		s = new(big.Int).Mod(sRaw, ec.Q)
 86	}
 87
 88	// q: new point
 89	var q Point
 90	// s^2
 91	s2 := new(big.Int).Exp(s, big.NewInt(int64(2)), nil)
 92	// s^2 - p1.X
 93	x2Xo := new(big.Int).Sub(s2, p1.X)
 94	// s^2 - p1.X - p2.X
 95	x2XoX2 := new(big.Int).Sub(x2Xo, p2.X)
 96	q.X = new(big.Int).Mod(x2XoX2, ec.Q)
 97
 98	// p1.X - q.X
 99	xoX2 := new(big.Int).Sub(p1.X, q.X)
100	// s(p1.X - q.X)
101	sXoX2 := new(big.Int).Mul(s, xoX2)
102	// s(p1.X - q.X) - p1.Y
103	sXoX2Y := new(big.Int).Sub(sXoX2, p1.Y)
104	// q.Y = (s(p1.X - q.X) - p1.Y) mod ec.Q
105	q.Y = new(big.Int).Mod(sXoX2Y, ec.Q)
106
107	return q, nil
108}
109
110// Mul multiplies a point n times on the elliptic curve
111func (ec *EC) Mul(p Point, n int) (Point, error) {
112	var err error
113	for i := 0; i < n; i++ {
114		p, err = ec.Add(p, p)
115		if err != nil {
116			return zeroPoint, err
117		}
118	}
119	return p, nil
120}