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