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

[Eugen Leitl]

----- Forwarded message from Jose Luis Gomez Pardo <gomez.pardo@usc.es> -----

Date: Wed, 04 Sep 2013 18:35:52 +0200
From: Jose Luis Gomez Pardo <gomez.pardo@usc.es>
To: ianG <iang@iang.org>
Cc: Phillip Hallam-Baker <hallam@gmail.com>, cryptography@metzdowd.com
Subject: Re: [Cryptography] Popular curves (was: NSA and cryptanalysis)
X-Mailer: QUALCOMM Windows Eudora Version 7.1.0.9

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.

_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography

----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://ativel.com http://postbiota.org
AC894EC5: 38A5 5F46 A4FF 59B8 336B  47EE F46E 3489 AC89 4EC5