bn256.go

Documentation: golang.org/x/crypto/bn256

     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  // RandomG2 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  }
   430
View as plain text