So, What Is Ed25519, and What Does It Have To Do With Curve 25519?

So, What Is Ed25519, and What Does It Have To Do With Curve 25519?

Satoshi Nakamoto selected the secp256k1 elliptic curve for Bitcoin, and the rest has become history. It was soon adopted for Ethereum, and where Blockchain researchers will know the curve well. For key exchange, such as with ECDH, the most commonly used curve is secp256r1, and typically known with the NIST P256 standard. But, are they good curves?

Well, in 2005, Dan Bernstein defined Curve 25519 [1]:

It uses the Montogomery curve form of:

y²=x²+486662x²+x (mod p)

and where p is 2²⁵⁵-19, and has a base point at x=9.

So, what about the “Ed” part? This comes from the Edwards form of Curve 25519, and which significantly speeds up the curve for signatures [2]:

Daniel then saw the potential of his curve for the Edwards curve method, and produce the Ed25519 definition:

And, in 2017, Ed25519 (EdDSA) was formally born [4]:

The Edwards25519 curve is birationally equivalent to Curve25519. This allows the transformation of a point (u,v) on Curve25519 to a point (x,y) on the Edwards 25519 curve using:

The curve itself is in the form of:

ax²+y²≡1+dx²y² (mod p)

and where:

p=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed (2^255-19)
a=0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec
d=0x52036cee2b6ffe738cc740797779e89800700a4d4141d8ab75eb4dca135978a3

The base point is:

G	(0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A, 
0x6666666666666666666666666666666666666666666666666666666666666658)

and the order is:

n	0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed

Key generation for Ed25519

Initially, Alice generates a random 32-byte secret key (sk) and then creates a public key of:

pk=sk⋅G

and where G is the base point of the curve.

Signing (r,s)

Alice creates an SHA-512 hash of her private key:

h=HASH(sk)

She then creates r from the upper 32 bytes of hash and the message:

r=HASH(h[32:]||m))

And where “||” represents a concatenation of the byte array values. Next, she matches r onto the curve with:

R=r⋅G

Next Alice computes s with:

s=r+(HASH(R||pk||m))⋅sk

The signature is (R,s). The values of R and s are 32 bytes long, and thus the signature is 64 bytes long.

Signature verification

Bob creates S using R, pk and m:

S=HASH(R||pk||m)

And next creates two verification values:

v1=s⋅G

v2=R+pk⋅S

If v1==v2 (mod q) the signature checks. This is because:

v1=s.G=(r+(HASH(R||pk||m))⋅sk)⋅G=rG+sk⋅G⋅(HASH(R||pk||m))=R+pk⋅S=v2

Coding

The following is the code [here]:

from cryptography.hazmat.primitives import serialization as crypto_serialization
from cryptography.hazmat.primitives.asymmetric.ed25519 import Ed25519PrivateKey
from cryptography.hazmat.backends import default_backend as crypto_default_backend
import binascii
import sys
message="Hello"
if (len(sys.argv)>1):
 message=(sys.argv[1])

key=Ed25519PrivateKey.generate()

print("Method:\t\t\tEd25519")
print(f"Message:\t\t{message}")

try:
 private_key = key.private_bytes(crypto_serialization.Encoding.Raw,crypto_serialization.PrivateFormat.Raw,crypto_serialization.NoEncryption())

 print(f"\nPrivate key:\n{binascii.b2a_hex(private_key).decode()}")

 public_key = key.public_key().public_bytes(crypto_serialization.Encoding.Raw,crypto_serialization.PublicFormat.Raw)

 print(f"\nPublic key:\n{binascii.b2a_hex(public_key).decode()}")

 signature = key.sign(message.encode())
 sig_bytes=binascii.b2a_hex(signature).decode()

 print(f"\nSignature:\nr={sig_bytes[:64]}\ns={sig_bytes[64:]}")

 rtn=key.public_key().verify(signature, message.encode())

 if (rtn==None): print("Signature verified")
 else: print("Signature failed")
except Exception as e:
 print("Public key error: ",e)

The following is a sample run [here]:

Method:			Ed25519
Message:		My test data
Private key:
eea74edbc454d0cc38fe77ffa47f63b1a10677b4eedf1de413ebfca0cf0ea8f8
Public key:
3a08d965f92b8a9489e618002dd03921b1a1bb334920e287d04df41cfca8e987
Signature:
r=a1f80d89fcb9945bda82b88b4cd0cb676142e00e021f3c205b2e56851fd88e67
s=c8280baca8e7e8ac00122398f9c37ec60001c2861670f8fe05baa9f500f48308
Signature verified

Conclusions

Ed25519 has been so successful, and many developers now use it for authentication. AWS Transfer is used to create an SSH server, and now supports Ed25519:

And so, here is Ed25519 — the superfast signature method:

https://asecuritysite.com/hazmat/ed25519

References

[1] Bernstein, D. J. (2006). Curve25519: new Diffie-Hellman speed records. In Public Key Cryptography-PKC 2006: 9th International Conference on Theory and Practice in Public-Key Cryptography, New York, NY, USA, April 24–26, 2006. Proceedings 9 (pp. 207–228). Springer Berlin Heidelberg. https://core.ac.uk/download/pdf/191282977.pdf

[2] Edwards, H. (2007). A normal form for elliptic curves. Bulletin of the American mathematical society, 44(3), 393–422. https://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf

[3] Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B. Y. (2012). High-speed high-security signatures. Journal of cryptographic engineering, 2(2), 77–89. https://link.springer.com/content/pdf/10.1007/s13389-012-0027-1.pdf

[4] Josefsson, S., & Liusvaara, I. (2017). RFC 8032: Edwards-curve digital signature algorithm (EdDSA). https://www.rfc-editor.org/rfc/rfc8032