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. A vulnerability in Ed25519 using Python is [Here].
Ed25519 in Python |
Theory
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 \pmod q\) the signature checks. This is because:
\( \begin{align} v_1&=s.G\\ &= (r + (\textrm{HASH}(R \: || \: pk \: || \: m)) \cdot sk) \cdot G \\ &= rG + sk \cdot G \cdot (\textrm{HASH}(R \: || \: pk \: || \: m)) \\ &= R+ pk \cdot S \\ &= v_2 \end{align} \)
The following is an outline of the code:
# Based on code at https://github.com/warner/python-pure25519/blob/master/pure25519/eddsa.py from pure25519.basic import (bytes_to_clamped_scalar, bytes_to_scalar, scalar_to_bytes, bytes_to_element, Base) import hashlib, binascii import os,sys def H(m): return hashlib.sha512(m).digest() def publickey(seed): # turn first half of SHA512(seed) into scalar, then into point assert len(seed) == 32 a = bytes_to_clamped_scalar(H(seed)[:32]) A = Base.scalarmult(a) return A.to_bytes() def Hint(m): h = H(m) return int(binascii.hexlify(h[::-1]), 16) def signature(m,sk,pk): assert len(sk) == 32 # seed assert len(pk) == 32 h = H(sk[:32]) a_bytes, inter = h[:32], h[32:] a = bytes_to_clamped_scalar(a_bytes) r = Hint(inter + m) R = Base.scalarmult(r) R_bytes = R.to_bytes() S = r + Hint(R_bytes + pk + m) * a return R_bytes + scalar_to_bytes(S) def checkvalid(s, m, pk): if len(s) != 64: raise Exception("signature length is wrong") if len(pk) != 32: raise Exception("public-key length is wrong") R = bytes_to_element(s[:32]) A = bytes_to_element(pk) S = bytes_to_scalar(s[32:]) h = Hint(s[:32] + pk + m) v1 = Base.scalarmult(S) v2 = R.add(A.scalarmult(h)) return v1==v2 def create_signing_key(): seed = os.urandom(32) return seed def create_verifying_key(signing_key): return publickey(signing_key) def sign(skbytes, msg): """Return just the signature, given the message and just the secret key.""" if len(skbytes) != 32: raise ValueError("Bad signing key length %d" % len(skbytes)) vkbytes = create_verifying_key(skbytes) sig = signature(msg, skbytes, vkbytes) return sig def verify(vkbytes, sig, msg): if len(vkbytes) != 32: raise ValueError("Bad verifying key length %d" % len(vkbytes)) if len(sig) != 64: raise ValueError("Bad signature length %d" % len(sig)) rc = checkvalid(sig, msg, vkbytes) if not rc: raise ValueError("rc != 0", rc) return True msg="Hello" if (len(sys.argv)>1): msg=str(sys.argv[1]) m = msg.encode() print("Message:",msg) sk1 = create_signing_key() vk1 = create_verifying_key(sk1) sk2 = create_signing_key() vk2 = create_verifying_key(sk2) print("Secret key 1: ",sk1.hex()) print("Verifing key 1: ",vk1.hex()) print("Secret key 2: ",sk2.hex()) print("Verifing key 2: ",vk2.hex()) sig1 = signature(m,sk1,vk1) sig2 = signature(m,sk1,vk2) print("Signature 1 (sk1, pk1): ",sig1.hex()) R1=sig1.hex()[:len(sig1.hex())//2] S1=sig1.hex()[len(sig1.hex())//2:] R2=sig2.hex()[:len(sig2.hex())//2] S2=sig2.hex()[len(sig2.hex())//2:] print("Now we will sign the message with sk1 and use pk1 to give Sig1") print("And sign the message with sk1 and use pk2 to give Sig2") print("\nR1=", R1) print("S1= ",S1) print("R2=", R2) print("S2= ",S2) rtn1=verify(vk1,sig1,m) if (rtn1==True): print("Signature Success") if (R1==R2): print("R1 is equal to R2!")
A sample run is:
Message: Hello Secret key: f85d5062036a7b7cfe4627e6978ab95ca2e2878f1c319a653a69439009b9ce53 Verifing key: be3c90fdf892123a53ebd29b96e09d3d30cf3f450e54619ae35e75c1d7d49729 Signature: 4c0d15b5f54e3e80e4bdba1386bfc30a3e648e3c6f286c565b5927e71fc0c3609d3d093d6c7fe683aa5b15c8eb63dcd47bca89ab62058fd72c0d68999013d600 R= 4c0d15b5f54e3e80e4bdba1386bfc30a3e648e3c6f286c565b5927e71fc0c360 S= 9d3d093d6c7fe683aa5b15c8eb63dcd47bca89ab62058fd72c0d68999013d600 Signature Success