[Cryptography] Popular curves (was: NSA and cryptanalysis)
Jose Luis Gomez Pardo
gomez.pardo at usc.es
Wed Sep 4 12:35:52 EDT 2013
At 08:20 04/09/2013, ianG wrote:
>On 3/09/13 18:13 PM, Phillip Hallam-Baker wrote:
>....
>>Do we have an ECC curve that is (1) secure and (2) has a written
>>description prior to 1 Sept 1993?
>
>
>(Not answering your direct question.) Personally, I was happy to
>plan on using DJB's Curve25519. He's done the research and says it
>is good. Comments?
>
>iang
Curve25519 was designed for elliptic Diffie-Hellman taking care of
both security and efficiency aspects and seems very strong in both of
them. Some comments on its usage for other purposes can be found in
http://stackoverflow.com/questions/2515948/use-of-curve25519
This curve was originally written for x86 32-bit platforms and a
64-bit implementation can be found in the following links:
https://code.google.com/p/curve25519-donna/
https://github.com/agl/curve25519-donna
In addition to this curve and to the NIST curves, another source for
elliptic curves that can be (according to the developers) freely used is:
http://certivox.org/display/EXT/CertiVox+Standard+Curves
where cuves over 384 and 512-bit prime fields can be found which are
likely secure. Of course, in all these cases you have to trust the
curve developers somewhat although you can also check these curves
for possible vulnerabilities.
Alternatively, one can build one's own curve and for this one
needs to have access to an implementation of the SEA point counting
algorithm. A little while ago I was writing a cryptography book that
uses Maple to implement both cryptographic schemes and cryptanalytic
algorithms and, for a while, I contemplated the idea of programming
SEA in Maple. However, I soon discarded it because there are already
some freely available excelent implementations in compiled languages
and my Maple implementation would necessarily be much slower. Thus,
for some computations in the examples in my book I ended using
MIRACL, a C/C++ library with excellent support for ECC which was
recently adquired by CertiVox and can be found in the following links:
http://www.certivox.com/miracl/
https://github.com/CertiVox/MIRACL
Using the SEA algorithm one can readily find elliptic curves of prime
order (or with a very small cofactor) which, additionally, can
be tested to ensure that they satisfy some important conditions such
as not having small embedding degree (to prevent the MOV reduction
attack) or not having trace one (anomalous curves) which makes them
also vulnerable. Of course, if the curves are (pseudo)randomly
generated, it is very unlikely that they suffer from these
vulnerabilities. Methods for verifiably random generation of such
curves can be found in:
http://www.secg.org/download/aid-780/sec1-v2.pdf
and some recommended elliptic curves generated using these methods
(including curves over 384-bit and 521-bit prime fields) are available from:
http://www.secg.org/download/aid-784/sec2-v2.pdf
Of course, I don't know whether these curves are completely free from
IP concerns but, according to the sources where these curves are
published, this seems to be the case (I am far from expert in the IP
subject but, as a mathematician, the idea of someone "owning" an
elliptic curve in some sense, seems to me very strange).
Jose Luis.
More information about the cryptography
mailing list