1// Copyright 2020 The go-ethereum Authors 2// This file is part of the go-ethereum library. 3// 4// The go-ethereum library is free software: you can redistribute it and/or modify 5// it under the terms of the GNU Lesser General Public License as published by 6// the Free Software Foundation, either version 3 of the License, or 7// (at your option) any later version. 8// 9// The go-ethereum library is distributed in the hope that it will be useful, 10// but WITHOUT ANY WARRANTY; without even the implied warranty of 11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12// GNU Lesser General Public License for more details. 13// 14// You should have received a copy of the GNU Lesser General Public License 15// along with the go-ethereum library. If not, see <http://www.gnu.org/licenses/>. 16 17package bls12381 18 19import ( 20 "errors" 21 "math/big" 22) 23 24type fp2Temp struct { 25 t [4]*fe 26} 27 28type fp2 struct { 29 fp2Temp 30} 31 32func newFp2Temp() fp2Temp { 33 t := [4]*fe{} 34 for i := 0; i < len(t); i++ { 35 t[i] = &fe{} 36 } 37 return fp2Temp{t} 38} 39 40func newFp2() *fp2 { 41 t := newFp2Temp() 42 return &fp2{t} 43} 44 45func (e *fp2) fromBytes(in []byte) (*fe2, error) { 46 if len(in) != 96 { 47 return nil, errors.New("length of input string should be 96 bytes") 48 } 49 c1, err := fromBytes(in[:48]) 50 if err != nil { 51 return nil, err 52 } 53 c0, err := fromBytes(in[48:]) 54 if err != nil { 55 return nil, err 56 } 57 return &fe2{*c0, *c1}, nil 58} 59 60func (e *fp2) toBytes(a *fe2) []byte { 61 out := make([]byte, 96) 62 copy(out[:48], toBytes(&a[1])) 63 copy(out[48:], toBytes(&a[0])) 64 return out 65} 66 67func (e *fp2) new() *fe2 { 68 return new(fe2).zero() 69} 70 71func (e *fp2) zero() *fe2 { 72 return new(fe2).zero() 73} 74 75func (e *fp2) one() *fe2 { 76 return new(fe2).one() 77} 78 79func (e *fp2) add(c, a, b *fe2) { 80 add(&c[0], &a[0], &b[0]) 81 add(&c[1], &a[1], &b[1]) 82} 83 84func (e *fp2) addAssign(a, b *fe2) { 85 addAssign(&a[0], &b[0]) 86 addAssign(&a[1], &b[1]) 87} 88 89func (e *fp2) ladd(c, a, b *fe2) { 90 ladd(&c[0], &a[0], &b[0]) 91 ladd(&c[1], &a[1], &b[1]) 92} 93 94func (e *fp2) double(c, a *fe2) { 95 double(&c[0], &a[0]) 96 double(&c[1], &a[1]) 97} 98 99func (e *fp2) doubleAssign(a *fe2) { 100 doubleAssign(&a[0]) 101 doubleAssign(&a[1]) 102} 103 104func (e *fp2) ldouble(c, a *fe2) { 105 ldouble(&c[0], &a[0]) 106 ldouble(&c[1], &a[1]) 107} 108 109func (e *fp2) sub(c, a, b *fe2) { 110 sub(&c[0], &a[0], &b[0]) 111 sub(&c[1], &a[1], &b[1]) 112} 113 114func (e *fp2) subAssign(c, a *fe2) { 115 subAssign(&c[0], &a[0]) 116 subAssign(&c[1], &a[1]) 117} 118 119func (e *fp2) neg(c, a *fe2) { 120 neg(&c[0], &a[0]) 121 neg(&c[1], &a[1]) 122} 123 124func (e *fp2) mul(c, a, b *fe2) { 125 t := e.t 126 mul(t[1], &a[0], &b[0]) 127 mul(t[2], &a[1], &b[1]) 128 add(t[0], &a[0], &a[1]) 129 add(t[3], &b[0], &b[1]) 130 sub(&c[0], t[1], t[2]) 131 addAssign(t[1], t[2]) 132 mul(t[0], t[0], t[3]) 133 sub(&c[1], t[0], t[1]) 134} 135 136func (e *fp2) mulAssign(a, b *fe2) { 137 t := e.t 138 mul(t[1], &a[0], &b[0]) 139 mul(t[2], &a[1], &b[1]) 140 add(t[0], &a[0], &a[1]) 141 add(t[3], &b[0], &b[1]) 142 sub(&a[0], t[1], t[2]) 143 addAssign(t[1], t[2]) 144 mul(t[0], t[0], t[3]) 145 sub(&a[1], t[0], t[1]) 146} 147 148func (e *fp2) square(c, a *fe2) { 149 t := e.t 150 ladd(t[0], &a[0], &a[1]) 151 sub(t[1], &a[0], &a[1]) 152 ldouble(t[2], &a[0]) 153 mul(&c[0], t[0], t[1]) 154 mul(&c[1], t[2], &a[1]) 155} 156 157func (e *fp2) squareAssign(a *fe2) { 158 t := e.t 159 ladd(t[0], &a[0], &a[1]) 160 sub(t[1], &a[0], &a[1]) 161 ldouble(t[2], &a[0]) 162 mul(&a[0], t[0], t[1]) 163 mul(&a[1], t[2], &a[1]) 164} 165 166func (e *fp2) mulByNonResidue(c, a *fe2) { 167 t := e.t 168 sub(t[0], &a[0], &a[1]) 169 add(&c[1], &a[0], &a[1]) 170 c[0].set(t[0]) 171} 172 173func (e *fp2) mulByB(c, a *fe2) { 174 t := e.t 175 double(t[0], &a[0]) 176 double(t[1], &a[1]) 177 doubleAssign(t[0]) 178 doubleAssign(t[1]) 179 sub(&c[0], t[0], t[1]) 180 add(&c[1], t[0], t[1]) 181} 182 183func (e *fp2) inverse(c, a *fe2) { 184 t := e.t 185 square(t[0], &a[0]) 186 square(t[1], &a[1]) 187 addAssign(t[0], t[1]) 188 inverse(t[0], t[0]) 189 mul(&c[0], &a[0], t[0]) 190 mul(t[0], t[0], &a[1]) 191 neg(&c[1], t[0]) 192} 193 194func (e *fp2) mulByFq(c, a *fe2, b *fe) { 195 mul(&c[0], &a[0], b) 196 mul(&c[1], &a[1], b) 197} 198 199func (e *fp2) exp(c, a *fe2, s *big.Int) { 200 z := e.one() 201 for i := s.BitLen() - 1; i >= 0; i-- { 202 e.square(z, z) 203 if s.Bit(i) == 1 { 204 e.mul(z, z, a) 205 } 206 } 207 c.set(z) 208} 209 210func (e *fp2) frobeniusMap(c, a *fe2, power uint) { 211 c[0].set(&a[0]) 212 if power%2 == 1 { 213 neg(&c[1], &a[1]) 214 return 215 } 216 c[1].set(&a[1]) 217} 218 219func (e *fp2) frobeniusMapAssign(a *fe2, power uint) { 220 if power%2 == 1 { 221 neg(&a[1], &a[1]) 222 return 223 } 224} 225 226func (e *fp2) sqrt(c, a *fe2) bool { 227 u, x0, a1, alpha := &fe2{}, &fe2{}, &fe2{}, &fe2{} 228 u.set(a) 229 e.exp(a1, a, pMinus3Over4) 230 e.square(alpha, a1) 231 e.mul(alpha, alpha, a) 232 e.mul(x0, a1, a) 233 if alpha.equal(negativeOne2) { 234 neg(&c[0], &x0[1]) 235 c[1].set(&x0[0]) 236 return true 237 } 238 e.add(alpha, alpha, e.one()) 239 e.exp(alpha, alpha, pMinus1Over2) 240 e.mul(c, alpha, x0) 241 e.square(alpha, c) 242 return alpha.equal(u) 243} 244 245func (e *fp2) isQuadraticNonResidue(a *fe2) bool { 246 // https://github.com/leovt/constructible/wiki/Taking-Square-Roots-in-quadratic-extension-Fields 247 c0, c1 := new(fe), new(fe) 248 square(c0, &a[0]) 249 square(c1, &a[1]) 250 add(c1, c1, c0) 251 return isQuadraticNonResidue(c1) 252} 253