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