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	result := sha512.Sha512Bytes(api, m)
 16	return result[:]
 17}
 18
 19func pow2(n uint) *big.Int {
 20	result := big.NewInt(1)
 21	result.Lsh(result, n)
 22	return result
 23}
 24
 25type EdCurve = Curve[Ed25519, Ed25519Scalars]
 26type EdPoint = AffinePoint[Ed25519]
 27type EdCoordinate = emulated.Element[Ed25519]
 28type EdScalar = emulated.Element[Ed25519Scalars]
 29
 30func bits_to_scalar(c *EdCurve, s []frontend.Variable) EdCoordinate {
 31	if len(s) != 256 { panic("bad length") }
 32	elt := emulated.NewElement[Ed25519](0)
 33	if len(elt.Limbs) != 4 { panic("bad length") }
 34	i := 0
 35	elt.Limbs[0] = c.api.FromBinary(s[i:i+64]); i += 64
 36	elt.Limbs[1] = c.api.FromBinary(s[i:i+64]); i += 64
 37	elt.Limbs[2] = c.api.FromBinary(s[i:i+64]); i += 64
 38	elt.Limbs[3] = c.api.FromBinary(s[i:i+64]); i += 64
 39	if i != len(s) { panic("bad length") }
 40	return elt
 41}
 42
 43// func bits_to_clamped_scalar(c *EdCurve, input []frontend.Variable) EdScalar {
 44// 	if len(input) != 256 { panic("bad length") }
 45// 	s := make([]frontend.Variable, len(input))
 46// 	copy(s, input)
 47// 	s[0] = 0
 48// 	s[1] = 0
 49// 	s[2] = 0
 50// 	s[254] = 1
 51// 	return bits_to_scalar[Ed25519Scalars](c, s)
 52// }
 53
 54func bits_to_element(c *EdCurve, input []frontend.Variable) EdPoint {
 55	L := emulated.NewElement[Ed25519Scalars](rEd25519)
 56	unchecked_point := decodepoint(c, input)
 57	c.AssertIsZero(c.ScalarMul(unchecked_point, L))
 58	return unchecked_point
 59}
 60
 61// func publickey(c *EdCurve, seed []frontend.Variable) EdPoint {
 62// 	if len(seed) != 32 { panic("bad length") }
 63// 	a := bits_to_clamped_scalar(c, H(c.api, seed)[:256])
 64// 	return c.ScalarMul(c.g, a)
 65// }
 66
 67func checkvalid(c *EdCurve, s, m, pk []frontend.Variable) {
 68	if len(s) != 512 { panic("bad signature length") }
 69	if len(pk) != 256 { panic("bad public key length") }
 70	R := bits_to_element(c, s[:256])
 71	A := bits_to_element(c, pk)
 72	h := H(c.api, concat(s[:256], pk, m))
 73	v1 := c.ScalarMulBinary(c.g, s[256:])
 74	v2 := c.Add(R, c.ScalarMulBinary(A, h))
 75	c.AssertIsEqual(v1, v2)
 76}
 77
 78func concat(args ...[]frontend.Variable) []frontend.Variable {
 79	result := []frontend.Variable{}
 80	for _, v := range args {
 81		result = append(result, v...)
 82	}
 83	return result
 84}
 85
 86func decodepoint(c *EdCurve, input []frontend.Variable) EdPoint {
 87	if len(input) != 256 { panic("bad length") }
 88
 89	s := make([]frontend.Variable, len(input))
 90	copy(s, input)
 91	s[255] = 0
 92	y := bits_to_scalar(c, s)
 93//     unclamped = int(binascii.hexlify(s[:32][::-1]), 16)
 94//     clamp = (1 << 255) - 1
 95//     y = unclamped & clamp # clear MSB
 96
 97	x := xrecover(c, y)
 98//     x = xrecover(y)
 99
100	xbits := c.baseApi.ToBinary(x)
101	if len(xbits) != 256 { panic("bad length") }
102	mismatch := c.api.Xor(xbits[0], xbits[255])
103	x = c.baseApi.Select(mismatch, c.baseApi.Neg(x), x).(EdCoordinate)
104//     if bool(x & 1) != bool(unclamped & (1<<255)): x = Q-x
105
106	P := AffinePoint[Ed25519]{
107		X: x,
108		Y: y,
109	}
110//     P = [x,y]
111
112	c.AssertIsOnCurve(P)
113//     if not isoncurve(P): raise NotOnCurve("decoding point that is not on curve")
114
115	return P
116}
117
118func _const(x int64) EdCoordinate {
119	return emulated.NewElement[Ed25519](big.NewInt(x))
120}
121
122// Q = 2**255 - 19
123// L = 2**252 + 27742317777372353535851937790883648493
124// def inv(x):
125//     return pow(x, Q-2, Q)
126// d = -121665 * inv(121666)
127// I = pow(2,(Q-1)//4,Q)
128
129func xrecover(c *EdCurve, y EdCoordinate) EdCoordinate {	
130	Q := Ed25519{}.Modulus()
131	I := emulated.NewElement[Ed25519](newBigInt("2b8324804fc1df0b2b4d00993dfbd7a72f431806ad2fe478c4ee1b274a0ea0b0"))
132
133	yy := c.baseApi.Mul(y, y)
134	xx := c.baseApi.Div(
135		c.baseApi.Sub(yy, _const(1)),
136		c.baseApi.Add(c.baseApi.Mul(c.d, yy), _const(1)),
137	).(EdCoordinate)
138	// xx = (y*y-1) * inv(d*y*y+1)
139
140	power := new(big.Int).Add(Q, big.NewInt(3))
141	power.Rsh(power, 3)
142	x := pow(c, xx, power)
143	// x = pow(xx,(Q+3)//8,Q)
144
145	matches := c.baseApi.IsZero(c.baseApi.Sub(
146		c.baseApi.Mul(x, x),
147		xx,
148	))
149	x = c.baseApi.Select(matches, x, c.baseApi.Mul(x, emulated.NewElement[Ed25519](I))).(EdCoordinate)
150	// if (x*x - xx) % Q != 0: x = (x*I) % Q
151
152	even := c.baseApi.ToBinary(x)[0]
153	x = c.baseApi.Select(even, x, c.baseApi.Neg(x)).(EdCoordinate)
154	// if x % 2 != 0: x = Q-x
155
156	return x
157}
158
159func pow(c *EdCurve, base EdCoordinate, exponent *big.Int) EdCoordinate {
160	mul := base
161	result := _const(1)
162	for exponent.Sign() > 0 {
163		if exponent.Bit(0) != 0 {
164			result = c.baseApi.Mul(result, mul).(EdCoordinate)
165		}
166		mul = c.baseApi.Mul(mul, mul).(EdCoordinate)
167		exponent.Rsh(exponent, 1)
168	}
169	return result
170}
171
172// def checkvalid(s, m, pk):
173//     if len(s) != 64: raise Exception("signature length is wrong")
174//     if len(pk) != 32: raise Exception("public-key length is wrong")
175//     R = bytes_to_element(s[:32])
176//     A = bytes_to_element(pk)
177//     S = bytes_to_scalar(s[32:])
178//     h = Hint(s[:32] + pk + m)
179//     v1 = Base.scalarmult(S)
180//     v2 = R.add(A.scalarmult(h))
181//     return v1==v2
182
183// def publickey(seed):
184//     # turn first half of SHA512(seed) into scalar, then into point
185//     assert len(seed) == 32
186//     a = bytes_to_clamped_scalar(H(seed)[:32])
187//     A = Base.scalarmult(a)
188//     return A.to_bytes()
189
190// def bytes_to_scalar(s):
191//     assert len(s) == 32, len(s)
192//     return int(binascii.hexlify(s[::-1]), 16)
193
194
195// from pure25519.basic import (bytes_to_clamped_scalar,
196//                              bytes_to_scalar, scalar_to_bytes,
197//                              bytes_to_element, Base)
198// import hashlib, binascii
199
200// def H(m):
201//     return hashlib.sha512(m).digest()
202
203// def Hint(m):
204//     h = H(m)
205//     return int(binascii.hexlify(h[::-1]), 16)
206
207// def signature(m,sk,pk):
208//     assert len(sk) == 32 # seed
209//     assert len(pk) == 32
210//     h = H(sk[:32])
211//     a_bytes, inter = h[:32], h[32:]
212//     a = bytes_to_clamped_scalar(a_bytes)
213//     r = Hint(inter + m)
214//     R = Base.scalarmult(r)
215//     R_bytes = R.to_bytes()
216//     S = r + Hint(R_bytes + pk + m) * a
217//     return R_bytes + scalar_to_bytes(S)
218
219// def checkvalid(s, m, pk):
220//     if len(s) != 64: raise Exception("signature length is wrong")
221//     if len(pk) != 32: raise Exception("public-key length is wrong")
222//     R = bytes_to_element(s[:32])
223//     A = bytes_to_element(pk)
224//     S = bytes_to_scalar(s[32:])
225//     h = Hint(s[:32] + pk + m)
226//     v1 = Base.scalarmult(S)
227//     v2 = R.add(A.scalarmult(h))
228//     return v1==v2
229
230// # wrappers
231
232// import os
233
234// def create_signing_key():
235//     seed = os.urandom(32)
236//     return seed
237// def create_verifying_key(signing_key):
238//     return publickey(signing_key)
239
240// def sign(skbytes, msg):
241//     """Return just the signature, given the message and just the secret
242//     key."""
243//     if len(skbytes) != 32:
244//         raise ValueError("Bad signing key length %d" % len(skbytes))
245//     vkbytes = create_verifying_key(skbytes)
246//     sig = signature(msg, skbytes, vkbytes)
247//     return sig
248
249// def verify(vkbytes, sig, msg):
250//     if len(vkbytes) != 32:
251//         raise ValueError("Bad verifying key length %d" % len(vkbytes))
252//     if len(sig) != 64:
253//         raise ValueError("Bad signature length %d" % len(sig))
254//     rc = checkvalid(sig, msg, vkbytes)
255//     if not rc:
256//         raise ValueError("rc != 0", rc)
257//     return True