vendor/golang.org/x/crypto/bn256/gfp6.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 // 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 }