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 5package 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 11import ( 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. 17type gfP2 struct { 18 x, y *big.Int // value is xi+y. 19} 20 21func newGFp2(pool *bnPool) *gfP2 { 22 return &gfP2{pool.Get(), pool.Get()} 23} 24 25func (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 31func (e *gfP2) Put(pool *bnPool) { 32 pool.Put(e.x) 33 pool.Put(e.y) 34} 35 36func (e *gfP2) Set(a *gfP2) *gfP2 { 37 e.x.Set(a.x) 38 e.y.Set(a.y) 39 return e 40} 41 42func (e *gfP2) SetZero() *gfP2 { 43 e.x.SetInt64(0) 44 e.y.SetInt64(0) 45 return e 46} 47 48func (e *gfP2) SetOne() *gfP2 { 49 e.x.SetInt64(0) 50 e.y.SetInt64(1) 51 return e 52} 53 54func (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 63func (e *gfP2) IsZero() bool { 64 return e.x.Sign() == 0 && e.y.Sign() == 0 65} 66 67func (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 75func (e *gfP2) Conjugate(a *gfP2) *gfP2 { 76 e.y.Set(a.y) 77 e.x.Neg(a.x) 78 return e 79} 80 81func (e *gfP2) Negative(a *gfP2) *gfP2 { 82 e.x.Neg(a.x) 83 e.y.Neg(a.y) 84 return e 85} 86 87func (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 93func (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 99func (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 105func (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 129func (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 148func (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+9 and then returns e. 155func (e *gfP2) MulXi(a *gfP2, pool *bnPool) *gfP2 { 156 // (xi+y)(i+3) = (9x+y)i+(9y-x) 157 tx := pool.Get().Lsh(a.x, 3) 158 tx.Add(tx, a.x) 159 tx.Add(tx, a.y) 160 161 ty := pool.Get().Lsh(a.y, 3) 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 174func (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 195func (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 221func (e *gfP2) Real() *big.Int { 222 return e.x 223} 224 225func (e *gfP2) Imag() *big.Int { 226 return e.y 227} 228