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// PackSignY packs the given sign and the coordinate Y of a point into a 32
207// byte array. This method does not check that the values belong to a valid
208// Point in the curve.
209func PackSignY(sign bool, y *big.Int) [32]byte {
210	leBuf := utils.BigIntLEBytes(y)
211	if sign {
212		leBuf[31] = leBuf[31] | 0x80 //nolint:gomnd
213	}
214	return leBuf
215}
216
217// UnpackSignY returns the sign and coordinate Y from a given compressed point.
218// This method does not check that the Point belongs to the BabyJubJub curve,
219// thus does not return error in such case. This method is intended to obtain
220// the sign and the Y coordinate without checking if the point belongs to the
221// curve, if the objective is to uncompress a point, Decompress method should
222// be used instead.
223func UnpackSignY(leBuf [32]byte) (bool, *big.Int) {
224	sign := false
225	y := big.NewInt(0)
226	if (leBuf[31] & 0x80) != 0x00 { //nolint:gomnd
227		sign = true
228		leBuf[31] = leBuf[31] & 0x7F //nolint:gomnd
229	}
230	utils.SetBigIntFromLEBytes(y, leBuf[:])
231	return sign, y
232}
233
234// Compress the point into a 32 byte array that contains the y coordinate in
235// little endian and the sign of the x coordinate.
236func (p *Point) Compress() [32]byte {
237	sign := PointCoordSign(p.X)
238	return PackSignY(sign, p.Y)
239}
240
241// Decompress a compressed Point into p, and also returns the decompressed
242// Point.  Returns error if the compressed Point is invalid.
243func (p *Point) Decompress(leBuf [32]byte) (*Point, error) {
244	var sign bool
245	sign, p.Y = UnpackSignY(leBuf)
246	return PointFromSignAndY(sign, p.Y)
247}
248
249// PointFromSignAndY returns a Point from a Sign and the Y coordinate
250func PointFromSignAndY(sign bool, y *big.Int) (*Point, error) {
251	var p Point
252	p.X = big.NewInt(0)
253	p.Y = y
254	if p.Y.Cmp(constants.Q) >= 0 {
255		return nil, fmt.Errorf("p.y >= Q")
256	}
257
258	y2 := new(big.Int).Mul(p.Y, p.Y)
259	y2.Mod(y2, constants.Q)
260	xa := big.NewInt(1)
261	xa.Sub(xa, y2) // xa == 1 - y^2
262
263	xb := new(big.Int).Mul(D, y2)
264	xb.Mod(xb, constants.Q)
265	xb.Sub(A, xb) // xb = A - d * y^2
266
267	if xb.Cmp(big.NewInt(0)) == 0 {
268		return nil, fmt.Errorf("division by 0")
269	}
270	xb.ModInverse(xb, constants.Q)
271	p.X.Mul(xa, xb) // xa / xb
272	p.X.Mod(p.X, constants.Q)
273	noSqrt := p.X.ModSqrt(p.X, constants.Q)
274	if noSqrt == nil {
275		return nil, fmt.Errorf("x is not a square mod q")
276	}
277	if (sign && !PointCoordSign(p.X)) || (!sign && PointCoordSign(p.X)) {
278		p.X.Mul(p.X, constants.MinusOne)
279	}
280	p.X.Mod(p.X, constants.Q)
281
282	return &p, nil
283}