vendor/golang.org/x/crypto/bn256/twist.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
   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 func (c *twistPoint) MakeAffine(pool *bnPool) *twistPoint {
 223         if c.z.IsOne() {
 224                 return c
 225         }
 226
 227         zInv := newGFp2(pool).Invert(c.z, pool)
 228         t := newGFp2(pool).Mul(c.y, zInv, pool)
 229         zInv2 := newGFp2(pool).Square(zInv, pool)
 230         c.y.Mul(t, zInv2, pool)
 231         t.Mul(c.x, zInv2, pool)
 232         c.x.Set(t)
 233         c.z.SetOne()
 234         c.t.SetOne()
 235
 236         zInv.Put(pool)
 237         t.Put(pool)
 238         zInv2.Put(pool)
 239
 240         return c
 241 }
 242
 243 func (c *twistPoint) Negative(a *twistPoint, pool *bnPool) {
 244         c.x.Set(a.x)
 245         c.y.SetZero()
 246         c.y.Sub(c.y, a.y)
 247         c.z.Set(a.z)
 248         c.t.SetZero()
 249 }