1// Copyright 2020 ConsenSys AG 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15package bn254 16 17import ( 18 "math/big" 19 20 "github.com/consensys/gnark-crypto/ecc" 21 "github.com/consensys/gnark-crypto/ecc/bn254/fp" 22 "github.com/consensys/gnark-crypto/ecc/bn254/internal/fptower" 23) 24 25// hashToFp hashes msg to count prime field elements. 26// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-5.2 27func hashToFp(msg, dst []byte, count int) ([]fp.Element, error) { 28 29 // 128 bits of security 30 // L = ceil((ceil(log2(p)) + k) / 8), where k is the security parameter = 128 31 L := 48 32 33 lenInBytes := count * L 34 pseudoRandomBytes, err := ecc.ExpandMsgXmd(msg, dst, lenInBytes) 35 if err != nil { 36 return nil, err 37 } 38 39 res := make([]fp.Element, count) 40 for i := 0; i < count; i++ { 41 res[i].SetBytes(pseudoRandomBytes[i*L : (i+1)*L]) 42 } 43 return res, nil 44} 45 46// returns false if u>-u when seen as a bigInt 47func sign0(u fp.Element) bool { 48 var a, b big.Int 49 u.ToBigIntRegular(&a) 50 u.Neg(&u) 51 u.ToBigIntRegular(&b) 52 return a.Cmp(&b) <= 0 53} 54 55// ---------------------------------------------------------------------------------------- 56// G1Affine 57 58// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-4.1 59// Shallue and van de Woestijne method, works for any elliptic curve in Weierstrass curve 60func svdwMapG1(u fp.Element) G1Affine { 61 62 var res G1Affine 63 64 // constants 65 // sage script to find z: https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#appendix-E.1 66 var z, c1, c2, c3, c4 fp.Element 67 z.SetOne() 68 c1.SetString("4") 69 c2.SetString("10944121435919637611123202872628637544348155578648911831344518947322613104291") 70 c3.SetString("8815841940592487685674414971303048083897117035520822607866") 71 c4.SetString("7296080957279758407415468581752425029565437052432607887563012631548408736189") 72 73 var tv1, tv2, tv3, tv4, one, x1, gx1, x2, gx2, x3, x, gx, y fp.Element 74 one.SetOne() 75 tv1.Square(&u).Mul(&tv1, &c1) 76 tv2.Add(&one, &tv1) 77 tv1.Sub(&one, &tv1) 78 tv3.Mul(&tv2, &tv1).Inverse(&tv3) 79 tv4.Mul(&u, &tv1) 80 tv4.Mul(&tv4, &tv3) 81 tv4.Mul(&tv4, &c3) 82 x1.Sub(&c2, &tv4) 83 gx1.Square(&x1) 84 // 12. gx1 = gx1 + A 85 gx1.Mul(&gx1, &x1) 86 gx1.Add(&gx1, &bCurveCoeff) 87 e1 := gx1.Legendre() 88 x2.Add(&c2, &tv4) 89 gx2.Square(&x2) 90 // 18. gx2 = gx2 + A 91 gx2.Mul(&gx2, &x2) 92 gx2.Add(&gx2, &bCurveCoeff) 93 e2 := gx2.Legendre() - e1 // 2 if is_square(gx2) AND NOT e1 94 x3.Square(&tv2) 95 x3.Mul(&x3, &tv3) 96 x3.Square(&x3) 97 x3.Mul(&x3, &c4) 98 x3.Add(&x3, &z) 99 if e1 == 1 { 100 x.Set(&x1) 101 } else { 102 x.Set(&x3) 103 } 104 if e2 == 2 { 105 x.Set(&x2) 106 } 107 gx.Square(&x) 108 // gx = gx + A 109 gx.Mul(&gx, &x) 110 gx.Add(&gx, &bCurveCoeff) 111 y.Sqrt(&gx) 112 e3 := sign0(u) && sign0(y) 113 if !e3 { 114 y.Neg(&y) 115 } 116 res.X.Set(&x) 117 res.Y.Set(&y) 118 119 return res 120} 121 122// MapToCurveG1Svdw maps an fp.Element to a point on the curve using the Shallue and van de Woestijne map 123// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-2.2.1 124func MapToCurveG1Svdw(t fp.Element) G1Affine { 125 res := svdwMapG1(t) 126 return res 127} 128 129// EncodeToCurveG1Svdw maps an fp.Element to a point on the curve using the Shallue and van de Woestijne map 130// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-2.2.2 131func EncodeToCurveG1Svdw(msg, dst []byte) (G1Affine, error) { 132 var res G1Affine 133 t, err := hashToFp(msg, dst, 1) 134 if err != nil { 135 return res, err 136 } 137 res = MapToCurveG1Svdw(t[0]) 138 return res, nil 139} 140 141// HashToCurveG1Svdw maps an fp.Element to a point on the curve using the Shallue and van de Woestijne map 142// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-3 143func HashToCurveG1Svdw(msg, dst []byte) (G1Affine, error) { 144 var res G1Affine 145 u, err := hashToFp(msg, dst, 2) 146 if err != nil { 147 return res, err 148 } 149 Q0 := MapToCurveG1Svdw(u[0]) 150 Q1 := MapToCurveG1Svdw(u[1]) 151 var _Q0, _Q1, _res G1Jac 152 _Q0.FromAffine(&Q0) 153 _Q1.FromAffine(&Q1) 154 _res.Set(&_Q1).AddAssign(&_Q0) 155 res.FromJacobian(&_res) 156 return res, nil 157} 158 159// ---------------------------------------------------------------------------------------- 160// G2Affine 161 162// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-4.1 163// Shallue and van de Woestijne method, works for any elliptic curve in Weierstrass curve 164func svdwMapG2(u fptower.E2) G2Affine { 165 166 var res G2Affine 167 168 // constants 169 // sage script to find z: https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#appendix-E.1 170 var z, c1, c2, c3, c4 fptower.E2 171 z.A1.SetString("1") 172 c1.A0.SetString("19485874751759354771024239261021720505790618469301721065564631296452457478373") 173 c1.A1.SetString("266929791119991161246907387137283842545076965332900288569378510910307636689") 174 c2.A1.SetString("10944121435919637611123202872628637544348155578648911831344518947322613104291") 175 c3.A0.SetString("13617985070220897759416741581922326973608167195618746963957740978229330444385") 176 c3.A1.SetString("6485072654231349560354894037339044590945718224403932749563131108378844487223") 177 c4.A0.SetString("18685085378399381287283517099609868978155387573303020199856495763721534568303") 178 c4.A1.SetString("355906388159988214995876516183045123393435953777200384759171347880410182252") 179 180 var tv1, tv2, tv3, tv4, one, x1, gx1, x2, gx2, x3, x, gx, y fptower.E2 181 one.SetOne() 182 tv1.Square(&u).Mul(&tv1, &c1) 183 tv2.Add(&one, &tv1) 184 tv1.Sub(&one, &tv1) 185 tv3.Mul(&tv2, &tv1).Inverse(&tv3) 186 tv4.Mul(&u, &tv1) 187 tv4.Mul(&tv4, &tv3) 188 tv4.Mul(&tv4, &c3) 189 x1.Sub(&c2, &tv4) 190 gx1.Square(&x1) 191 // 12. gx1 = gx1 + A 192 gx1.Mul(&gx1, &x1) 193 gx1.Add(&gx1, &bTwistCurveCoeff) 194 e1 := gx1.Legendre() 195 x2.Add(&c2, &tv4) 196 gx2.Square(&x2) 197 // 18. gx2 = gx2 + A 198 gx2.Mul(&gx2, &x2) 199 gx2.Add(&gx2, &bTwistCurveCoeff) 200 e2 := gx2.Legendre() - e1 // 2 if is_square(gx2) AND NOT e1 201 x3.Square(&tv2) 202 x3.Mul(&x3, &tv3) 203 x3.Square(&x3) 204 x3.Mul(&x3, &c4) 205 x3.Add(&x3, &z) 206 if e1 == 1 { 207 x.Set(&x1) 208 } else { 209 x.Set(&x3) 210 } 211 if e2 == 2 { 212 x.Set(&x2) 213 } 214 gx.Square(&x) 215 // gx = gx + A 216 gx.Mul(&gx, &x) 217 gx.Add(&gx, &bTwistCurveCoeff) 218 y.Sqrt(&gx) 219 e3 := sign0(u.A0) && sign0(y.A0) 220 if !e3 { 221 y.Neg(&y) 222 } 223 res.X.Set(&x) 224 res.Y.Set(&y) 225 226 return res 227} 228 229// MapToCurveG2Svdw maps an fp.Element to a point on the curve using the Shallue and van de Woestijne map 230// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-2.2.1 231func MapToCurveG2Svdw(t fptower.E2) G2Affine { 232 res := svdwMapG2(t) 233 res.ClearCofactor(&res) 234 return res 235} 236 237// EncodeToCurveG2Svdw maps an fp.Element to a point on the curve using the Shallue and van de Woestijne map 238// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-2.2.2 239func EncodeToCurveG2Svdw(msg, dst []byte) (G2Affine, error) { 240 var res G2Affine 241 _t, err := hashToFp(msg, dst, 2) 242 if err != nil { 243 return res, err 244 } 245 var t fptower.E2 246 t.A0.Set(&_t[0]) 247 t.A1.Set(&_t[1]) 248 res = MapToCurveG2Svdw(t) 249 return res, nil 250} 251 252// HashToCurveG2Svdw maps an fp.Element to a point on the curve using the Shallue and van de Woestijne map 253// https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-3 254func HashToCurveG2Svdw(msg, dst []byte) (G2Affine, error) { 255 var res G2Affine 256 u, err := hashToFp(msg, dst, 4) 257 if err != nil { 258 return res, err 259 } 260 var u0, u1 fptower.E2 261 u0.A0.Set(&u[0]) 262 u0.A1.Set(&u[1]) 263 u1.A0.Set(&u[2]) 264 u1.A1.Set(&u[3]) 265 Q0 := MapToCurveG2Svdw(u0) 266 Q1 := MapToCurveG2Svdw(u1) 267 var _Q0, _Q1, _res G2Jac 268 _Q0.FromAffine(&Q0) 269 _Q1.FromAffine(&Q1) 270 _res.Set(&_Q1).AddAssign(&_Q0) 271 res.FromJacobian(&_res) 272 return res, nil 273} 274