[147466] in cryptography@c2.net mail archive
Re: [Cryptography] RSA equivalent key length/strength
daemon@ATHENA.MIT.EDU (=?iso-8859-1?Q?Kristian_Gj=F8steen)
Wed Oct 2 12:30:03 2013
X-Original-To: cryptography@metzdowd.com
From: =?iso-8859-1?Q?Kristian_Gj=F8steen?= <kristian.gjosteen@math.ntnu.no>
In-Reply-To: <B7E96B27-22C5-41BF-A1B4-9CA62B39C951@gmail.com>
Date: Wed, 2 Oct 2013 18:18:31 +0200
To: John Kelsey <crypto.jmk@gmail.com>
Cc: cryptography <cryptography@metzdowd.com>,
Paul Crowley <paul@ciphergoth.org>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
2. okt. 2013 kl. 16:59 skrev John Kelsey <crypto.jmk@gmail.com>:
> On Oct 2, 2013, at 9:54 AM, Paul Crowley <paul@ciphergoth.org> wrote:
> =
>> On 30 September 2013 23:35, John Kelsey <crypto.jmk@gmail.com> wrote:
>> If there is a weak curve class of greater than about 2^{80} that NSA kne=
w 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 cur=
ve 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 wo=
rried 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 no=
t 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 secre=
t 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 generation=
s, you find a collision. You now have your trapdoor curve. However, the amo=
unt 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 f=
ields long before Weil descent attacks were discovered. (Some people like t=
hem 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) cu=
rves, NSA in 1999 was way ahead of where the open community is today in the=
ory, 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): 11=
5-133 (2006)
-- =
Kristian Gj=F8steen
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
