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) |
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 B\)
and where \(B\) 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 B\)
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 B\)
\(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 B = rB + sk \cdot B \cdot (\textrm{HASH}(R \: || \: pk \: || \: m))= R+ pk \cdot S = v_2 \)
Overall, we just need point multiplication and point addition.
The following is an outline of the code:
from basic import (clamp,bytes_to_scalar, scalar_to_bytes,bytes_to_element, Base,B) import hashlib, binascii import os import sys def HashIt(m): return hashlib.sha512(m).digest() def publickey(sk): # turn first half of SHA512(seed) a = clamp(HashIt(sk)[:32]) A = Base.scalarmult(a) return A.to_bytes() def HashToInt(m): h = HashIt(m) return int(binascii.hexlify(h[::-1]), 16) def signature(m,sk,pk): h = HashIt(sk[:32]) a_bytes, inter = h[:32], h[32:] a = clamp(a_bytes) r = HashToInt(inter + m) R = Base.scalarmult(r) R_bytes = R.to_bytes() S = r + HashToInt(R_bytes + pk + m) * a return R_bytes , scalar_to_bytes(S) def verify(pk, sig, msg): R = bytes_to_element(sig[:32]) A = bytes_to_element(pk) S = bytes_to_scalar(sig[32:]) h = HashToInt(sig[:32] + pk + m) v1 = Base.scalarmult(S) v2 = R.add(A.scalarmult(h)) if (v1==v2): return (True) return False print (f"Base point: {B[0]},{B[1]}") sk=os.urandom(32) pk=publickey(sk) print (f"\nPrivate key: {binascii.hexlify(sk)}\nPublic key: {binascii.hexlify(pk)}") m="Hello" if (len(sys.argv)>1): m=str(sys.argv[1]) m=m.encode() print(f"\nMessage: {m.decode()}\n") R,s=signature(m,sk,pk) print (f"\nSignature\nR: {binascii.hexlify(R)}\ns:{binascii.hexlify(s)}") sig=R+s ver=verify(pk,sig,m) print ("\nVerified: ",ver)
A sample run is:
Base point: 15112221349535400772501151409588531511454012693041857206046113283949847762202,46316835694926478169428394003475163141307993866256225615783033603165251855960 Private key: 53b7ba00b4eb1b9ef4b160f80aeb75b300b709e15eb5aba5079e362a1a39e39e Public key: 7ec476332a76d264f6553a2881b04a3f8b685542b3bf2e25213856166dc70c1f Message: Hello Signature R: f46add9cfc1dce483548deeb3d533d0531dfcc17d292cfe2d90acd9380767e0b s: f557d36cb3484d0dd2fbaec886560cb2983225299e80929d442042be74a84305 Verified: True