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(),
 63		Y: ff.NewElement().SetOne(), Z: ff.NewElement().SetOne()}
 64}
 65
 66// Affine returns the Point from the projective representation
 67func (p *PointProjective) Affine() *Point {
 68	if p.Z.Equal(ff.NewElement().SetZero()) {
 69		return &Point{
 70			X: big.NewInt(0),
 71			Y: big.NewInt(0),
 72		}
 73	}
 74	zinv := ff.NewElement().Inverse(p.Z)
 75	x := ff.NewElement().Mul(p.X, zinv)
 76
 77	y := ff.NewElement().Mul(p.Y, zinv)
 78	xBig := big.NewInt(0)
 79	x.ToBigIntRegular(xBig)
 80	yBig := big.NewInt(0)
 81	y.ToBigIntRegular(yBig)
 82	return &Point{
 83		X: xBig,
 84		Y: yBig,
 85	}
 86}
 87
 88// Add computes the addition of two points in projective coordinates
 89// representation
 90func (p *PointProjective) Add(q *PointProjective, o *PointProjective) *PointProjective {
 91	// add-2008-bbjlp
 92	// https://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html#doubling-dbl-2008-bbjlp
 93	a := ff.NewElement().Mul(q.Z, o.Z)
 94	b := ff.NewElement().Square(a)
 95	c := ff.NewElement().Mul(q.X, o.X)
 96	d := ff.NewElement().Mul(q.Y, o.Y)
 97	e := ff.NewElement().Mul(Dff, c)
 98	e.MulAssign(d)
 99	f := ff.NewElement().Sub(b, e)
100	g := ff.NewElement().Add(b, e)
101	x1y1 := ff.NewElement().Add(q.X, q.Y)
102	x2y2 := ff.NewElement().Add(o.X, o.Y)
103	x3 := ff.NewElement().Mul(x1y1, x2y2)
104	x3.SubAssign(c)
105	x3.SubAssign(d)
106	x3.MulAssign(a)
107	x3.MulAssign(f)
108	ac := ff.NewElement().Mul(Aff, c)
109	y3 := ff.NewElement().Sub(d, ac)
110	y3.MulAssign(a)
111	y3.MulAssign(g)
112	z3 := ff.NewElement().Mul(f, g)
113
114	p.X = x3
115	p.Y = y3
116	p.Z = z3
117	return p
118}
119
120// Point represents a point of the babyjub curve.
121type Point struct {
122	X *big.Int
123	Y *big.Int
124}
125
126// NewPoint creates a new Point.
127func NewPoint() *Point {
128	return &Point{X: big.NewInt(0), Y: big.NewInt(1)}
129}
130
131// Set copies a Point c into the Point p
132func (p *Point) Set(c *Point) *Point {
133	p.X.Set(c.X)
134	p.Y.Set(c.Y)
135	return p
136}
137
138// Projective returns a PointProjective from the Point
139func (p *Point) Projective() *PointProjective {
140	return &PointProjective{
141		X: ff.NewElement().SetBigInt(p.X),
142		Y: ff.NewElement().SetBigInt(p.Y),
143		Z: ff.NewElement().SetOne(),
144	}
145}
146
147// Mul multiplies the Point q by the scalar s and stores the result in p,
148// which is also returned.
149func (p *Point) Mul(s *big.Int, q *Point) *Point {
150	resProj := &PointProjective{
151		X: ff.NewElement().SetZero(),
152		Y: ff.NewElement().SetOne(),
153		Z: ff.NewElement().SetOne(),
154	}
155	exp := q.Projective()
156
157	for i := 0; i < s.BitLen(); i++ {
158		if s.Bit(i) == 1 {
159			resProj.Add(resProj, exp)
160		}
161		exp = exp.Add(exp, exp)
162	}
163	p = resProj.Affine()
164	return p
165}
166
167// InCurve returns true when the Point p is in the babyjub curve.
168func (p *Point) InCurve() bool {
169	x2 := new(big.Int).Set(p.X)
170	x2.Mul(x2, x2)
171	x2.Mod(x2, constants.Q)
172
173	y2 := new(big.Int).Set(p.Y)
174	y2.Mul(y2, y2)
175	y2.Mod(y2, constants.Q)
176
177	a := new(big.Int).Mul(A, x2)
178	a.Add(a, y2)
179	a.Mod(a, constants.Q)
180
181	b := new(big.Int).Set(D)
182	b.Mul(b, x2)
183	b.Mul(b, y2)
184	b.Add(constants.One, b)
185	b.Mod(b, constants.Q)
186
187	return a.Cmp(b) == 0
188}
189
190// InSubGroup returns true when the Point p is in the subgroup of the babyjub
191// curve.
192func (p *Point) InSubGroup() bool {
193	if !p.InCurve() {
194		return false
195	}
196	res := NewPoint().Mul(SubOrder, p)
197	return (res.X.Cmp(constants.Zero) == 0) && (res.Y.Cmp(constants.One) == 0)
198}
199
200// PointCoordSign returns the sign of the curve point coordinate.  It returns
201// false if the sign is positive and false if the sign is negative.
202func PointCoordSign(c *big.Int) bool {
203	return c.Cmp(new(big.Int).Rsh(constants.Q, 1)) == 1
204}
205
206// PackPoint packs a point into a 32 byte array
207func PackPoint(ay *big.Int, sign bool) [32]byte {
208	leBuf := utils.BigIntLEBytes(ay)
209	if sign {
210		leBuf[31] = leBuf[31] | 0x80 //nolint:gomnd
211	}
212	return leBuf
213}
214
215// Compress the point into a 32 byte array that contains the y coordinate in
216// little endian and the sign of the x coordinate.
217func (p *Point) Compress() [32]byte {
218	sign := PointCoordSign(p.X)
219	return PackPoint(p.Y, sign)
220}
221
222// Decompress a compressed Point into p, and also returns the decompressed
223// Point.  Returns error if the compressed Point is invalid.
224func (p *Point) Decompress(leBuf [32]byte) (*Point, error) {
225	sign := false
226	if (leBuf[31] & 0x80) != 0x00 { //nolint:gomnd
227		sign = true
228		leBuf[31] = leBuf[31] & 0x7F //nolint:gomnd
229	}
230	utils.SetBigIntFromLEBytes(p.Y, leBuf[:])
231	return PointFromSignAndY(sign, p.Y)
232}
233
234// PointFromSignAndY returns a Point from a Sign and the Y coordinate
235func PointFromSignAndY(sign bool, y *big.Int) (*Point, error) {
236	var p Point
237	p.X = big.NewInt(0)
238	p.Y = y
239	if p.Y.Cmp(constants.Q) >= 0 {
240		return nil, fmt.Errorf("p.y >= Q")
241	}
242
243	y2 := new(big.Int).Mul(p.Y, p.Y)
244	y2.Mod(y2, constants.Q)
245	xa := big.NewInt(1)
246	xa.Sub(xa, y2) // xa == 1 - y^2
247
248	xb := new(big.Int).Mul(D, y2)
249	xb.Mod(xb, constants.Q)
250	xb.Sub(A, xb) // xb = A - d * y^2
251
252	if xb.Cmp(big.NewInt(0)) == 0 {
253		return nil, fmt.Errorf("division by 0")
254	}
255	xb.ModInverse(xb, constants.Q)
256	p.X.Mul(xa, xb) // xa / xb
257	p.X.Mod(p.X, constants.Q)
258	noSqrt := p.X.ModSqrt(p.X, constants.Q)
259	if noSqrt == nil {
260		return nil, fmt.Errorf("x is not a square mod q")
261	}
262	if (sign && !PointCoordSign(p.X)) || (!sign && PointCoordSign(p.X)) {
263		p.X.Mul(p.X, constants.MinusOne)
264	}
265	p.X.Mod(p.X, constants.Q)
266
267	return &p, nil
268}