1package babyjub
  2
  3import (
  4	"bytes"
  5	"fmt"
  6	"math/big"
  7
  8	"github.com/iden3/go-iden3-crypto/constants"
  9	"github.com/iden3/go-iden3-crypto/utils"
 10)
 11
 12// A is one of the babyjub constants.
 13var A *big.Int
 14
 15// D is one of the babyjub constants.
 16var D *big.Int
 17
 18// Order of the babyjub curve.
 19var Order *big.Int
 20
 21// SubOrder is the order of the subgroup of the babyjub curve that contains the
 22// points that we use.
 23var SubOrder *big.Int
 24
 25// B8 is a base point of the babyjub multiplied by 8 to make it a base point of
 26// the subgroup in the curve.
 27var B8 *Point
 28
 29// init initializes global numbers and the subgroup base.
 30func init() {
 31	A = utils.NewIntFromString("168700")
 32	D = utils.NewIntFromString("168696")
 33
 34	Order = utils.NewIntFromString(
 35		"21888242871839275222246405745257275088614511777268538073601725287587578984328")
 36	SubOrder = new(big.Int).Rsh(Order, 3)
 37
 38	B8 = NewPoint()
 39	B8.X = utils.NewIntFromString(
 40		"5299619240641551281634865583518297030282874472190772894086521144482721001553")
 41	B8.Y = utils.NewIntFromString(
 42		"16950150798460657717958625567821834550301663161624707787222815936182638968203")
 43}
 44
 45// PointProjective is the Point representation in projective coordinates
 46type PointProjective struct {
 47	X *big.Int
 48	Y *big.Int
 49	Z *big.Int
 50}
 51
 52// NewPointProjective creates a new Point in projective coordinates.
 53func NewPointProjective() *PointProjective {
 54	return &PointProjective{X: big.NewInt(0), Y: big.NewInt(1), Z: big.NewInt(1)}
 55}
 56
 57// Affine returns the Point from the projective representation
 58func (p *PointProjective) Affine() *Point {
 59	if bytes.Equal(p.Z.Bytes(), big.NewInt(0).Bytes()) {
 60		return &Point{
 61			X: big.NewInt(0),
 62			Y: big.NewInt(0),
 63		}
 64	}
 65	zinv := new(big.Int).ModInverse(p.Z, constants.Q)
 66	x := new(big.Int).Mul(p.X, zinv)
 67	x.Mod(x, constants.Q)
 68	y := new(big.Int).Mul(p.Y, zinv)
 69	y.Mod(y, constants.Q)
 70	return &Point{
 71		X: x,
 72		Y: y,
 73	}
 74}
 75
 76// Add computes the addition of two points in projective coordinates representation
 77func (res *PointProjective) Add(p *PointProjective, q *PointProjective) *PointProjective {
 78	// add-2008-bbjlp https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp
 79	a := new(big.Int).Mul(p.Z, q.Z)
 80	b := new(big.Int).Set(a)
 81	b.Exp(b, big.NewInt(2), constants.Q)
 82	c := new(big.Int).Mul(p.X, q.X)
 83	c.Mod(c, constants.Q) // apply Mod to reduce number file and speed computation
 84	d := new(big.Int).Mul(p.Y, q.Y)
 85	d.Mod(d, constants.Q)
 86	e := new(big.Int).Mul(D, c)
 87	e.Mul(e, d)
 88	e.Mod(e, constants.Q)
 89	f := new(big.Int).Sub(b, e)
 90	f.Mod(f, constants.Q)
 91	g := new(big.Int).Add(b, e)
 92	g.Mod(g, constants.Q)
 93	x1y1 := new(big.Int).Add(p.X, p.Y)
 94	x2y2 := new(big.Int).Add(q.X, q.Y)
 95	x3 := new(big.Int).Mul(x1y1, x2y2)
 96	x3.Sub(x3, c)
 97	x3.Sub(x3, d)
 98	x3.Mul(x3, a)
 99	x3.Mul(x3, f)
100	x3.Mod(x3, constants.Q)
101	ac := new(big.Int).Mul(A, c)
102	y3 := new(big.Int).Sub(d, ac)
103	y3.Mul(y3, a)
104	y3.Mul(y3, g)
105	y3.Mod(y3, constants.Q)
106	z3 := new(big.Int).Mul(f, g)
107	z3.Mod(z3, constants.Q)
108
109	res.X = x3
110	res.Y = y3
111	res.Z = z3
112	return res
113}
114
115// Point represents a point of the babyjub curve.
116type Point struct {
117	X *big.Int
118	Y *big.Int
119}
120
121// NewPoint creates a new Point.
122func NewPoint() *Point {
123	return &Point{X: big.NewInt(0), Y: big.NewInt(1)}
124}
125
126// Set copies a Point c into the Point p
127func (p *Point) Set(c *Point) *Point {
128	p.X.Set(c.X)
129	p.Y.Set(c.Y)
130	return p
131}
132
133// Projective returns a PointProjective from the Point
134func (p *Point) Projective() *PointProjective {
135	return &PointProjective{
136		X: p.X,
137		Y: p.Y,
138		Z: big.NewInt(1),
139	}
140}
141
142// Mul multiplies the Point p by the scalar s and stores the result in res,
143// which is also returned.
144func (res *Point) Mul(s *big.Int, p *Point) *Point {
145	resProj := &PointProjective{
146		X: big.NewInt(0),
147		Y: big.NewInt(1),
148		Z: big.NewInt(1),
149	}
150	exp := p.Projective()
151
152	for i := 0; i < s.BitLen(); i++ {
153		if s.Bit(i) == 1 {
154			resProj.Add(resProj, exp)
155		}
156		exp = exp.Add(exp, exp)
157	}
158	res = resProj.Affine()
159	return res
160}
161
162// InCurve returns true when the Point p is in the babyjub curve.
163func (p *Point) InCurve() bool {
164	x2 := new(big.Int).Set(p.X)
165	x2.Mul(x2, x2)
166	x2.Mod(x2, constants.Q)
167
168	y2 := new(big.Int).Set(p.Y)
169	y2.Mul(y2, y2)
170	y2.Mod(y2, constants.Q)
171
172	a := new(big.Int).Mul(A, x2)
173	a.Add(a, y2)
174	a.Mod(a, constants.Q)
175
176	b := new(big.Int).Set(D)
177	b.Mul(b, x2)
178	b.Mul(b, y2)
179	b.Add(constants.One, b)
180	b.Mod(b, constants.Q)
181
182	return a.Cmp(b) == 0
183}
184
185// InSubGroup returns true when the Point p is in the subgroup of the babyjub
186// curve.
187func (p *Point) InSubGroup() bool {
188	if !p.InCurve() {
189		return false
190	}
191	res := NewPoint().Mul(SubOrder, p)
192	return (res.X.Cmp(constants.Zero) == 0) && (res.Y.Cmp(constants.One) == 0)
193}
194
195// PointCoordSign returns the sign of the curve point coordinate.  It returns
196// false if the sign is positive and false if the sign is negative.
197func PointCoordSign(c *big.Int) bool {
198	return c.Cmp(new(big.Int).Rsh(constants.Q, 1)) == 1
199}
200
201func PackPoint(ay *big.Int, sign bool) [32]byte {
202	leBuf := utils.BigIntLEBytes(ay)
203	if sign {
204		leBuf[31] = leBuf[31] | 0x80
205	}
206	return leBuf
207}
208
209// Compress the point into a 32 byte array that contains the y coordinate in
210// little endian and the sign of the x coordinate.
211func (p *Point) Compress() [32]byte {
212	sign := PointCoordSign(p.X)
213	return PackPoint(p.Y, sign)
214}
215
216// Decompress a compressed Point into p, and also returns the decompressed
217// Point.  Returns error if the compressed Point is invalid.
218func (p *Point) Decompress(leBuf [32]byte) (*Point, error) {
219	sign := false
220	if (leBuf[31] & 0x80) != 0x00 {
221		sign = true
222		leBuf[31] = leBuf[31] & 0x7F
223	}
224	utils.SetBigIntFromLEBytes(p.Y, leBuf[:])
225	return PointFromSignAndY(sign, p.Y)
226}
227
228// PointFromSignAndY returns a Point from a Sign and the Y coordinate
229func PointFromSignAndY(sign bool, y *big.Int) (*Point, error) {
230	var p Point
231	p.X = big.NewInt(0)
232	p.Y = y
233	if p.Y.Cmp(constants.Q) >= 0 {
234		return nil, fmt.Errorf("p.y >= Q")
235	}
236
237	y2 := new(big.Int).Mul(p.Y, p.Y)
238	y2.Mod(y2, constants.Q)
239	xa := big.NewInt(1)
240	xa.Sub(xa, y2) // xa == 1 - y^2
241
242	xb := new(big.Int).Mul(D, y2)
243	xb.Mod(xb, constants.Q)
244	xb.Sub(A, xb) // xb = A - d * y^2
245
246	if xb.Cmp(big.NewInt(0)) == 0 {
247		return nil, fmt.Errorf("division by 0")
248	}
249	xb.ModInverse(xb, constants.Q)
250	p.X.Mul(xa, xb) // xa / xb
251	p.X.Mod(p.X, constants.Q)
252	noSqrt := p.X.ModSqrt(p.X, constants.Q)
253	if noSqrt == nil {
254		return nil, fmt.Errorf("x is not a square mod q")
255	}
256	if (sign && !PointCoordSign(p.X)) || (!sign && PointCoordSign(p.X)) {
257		p.X.Mul(p.X, constants.MinusOne)
258	}
259	p.X.Mod(p.X, constants.Q)
260
261	return &p, nil
262}