vendor/golang.org/x/crypto/bn256/bn256.go

   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.
  17 package bn256 // import "golang.org/x/crypto/bn256"
  18
  19 import (
  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.
  30 type G1 struct {
  31         p *curvePoint
  32 }
  33
  34 // RandomG1 returns x and g₁ˣ where x is a random, non-zero number read from r.
  35 func 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
  52 func (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.
  58 func (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.
  67 func (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.
  77 func (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.
  86 func (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.
  95 func (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.
 113 func (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.
 147 type G2 struct {
 148         p *twistPoint
 149 }
 150
 151 // RandomG1 returns x and g₂ˣ where x is a random, non-zero number read from r.
 152 func 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
 169 func (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.
 175 func (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.
 184 func (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.
 194 func (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.
 203 func (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.
 225 func (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.
 264 type GT struct {
 265         p *gfP12
 266 }
 267
 268 func (g *GT) String() string {
 269         return "bn256.GT" + g.p.String()
 270 }
 271
 272 // ScalarMult sets e to a*k and then returns e.
 273 func (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.
 282 func (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.
 291 func (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.
 300 func (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.
 338 func (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.
 367 func Pair(g1 *G1, g2 *G2) *GT {
 368         return &GT{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.
 373 type bnPool struct {
 374         bns   []*big.Int
 375         count int
 376 }
 377
 378 func (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
 394 func (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
 402 func (pool *bnPool) Count() int {
 403         return pool.count
 404 }