[Cryptography] RSA equivalent key length/strength

Kristian Gjøsteen kristian.gjosteen at math.ntnu.no
Wed Oct 2 12:18:31 EDT 2013


2. okt. 2013 kl. 16:59 skrev John Kelsey <crypto.jmk at gmail.com>:

> On Oct 2, 2013, at 9:54 AM, Paul Crowley <paul at ciphergoth.org> wrote:
> 
>> On 30 September 2013 23:35, John Kelsey <crypto.jmk at gmail.com> wrote:
>> If there is a weak curve class of greater than about 2^{80} that NSA knew about 15 years ago and were sure nobody were ever going to find that weak curve class and exploit it to break classified communications protected by it, then they could have generated 2^{80} or so seeds to hit that weak curve class.
>> 
>> If the NSA's attack involves generating some sort of collision between a curve and something else over a 160-bit space, they wouldn't have to be worried that someone else would find and attack that "weak curve class" with less than 2^160 work.
> 
> I don't know enough about elliptic curves to have an intelligent opinion on whether this is possible.  Has anyone worked out a way to do this?  

Edlyn Teske [1] describes a way in which you select one curve and then find a second curve together with an isogeny (essentially a group homomorphism) to the first curve. The first curve is susceptible to Weil descent attacks, making it feasible to compute d.log.s on the curve. The other curve is not susceptible to Weil descent attacks.

You publish the latter curve, and keep the first curve and a description of the isogeny suitable for computation to yourself. When you want to compute a d.log. on the public curve, you use the isogeny to move it to your secret curve and then use Weil descent to find the d.log.

I suppose you could generate lots of such pairs of curves, and at the same time generate lots of curves from seeds. After a large number of generations, you find a collision. You now have your trapdoor curve. However, the amount of work should be about the square root of the field size.

Do we have something here?

(a) Weil descent (mostly) works over curves over composite-degree extension fields.

(b) Cryptographers worried about curves over (composite-degree) extension fields long before Weil descent attacks were discovered. (Some people like them because they speed things up slightly.)

(c) NIST's extension fields all have prime degree, which isn't optimal for Weil descent.

(d) NIST's fields are all too big, if we assume that NSA couldn't do 2^112 computations in 1999.

(e) This doesn't work for prime fields.

It seems that if there is a trapdoor built into NIST's (extension field) curves, NSA in 1999 was way ahead of where the open community is today in theory, and had computing power that we generally don't think they have today.

We have evidence of NSA doing bad things. This seems unlikely to be it.

[1] Edlyn Teske: An Elliptic Curve Trapdoor System. J. Cryptology 19(1): 115-133 (2006)

-- 
Kristian Gjøsteen





More information about the cryptography mailing list