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 at the 128-bit security level. 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. 17package bn256 // import "golang.org/x/crypto/bn256" 18 19import ( 20 "crypto/rand" 21 "io" 22 "math/big" 23) 24 25// BUG(agl): this implementation is not constant time. 26// TODO(agl): keep GF(p²) elements in Mongomery form. 27 28// G1 is an abstract cyclic group. The zero value is suitable for use as the 29// output of an operation, but cannot be used as an input. 30type G1 struct { 31 p *curvePoint 32} 33 34// RandomG1 returns x and g₁ˣ where x is a random, non-zero number read from r. 35func RandomG1(r io.Reader) (*big.Int, *G1, error) { 36 var k *big.Int 37 var err error 38 39 for { 40 k, err = rand.Int(r, Order) 41 if err != nil { 42 return nil, nil, err 43 } 44 if k.Sign() > 0 { 45 break 46 } 47 } 48 49 return k, new(G1).ScalarBaseMult(k), nil 50} 51 52func (g *G1) String() string { 53 return "bn256.G1" + g.p.String() 54} 55 56// ScalarBaseMult sets e to g*k where g is the generator of the group and 57// then returns e. 58func (e *G1) ScalarBaseMult(k *big.Int) *G1 { 59 if e.p == nil { 60 e.p = newCurvePoint(nil) 61 } 62 e.p.Mul(curveGen, k, new(bnPool)) 63 return e 64} 65 66// ScalarMult sets e to a*k and then returns e. 67func (e *G1) ScalarMult(a *G1, k *big.Int) *G1 { 68 if e.p == nil { 69 e.p = newCurvePoint(nil) 70 } 71 e.p.Mul(a.p, k, new(bnPool)) 72 return e 73} 74 75// Add sets e to a+b and then returns e. 76// BUG(agl): this function is not complete: a==b fails. 77func (e *G1) Add(a, b *G1) *G1 { 78 if e.p == nil { 79 e.p = newCurvePoint(nil) 80 } 81 e.p.Add(a.p, b.p, new(bnPool)) 82 return e 83} 84 85// Neg sets e to -a and then returns e. 86func (e *G1) Neg(a *G1) *G1 { 87 if e.p == nil { 88 e.p = newCurvePoint(nil) 89 } 90 e.p.Negative(a.p) 91 return e 92} 93 94// Marshal converts n to a byte slice. 95func (n *G1) Marshal() []byte { 96 n.p.MakeAffine(nil) 97 98 xBytes := new(big.Int).Mod(n.p.x, p).Bytes() 99 yBytes := new(big.Int).Mod(n.p.y, p).Bytes() 100 101 // Each value is a 256-bit number. 102 const numBytes = 256 / 8 103 104 ret := make([]byte, numBytes*2) 105 copy(ret[1*numBytes-len(xBytes):], xBytes) 106 copy(ret[2*numBytes-len(yBytes):], yBytes) 107 108 return ret 109} 110 111// Unmarshal sets e to the result of converting the output of Marshal back into 112// a group element and then returns e. 113func (e *G1) Unmarshal(m []byte) (*G1, bool) { 114 // Each value is a 256-bit number. 115 const numBytes = 256 / 8 116 117 if len(m) != 2*numBytes { 118 return nil, false 119 } 120 121 if e.p == nil { 122 e.p = newCurvePoint(nil) 123 } 124 125 e.p.x.SetBytes(m[0*numBytes : 1*numBytes]) 126 e.p.y.SetBytes(m[1*numBytes : 2*numBytes]) 127 128 if e.p.x.Sign() == 0 && e.p.y.Sign() == 0 { 129 // This is the point at infinity. 130 e.p.y.SetInt64(1) 131 e.p.z.SetInt64(0) 132 e.p.t.SetInt64(0) 133 } else { 134 e.p.z.SetInt64(1) 135 e.p.t.SetInt64(1) 136 137 if !e.p.IsOnCurve() { 138 return nil, false 139 } 140 } 141 142 return e, true 143} 144 145// G2 is an abstract cyclic group. The zero value is suitable for use as the 146// output of an operation, but cannot be used as an input. 147type G2 struct { 148 p *twistPoint 149} 150 151// RandomG1 returns x and g₂ˣ where x is a random, non-zero number read from r. 152func RandomG2(r io.Reader) (*big.Int, *G2, error) { 153 var k *big.Int 154 var err error 155 156 for { 157 k, err = rand.Int(r, Order) 158 if err != nil { 159 return nil, nil, err 160 } 161 if k.Sign() > 0 { 162 break 163 } 164 } 165 166 return k, new(G2).ScalarBaseMult(k), nil 167} 168 169func (g *G2) String() string { 170 return "bn256.G2" + g.p.String() 171} 172 173// ScalarBaseMult sets e to g*k where g is the generator of the group and 174// then returns out. 175func (e *G2) ScalarBaseMult(k *big.Int) *G2 { 176 if e.p == nil { 177 e.p = newTwistPoint(nil) 178 } 179 e.p.Mul(twistGen, k, new(bnPool)) 180 return e 181} 182 183// ScalarMult sets e to a*k and then returns e. 184func (e *G2) ScalarMult(a *G2, k *big.Int) *G2 { 185 if e.p == nil { 186 e.p = newTwistPoint(nil) 187 } 188 e.p.Mul(a.p, k, new(bnPool)) 189 return e 190} 191 192// Add sets e to a+b and then returns e. 193// BUG(agl): this function is not complete: a==b fails. 194func (e *G2) Add(a, b *G2) *G2 { 195 if e.p == nil { 196 e.p = newTwistPoint(nil) 197 } 198 e.p.Add(a.p, b.p, new(bnPool)) 199 return e 200} 201 202// Marshal converts n into a byte slice. 203func (n *G2) Marshal() []byte { 204 n.p.MakeAffine(nil) 205 206 xxBytes := new(big.Int).Mod(n.p.x.x, p).Bytes() 207 xyBytes := new(big.Int).Mod(n.p.x.y, p).Bytes() 208 yxBytes := new(big.Int).Mod(n.p.y.x, p).Bytes() 209 yyBytes := new(big.Int).Mod(n.p.y.y, p).Bytes() 210 211 // Each value is a 256-bit number. 212 const numBytes = 256 / 8 213 214 ret := make([]byte, numBytes*4) 215 copy(ret[1*numBytes-len(xxBytes):], xxBytes) 216 copy(ret[2*numBytes-len(xyBytes):], xyBytes) 217 copy(ret[3*numBytes-len(yxBytes):], yxBytes) 218 copy(ret[4*numBytes-len(yyBytes):], yyBytes) 219 220 return ret 221} 222 223// Unmarshal sets e to the result of converting the output of Marshal back into 224// a group element and then returns e. 225func (e *G2) Unmarshal(m []byte) (*G2, bool) { 226 // Each value is a 256-bit number. 227 const numBytes = 256 / 8 228 229 if len(m) != 4*numBytes { 230 return nil, false 231 } 232 233 if e.p == nil { 234 e.p = newTwistPoint(nil) 235 } 236 237 e.p.x.x.SetBytes(m[0*numBytes : 1*numBytes]) 238 e.p.x.y.SetBytes(m[1*numBytes : 2*numBytes]) 239 e.p.y.x.SetBytes(m[2*numBytes : 3*numBytes]) 240 e.p.y.y.SetBytes(m[3*numBytes : 4*numBytes]) 241 242 if e.p.x.x.Sign() == 0 && 243 e.p.x.y.Sign() == 0 && 244 e.p.y.x.Sign() == 0 && 245 e.p.y.y.Sign() == 0 { 246 // This is the point at infinity. 247 e.p.y.SetOne() 248 e.p.z.SetZero() 249 e.p.t.SetZero() 250 } else { 251 e.p.z.SetOne() 252 e.p.t.SetOne() 253 254 if !e.p.IsOnCurve() { 255 return nil, false 256 } 257 } 258 259 return e, true 260} 261 262// GT is an abstract cyclic group. The zero value is suitable for use as the 263// output of an operation, but cannot be used as an input. 264type GT struct { 265 p *gfP12 266} 267 268func (g *GT) String() string { 269 return "bn256.GT" + g.p.String() 270} 271 272// ScalarMult sets e to a*k and then returns e. 273func (e *GT) ScalarMult(a *GT, k *big.Int) *GT { 274 if e.p == nil { 275 e.p = newGFp12(nil) 276 } 277 e.p.Exp(a.p, k, new(bnPool)) 278 return e 279} 280 281// Add sets e to a+b and then returns e. 282func (e *GT) Add(a, b *GT) *GT { 283 if e.p == nil { 284 e.p = newGFp12(nil) 285 } 286 e.p.Mul(a.p, b.p, new(bnPool)) 287 return e 288} 289 290// Neg sets e to -a and then returns e. 291func (e *GT) Neg(a *GT) *GT { 292 if e.p == nil { 293 e.p = newGFp12(nil) 294 } 295 e.p.Invert(a.p, new(bnPool)) 296 return e 297} 298 299// Marshal converts n into a byte slice. 300func (n *GT) Marshal() []byte { 301 n.p.Minimal() 302 303 xxxBytes := n.p.x.x.x.Bytes() 304 xxyBytes := n.p.x.x.y.Bytes() 305 xyxBytes := n.p.x.y.x.Bytes() 306 xyyBytes := n.p.x.y.y.Bytes() 307 xzxBytes := n.p.x.z.x.Bytes() 308 xzyBytes := n.p.x.z.y.Bytes() 309 yxxBytes := n.p.y.x.x.Bytes() 310 yxyBytes := n.p.y.x.y.Bytes() 311 yyxBytes := n.p.y.y.x.Bytes() 312 yyyBytes := n.p.y.y.y.Bytes() 313 yzxBytes := n.p.y.z.x.Bytes() 314 yzyBytes := n.p.y.z.y.Bytes() 315 316 // Each value is a 256-bit number. 317 const numBytes = 256 / 8 318 319 ret := make([]byte, numBytes*12) 320 copy(ret[1*numBytes-len(xxxBytes):], xxxBytes) 321 copy(ret[2*numBytes-len(xxyBytes):], xxyBytes) 322 copy(ret[3*numBytes-len(xyxBytes):], xyxBytes) 323 copy(ret[4*numBytes-len(xyyBytes):], xyyBytes) 324 copy(ret[5*numBytes-len(xzxBytes):], xzxBytes) 325 copy(ret[6*numBytes-len(xzyBytes):], xzyBytes) 326 copy(ret[7*numBytes-len(yxxBytes):], yxxBytes) 327 copy(ret[8*numBytes-len(yxyBytes):], yxyBytes) 328 copy(ret[9*numBytes-len(yyxBytes):], yyxBytes) 329 copy(ret[10*numBytes-len(yyyBytes):], yyyBytes) 330 copy(ret[11*numBytes-len(yzxBytes):], yzxBytes) 331 copy(ret[12*numBytes-len(yzyBytes):], yzyBytes) 332 333 return ret 334} 335 336// Unmarshal sets e to the result of converting the output of Marshal back into 337// a group element and then returns e. 338func (e *GT) Unmarshal(m []byte) (*GT, bool) { 339 // Each value is a 256-bit number. 340 const numBytes = 256 / 8 341 342 if len(m) != 12*numBytes { 343 return nil, false 344 } 345 346 if e.p == nil { 347 e.p = newGFp12(nil) 348 } 349 350 e.p.x.x.x.SetBytes(m[0*numBytes : 1*numBytes]) 351 e.p.x.x.y.SetBytes(m[1*numBytes : 2*numBytes]) 352 e.p.x.y.x.SetBytes(m[2*numBytes : 3*numBytes]) 353 e.p.x.y.y.SetBytes(m[3*numBytes : 4*numBytes]) 354 e.p.x.z.x.SetBytes(m[4*numBytes : 5*numBytes]) 355 e.p.x.z.y.SetBytes(m[5*numBytes : 6*numBytes]) 356 e.p.y.x.x.SetBytes(m[6*numBytes : 7*numBytes]) 357 e.p.y.x.y.SetBytes(m[7*numBytes : 8*numBytes]) 358 e.p.y.y.x.SetBytes(m[8*numBytes : 9*numBytes]) 359 e.p.y.y.y.SetBytes(m[9*numBytes : 10*numBytes]) 360 e.p.y.z.x.SetBytes(m[10*numBytes : 11*numBytes]) 361 e.p.y.z.y.SetBytes(m[11*numBytes : 12*numBytes]) 362 363 return e, true 364} 365 366// Pair calculates an Optimal Ate pairing. 367func Pair(g1 *G1, g2 *G2) *GT { 368 return >{optimalAte(g2.p, g1.p, new(bnPool))} 369} 370 371// bnPool implements a tiny cache of *big.Int objects that's used to reduce the 372// number of allocations made during processing. 373type bnPool struct { 374 bns []*big.Int 375 count int 376} 377 378func (pool *bnPool) Get() *big.Int { 379 if pool == nil { 380 return new(big.Int) 381 } 382 383 pool.count++ 384 l := len(pool.bns) 385 if l == 0 { 386 return new(big.Int) 387 } 388 389 bn := pool.bns[l-1] 390 pool.bns = pool.bns[:l-1] 391 return bn 392} 393 394func (pool *bnPool) Put(bn *big.Int) { 395 if pool == nil { 396 return 397 } 398 pool.bns = append(pool.bns, bn) 399 pool.count-- 400} 401 402func (pool *bnPool) Count() int { 403 return pool.count 404} 405