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 5// Package bn256 implements a particular bilinear group. 6// 7// Bilinear groups are the basis of many of the new cryptographic protocols 8// that have been proposed over the past decade. They consist of a triplet of 9// groups (G₁, G₂ and GT) such that there exists a function e(g₁ˣ,g₂ʸ)=gTˣʸ 10// (where gₓ is a generator of the respective group). That function is called 11// a pairing function. 12// 13// This package specifically implements the Optimal Ate pairing over a 256-bit 14// Barreto-Naehrig curve as described in 15// http://cryptojedi.org/papers/dclxvi-20100714.pdf. Its output is compatible 16// with the implementation described in that paper. 17// 18// (This package previously claimed to operate at a 128-bit security level. 19// However, recent improvements in attacks mean that is no longer true. See 20// https://moderncrypto.org/mail-archive/curves/2016/000740.html.) 21package bn256 22 23import ( 24 "crypto/rand" 25 "errors" 26 "io" 27 "math/big" 28) 29 30// BUG(agl): this implementation is not constant time. 31// TODO(agl): keep GF(p²) elements in Mongomery form. 32 33// G1 is an abstract cyclic group. The zero value is suitable for use as the 34// output of an operation, but cannot be used as an input. 35type G1 struct { 36 p *curvePoint 37} 38 39// RandomG1 returns x and g₁ˣ where x is a random, non-zero number read from r. 40func RandomG1(r io.Reader) (*big.Int, *G1, error) { 41 var k *big.Int 42 var err error 43 44 for { 45 k, err = rand.Int(r, Order) 46 if err != nil { 47 return nil, nil, err 48 } 49 if k.Sign() > 0 { 50 break 51 } 52 } 53 54 return k, new(G1).ScalarBaseMult(k), nil 55} 56 57func (e *G1) String() string { 58 return "bn256.G1" + e.p.String() 59} 60 61// CurvePoints returns p's curve points in big integer 62func (e *G1) CurvePoints() (*big.Int, *big.Int, *big.Int, *big.Int) { 63 return e.p.x, e.p.y, e.p.z, e.p.t 64} 65 66// ScalarBaseMult sets e to g*k where g is the generator of the group and 67// then returns e. 68func (e *G1) ScalarBaseMult(k *big.Int) *G1 { 69 if e.p == nil { 70 e.p = newCurvePoint(nil) 71 } 72 e.p.Mul(curveGen, k, new(bnPool)) 73 return e 74} 75 76// ScalarMult sets e to a*k and then returns e. 77func (e *G1) ScalarMult(a *G1, k *big.Int) *G1 { 78 if e.p == nil { 79 e.p = newCurvePoint(nil) 80 } 81 e.p.Mul(a.p, k, new(bnPool)) 82 return e 83} 84 85// Add sets e to a+b and then returns e. 86// BUG(agl): this function is not complete: a==b fails. 87func (e *G1) Add(a, b *G1) *G1 { 88 if e.p == nil { 89 e.p = newCurvePoint(nil) 90 } 91 e.p.Add(a.p, b.p, new(bnPool)) 92 return e 93} 94 95// Neg sets e to -a and then returns e. 96func (e *G1) Neg(a *G1) *G1 { 97 if e.p == nil { 98 e.p = newCurvePoint(nil) 99 } 100 e.p.Negative(a.p) 101 return e 102} 103 104// Marshal converts n to a byte slice. 105func (e *G1) Marshal() []byte { 106 // Each value is a 256-bit number. 107 const numBytes = 256 / 8 108 109 if e.p.IsInfinity() { 110 return make([]byte, numBytes*2) 111 } 112 113 e.p.MakeAffine(nil) 114 115 xBytes := new(big.Int).Mod(e.p.x, P).Bytes() 116 yBytes := new(big.Int).Mod(e.p.y, P).Bytes() 117 118 ret := make([]byte, numBytes*2) 119 copy(ret[1*numBytes-len(xBytes):], xBytes) 120 copy(ret[2*numBytes-len(yBytes):], yBytes) 121 122 return ret 123} 124 125// Unmarshal sets e to the result of converting the output of Marshal back into 126// a group element and then returns e. 127func (e *G1) Unmarshal(m []byte) ([]byte, error) { 128 // Each value is a 256-bit number. 129 const numBytes = 256 / 8 130 if len(m) != 2*numBytes { 131 return nil, errors.New("bn256: not enough data") 132 } 133 // Unmarshal the points and check their caps 134 if e.p == nil { 135 e.p = newCurvePoint(nil) 136 } 137 e.p.x.SetBytes(m[0*numBytes : 1*numBytes]) 138 if e.p.x.Cmp(P) >= 0 { 139 return nil, errors.New("bn256: coordinate exceeds modulus") 140 } 141 e.p.y.SetBytes(m[1*numBytes : 2*numBytes]) 142 if e.p.y.Cmp(P) >= 0 { 143 return nil, errors.New("bn256: coordinate exceeds modulus") 144 } 145 // Ensure the point is on the curve 146 if e.p.x.Sign() == 0 && e.p.y.Sign() == 0 { 147 // This is the point at infinity. 148 e.p.y.SetInt64(1) 149 e.p.z.SetInt64(0) 150 e.p.t.SetInt64(0) 151 } else { 152 e.p.z.SetInt64(1) 153 e.p.t.SetInt64(1) 154 155 if !e.p.IsOnCurve() { 156 return nil, errors.New("bn256: malformed point") 157 } 158 } 159 return m[2*numBytes:], nil 160} 161 162// G2 is an abstract cyclic group. The zero value is suitable for use as the 163// output of an operation, but cannot be used as an input. 164type G2 struct { 165 p *twistPoint 166} 167 168// RandomG1 returns x and g₂ˣ where x is a random, non-zero number read from r. 169func RandomG2(r io.Reader) (*big.Int, *G2, error) { 170 var k *big.Int 171 var err error 172 173 for { 174 k, err = rand.Int(r, Order) 175 if err != nil { 176 return nil, nil, err 177 } 178 if k.Sign() > 0 { 179 break 180 } 181 } 182 183 return k, new(G2).ScalarBaseMult(k), nil 184} 185 186func (e *G2) String() string { 187 return "bn256.G2" + e.p.String() 188} 189 190// CurvePoints returns the curve points of p which includes the real 191// and imaginary parts of the curve point. 192func (e *G2) CurvePoints() (*gfP2, *gfP2, *gfP2, *gfP2) { 193 return e.p.x, e.p.y, e.p.z, e.p.t 194} 195 196// ScalarBaseMult sets e to g*k where g is the generator of the group and 197// then returns out. 198func (e *G2) ScalarBaseMult(k *big.Int) *G2 { 199 if e.p == nil { 200 e.p = newTwistPoint(nil) 201 } 202 e.p.Mul(twistGen, k, new(bnPool)) 203 return e 204} 205 206// ScalarMult sets e to a*k and then returns e. 207func (e *G2) ScalarMult(a *G2, k *big.Int) *G2 { 208 if e.p == nil { 209 e.p = newTwistPoint(nil) 210 } 211 e.p.Mul(a.p, k, new(bnPool)) 212 return e 213} 214 215// Add sets e to a+b and then returns e. 216// BUG(agl): this function is not complete: a==b fails. 217func (e *G2) Add(a, b *G2) *G2 { 218 if e.p == nil { 219 e.p = newTwistPoint(nil) 220 } 221 e.p.Add(a.p, b.p, new(bnPool)) 222 return e 223} 224 225// Marshal converts n into a byte slice. 226func (n *G2) Marshal() []byte { 227 // Each value is a 256-bit number. 228 const numBytes = 256 / 8 229 230 if n.p.IsInfinity() { 231 return make([]byte, numBytes*4) 232 } 233 234 n.p.MakeAffine(nil) 235 236 xxBytes := new(big.Int).Mod(n.p.x.x, P).Bytes() 237 xyBytes := new(big.Int).Mod(n.p.x.y, P).Bytes() 238 yxBytes := new(big.Int).Mod(n.p.y.x, P).Bytes() 239 yyBytes := new(big.Int).Mod(n.p.y.y, P).Bytes() 240 241 ret := make([]byte, numBytes*4) 242 copy(ret[1*numBytes-len(xxBytes):], xxBytes) 243 copy(ret[2*numBytes-len(xyBytes):], xyBytes) 244 copy(ret[3*numBytes-len(yxBytes):], yxBytes) 245 copy(ret[4*numBytes-len(yyBytes):], yyBytes) 246 247 return ret 248} 249 250// Unmarshal sets e to the result of converting the output of Marshal back into 251// a group element and then returns e. 252func (e *G2) Unmarshal(m []byte) ([]byte, error) { 253 // Each value is a 256-bit number. 254 const numBytes = 256 / 8 255 if len(m) != 4*numBytes { 256 return nil, errors.New("bn256: not enough data") 257 } 258 // Unmarshal the points and check their caps 259 if e.p == nil { 260 e.p = newTwistPoint(nil) 261 } 262 e.p.x.x.SetBytes(m[0*numBytes : 1*numBytes]) 263 if e.p.x.x.Cmp(P) >= 0 { 264 return nil, errors.New("bn256: coordinate exceeds modulus") 265 } 266 e.p.x.y.SetBytes(m[1*numBytes : 2*numBytes]) 267 if e.p.x.y.Cmp(P) >= 0 { 268 return nil, errors.New("bn256: coordinate exceeds modulus") 269 } 270 e.p.y.x.SetBytes(m[2*numBytes : 3*numBytes]) 271 if e.p.y.x.Cmp(P) >= 0 { 272 return nil, errors.New("bn256: coordinate exceeds modulus") 273 } 274 e.p.y.y.SetBytes(m[3*numBytes : 4*numBytes]) 275 if e.p.y.y.Cmp(P) >= 0 { 276 return nil, errors.New("bn256: coordinate exceeds modulus") 277 } 278 // Ensure the point is on the curve 279 if e.p.x.x.Sign() == 0 && 280 e.p.x.y.Sign() == 0 && 281 e.p.y.x.Sign() == 0 && 282 e.p.y.y.Sign() == 0 { 283 // This is the point at infinity. 284 e.p.y.SetOne() 285 e.p.z.SetZero() 286 e.p.t.SetZero() 287 } else { 288 e.p.z.SetOne() 289 e.p.t.SetOne() 290 291 if !e.p.IsOnCurve() { 292 return nil, errors.New("bn256: malformed point") 293 } 294 } 295 return m[4*numBytes:], nil 296} 297 298// GT is an abstract cyclic group. The zero value is suitable for use as the 299// output of an operation, but cannot be used as an input. 300type GT struct { 301 p *gfP12 302} 303 304func (g *GT) String() string { 305 return "bn256.GT" + g.p.String() 306} 307 308// ScalarMult sets e to a*k and then returns e. 309func (e *GT) ScalarMult(a *GT, k *big.Int) *GT { 310 if e.p == nil { 311 e.p = newGFp12(nil) 312 } 313 e.p.Exp(a.p, k, new(bnPool)) 314 return e 315} 316 317// Add sets e to a+b and then returns e. 318func (e *GT) Add(a, b *GT) *GT { 319 if e.p == nil { 320 e.p = newGFp12(nil) 321 } 322 e.p.Mul(a.p, b.p, new(bnPool)) 323 return e 324} 325 326// Neg sets e to -a and then returns e. 327func (e *GT) Neg(a *GT) *GT { 328 if e.p == nil { 329 e.p = newGFp12(nil) 330 } 331 e.p.Invert(a.p, new(bnPool)) 332 return e 333} 334 335// Marshal converts n into a byte slice. 336func (n *GT) Marshal() []byte { 337 n.p.Minimal() 338 339 xxxBytes := n.p.x.x.x.Bytes() 340 xxyBytes := n.p.x.x.y.Bytes() 341 xyxBytes := n.p.x.y.x.Bytes() 342 xyyBytes := n.p.x.y.y.Bytes() 343 xzxBytes := n.p.x.z.x.Bytes() 344 xzyBytes := n.p.x.z.y.Bytes() 345 yxxBytes := n.p.y.x.x.Bytes() 346 yxyBytes := n.p.y.x.y.Bytes() 347 yyxBytes := n.p.y.y.x.Bytes() 348 yyyBytes := n.p.y.y.y.Bytes() 349 yzxBytes := n.p.y.z.x.Bytes() 350 yzyBytes := n.p.y.z.y.Bytes() 351 352 // Each value is a 256-bit number. 353 const numBytes = 256 / 8 354 355 ret := make([]byte, numBytes*12) 356 copy(ret[1*numBytes-len(xxxBytes):], xxxBytes) 357 copy(ret[2*numBytes-len(xxyBytes):], xxyBytes) 358 copy(ret[3*numBytes-len(xyxBytes):], xyxBytes) 359 copy(ret[4*numBytes-len(xyyBytes):], xyyBytes) 360 copy(ret[5*numBytes-len(xzxBytes):], xzxBytes) 361 copy(ret[6*numBytes-len(xzyBytes):], xzyBytes) 362 copy(ret[7*numBytes-len(yxxBytes):], yxxBytes) 363 copy(ret[8*numBytes-len(yxyBytes):], yxyBytes) 364 copy(ret[9*numBytes-len(yyxBytes):], yyxBytes) 365 copy(ret[10*numBytes-len(yyyBytes):], yyyBytes) 366 copy(ret[11*numBytes-len(yzxBytes):], yzxBytes) 367 copy(ret[12*numBytes-len(yzyBytes):], yzyBytes) 368 369 return ret 370} 371 372// Unmarshal sets e to the result of converting the output of Marshal back into 373// a group element and then returns e. 374func (e *GT) Unmarshal(m []byte) (*GT, bool) { 375 // Each value is a 256-bit number. 376 const numBytes = 256 / 8 377 378 if len(m) != 12*numBytes { 379 return nil, false 380 } 381 382 if e.p == nil { 383 e.p = newGFp12(nil) 384 } 385 386 e.p.x.x.x.SetBytes(m[0*numBytes : 1*numBytes]) 387 e.p.x.x.y.SetBytes(m[1*numBytes : 2*numBytes]) 388 e.p.x.y.x.SetBytes(m[2*numBytes : 3*numBytes]) 389 e.p.x.y.y.SetBytes(m[3*numBytes : 4*numBytes]) 390 e.p.x.z.x.SetBytes(m[4*numBytes : 5*numBytes]) 391 e.p.x.z.y.SetBytes(m[5*numBytes : 6*numBytes]) 392 e.p.y.x.x.SetBytes(m[6*numBytes : 7*numBytes]) 393 e.p.y.x.y.SetBytes(m[7*numBytes : 8*numBytes]) 394 e.p.y.y.x.SetBytes(m[8*numBytes : 9*numBytes]) 395 e.p.y.y.y.SetBytes(m[9*numBytes : 10*numBytes]) 396 e.p.y.z.x.SetBytes(m[10*numBytes : 11*numBytes]) 397 e.p.y.z.y.SetBytes(m[11*numBytes : 12*numBytes]) 398 399 return e, true 400} 401 402// Pair calculates an Optimal Ate pairing. 403func Pair(g1 *G1, g2 *G2) *GT { 404 return >{optimalAte(g2.p, g1.p, new(bnPool))} 405} 406 407// PairingCheck calculates the Optimal Ate pairing for a set of points. 408func PairingCheck(a []*G1, b []*G2) bool { 409 pool := new(bnPool) 410 411 acc := newGFp12(pool) 412 acc.SetOne() 413 414 for i := 0; i < len(a); i++ { 415 if a[i].p.IsInfinity() || b[i].p.IsInfinity() { 416 continue 417 } 418 acc.Mul(acc, miller(b[i].p, a[i].p, pool), pool) 419 } 420 ret := finalExponentiation(acc, pool) 421 acc.Put(pool) 422 423 return ret.IsOne() 424} 425 426// bnPool implements a tiny cache of *big.Int objects that's used to reduce the 427// number of allocations made during processing. 428type bnPool struct { 429 bns []*big.Int 430 count int 431} 432 433func (pool *bnPool) Get() *big.Int { 434 if pool == nil { 435 return new(big.Int) 436 } 437 438 pool.count++ 439 l := len(pool.bns) 440 if l == 0 { 441 return new(big.Int) 442 } 443 444 bn := pool.bns[l-1] 445 pool.bns = pool.bns[:l-1] 446 return bn 447} 448 449func (pool *bnPool) Put(bn *big.Int) { 450 if pool == nil { 451 return 452 } 453 pool.bns = append(pool.bns, bn) 454 pool.count-- 455} 456 457func (pool *bnPool) Count() int { 458 return pool.count 459} 460