1// Copyright 2012 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package bn256
6
7import (
8	"math/big"
9)
10
11// twistPoint implements the elliptic curve y²=x³+3/ξ over GF(p²). Points are
12// kept in Jacobian form and t=z² when valid. The group G₂ is the set of
13// n-torsion points of this curve over GF(p²) (where n = Order)
14type twistPoint struct {
15	x, y, z, t *gfP2
16}
17
18var twistB = &gfP2{
19	bigFromBase10("6500054969564660373279643874235990574282535810762300357187714502686418407178"),
20	bigFromBase10("45500384786952622612957507119651934019977750675336102500314001518804928850249"),
21}
22
23// twistGen is the generator of group G₂.
24var twistGen = &twistPoint{
25	&gfP2{
26		bigFromBase10("21167961636542580255011770066570541300993051739349375019639421053990175267184"),
27		bigFromBase10("64746500191241794695844075326670126197795977525365406531717464316923369116492"),
28	},
29	&gfP2{
30		bigFromBase10("20666913350058776956210519119118544732556678129809273996262322366050359951122"),
31		bigFromBase10("17778617556404439934652658462602675281523610326338642107814333856843981424549"),
32	},
33	&gfP2{
34		bigFromBase10("0"),
35		bigFromBase10("1"),
36	},
37	&gfP2{
38		bigFromBase10("0"),
39		bigFromBase10("1"),
40	},
41}
42
43func newTwistPoint(pool *bnPool) *twistPoint {
44	return &twistPoint{
45		newGFp2(pool),
46		newGFp2(pool),
47		newGFp2(pool),
48		newGFp2(pool),
49	}
50}
51
52func (c *twistPoint) String() string {
53	return "(" + c.x.String() + ", " + c.y.String() + ", " + c.z.String() + ")"
54}
55
56func (c *twistPoint) Put(pool *bnPool) {
57	c.x.Put(pool)
58	c.y.Put(pool)
59	c.z.Put(pool)
60	c.t.Put(pool)
61}
62
63func (c *twistPoint) Set(a *twistPoint) {
64	c.x.Set(a.x)
65	c.y.Set(a.y)
66	c.z.Set(a.z)
67	c.t.Set(a.t)
68}
69
70// IsOnCurve returns true iff c is on the curve where c must be in affine form.
71func (c *twistPoint) IsOnCurve() bool {
72	pool := new(bnPool)
73	yy := newGFp2(pool).Square(c.y, pool)
74	xxx := newGFp2(pool).Square(c.x, pool)
75	xxx.Mul(xxx, c.x, pool)
76	yy.Sub(yy, xxx)
77	yy.Sub(yy, twistB)
78	yy.Minimal()
79	return yy.x.Sign() == 0 && yy.y.Sign() == 0
80}
81
82func (c *twistPoint) SetInfinity() {
83	c.z.SetZero()
84}
85
86func (c *twistPoint) IsInfinity() bool {
87	return c.z.IsZero()
88}
89
90func (c *twistPoint) Add(a, b *twistPoint, pool *bnPool) {
91	// For additional comments, see the same function in curve.go.
92
93	if a.IsInfinity() {
94		c.Set(b)
95		return
96	}
97	if b.IsInfinity() {
98		c.Set(a)
99		return
100	}
101
102	// See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
103	z1z1 := newGFp2(pool).Square(a.z, pool)
104	z2z2 := newGFp2(pool).Square(b.z, pool)
105	u1 := newGFp2(pool).Mul(a.x, z2z2, pool)
106	u2 := newGFp2(pool).Mul(b.x, z1z1, pool)
107
108	t := newGFp2(pool).Mul(b.z, z2z2, pool)
109	s1 := newGFp2(pool).Mul(a.y, t, pool)
110
111	t.Mul(a.z, z1z1, pool)
112	s2 := newGFp2(pool).Mul(b.y, t, pool)
113
114	h := newGFp2(pool).Sub(u2, u1)
115	xEqual := h.IsZero()
116
117	t.Add(h, h)
118	i := newGFp2(pool).Square(t, pool)
119	j := newGFp2(pool).Mul(h, i, pool)
120
121	t.Sub(s2, s1)
122	yEqual := t.IsZero()
123	if xEqual && yEqual {
124		c.Double(a, pool)
125		return
126	}
127	r := newGFp2(pool).Add(t, t)
128
129	v := newGFp2(pool).Mul(u1, i, pool)
130
131	t4 := newGFp2(pool).Square(r, pool)
132	t.Add(v, v)
133	t6 := newGFp2(pool).Sub(t4, j)
134	c.x.Sub(t6, t)
135
136	t.Sub(v, c.x)       // t7
137	t4.Mul(s1, j, pool) // t8
138	t6.Add(t4, t4)      // t9
139	t4.Mul(r, t, pool)  // t10
140	c.y.Sub(t4, t6)
141
142	t.Add(a.z, b.z)    // t11
143	t4.Square(t, pool) // t12
144	t.Sub(t4, z1z1)    // t13
145	t4.Sub(t, z2z2)    // t14
146	c.z.Mul(t4, h, pool)
147
148	z1z1.Put(pool)
149	z2z2.Put(pool)
150	u1.Put(pool)
151	u2.Put(pool)
152	t.Put(pool)
153	s1.Put(pool)
154	s2.Put(pool)
155	h.Put(pool)
156	i.Put(pool)
157	j.Put(pool)
158	r.Put(pool)
159	v.Put(pool)
160	t4.Put(pool)
161	t6.Put(pool)
162}
163
164func (c *twistPoint) Double(a *twistPoint, pool *bnPool) {
165	// See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
166	A := newGFp2(pool).Square(a.x, pool)
167	B := newGFp2(pool).Square(a.y, pool)
168	C := newGFp2(pool).Square(B, pool)
169
170	t := newGFp2(pool).Add(a.x, B)
171	t2 := newGFp2(pool).Square(t, pool)
172	t.Sub(t2, A)
173	t2.Sub(t, C)
174	d := newGFp2(pool).Add(t2, t2)
175	t.Add(A, A)
176	e := newGFp2(pool).Add(t, A)
177	f := newGFp2(pool).Square(e, pool)
178
179	t.Add(d, d)
180	c.x.Sub(f, t)
181
182	t.Add(C, C)
183	t2.Add(t, t)
184	t.Add(t2, t2)
185	c.y.Sub(d, c.x)
186	t2.Mul(e, c.y, pool)
187	c.y.Sub(t2, t)
188
189	t.Mul(a.y, a.z, pool)
190	c.z.Add(t, t)
191
192	A.Put(pool)
193	B.Put(pool)
194	C.Put(pool)
195	t.Put(pool)
196	t2.Put(pool)
197	d.Put(pool)
198	e.Put(pool)
199	f.Put(pool)
200}
201
202func (c *twistPoint) Mul(a *twistPoint, scalar *big.Int, pool *bnPool) *twistPoint {
203	sum := newTwistPoint(pool)
204	sum.SetInfinity()
205	t := newTwistPoint(pool)
206
207	for i := scalar.BitLen(); i >= 0; i-- {
208		t.Double(sum, pool)
209		if scalar.Bit(i) != 0 {
210			sum.Add(t, a, pool)
211		} else {
212			sum.Set(t)
213		}
214	}
215
216	c.Set(sum)
217	sum.Put(pool)
218	t.Put(pool)
219	return c
220}
221
222// MakeAffine converts c to affine form and returns c. If c is ∞, then it sets
223// c to 0 : 1 : 0.
224func (c *twistPoint) MakeAffine(pool *bnPool) *twistPoint {
225	if c.z.IsOne() {
226		return c
227	}
228	if c.IsInfinity() {
229		c.x.SetZero()
230		c.y.SetOne()
231		c.z.SetZero()
232		c.t.SetZero()
233		return c
234	}
235
236	zInv := newGFp2(pool).Invert(c.z, pool)
237	t := newGFp2(pool).Mul(c.y, zInv, pool)
238	zInv2 := newGFp2(pool).Square(zInv, pool)
239	c.y.Mul(t, zInv2, pool)
240	t.Mul(c.x, zInv2, pool)
241	c.x.Set(t)
242	c.z.SetOne()
243	c.t.SetOne()
244
245	zInv.Put(pool)
246	t.Put(pool)
247	zInv2.Put(pool)
248
249	return c
250}
251
252func (c *twistPoint) Negative(a *twistPoint, pool *bnPool) {
253	c.x.Set(a.x)
254	c.y.SetZero()
255	c.y.Sub(c.y, a.y)
256	c.z.Set(a.z)
257	c.t.SetZero()
258}
259