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