twist.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  import (
     8  	"math/big"
     9  )
    10  
    11  // twistPoint implements the elliptic curve y²=x³+3/ξ over GF(p²). Points are
    12  // kept in Jacobian form and t=z² when valid. The group G₂ is the set of
    13  // n-torsion points of this curve over GF(p²) (where n = Order)
    14  type twistPoint struct {
    15  	x, y, z, t *gfP2
    16  }
    17  
    18  var twistB = &gfP2{
    19  	bigFromBase10("6500054969564660373279643874235990574282535810762300357187714502686418407178"),
    20  	bigFromBase10("45500384786952622612957507119651934019977750675336102500314001518804928850249"),
    21  }
    22  
    23  // twistGen is the generator of group G₂.
    24  var twistGen = &twistPoint{
    25  	&gfP2{
    26  		bigFromBase10("21167961636542580255011770066570541300993051739349375019639421053990175267184"),
    27  		bigFromBase10("64746500191241794695844075326670126197795977525365406531717464316923369116492"),
    28  	},
    29  	&gfP2{
    30  		bigFromBase10("20666913350058776956210519119118544732556678129809273996262322366050359951122"),
    31  		bigFromBase10("17778617556404439934652658462602675281523610326338642107814333856843981424549"),
    32  	},
    33  	&gfP2{
    34  		bigFromBase10("0"),
    35  		bigFromBase10("1"),
    36  	},
    37  	&gfP2{
    38  		bigFromBase10("0"),
    39  		bigFromBase10("1"),
    40  	},
    41  }
    42  
    43  func newTwistPoint(pool *bnPool) *twistPoint {
    44  	return &twistPoint{
    45  		newGFp2(pool),
    46  		newGFp2(pool),
    47  		newGFp2(pool),
    48  		newGFp2(pool),
    49  	}
    50  }
    51  
    52  func (c *twistPoint) String() string {
    53  	return "(" + c.x.String() + ", " + c.y.String() + ", " + c.z.String() + ")"
    54  }
    55  
    56  func (c *twistPoint) Put(pool *bnPool) {
    57  	c.x.Put(pool)
    58  	c.y.Put(pool)
    59  	c.z.Put(pool)
    60  	c.t.Put(pool)
    61  }
    62  
    63  func (c *twistPoint) Set(a *twistPoint) {
    64  	c.x.Set(a.x)
    65  	c.y.Set(a.y)
    66  	c.z.Set(a.z)
    67  	c.t.Set(a.t)
    68  }
    69  
    70  // IsOnCurve returns true iff c is on the curve where c must be in affine form.
    71  func (c *twistPoint) IsOnCurve() bool {
    72  	pool := new(bnPool)
    73  	yy := newGFp2(pool).Square(c.y, pool)
    74  	xxx := newGFp2(pool).Square(c.x, pool)
    75  	xxx.Mul(xxx, c.x, pool)
    76  	yy.Sub(yy, xxx)
    77  	yy.Sub(yy, twistB)
    78  	yy.Minimal()
    79  	return yy.x.Sign() == 0 && yy.y.Sign() == 0
    80  }
    81  
    82  func (c *twistPoint) SetInfinity() {
    83  	c.z.SetZero()
    84  }
    85  
    86  func (c *twistPoint) IsInfinity() bool {
    87  	return c.z.IsZero()
    88  }
    89  
    90  func (c *twistPoint) Add(a, b *twistPoint, pool *bnPool) {
    91  	// For additional comments, see the same function in curve.go.
    92  
    93  	if a.IsInfinity() {
    94  		c.Set(b)
    95  		return
    96  	}
    97  	if b.IsInfinity() {
    98  		c.Set(a)
    99  		return
   100  	}
   101  
   102  	// See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/addition/add-2007-bl.op3
   103  	z1z1 := newGFp2(pool).Square(a.z, pool)
   104  	z2z2 := newGFp2(pool).Square(b.z, pool)
   105  	u1 := newGFp2(pool).Mul(a.x, z2z2, pool)
   106  	u2 := newGFp2(pool).Mul(b.x, z1z1, pool)
   107  
   108  	t := newGFp2(pool).Mul(b.z, z2z2, pool)
   109  	s1 := newGFp2(pool).Mul(a.y, t, pool)
   110  
   111  	t.Mul(a.z, z1z1, pool)
   112  	s2 := newGFp2(pool).Mul(b.y, t, pool)
   113  
   114  	h := newGFp2(pool).Sub(u2, u1)
   115  	xEqual := h.IsZero()
   116  
   117  	t.Add(h, h)
   118  	i := newGFp2(pool).Square(t, pool)
   119  	j := newGFp2(pool).Mul(h, i, pool)
   120  
   121  	t.Sub(s2, s1)
   122  	yEqual := t.IsZero()
   123  	if xEqual && yEqual {
   124  		c.Double(a, pool)
   125  		return
   126  	}
   127  	r := newGFp2(pool).Add(t, t)
   128  
   129  	v := newGFp2(pool).Mul(u1, i, pool)
   130  
   131  	t4 := newGFp2(pool).Square(r, pool)
   132  	t.Add(v, v)
   133  	t6 := newGFp2(pool).Sub(t4, j)
   134  	c.x.Sub(t6, t)
   135  
   136  	t.Sub(v, c.x)       // t7
   137  	t4.Mul(s1, j, pool) // t8
   138  	t6.Add(t4, t4)      // t9
   139  	t4.Mul(r, t, pool)  // t10
   140  	c.y.Sub(t4, t6)
   141  
   142  	t.Add(a.z, b.z)    // t11
   143  	t4.Square(t, pool) // t12
   144  	t.Sub(t4, z1z1)    // t13
   145  	t4.Sub(t, z2z2)    // t14
   146  	c.z.Mul(t4, h, pool)
   147  
   148  	z1z1.Put(pool)
   149  	z2z2.Put(pool)
   150  	u1.Put(pool)
   151  	u2.Put(pool)
   152  	t.Put(pool)
   153  	s1.Put(pool)
   154  	s2.Put(pool)
   155  	h.Put(pool)
   156  	i.Put(pool)
   157  	j.Put(pool)
   158  	r.Put(pool)
   159  	v.Put(pool)
   160  	t4.Put(pool)
   161  	t6.Put(pool)
   162  }
   163  
   164  func (c *twistPoint) Double(a *twistPoint, pool *bnPool) {
   165  	// See http://hyperelliptic.org/EFD/g1p/auto-code/shortw/jacobian-0/doubling/dbl-2009-l.op3
   166  	A := newGFp2(pool).Square(a.x, pool)
   167  	B := newGFp2(pool).Square(a.y, pool)
   168  	C := newGFp2(pool).Square(B, pool)
   169  
   170  	t := newGFp2(pool).Add(a.x, B)
   171  	t2 := newGFp2(pool).Square(t, pool)
   172  	t.Sub(t2, A)
   173  	t2.Sub(t, C)
   174  	d := newGFp2(pool).Add(t2, t2)
   175  	t.Add(A, A)
   176  	e := newGFp2(pool).Add(t, A)
   177  	f := newGFp2(pool).Square(e, pool)
   178  
   179  	t.Add(d, d)
   180  	c.x.Sub(f, t)
   181  
   182  	t.Add(C, C)
   183  	t2.Add(t, t)
   184  	t.Add(t2, t2)
   185  	c.y.Sub(d, c.x)
   186  	t2.Mul(e, c.y, pool)
   187  	c.y.Sub(t2, t)
   188  
   189  	t.Mul(a.y, a.z, pool)
   190  	c.z.Add(t, t)
   191  
   192  	A.Put(pool)
   193  	B.Put(pool)
   194  	C.Put(pool)
   195  	t.Put(pool)
   196  	t2.Put(pool)
   197  	d.Put(pool)
   198  	e.Put(pool)
   199  	f.Put(pool)
   200  }
   201  
   202  func (c *twistPoint) Mul(a *twistPoint, scalar *big.Int, pool *bnPool) *twistPoint {
   203  	sum := newTwistPoint(pool)
   204  	sum.SetInfinity()
   205  	t := newTwistPoint(pool)
   206  
   207  	for i := scalar.BitLen(); i >= 0; i-- {
   208  		t.Double(sum, pool)
   209  		if scalar.Bit(i) != 0 {
   210  			sum.Add(t, a, pool)
   211  		} else {
   212  			sum.Set(t)
   213  		}
   214  	}
   215  
   216  	c.Set(sum)
   217  	sum.Put(pool)
   218  	t.Put(pool)
   219  	return c
   220  }
   221  
   222  // MakeAffine converts c to affine form and returns c. If c is ∞, then it sets
   223  // c to 0 : 1 : 0.
   224  func (c *twistPoint) MakeAffine(pool *bnPool) *twistPoint {
   225  	if c.z.IsOne() {
   226  		return c
   227  	}
   228  	if c.IsInfinity() {
   229  		c.x.SetZero()
   230  		c.y.SetOne()
   231  		c.z.SetZero()
   232  		c.t.SetZero()
   233  		return c
   234  	}
   235  
   236  	zInv := newGFp2(pool).Invert(c.z, pool)
   237  	t := newGFp2(pool).Mul(c.y, zInv, pool)
   238  	zInv2 := newGFp2(pool).Square(zInv, pool)
   239  	c.y.Mul(t, zInv2, pool)
   240  	t.Mul(c.x, zInv2, pool)
   241  	c.x.Set(t)
   242  	c.z.SetOne()
   243  	c.t.SetOne()
   244  
   245  	zInv.Put(pool)
   246  	t.Put(pool)
   247  	zInv2.Put(pool)
   248  
   249  	return c
   250  }
   251  
   252  func (c *twistPoint) Negative(a *twistPoint, pool *bnPool) {
   253  	c.x.Set(a.x)
   254  	c.y.SetZero()
   255  	c.y.Sub(c.y, a.y)
   256  	c.z.Set(a.z)
   257  	c.t.SetZero()
   258  }
   259
View as plain text