gfp6.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  // gfP6 implements the field of size p⁶ as a cubic extension of gfP2 where τ³=ξ
    16  // and ξ=i+3.
    17  type gfP6 struct {
    18  	x, y, z *gfP2 // value is xτ² + yτ + z
    19  }
    20  
    21  func newGFp6(pool *bnPool) *gfP6 {
    22  	return &gfP6{newGFp2(pool), newGFp2(pool), newGFp2(pool)}
    23  }
    24  
    25  func (e *gfP6) String() string {
    26  	return "(" + e.x.String() + "," + e.y.String() + "," + e.z.String() + ")"
    27  }
    28  
    29  func (e *gfP6) Put(pool *bnPool) {
    30  	e.x.Put(pool)
    31  	e.y.Put(pool)
    32  	e.z.Put(pool)
    33  }
    34  
    35  func (e *gfP6) Set(a *gfP6) *gfP6 {
    36  	e.x.Set(a.x)
    37  	e.y.Set(a.y)
    38  	e.z.Set(a.z)
    39  	return e
    40  }
    41  
    42  func (e *gfP6) SetZero() *gfP6 {
    43  	e.x.SetZero()
    44  	e.y.SetZero()
    45  	e.z.SetZero()
    46  	return e
    47  }
    48  
    49  func (e *gfP6) SetOne() *gfP6 {
    50  	e.x.SetZero()
    51  	e.y.SetZero()
    52  	e.z.SetOne()
    53  	return e
    54  }
    55  
    56  func (e *gfP6) Minimal() {
    57  	e.x.Minimal()
    58  	e.y.Minimal()
    59  	e.z.Minimal()
    60  }
    61  
    62  func (e *gfP6) IsZero() bool {
    63  	return e.x.IsZero() && e.y.IsZero() && e.z.IsZero()
    64  }
    65  
    66  func (e *gfP6) IsOne() bool {
    67  	return e.x.IsZero() && e.y.IsZero() && e.z.IsOne()
    68  }
    69  
    70  func (e *gfP6) Negative(a *gfP6) *gfP6 {
    71  	e.x.Negative(a.x)
    72  	e.y.Negative(a.y)
    73  	e.z.Negative(a.z)
    74  	return e
    75  }
    76  
    77  func (e *gfP6) Frobenius(a *gfP6, pool *bnPool) *gfP6 {
    78  	e.x.Conjugate(a.x)
    79  	e.y.Conjugate(a.y)
    80  	e.z.Conjugate(a.z)
    81  
    82  	e.x.Mul(e.x, xiTo2PMinus2Over3, pool)
    83  	e.y.Mul(e.y, xiToPMinus1Over3, pool)
    84  	return e
    85  }
    86  
    87  // FrobeniusP2 computes (xτ²+yτ+z)^(p²) = xτ^(2p²) + yτ^(p²) + z
    88  func (e *gfP6) FrobeniusP2(a *gfP6) *gfP6 {
    89  	// τ^(2p²) = τ²τ^(2p²-2) = τ²ξ^((2p²-2)/3)
    90  	e.x.MulScalar(a.x, xiTo2PSquaredMinus2Over3)
    91  	// τ^(p²) = ττ^(p²-1) = τξ^((p²-1)/3)
    92  	e.y.MulScalar(a.y, xiToPSquaredMinus1Over3)
    93  	e.z.Set(a.z)
    94  	return e
    95  }
    96  
    97  func (e *gfP6) Add(a, b *gfP6) *gfP6 {
    98  	e.x.Add(a.x, b.x)
    99  	e.y.Add(a.y, b.y)
   100  	e.z.Add(a.z, b.z)
   101  	return e
   102  }
   103  
   104  func (e *gfP6) Sub(a, b *gfP6) *gfP6 {
   105  	e.x.Sub(a.x, b.x)
   106  	e.y.Sub(a.y, b.y)
   107  	e.z.Sub(a.z, b.z)
   108  	return e
   109  }
   110  
   111  func (e *gfP6) Double(a *gfP6) *gfP6 {
   112  	e.x.Double(a.x)
   113  	e.y.Double(a.y)
   114  	e.z.Double(a.z)
   115  	return e
   116  }
   117  
   118  func (e *gfP6) Mul(a, b *gfP6, pool *bnPool) *gfP6 {
   119  	// "Multiplication and Squaring on Pairing-Friendly Fields"
   120  	// Section 4, Karatsuba method.
   121  	// http://eprint.iacr.org/2006/471.pdf
   122  
   123  	v0 := newGFp2(pool)
   124  	v0.Mul(a.z, b.z, pool)
   125  	v1 := newGFp2(pool)
   126  	v1.Mul(a.y, b.y, pool)
   127  	v2 := newGFp2(pool)
   128  	v2.Mul(a.x, b.x, pool)
   129  
   130  	t0 := newGFp2(pool)
   131  	t0.Add(a.x, a.y)
   132  	t1 := newGFp2(pool)
   133  	t1.Add(b.x, b.y)
   134  	tz := newGFp2(pool)
   135  	tz.Mul(t0, t1, pool)
   136  
   137  	tz.Sub(tz, v1)
   138  	tz.Sub(tz, v2)
   139  	tz.MulXi(tz, pool)
   140  	tz.Add(tz, v0)
   141  
   142  	t0.Add(a.y, a.z)
   143  	t1.Add(b.y, b.z)
   144  	ty := newGFp2(pool)
   145  	ty.Mul(t0, t1, pool)
   146  	ty.Sub(ty, v0)
   147  	ty.Sub(ty, v1)
   148  	t0.MulXi(v2, pool)
   149  	ty.Add(ty, t0)
   150  
   151  	t0.Add(a.x, a.z)
   152  	t1.Add(b.x, b.z)
   153  	tx := newGFp2(pool)
   154  	tx.Mul(t0, t1, pool)
   155  	tx.Sub(tx, v0)
   156  	tx.Add(tx, v1)
   157  	tx.Sub(tx, v2)
   158  
   159  	e.x.Set(tx)
   160  	e.y.Set(ty)
   161  	e.z.Set(tz)
   162  
   163  	t0.Put(pool)
   164  	t1.Put(pool)
   165  	tx.Put(pool)
   166  	ty.Put(pool)
   167  	tz.Put(pool)
   168  	v0.Put(pool)
   169  	v1.Put(pool)
   170  	v2.Put(pool)
   171  	return e
   172  }
   173  
   174  func (e *gfP6) MulScalar(a *gfP6, b *gfP2, pool *bnPool) *gfP6 {
   175  	e.x.Mul(a.x, b, pool)
   176  	e.y.Mul(a.y, b, pool)
   177  	e.z.Mul(a.z, b, pool)
   178  	return e
   179  }
   180  
   181  func (e *gfP6) MulGFP(a *gfP6, b *big.Int) *gfP6 {
   182  	e.x.MulScalar(a.x, b)
   183  	e.y.MulScalar(a.y, b)
   184  	e.z.MulScalar(a.z, b)
   185  	return e
   186  }
   187  
   188  // MulTau computes τ·(aτ²+bτ+c) = bτ²+cτ+aξ
   189  func (e *gfP6) MulTau(a *gfP6, pool *bnPool) {
   190  	tz := newGFp2(pool)
   191  	tz.MulXi(a.x, pool)
   192  	ty := newGFp2(pool)
   193  	ty.Set(a.y)
   194  	e.y.Set(a.z)
   195  	e.x.Set(ty)
   196  	e.z.Set(tz)
   197  	tz.Put(pool)
   198  	ty.Put(pool)
   199  }
   200  
   201  func (e *gfP6) Square(a *gfP6, pool *bnPool) *gfP6 {
   202  	v0 := newGFp2(pool).Square(a.z, pool)
   203  	v1 := newGFp2(pool).Square(a.y, pool)
   204  	v2 := newGFp2(pool).Square(a.x, pool)
   205  
   206  	c0 := newGFp2(pool).Add(a.x, a.y)
   207  	c0.Square(c0, pool)
   208  	c0.Sub(c0, v1)
   209  	c0.Sub(c0, v2)
   210  	c0.MulXi(c0, pool)
   211  	c0.Add(c0, v0)
   212  
   213  	c1 := newGFp2(pool).Add(a.y, a.z)
   214  	c1.Square(c1, pool)
   215  	c1.Sub(c1, v0)
   216  	c1.Sub(c1, v1)
   217  	xiV2 := newGFp2(pool).MulXi(v2, pool)
   218  	c1.Add(c1, xiV2)
   219  
   220  	c2 := newGFp2(pool).Add(a.x, a.z)
   221  	c2.Square(c2, pool)
   222  	c2.Sub(c2, v0)
   223  	c2.Add(c2, v1)
   224  	c2.Sub(c2, v2)
   225  
   226  	e.x.Set(c2)
   227  	e.y.Set(c1)
   228  	e.z.Set(c0)
   229  
   230  	v0.Put(pool)
   231  	v1.Put(pool)
   232  	v2.Put(pool)
   233  	c0.Put(pool)
   234  	c1.Put(pool)
   235  	c2.Put(pool)
   236  	xiV2.Put(pool)
   237  
   238  	return e
   239  }
   240  
   241  func (e *gfP6) Invert(a *gfP6, pool *bnPool) *gfP6 {
   242  	// See "Implementing cryptographic pairings", M. Scott, section 3.2.
   243  	// ftp://136.206.11.249/pub/crypto/pairings.pdf
   244  
   245  	// Here we can give a short explanation of how it works: let j be a cubic root of
   246  	// unity in GF(p²) so that 1+j+j²=0.
   247  	// Then (xτ² + yτ + z)(xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
   248  	// = (xτ² + yτ + z)(Cτ²+Bτ+A)
   249  	// = (x³ξ²+y³ξ+z³-3ξxyz) = F is an element of the base field (the norm).
   250  	//
   251  	// On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
   252  	// = τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)
   253  	//
   254  	// So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)
   255  	t1 := newGFp2(pool)
   256  
   257  	A := newGFp2(pool)
   258  	A.Square(a.z, pool)
   259  	t1.Mul(a.x, a.y, pool)
   260  	t1.MulXi(t1, pool)
   261  	A.Sub(A, t1)
   262  
   263  	B := newGFp2(pool)
   264  	B.Square(a.x, pool)
   265  	B.MulXi(B, pool)
   266  	t1.Mul(a.y, a.z, pool)
   267  	B.Sub(B, t1)
   268  
   269  	C := newGFp2(pool)
   270  	C.Square(a.y, pool)
   271  	t1.Mul(a.x, a.z, pool)
   272  	C.Sub(C, t1)
   273  
   274  	F := newGFp2(pool)
   275  	F.Mul(C, a.y, pool)
   276  	F.MulXi(F, pool)
   277  	t1.Mul(A, a.z, pool)
   278  	F.Add(F, t1)
   279  	t1.Mul(B, a.x, pool)
   280  	t1.MulXi(t1, pool)
   281  	F.Add(F, t1)
   282  
   283  	F.Invert(F, pool)
   284  
   285  	e.x.Mul(C, F, pool)
   286  	e.y.Mul(B, F, pool)
   287  	e.z.Mul(A, F, pool)
   288  
   289  	t1.Put(pool)
   290  	A.Put(pool)
   291  	B.Put(pool)
   292  	C.Put(pool)
   293  	F.Put(pool)
   294  
   295  	return e
   296  }
   297
View as plain text