What’s The Base Point for Ed25519?

What’s The Base Point for Ed25519?

Much of the foundation of your online security comes down to a basic thing: elliptic curves. It is these magical little curves that allow your browser and the server to talk openly and then agree on an encryption key. This key then stops people spying on you, and makes sure that no one hi-jacks your connection. to me, they are beautiful.

With the ECDH (Elliptic Curve Diffie Hellman) handshake method, we have an almost perfect way to generate a shared key between Bob and Alice, without Eve ever finding it out. So what curve can we use? Well, Curve 25519, is one of the best elliptic curves around (and free from backdoors, he hope). It uses the Montgomery curve form of:

And where we take a base point (G), and then create a private key (n), and then determine our public key (nG). With this, nG is the point G added n times (G+G+…G). Overall, Curve 25519 was created by Daniel J Bernstein, and who has contributed so much to cybersecurity. The form he chose was:

and where p=2²⁵⁵-19. It gives 128-bit security levels, and which is currently strong enough in most applications.

Finding the base point (G)

The way elliptic curve cryptography works is that we take a private key value (n), and then compute a public key point (nG), and where G is the base point on the curve. If n is large enough and random, it will be almost impossible to determine the private key (n) from the public key (nG).

For Ed25519, let’s determine the base point of the curve from [here]:

import nacl.bindings as b
import binascii
import sys

p = 2**255 - 19

def inv(x):
    return pow(x, p-2, p)

d = -121665 * inv(121666)
I = pow(2,(p-1)//4,p)

def findx(y):
    xx = (y*y-1) * inv(d*y*y+1)
    x = pow(xx,(p+3)//8,p)
    if (x*x - xx) % p != 0: x = (x*I) % p
    if x % 2 != 0: x = p-x
    return x

def convert_to_little_int(val):
  little_hex = bytearray.fromhex(val)
  little_hex.reverse()
  little = ''.join(format(x, '02x') for x in little_hex)
  return little

i=1

n = binascii.a2b_hex("0100000000000000000000000000000000000000000000000000000000000000")

if (len(sys.argv)>1):
  i=int(sys.argv[1])

n= i.to_bytes(32, 'little')

x= b.crypto_scalarmult_ed25519_base_noclamp(n)

print ("Base point, X value: ",binascii.b2a_hex(x))

print (f"\nn={i} [{binascii.b2a_hex(n).decode()}]")
point= b.crypto_scalarmult_ed25519_base_noclamp(n)

point_hex= binascii.b2a_hex(x).decode()

point_int = int(convert_to_little_int(point_hex),16)

print (f"{i}G, Point (y): {point_hex} ({point_int})")

print ()
print (f"x point: {findx(point_int)}")
print (f"y point: {point_int}")

With this we compute just the y-axis point (as we can then compute the x-axis point, if required). A sample run is [here]:

y co-ordinate value:  b'5866666666666666666666666666666666666666666666666666666666666666'

n=1 [0100000000000000000000000000000000000000000000000000000000000000]

1G -> Point (y): 5866666666666666666666666666666666666666666666666666666666666666 (46316835694926478169428394003475163141307993866256225615783033603165251855960)

x point: 15112221349535400772501151409588531511454012693041857206046113283949847762202
y point: 46316835694926478169428394003475163141307993866256225615783033603165251855960

and for 2.G [here]:

y co-ordinate value:  b'c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022'

n=2 [0200000000000000000000000000000000000000000000000000000000000000]

2G -> Point (y): c9a3f86aae465f0e56513864510f3997561fa2c9e85ea21dc2292309f3cd6022 (15549675580280190176352668710449542251549572066445060580507079593062643049417)

x point: 24727413235106541002554574571675588834622768167397638456726423682521233608206
y point: 15549675580280190176352668710449542251549572066445060580507079593062643049417

Along with key exchange, elliptic curve methods are used to create digital signatures, such as with ECDSA and EdDSA (and which uses the Ed25519 curve). So next time someone talks about trust with cryptocurrency, think about the magic of elliptic curves in securing the transaction. One day the rest of the work will catch up with cryptocurrencies and blockchains, and we will live in a more secure and trusted digital world.

Conclusions

To me, elliptic curves are beautiful. But there’s a threat to them coming along … and that threat is quantum computers. These sneaky devices know the secret of finding the private key within elliptic curves. And so, something even more mathematically beautiful is coming along … lattice crypto.

Postscript

Daniel J Bernstein (djb) was born in 1971. He is a USA/German citizen and a Personal Professor at Eindhoven University of Technology and a Research Professor at the University of Illinois at Chicago.

At the tender age of 24 — in 1995 — he, along with the Electronic Frontier Foundation — brought a case against the US Government related to the protection of free speech (Bernstein v. United States: here). It resulted in a ruling that software should be included in the First Amendment. A core contribution is that it has reduced government regulations around cryptography. It was a sign of the greatness that was to come from the amazing mind of Daniel. His viewpoint on reducing the strength of cryptography at the time defined:

“There are, fortunately, not many terrorists in the world. But there are many criminals exploiting Internet vulnerabilities for economic gain. They infiltrate computers and steal whatever secrets they can find, from individual credit-card numbers to corporate business plans. There are also quite a few vandals causing trouble just for fun.”

Since then few others have done so much for the cause of privacy, including creating the Sala20 [link] stream cipher in 2005, and then with ChaCha20 [link] and Poly1305 in 2008. Many connections in TLS now use ChaCha20, rather than AES, as it is faster — over three times after than AES — and has a lower computing requirement. His love of using dance names also comes to the fore with Rumba [here].

It is not just in symmetric key encryption that he has contributed to, he has made significant contributions to public key encryption. In 2005, he defined the Curve 25519 elliptic curve, and which is now a fairly standard way of defining elliptic curves. For signatures, he then defined Ed25519, and the resultant version of a new EdDSA signature (and which is now included in OpenSSH). The Tor protocol, for example, uses Curve 25519 for its key exchange for each of the nodes involved in a secure route.