2. okt. 2013 kl. 16:59 skrev John Kelsey <crypto....@gmail.com>:
> On Oct 2, 2013, at 9:54 AM, Paul Crowley <p...@ciphergoth.org> wrote:
>
>> On 30 September 2013 23:35, John Kelsey <crypto....@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
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
