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