RFC 6637 and construct elliptic curves

A new request for comments is available for elliptic curve cryptography. With the number 6637 the past June 11th was announced as official. Very good news for the elliptic curves and its cryptographic implementations. 


From the first version of this standard when it was a candidate has passed a few months more than 4 years. Yes, more than 4 years to public discussion. Necessary for consensus in standard development, but much more necessary for cryptography.


The old project of the patch for GnuPG, who was already obsolete a long a go, have some relation with the final code in the GnuPG. I'm glad when I see it in the sources that I have contributed somehow.


But what about the supported curves? The mentioned standard restricts the use of only a very few of them. The supported curves are only 3, one per each supported size: from the fips 186-3 the p-256, p-384 and p-521 (the biggest 3 of the 5 in the Appendix D.1.2 "Curves over Prime Fields). They are known as the NIST curves and they are from the NSA suite b.


Yes, the standard doesn't close completely the use of other curves. There is a field in the structure of the key to specify the curve, but is not set directly the curve. What is place in the field is the curve OID. Even if the number of curves that can be listed using this Object Identifiers can be very big, it will never be as big as the existing and cryptographically valid elliptic curves. But there is hope in this issue, it wasn't like that the full time of this pre-standard process, there is a octet, the first one, who have a reserved value (0xFF) for future extensions.


Why can be so important to use as many curves as the users want? Easy, one of the biggest features in elliptic curves is the possibility to change the cyclic group where the discrete logarithm is protecting your secrets, without changing the size is because using a different curve with in the same base finite field the hardness of move an attack from the cyclic group in one curve to another cyclic group in another will be almost equivalent to start from scratch the attack over the new cyclic group on the new curve over the same finite field.


But, how can be a new curve generated? Recently in arxiv I've seen a article about this matter: "Method for constructing elliptic curves using complex multiplication and its optimizations" (July 30, 2012).


I've been working in isogenies using volcanoes and stars of them to speed up the initial way to construct a new curve (pointed in the abstract of the cited article):

1. 
2. , where and
3. If it doesn't satisfy the conditions restart from 1

But this article proposes the other way around, start finding an order that satisfy the conditions and then build a curve of this order. It's a promising idea to have a nice way to have as many curves as necessary. 


With the isogenies, I didn't found how to speed this up enough to have a new (cryptographically good) curve during the key generation (a reasonable time to not desperate the user). And even more, having the possibility to reset your key by change and old curve by a new one with out needing to create a new key, but assuring the security by a public and auditable procedure.

What is the utility of this feature of the cryptosystem reset? One that I can imagine, and can be compatible with the current standard is to have a corporative elliptic curve in the smart cards and periodically renew the curve. Knowing the path in the isogeny star, all the smart cards would be able to "migrate", but for a cryptoanalyser will be a very enormous hard work to "port" any running attack, even if the public keys are available in both curves, from the origin to the current if the path is still secret.

The most important thing in cryptology is the trust on mathematics. Giving the user 3 curves, that looks good, but only 3, is not enough. Like the S-boxes in DES, that wakes up susceptibilities, specially at the beginning, to know how they had been build (why those and not any other). Even more, giving a list of hundreds of thousands curves is neither enough because the problem is still the same.

The unique solution I see on that issue, is to give this public and auditable algorithm that allows the community to validate (or break) it that make the user confortable with the provided security.