Ed25519 - Edwards-curve Digital Signature Algorithm (EdDSA) uses Curve 25519 and SHA-512 to produce an EdDSA signature. In this case we will perform the core operations in the signing and verification. With this we calculate the hash of the message (\(h\)) and have a public key (\(pk\)) and a private key (\(sk\)). We then generate a signature of (\(R,s\)). The public key (\(pk\)) and (\(R,s\)) is then used to check the signature. It is standardized RFC [RFC 8032] and is based on the Schnorr's signature scheme and uses (possibly twisted) Edwards curves. For Ed25519 we use 32 byte values for both the private key and the public key, and for X448 we use 57 byte values for both the private key and the public key.
Ed25519 - Edwards-curve Digital Signature Algorithm (EdDSA) using RFC 8032 |
Theory
The generalize form of the curve is:
\(x^2 = (y^2 - 1) / (d y^2 + 1) \pmod p \)
and is specificially defined as:
\(−x^2+y^2=1−(121665/121666)x^2y^2 \pmod p\)
with a prime number (\(p\)) of \(2^{255}-19\) and the order (\(L\)) of \(2^{252}+27742317777372353535851937790883648493\). The base point is \(y=4/5\), and which is:
>>> p=2**255-19 >>> y=4*pow(5,-1,p) >>> print (y) 46316835694926478169428394003475163141307993866256225615783033603165251855960
And we can then work out the x co-ordinate with:
\(x=(u/v)^{(p+3)/8}\)
and where \(u = y^2 - 1\) and \(v = d y^2 + 1\). A Python program to recover the base point is:
p = 2**255 - 19 def inv(x): return pow(x, p-2, p) d = -121665 * inv(121666) I = pow(2,(p-1)//4,p) def findx(y): xx = (y*y-1) * inv(d*y*y+1) x = pow(xx,(p+3)//8,p) if (x*x - xx) % p != 0: x = (x*I) % p if x % 2 != 0: x = p-x return x y = 4 * inv(5) x = findx(y) print (x,y)
and which gives:
15112221349535400772501151409588531511454012693041857206046113283949847762202 46316835694926478169428394003475163141307993866256225615783033603165251855960
With EdDSA, Alice will sign a message with her private key, and then Bob will use her public key to verify that she signed the message (and that the message has now changed):
Key generation
Alice generates a random 32-byte secret key (\(sk\)) and then creates a public key of:
\(pk=sk \cdot G\)
and where \(G\) is the base point of the curve.
Signing
Alice creates a SHA-512 hash of her private key:
\(h=\textrm{HASH}(sk)\)
Create \(r\) from the upper 32 bytes of hash and the message:
\( r = \textrm{HASH}(h[32:] \: || \: m))\)
And where "||" represents a concatenation of the byte array values. Next she matches \(r\) onto curve with:
\(R=r \cdot G\)
Next Alice computes \(s\) with:
\(s=r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk\)
The signature is (\(R,s\)). The values of \(R\) and \(s\) are 32 bytes long, and thus the signature is 64 bytes long.
Verifying
Bob creates \(S\) using \(R\), \(pk\) and \(m\):
\(S =\textrm{HASH}(R \: || \: pk \: || \: m) \)
And next creates two verification values:
\(v_1=s \cdot G\)
\(v_2=R+ pk \cdot S\)
If \(v_1==v_2\) the signature checks. This is because:
\(v_1=sB = (r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk) \cdot G = rG + sk \cdot B \cdot (\textrm{HASH}(R \: || \: pk \: || \: m))= R+ pk \cdot S = v_2 \pmod q \)
Overall, we just need point multiplication and point addition.
The following is an outline of the code from RFC 8032:
import hashlib import os import sys import binascii def sha512(s): return hashlib.sha512(s).digest() # Base field Z_p p = 2**255 - 19 def modp_inv(x): return pow(x, p-2, p) # Curve constant d = -121665 * modp_inv(121666) % p # Group order q = 2**252 + 27742317777372353535851937790883648493 def sha512_modq(s): return int.from_bytes(sha512(s), "little") % q ## Then follows functions to perform point operations. # Points are represented as tuples (X, Y, Z, T) of extended # coordinates, with x = X/Z, y = Y/Z, x*y = T/Z def point_add(P, Q): A, B = (P[1]-P[0]) * (Q[1]-Q[0]) % p, (P[1]+P[0]) * (Q[1]+Q[0]) % p; C, D = 2 * P[3] * Q[3] * d % p, 2 * P[2] * Q[2] % p; E, F, G, H = B-A, D-C, D+C, B+A; return (E*F, G*H, F*G, E*H); # Computes Q = s * Q def point_mul(s, P): Q = (0, 1, 1, 0) # Neutral element while s > 0: if s & 1: Q = point_add(Q, P) P = point_add(P, P) s >>= 1 return Q def point_equal(P, Q): # x1 / z1 == x2 / z2 <==> x1 * z2 == x2 * z1 if (P[0] * Q[2] - Q[0] * P[2]) % p != 0: return False if (P[1] * Q[2] - Q[1] * P[2]) % p != 0: return False return True ## Now follows functions for point compression. # Square root of -1 modp_sqrt_m1 = pow(2, (p-1) // 4, p) # Compute corresponding x-coordinate, with low bit corresponding to # sign, or return None on failure def recover_x(y, sign): if y >= p: return None x2 = (y*y-1) * modp_inv(d*y*y+1) if x2 == 0: if sign: return None else: return 0 # Compute square root of x2 x = pow(x2, (p+3) // 8, p) if (x*x - x2) % p != 0: x = x * modp_sqrt_m1 % p if (x*x - x2) % p != 0: return None if (x & 1) != sign: x = p - x return x # Base point g_y = 4 * modp_inv(5) % p g_x = recover_x(g_y, 0) G = (g_x, g_y, 1, g_x * g_y % p) def point_compress(P): zinv = modp_inv(P[2]) x = P[0] * zinv % p y = P[1] * zinv % p return int.to_bytes(y | ((x & 1) << 255), 32, "little") def point_decompress(s): if len(s) != 32: raise Exception("Invalid input length for decompression") y = int.from_bytes(s, "little") sign = y >> 255 y &= (1 << 255) - 1 x = recover_x(y, sign) if x is None: return None else: return (x, y, 1, x*y % p) ## These are functions for manipulating the private key. def secret_expand(secret): if len(secret) != 32: raise Exception("Bad size of private key") h = sha512(secret) a = int.from_bytes(h[:32], "little") a &= (1 << 254) - 8 a |= (1 << 254) return (a, h[32:]) def publickey(secret): (a, dummy) = secret_expand(secret) return point_compress(point_mul(a, G)) ## The signature function works as below. def signature(secret, msg): a, prefix = secret_expand(secret) A = point_compress(point_mul(a, G)) r = sha512_modq(prefix + msg) R = point_mul(r, G) Rs = point_compress(R) h = sha512_modq(Rs + A + msg) s = (r + h * a) % q return Rs ,int.to_bytes(s, 32, "little") ## And finally the verification function. def verify(public, msg, signature): if len(public) != 32: raise Exception("Bad public key length") if len(signature) != 64: Exception("Bad signature length") A = point_decompress(public) if not A: return False Rs = signature[:32] R = point_decompress(Rs) if not R: return False s = int.from_bytes(signature[32:], "little") if s >= q: return False h = sha512_modq(Rs + public + msg) sB = point_mul(s, G) hA = point_mul(h, A) return point_equal(sB, point_add(R, hA)) print (f"Base point: {G[0]},{G[1]}") sk=os.urandom(32) pk=publickey(sk) print (f"\nPrivate key: {binascii.hexlify(sk).decode()}\nPublic key: {binascii.hexlify(pk).decode()}") m="Hello" if (len(sys.argv)>1): m=str(sys.argv[1]) m=m.encode() print(f"\nMessage: {m.decode()}\n") R,s=signature(sk,m) print (f"\nSignature\nR: {binascii.hexlify(R).decode()}\ns:{binascii.hexlify(s).decode()}") sig=R+s ver=verify(pk,m,sig) print ("\nVerified: ",ver)
A sample run is:
Base point: 15112221349535400772501151409588531511454012693041857206046113283949847762202,46316835694926478169428394003475163141307993866256225615783033603165251855960 Private key: b'38d555fc69d30269a371871473e4727f7406d40855840b32816367476f6d1f88' Public key: b'e9f2dcb6bbfb9fbd41d984490265cb624918c3b0eb16b1b30cfeea656a243360' Message: Hello Signature R: b'b31effd71522fb03e1f932d5f4e2115b43f5ae9d793407c752a36b4937339953' s:b'9000dc10cf0ee2695c143df1ce7976102f50c8d999e365522e9b656db63b990f' Verified: True