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