Discussion:
Curve25519 and magic numbers
Ron Garret
2016-04-01 19:37:18 UTC
One of the motivations for using curve25519 is supposedly its transparency in terms of not having any weird parameters of unknown provenance that could conceal weaknesses. But there is one weird number in the curve25519 spec, the coefficient of x^2, which is 486662. That number seems to have been pulled out of a hat. The only condition on it is that A^2-4 is not a square in 2^255-19. But 486662 is far from the smallest number that meets that conditions. That would be (AFAICT) 5. So why 486662?

rg
Thomas Ptacek
2016-04-01 19:40:02 UTC
https://www.ietf.org/mail-archive/web/cfrg/current/msg05619.html

--Â
Thomas Ptacek
312-231-7805

On April 1, 2016 at 12:37:30 PM, Ron Garret (***@flownet.com) wrote:

One of the motivations for using curve25519 is supposedly its transparency in terms of not having any weird parameters of unknown provenance that could conceal weaknesses. But there is one weird number in the curve25519 spec, the coefficient of x^2, which is 486662. That number seems to have been pulled out of a hat. The only condition on it is that A^2-4 is not a square in 2^255-19. But 486662 is far from the smallest number that meets that conditions. That would be (AFAICT) 5. So why 486662?

rg

_______________________________________________
Curves mailing list
***@moderncrypto.org
https://moderncrypto.org/mailman/listinfo/curves
Tanja Lange
2016-04-01 19:41:58 UTC
Dear Ron,
Post by Ron Garret
One of the motivations for using curve25519 is supposedly its transparency in terms of not having any weird parameters of unknown provenance that could conceal weaknesses. But there is one weird number in the curve25519 spec, the coefficient of x^2, which is 486662. That number seems to have been pulled out of a hat. The only condition on it is that A^2-4 is not a square in 2^255-19. But 486662 is far from the smallest number that meets that conditions. That would be (AFAICT) 5. So why 486662?
You also need tht the curve is cryptographically secure.

http://safecurves.cr.yp.to/rigid.html

All the best
Tanja
Ron Garret
2016-04-01 21:24:32 UTC
Thanks!

I also realized after chasing down those leads that this question is answered in the curve25519 paper itself, but it’s at the very end so I missed it. Sorry about that.

As long as I’m asking stupid questions, is there a good ECC primer out there somewhere? The materials available on the web seem to leave out an awful lot of background. What are the relationships between Weirstrass, Edwards and Montgomery curves? Are those the only kinds of elliptic curves, or are there others? If there are others, why focus on those three? What is so special about 4a^3+27b^2? What’s a twist and why does it matter? Why are Montgomery curves good for DH while Edwards curves are good for DSA? Why not use one curve form for both? How do you determine the order of a curve group?

Feel free to treat those as rhetorical questions. I mention them only to illustrate the kinds of information I’m looking for and having a hard time finding.

Thanks,
rg
Post by Tanja Lange
Dear Ron,
Post by Ron Garret
One of the motivations for using curve25519 is supposedly its transparency in terms of not having any weird parameters of unknown provenance that could conceal weaknesses. But there is one weird number in the curve25519 spec, the coefficient of x^2, which is 486662. That number seems to have been pulled out of a hat. The only condition on it is that A^2-4 is not a square in 2^255-19. But 486662 is far from the smallest number that meets that conditions. That would be (AFAICT) 5. So why 486662?
You also need tht the curve is cryptographically secure.
http://safecurves.cr.yp.to/rigid.html
All the best
Tanja
lvh
2016-04-01 21:38:39 UTC
As long as Im asking stupid questions, is there a good ECC primer out there somewhere?
If youre not afraid of a strict mathematical approach, the Handbook of Elliptic and Hyperelliptic Cryptography (co-authored by Tanja) is a fantastic (albeit voluminous) read.

lvh

D. J. Bernstein
2016-04-01 19:43:12 UTC