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