Hacker News new | past | comments | ask | show | jobs | submit login

He did basically run the Manhattan Project for searching for ideal curves, brute forcing millions of them and testing their properties, out of which came Curve25519, which is pretty much the curve used by anyone who knows what they're doing.

https://en.wikipedia.org/wiki/Curve25519

I saw him give a really awesome talk about the process of finding Curve25519 around the time he published it, and I think the story is a lot more interesting than people realize.




I would not call it the "Manhatten Project" for elliptic curves. Sure, he found a curve that, when used with Diffie Hellman, allows us to treat any 32-byte string as a public key, but note that I said only Diffie Hellman. Edwards25519 does not have this property unless you map from Curve25519 keys. In addition, you can't clamp and preserve the group structure, and you also can't assume said decoding lands in the desired prime order subgroup, because it doesn't.

Curve25519's group of points over the whole curve is not of prime order. By Lagrange, the subgroups are the prime factorization of the group order. Luckily we do have a large prime order subgroup, but we also have a subgroup of order 8 and consequently of order 4 and 2 also. If you by chance decode a point into one of these groups, scalar multiplication has a high chance of hitting the identity point. In Diffie Hellman, this isn't a problem: we call it "non contributory behaviour".

If however you care about each party making a contribution and group properties, you end up having to check group membership anyway. Not having to do that is one of the main selling points of Curve25519.

Looking through the SafeCurves criteria, there are now complete addition law for prime-order weierstrass curves, negating another safecurves benefit. Since the NIST curves form a prime order group, they don't have the same subgroup problem (all Montgomery curves, by contrast, have a subgroup of order at least 4).

We owe the "fix" to this to Mike Hamburg, effectively, who came up with a mapping to and from a Jacobi Quartic form that allows you to encode and decode directly into the prime order subgroup. This is Decaf, one of the contributions of his Ed448-Goldilocks paper, and was applied to Curve25519 under the name Ristretto.

We can go further if you like. There's extensive literature on appropriate choices of pairing friendly curves, and I'm not aware of any DJB contributions here. There are also faster curves at the 128-bit security level for Diffie Hellman, i.e. FourQ, which uses the GLV decomposition and Q-curves. ---

While DJB has made some very notable contributions and helped push the state of the art along, he's not the only contributor to the field by a very long way. At the very least, we should also mention Peter Montgomery and Harold Edwards, but these are by no means the only names.


A great comment from someone very knowledgeable in the field.


Which talk is that? This one seems interesting but it only has slides and (bad) audio https://cr.yp.to/talks.html#2016.03.09




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: