[Cryptography] Popular curves (was: NSA and cryptanalysis)

[Jose Luis Gomez Pardo]

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.