What’s the “Ed” in Ed25519?

What’s the “Ed” in Ed25519?

Curve 25519 is one of the most trusted elliptic curve methods, and there’s a chance you are using it on a daily basis. With this, you may be connecting to a remote service and performing a key exchange using X25519. This is a key exchange method that uses Curve 25519. Basically, we have a Montgomery curve defined by:

And here is a plot:

The curve uses a base point (G) and which is at: (9,1478161944 … 7755586237401). For key exchange, Bob generates a value of b, and computes an elliptic curve point of b.G. Alice generates a and computes, a.G. They exchange these points, and then Bob multiples the a.G value by b to get a.b.G. Alice takes Bob’s public key point, and multiples by a to get a.b.G. They should then have the same shared point, and can derive the same encryption key.

Meet “Ed”

While X25519 implements key exchange, we can also use Curve 25519 for digital signatures: Ed25519. The “Ed” part is named the Edwards Twisted Curve — after Harold Edwards [here]. Unfortunately, he passed away on 10 November 2020 but left an amazing legacy in computer security. One of his classic papers led to the creation of the Edwards Curve:

In 2008, Dan Bernstein et all then named a new curve after him — the twisted Edwards curve [here]:

These are the curves used in Ed2215 and EdDSA. Overall, twisted Edwards curve takes the form of:

A plot of 10x²+y² = 1 + 6x²y² is [here]:

For Ed25519 — based on Curve 25519 — it has a finite field defined by a prime number of p=²²⁵⁵−19, a=-1, d=37095705934669439343138083508754565189542113879843219016388785533085940283555 and the base point is at x=5866666666666666666666666666666666666666666666666666666666666666.

The simplest operation we have is to take a base point G on this curve, and then perform point addition. We always end up with another point on the curve. So 2G is equal to G+G and where we get a new point on the elliptic curve. For 3G we can have G+2G, and so on. We can also perform a scalar multiplication, such as taking a scalar of 3 and finding 3G. In the following code we have three scalar values of 1, 2 and 3, and then use point addition and scalar multiplication to find 2G and 3G, and where we should get the same values as G+G and G+2G, respectively:

  suite := suites.MustFind("Ed25519")	  
  one := suite.Scalar().SetInt64(1)
  two := suite.Scalar().SetInt64(2)
  three := suite.Scalar().SetInt64(3)  
  G:=suite.Point().Base()
 
  n := suite.Scalar().Pick(suite.RandomStream())   
  G_1 := suite.Point().Mul(one,G)  
  G_2 := suite.Point().Mul(two,G)  
  G_3 := suite.Point().Mul(three,G)
  G_T1 := suite.Point().Add(G_1,G_1)
  G_T2 := suite.Point().Add(G_1,G_2)

Note in Curve 25519, we typically only define the x co-ordinate, and not as an (x,y) point. This differs from secp256k1 (which is used with Bitcoin and Ethereum) as we store a public key point for the (x,y) coordinate (but can also compress it with the x value and where the y coordinate is odd or even). A sample run for the program shows that 2G is equal to G+G, and 3G is equal to G+2G:

Curve: Ed25519
Point G 5866666666666666666666666666666666666666666666666666666666666666
Point 1G 5866666666666666666666666666666666666666666666666666666666666666
Point 2G c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022
Point 3G d4b4f5784868c3020403246717ec169ff79e26608ea126a1ab69ee77d1b16712Point G+G c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022
Point G+2G d4b4f5784868c3020403246717ec169ff79e26608ea126a1ab69ee77d1b16712

An outline of the code is:

and here is an online demo that you can add your own scalar to:

https://asecuritysite.com/curve25519/ed

A sample run gives for a user-entered value of 4 is:

Curve: Ed25519
Point G 5866666666666666666666666666666666666666666666666666666666666666
Point 1G 5866666666666666666666666666666666666666666666666666666666666666
Point 2G c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022
Point 3G d4b4f5784868c3020403246717ec169ff79e26608ea126a1ab69ee77d1b16712Point G+G c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022
Point G+2G d4b4f5784868c3020403246717ec169ff79e26608ea126a1ab69ee77d1b16712Value 0400000000000000000000000000000000000000000000000000000000000000
Point vG 2f1132ca61ab38dff00f2fea3228f24c6c71d58085b80e47e19515cb27e8d047Random scale (n) 0f9279f7e3a40aaf06d175bb427567b3caca63b69989555762fd015fc047a402
Point nG 838e88d473fe7b2d0685021454c20275c428db93cc0c150ca192e0f4b86b572d

Conclusions

Beauty exists in many forms, and for cybersecurity, elliptic curves are the nearest thing to providing beauty. We all build on the shoulders of against, and Ed has certainly left a great legacy.

If you are interested in learning more about Curve 25519, try here:

https://asecuritysite.com/curve25519/ed