Barebones Curve 25519

Barebones Curve 25519

Beauty comes in many forms

Don’t you think there’s those wizards who perform black magic on the Intenret, and their secret magic is … elliptic curve cryptography (ECC). There’s Curve 25519, and NIST 512, with Montgomory this, and Weierstrass that, and base points, and private keys scalars and public key points. It’s a pace for wizards, but it’s not actually that difficult to understand. In this article, I outline a bit of code that takes Curve 25519 down to the bare metal, and expose its beauty.

The core of security on the Internet …

The core of the security on the Web comes down to … elliptic curve cryptography (ECC). 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. And so we turn to Curve 25519, and which is one of the best elliptic curves around. 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). 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 thus gave 128-bit security levels, and which is currently strong enough in most applications. The base point chosen is x=9, and which gives a point of:

P=( 9 , 14781619447589544791020593568409986887264606134616475288964881837755586237401 )

The point adding and scaling uses the method defined in RFC 7748 [here]:

And so I have implemented the basic methods for point adding and scaling here:

and the code is here:

If you are interested, here is how ECDH with Curve 25519 (named X25519) works:

Daniel J Bernstein

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.

Conclusions

ECC is such an interesting area. And, so, if Curve 25519 doesn’t bring you enough security, then try it’s big brother: X448. It has the Godilocks prime number: