1package edwards_curve
  2
  3
  4// This file is little-endian
  5
  6import (
  7	"math/big"
  8	"github.com/consensys/gnark/frontend"
  9	"github.com/consensys/gnark/std/math/emulated"
 10	"gnark-ed25519/sha512"
 11)
 12
 13
 14func H(api frontend.API, m []frontend.Variable) []frontend.Variable {
 15	rawResult := sha512.Sha512(api, swapByteEndianness(m))
 16	sResult := swapByteEndianness(rawResult[:])
 17	return sResult
 18}
 19
 20func pow2(n uint) *big.Int {
 21	result := big.NewInt(1)
 22	result.Lsh(result, n)
 23	return result
 24}
 25
 26type EdCurve = Curve[Ed25519, Ed25519Scalars]
 27type EdPoint = AffinePoint[Ed25519]
 28type EdCoordinate = emulated.Element[Ed25519]
 29type EdScalar = emulated.Element[Ed25519Scalars]
 30
 31func bits_to_scalar(c *EdCurve, s []frontend.Variable) EdCoordinate {
 32	if len(s) != 256 { panic("bad length") }
 33	elt := emulated.NewElement[Ed25519](0)
 34	if len(elt.Limbs) != 4 { panic("bad length") }
 35	i := 0
 36	for k := 0; k < 4; k++ {
 37		elt.Limbs[k] = c.api.FromBinary(s[i:i+64]...)
 38		i += 64
 39	}
 40	if i != len(s) { panic("bad length") }
 41	return elt
 42}
 43
 44// func bits_to_clamped_scalar(c *EdCurve, input []frontend.Variable) EdScalar {
 45// 	if len(input) != 256 { panic("bad length") }
 46// 	s := make([]frontend.Variable, len(input))
 47// 	copy(s, input)
 48// 	s[0] = 0
 49// 	s[1] = 0
 50// 	s[2] = 0
 51// 	s[254] = 1
 52// 	return bits_to_scalar[Ed25519Scalars](c, s)
 53// }
 54
 55func bits_to_element(c *EdCurve, input []frontend.Variable) EdPoint {
 56	// L := emulated.NewElement[Ed25519Scalars](rEd25519)
 57	unchecked_point := decodepoint(c, input)
 58
 59	// // TODO: https://github.com/warner/python-pure25519 says this check is not necessary:
 60	// //
 61	// // > This library is conservative, and performs full subgroup-membership checks on decoded
 62	// // > points, which adds considerable overhead. The Curve25519/Ed25519 algorithms were
 63	// // > designed to not require these checks, so a careful application might be able to
 64	// // > improve on this slightly (Ed25519 verify down to 6.2ms, DH-finish to 3.2ms).
 65	// c.AssertIsZero(c.ScalarMul(unchecked_point, L))
 66
 67	return unchecked_point
 68}
 69
 70// func publickey(c *EdCurve, seed []frontend.Variable) EdPoint {
 71// 	if len(seed) != 32 { panic("bad length") }
 72// 	a := bits_to_clamped_scalar(c, H(c.api, seed)[:256])
 73// 	return c.ScalarMul(c.g, a)
 74// }
 75
 76func CheckValid(c *EdCurve, s, m, pk []frontend.Variable) {
 77	if len(s) != 512 { panic("bad signature length") }
 78	if len(pk) != 256 { panic("bad public key length") }
 79	if len(m) % 8 != 0 { panic("bad message length") }
 80	R := bits_to_element(c, s[:256])
 81	A := bits_to_element(c, pk)
 82	h := H(c.api, concat(s[:256], pk, m))
 83	v1 := c.ScalarMulBinary(c.g, s[256:])
 84	v2 := c.Add(R, c.ScalarMulBinary(A, h))
 85	c.AssertIsEqual(v1, v2)
 86}
 87
 88func reverse[T interface{}](arr []T) []T {
 89	result := make([]T, len(arr))
 90	for i, v := range arr {
 91		result[len(result)-i-1] = v
 92	}
 93	return result
 94}
 95
 96func concat(args ...[]frontend.Variable) []frontend.Variable {
 97	result := []frontend.Variable{}
 98	for _, v := range args {
 99		result = append(result, v...)
100	}
101	return result
102}
103
104func decodepoint(c *EdCurve, unclamped []frontend.Variable) EdPoint {
105	if len(unclamped) != 256 { panic("bad length") }
106
107	s := make([]frontend.Variable, len(unclamped))
108	copy(s, unclamped)
109	s[255] = 0
110	y := bits_to_scalar(c, s)
111//     unclamped = int(binascii.hexlify(s[:32][::-1]), 16)
112//     clamp = (1 << 255) - 1
113//     y = unclamped & clamp # clear MSB
114
115	x := xrecover(c, y)
116//     x = xrecover(y)
117
118	xbits := c.baseApi.ToBinary(x)
119	if len(xbits) != 256 { panic("bad length") }
120	mismatch := c.api.Xor(xbits[0], unclamped[255])
121	x = c.baseApi.Select(mismatch, c.baseApi.Neg(x), x).(EdCoordinate)
122//     if bool(x & 1) != bool(unclamped & (1<<255)): x = Q-x
123
124	P := AffinePoint[Ed25519]{
125		X: x,
126		Y: y,
127	}
128//     P = [x,y]
129
130	c.AssertIsOnCurve(P)
131//     if not isoncurve(P): raise NotOnCurve("decoding point that is not on curve")
132
133	return P
134}
135
136func toValue(s EdCoordinate) *big.Int {
137	result := big.NewInt(0)
138	placeValue := big.NewInt(1)
139	for _, v := range s.Limbs {
140		q := new(big.Int).Mul(placeValue, v.(*big.Int))
141		result.Add(result, q)
142		placeValue.Lsh(placeValue, Ed25519{}.BitsPerLimb())
143	}
144	return result
145}
146
147func _const(x int64) EdCoordinate {
148	return emulated.NewElement[Ed25519](big.NewInt(x))
149}
150
151// Q = 2**255 - 19
152// L = 2**252 + 27742317777372353535851937790883648493
153// def inv(x):
154//     return pow(x, Q-2, Q)
155// d = -121665 * inv(121666)
156// I = pow(2,(Q-1)//4,Q)
157
158func xrecover(c *EdCurve, y EdCoordinate) EdCoordinate {	
159	Q := Ed25519{}.Modulus()
160	I := emulated.NewElement[Ed25519](newBigInt("2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0"))
161
162	yy := c.baseApi.Mul(y, y)
163	xx := c.baseApi.Div(
164		c.baseApi.Sub(yy, _const(1)),
165		c.baseApi.Add(c.baseApi.Mul(c.d, yy), _const(1)),
166	).(EdCoordinate)
167	// xx = (y*y-1) * inv(d*y*y+1)
168
169	power := new(big.Int).Add(Q, big.NewInt(3))
170	power.Rsh(power, 3)
171	x := pow(c, xx, power)
172	// x = pow(xx,(Q+3)//8,Q)
173
174	matches := c.baseApi.IsZero(c.baseApi.Sub(
175		c.baseApi.Mul(x, x),
176		xx,
177	))
178	x = c.baseApi.Select(matches, x, c.baseApi.Mul(x, emulated.NewElement[Ed25519](I))).(EdCoordinate)
179	// if (x*x - xx) % Q != 0: x = (x*I) % Q
180
181	odd := c.baseApi.ToBinary(x)[0]
182	x = c.baseApi.Select(odd, c.baseApi.Neg(x), x).(EdCoordinate)
183	// if x % 2 != 0: x = Q-x
184
185	return x
186}
187
188func pow(c *EdCurve, base EdCoordinate, exponent *big.Int) EdCoordinate {
189	mul := base
190	result := _const(1)
191	for exponent.Sign() > 0 {
192		if exponent.Bit(0) != 0 {
193			result = c.baseApi.Mul(result, mul).(EdCoordinate)
194		}
195		mul = c.baseApi.Mul(mul, mul).(EdCoordinate)
196		exponent.Rsh(exponent, 1)
197	}
198	return result
199}
200
201func swapByteEndianness(in []frontend.Variable) []frontend.Variable {
202	if len(in) % 8 != 0 { panic("must be a multiple of 8 bits") }
203	result := make([]frontend.Variable, len(in))
204	for i := 0; i < len(in); i += 8 {
205		for j := 0; j < 8; j++ {
206			result[i+j] = in[i+7-j]
207		}
208	}
209	return result
210}
211
212// def checkvalid(s, m, pk):
213//     if len(s) != 64: raise Exception("signature length is wrong")
214//     if len(pk) != 32: raise Exception("public-key length is wrong")
215//     R = bytes_to_element(s[:32])
216//     A = bytes_to_element(pk)
217//     S = bytes_to_scalar(s[32:])
218//     h = Hint(s[:32] + pk + m)
219//     v1 = Base.scalarmult(S)
220//     v2 = R.add(A.scalarmult(h))
221//     return v1==v2
222
223// def publickey(seed):
224//     # turn first half of SHA512(seed) into scalar, then into point
225//     assert len(seed) == 32
226//     a = bytes_to_clamped_scalar(H(seed)[:32])
227//     A = Base.scalarmult(a)
228//     return A.to_bytes()
229
230// def bytes_to_scalar(s):
231//     assert len(s) == 32, len(s)
232//     return int(binascii.hexlify(s[::-1]), 16)
233
234
235// from pure25519.basic import (bytes_to_clamped_scalar,
236//                              bytes_to_scalar, scalar_to_bytes,
237//                              bytes_to_element, Base)
238// import hashlib, binascii
239
240// def H(m):
241//     return hashlib.sha512(m).digest()
242
243// def Hint(m):
244//     h = H(m)
245//     return int(binascii.hexlify(h[::-1]), 16)
246
247// def signature(m,sk,pk):
248//     assert len(sk) == 32 # seed
249//     assert len(pk) == 32
250//     h = H(sk[:32])
251//     a_bytes, inter = h[:32], h[32:]
252//     a = bytes_to_clamped_scalar(a_bytes)
253//     r = Hint(inter + m)
254//     R = Base.scalarmult(r)
255//     R_bytes = R.to_bytes()
256//     S = r + Hint(R_bytes + pk + m) * a
257//     return R_bytes + scalar_to_bytes(S)
258
259// def checkvalid(s, m, pk):
260//     if len(s) != 64: raise Exception("signature length is wrong")
261//     if len(pk) != 32: raise Exception("public-key length is wrong")
262//     R = bytes_to_element(s[:32])
263//     A = bytes_to_element(pk)
264//     S = bytes_to_scalar(s[32:])
265//     h = Hint(s[:32] + pk + m)
266//     v1 = Base.scalarmult(S)
267//     v2 = R.add(A.scalarmult(h))
268//     return v1==v2
269
270// # wrappers
271
272// import os
273
274// def create_signing_key():
275//     seed = os.urandom(32)
276//     return seed
277// def create_verifying_key(signing_key):
278//     return publickey(signing_key)
279
280// def sign(skbytes, msg):
281//     """Return just the signature, given the message and just the secret
282//     key."""
283//     if len(skbytes) != 32:
284//         raise ValueError("Bad signing key length %d" % len(skbytes))
285//     vkbytes = create_verifying_key(skbytes)
286//     sig = signature(msg, skbytes, vkbytes)
287//     return sig
288
289// def verify(vkbytes, sig, msg):
290//     if len(vkbytes) != 32:
291//         raise ValueError("Bad verifying key length %d" % len(vkbytes))
292//     if len(sig) != 64:
293//         raise ValueError("Bad signature length %d" % len(sig))
294//     rc = checkvalid(sig, msg, vkbytes)
295//     if not rc:
296//         raise ValueError("rc != 0", rc)
297//     return True