gfp2.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
     6  
     7  // For details of the algorithms used, see "Multiplication and Squaring on
     8  // Pairing-Friendly Fields, Devegili et al.
     9  // http://eprint.iacr.org/2006/471.pdf.
    10  
    11  import (
    12  	"math/big"
    13  )
    14  
    15  // gfP2 implements a field of size p² as a quadratic extension of the base
    16  // field where i²=-1.
    17  type gfP2 struct {
    18  	x, y *big.Int // value is xi+y.
    19  }
    20  
    21  func newGFp2(pool *bnPool) *gfP2 {
    22  	return &gfP2{pool.Get(), pool.Get()}
    23  }
    24  
    25  func (e *gfP2) String() string {
    26  	x := new(big.Int).Mod(e.x, p)
    27  	y := new(big.Int).Mod(e.y, p)
    28  	return "(" + x.String() + "," + y.String() + ")"
    29  }
    30  
    31  func (e *gfP2) Put(pool *bnPool) {
    32  	pool.Put(e.x)
    33  	pool.Put(e.y)
    34  }
    35  
    36  func (e *gfP2) Set(a *gfP2) *gfP2 {
    37  	e.x.Set(a.x)
    38  	e.y.Set(a.y)
    39  	return e
    40  }
    41  
    42  func (e *gfP2) SetZero() *gfP2 {
    43  	e.x.SetInt64(0)
    44  	e.y.SetInt64(0)
    45  	return e
    46  }
    47  
    48  func (e *gfP2) SetOne() *gfP2 {
    49  	e.x.SetInt64(0)
    50  	e.y.SetInt64(1)
    51  	return e
    52  }
    53  
    54  func (e *gfP2) Minimal() {
    55  	if e.x.Sign() < 0 || e.x.Cmp(p) >= 0 {
    56  		e.x.Mod(e.x, p)
    57  	}
    58  	if e.y.Sign() < 0 || e.y.Cmp(p) >= 0 {
    59  		e.y.Mod(e.y, p)
    60  	}
    61  }
    62  
    63  func (e *gfP2) IsZero() bool {
    64  	return e.x.Sign() == 0 && e.y.Sign() == 0
    65  }
    66  
    67  func (e *gfP2) IsOne() bool {
    68  	if e.x.Sign() != 0 {
    69  		return false
    70  	}
    71  	words := e.y.Bits()
    72  	return len(words) == 1 && words[0] == 1
    73  }
    74  
    75  func (e *gfP2) Conjugate(a *gfP2) *gfP2 {
    76  	e.y.Set(a.y)
    77  	e.x.Neg(a.x)
    78  	return e
    79  }
    80  
    81  func (e *gfP2) Negative(a *gfP2) *gfP2 {
    82  	e.x.Neg(a.x)
    83  	e.y.Neg(a.y)
    84  	return e
    85  }
    86  
    87  func (e *gfP2) Add(a, b *gfP2) *gfP2 {
    88  	e.x.Add(a.x, b.x)
    89  	e.y.Add(a.y, b.y)
    90  	return e
    91  }
    92  
    93  func (e *gfP2) Sub(a, b *gfP2) *gfP2 {
    94  	e.x.Sub(a.x, b.x)
    95  	e.y.Sub(a.y, b.y)
    96  	return e
    97  }
    98  
    99  func (e *gfP2) Double(a *gfP2) *gfP2 {
   100  	e.x.Lsh(a.x, 1)
   101  	e.y.Lsh(a.y, 1)
   102  	return e
   103  }
   104  
   105  func (c *gfP2) Exp(a *gfP2, power *big.Int, pool *bnPool) *gfP2 {
   106  	sum := newGFp2(pool)
   107  	sum.SetOne()
   108  	t := newGFp2(pool)
   109  
   110  	for i := power.BitLen() - 1; i >= 0; i-- {
   111  		t.Square(sum, pool)
   112  		if power.Bit(i) != 0 {
   113  			sum.Mul(t, a, pool)
   114  		} else {
   115  			sum.Set(t)
   116  		}
   117  	}
   118  
   119  	c.Set(sum)
   120  
   121  	sum.Put(pool)
   122  	t.Put(pool)
   123  
   124  	return c
   125  }
   126  
   127  // See "Multiplication and Squaring in Pairing-Friendly Fields",
   128  // http://eprint.iacr.org/2006/471.pdf
   129  func (e *gfP2) Mul(a, b *gfP2, pool *bnPool) *gfP2 {
   130  	tx := pool.Get().Mul(a.x, b.y)
   131  	t := pool.Get().Mul(b.x, a.y)
   132  	tx.Add(tx, t)
   133  	tx.Mod(tx, p)
   134  
   135  	ty := pool.Get().Mul(a.y, b.y)
   136  	t.Mul(a.x, b.x)
   137  	ty.Sub(ty, t)
   138  	e.y.Mod(ty, p)
   139  	e.x.Set(tx)
   140  
   141  	pool.Put(tx)
   142  	pool.Put(ty)
   143  	pool.Put(t)
   144  
   145  	return e
   146  }
   147  
   148  func (e *gfP2) MulScalar(a *gfP2, b *big.Int) *gfP2 {
   149  	e.x.Mul(a.x, b)
   150  	e.y.Mul(a.y, b)
   151  	return e
   152  }
   153  
   154  // MulXi sets e=ξa where ξ=i+3 and then returns e.
   155  func (e *gfP2) MulXi(a *gfP2, pool *bnPool) *gfP2 {
   156  	// (xi+y)(i+3) = (3x+y)i+(3y-x)
   157  	tx := pool.Get().Lsh(a.x, 1)
   158  	tx.Add(tx, a.x)
   159  	tx.Add(tx, a.y)
   160  
   161  	ty := pool.Get().Lsh(a.y, 1)
   162  	ty.Add(ty, a.y)
   163  	ty.Sub(ty, a.x)
   164  
   165  	e.x.Set(tx)
   166  	e.y.Set(ty)
   167  
   168  	pool.Put(tx)
   169  	pool.Put(ty)
   170  
   171  	return e
   172  }
   173  
   174  func (e *gfP2) Square(a *gfP2, pool *bnPool) *gfP2 {
   175  	// Complex squaring algorithm:
   176  	// (xi+b)² = (x+y)(y-x) + 2*i*x*y
   177  	t1 := pool.Get().Sub(a.y, a.x)
   178  	t2 := pool.Get().Add(a.x, a.y)
   179  	ty := pool.Get().Mul(t1, t2)
   180  	ty.Mod(ty, p)
   181  
   182  	t1.Mul(a.x, a.y)
   183  	t1.Lsh(t1, 1)
   184  
   185  	e.x.Mod(t1, p)
   186  	e.y.Set(ty)
   187  
   188  	pool.Put(t1)
   189  	pool.Put(t2)
   190  	pool.Put(ty)
   191  
   192  	return e
   193  }
   194  
   195  func (e *gfP2) Invert(a *gfP2, pool *bnPool) *gfP2 {
   196  	// See "Implementing cryptographic pairings", M. Scott, section 3.2.
   197  	// ftp://136.206.11.249/pub/crypto/pairings.pdf
   198  	t := pool.Get()
   199  	t.Mul(a.y, a.y)
   200  	t2 := pool.Get()
   201  	t2.Mul(a.x, a.x)
   202  	t.Add(t, t2)
   203  
   204  	inv := pool.Get()
   205  	inv.ModInverse(t, p)
   206  
   207  	e.x.Neg(a.x)
   208  	e.x.Mul(e.x, inv)
   209  	e.x.Mod(e.x, p)
   210  
   211  	e.y.Mul(a.y, inv)
   212  	e.y.Mod(e.y, p)
   213  
   214  	pool.Put(t)
   215  	pool.Put(t2)
   216  	pool.Put(inv)
   217  
   218  	return e
   219  }
   220
View as plain text