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\)) using a random value of \(k\). The public key (\(pk\)) and (\(R,s\)) is then used to check the signature. It is standardized [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. In this case, we will run three standard tests for private and public keys, and with given messages.
Testing Ed25519 using RFC 8032 Test Vectors |
Tests
The standard tests are [RFC 8032]:
-----TEST 1 ALGORITHM: Ed25519 SECRET KEY: 9d61b19deffd5a60ba844af492ec2cc4 4449c5697b326919703bac031cae7f60 PUBLIC KEY: d75a980182b10ab7d54bfed3c964073a 0ee172f3daa62325af021a68f707511a MESSAGE (length 0 bytes): SIGNATURE: e5564300c360ac729086e2cc806e828a 84877f1eb8e5d974d873e06522490155 5fb8821590a33bacc61e39701cf9b46b d25bf5f0595bbe24655141438e7a100b -----TEST 2 ALGORITHM: Ed25519 SECRET KEY: 4ccd089b28ff96da9db6c346ec114e0f 5b8a319f35aba624da8cf6ed4fb8a6fb PUBLIC KEY: 3d4017c3e843895a92b70aa74d1b7ebc 9c982ccf2ec4968cc0cd55f12af4660c MESSAGE (length 1 byte): 72 SIGNATURE: 92a009a9f0d4cab8720e820b5f642540 a2b27b5416503f8fb3762223ebdb69da 085ac1e43e15996e458f3613d0f11d8c 387b2eaeb4302aeeb00d291612bb0c00 -----TEST 3 ALGORITHM: Ed25519 SECRET KEY: c5aa8df43f9f837bedb7442f31dcb7b1 66d38535076f094b85ce3a2e0b4458f7 PUBLIC KEY: fc51cd8e6218a1a38da47ed00230f058 0816ed13ba3303ac5deb911548908025 MESSAGE (length 2 bytes): af82 SIGNATURE: 6291d657deec24024827e69c3abe01a3 0ce548a284743a445e3680d7db5ac3ac 18ff9b538d16f290ae67f760984dc659 4a7c15e9716ed28dc027beceea1ec40a
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 binascii import sys 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 ("\n=== Test 1 ===") sk=binascii.unhexlify("9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60") pk=binascii.unhexlify("d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a") m=b"" print (f"Private key: {binascii.hexlify(sk).decode()}\nPublic key: {binascii.hexlify(pk).decode()}") print(f"Message: {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) print ("\n=== Test 2 ===") sk=binascii.unhexlify("4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb") pk=binascii.unhexlify("3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c") m=b"\x72" print (f"Private key: {binascii.hexlify(sk).decode()}\nPublic key: {binascii.hexlify(pk).decode()}") print(f"Message: {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) print ("\n=== Test 3 ===") sk=binascii.unhexlify("c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7") pk=binascii.unhexlify("fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025") m=b"\xaf\x82" print (f"Private key: {binascii.hexlify(sk).decode()}\nPublic key: {binascii.hexlify(pk).decode()}") print(f"Message: {m}\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) print ("\n=== Test 4 (with message) ===") m=b"Hello" if (len(sys.argv)>1): m=str(sys.argv[1]).decode() print(f"Message: {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:
=== Test 1 === Private key: 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 Public key: d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a Message: Signature R: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e06522490155 s:5fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b Verified: True === Test 2 === Private key: 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb Public key: 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c Message: r Signature R: 92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da s:085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00 Verified: True === Test 3 === Private key: c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7 Public key: fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025 Message: b'\xaf\x82' Signature R: 6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac s:18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40a Verified: True === Test 4 (with message) === Message: Hello Signature R: 7ee8b167a2ce0efd93b992cb91586d2ac1768a34ff6314376b61a6128cda3db6 s:0982ffc227f331818a77ad9fa4980d355e29a7290c9ddf62afd5d51c58ceb604 Verified: True Verified: True