The Confusing Thing About X25519 and Ed25519

Head spinning time. With Curve 25519, we can have Ed25519 and X25519, and whereEd25519 is used for digital signatures (and a replacement for RSA and ECDSA), and X25519 is used for key exchange (and a replacement for ECDH). Both use Curve 25519 as their base. But, one uses Curve 25519 and which is a Montgomery Curve (X25519), and the other uses a twisted Edwards Curve (Ed25519).

And so, Ed25519 uses the twisted Edwards curve used by Ed25519 and the Montgomery curve is used by X25519, but where you can convert between the two. We normally defines points on an Edwards curve as (x, y), and (u, v)for a Montgomery curve. The specification of the conversion from Edwareds to Mongomery (and vice-versa) is defined in RFC 7748 as:

(u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
(x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))

An X25519 public is actually u co-ordinate on Curve 25519 (Montgomery curve), and where we multiply a base point by our private key (and which is a random scalar value): Pub=priv.G. With an Ed25519 public key we have a compressed version of an (x,y) point on the Edwards curve, and where we hash a secret value to create the private key.

When the same secret scalar value is used, we can easily convert between Ed25519 and X25519, but where we have two values for Ed25519 (x,y), and only one value for X25519 (u). Overall, we only need the u value in X25519 for a Diffie-Hellman key exchange operation. For every u coordinate value, there will be two points on the Montgomery, and there will be two y co-ordinates for the Edwards curve. A compressed point has a sign bit for the x-co-ordinate.

In the following code, we convert between the two forms [here]:

package main

import (
 "fmt"

 "crypto/ed25519"

 "encoding/base64"

 "filippo.io/edwards25519"
)

func main() {

 public, private, _ := ed25519.GenerateKey(nil)

 p, _ := new(edwards25519.Point).SetBytes(public)

 fmt.Printf("== Private key ==\n")

 fmt.Printf("Private key=%s\n", base64.StdEncoding.EncodeToString(private))
 fmt.Printf("Private key=%x\n", private)

 fmt.Printf("\n== Public key ==\n")

 fmt.Printf("Public key=%s\n", base64.StdEncoding.EncodeToString(public))
 fmt.Printf("Private key=%x\n", public)

 fmt.Printf("\n== Edwards Point ==\n")

 fmt.Printf("Edwards point =%x\n", p.Bytes())
 fmt.Printf("Montgomery point =%x\n", p.BytesMontgomery())

}

and a sample run is [here]:

== Private key ==
Private key=mEZWiZ7FrnVJ+lzhG0IGfmyVKIPcaXPnVr+Fd3iKPctI2Rx0uIjC2LW9+v3FtKz25rA9IsC3qTzONwjHHca03g==
Private key=984656899ec5ae7549fa5ce11b42067e6c952883dc6973e756bf8577788a3dcb48d91c74b888c2d8b5bdfafdc5b4acf6e6b03d22c0b7a93cce3708c71dc6b4de

== Public key ==
Public key=SNkcdLiIwti1vfr9xbSs9uawPSLAt6k8zjcIxx3GtN4=
Private key=48d91c74b888c2d8b5bdfafdc5b4acf6e6b03d22c0b7a93cce3708c71dc6b4de

== Edwards Point ==
Edwards (Ed25519) point =48d91c74b888c2d8b5bdfafdc5b4acf6e6b03d22c0b7a93cce3708c71dc6b4de
Montgomery (Curve 25519) point =a9216e9b2f635846f25aaec69f1dfd5c1fd7314204ae26f11242b922a846e546

Curve 25519 and Ed25519

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

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