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

[ianG]

On 3/09/13 18:13 PM, Phillip Hallam-Baker wrote:


The real issue is that the P-521 curve has IP against it, so if you
want to use freely usable curves, you're stuck with P-256 and P-384
until some more patents expire. That's more of it than 192 bit
security. We can hold our noses and use P-384 and AES-256 for a while.

 Jon


What is the state of prior art for the P-384? When was it first published?

Given that RIM is trying to sell itself right now and the patents are
the only asset worth having, I don't have good feelings on this. Well
apart from the business opportunities for expert witnesses specializing
in crypto.

The problem is that to make the market move we need everyone to decide
to go in the same direction. So even though my employer can afford a
license, there is no commercial value to that license unless everyone
else has access.


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?




Due to submarine patent potential, even that is not necessarily enough
but it would be a start.




iang


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

Re: [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. 


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