Ed, RIP

Ed, RIP

Harold Edwards [here] 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:

The basic form is y² = x² + ax +b, but we can also have a Montgomery curve which is y²=x³+ax²+x. 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 operations 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. A sample run 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:

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 have interested to learn more about elliptic curves, here’s NIST P256: