[Mac_crypto] Re: # Elliptic Curve Point Counting, made easy

[R. A. Hettinga]

--- begin forwarded text


Status: RO
Delivered-To: fork@xent.com
To: fork@xent.com
Subject: Re: # Elliptic Curve Point Counting, made easy
From: harley@argote.ch (Robert Harley)
Sender: fork-admin@xent.com
Date: Tue, 20 Aug 2002 18:24:44 +0200 (CEST)

Gordon Mohr wrote:
>Does this mean that Eliptic Curve encryption is
>now easily breakable? Or faster than before with
>no loss in strength? Or stronger?
>
>Raw bits are OK, cooked bits are better.

Oh.  OK.

These results don't help break EC crypto at all.

With RSA, you pick a number with secret factors and to break the
cryptosystem, you can factor the number.  Due to fast sub-exponential
algorithms for factoring, the number had better be 1024 bits at the
very least (record = 524 bits).

With EC, you pick a curve and pick points on the curve with secret
discrete logarithm.  To break the cryptosystem you can compute a
discrete log but the best algorithms for random curves are exponential
(record = 109 bits, for a slightly special curve).

Up until now, people pick curves chosen from a small fixed set.  One
choice is a few curves with special properties that originally were
chosen to make point-counting easier, and can also speed up the crypto
operations, but in some cases they can also speed up attacks, not on
curves deployed at the moment but the danger exists.  The other
choice is to precompute a handful of random curves.  The NSA did this
a few years ago when it took hours on a fast machine and NIST
standardized those curves.

What changes is that it is now possible is to generate your own curves
on an ordinary PC.  This has been getting easier and easier, with
small curves taking seconds on a fast machine since a year or two.
Now even reasonably big curves take seconds on a typical PC.

This means that you don't have to rely on standard curves but can
distribute risk over many curves in case some get broken at some
stage.  In certain circumstances you can even keep the curve itself
secret so an attacker doesn't know which discrete log to try to
compute!  There isn't really a good analogy with RSA, but imagine
wanting to factor a number and you don't even know what it is...

So basically recent progress has made new things feasible and this
makes them even more so.  The underlying primitives for signing,
encoding and so on are not affected, but the security vibes get better.

R
http://xent.com/mailman/listinfo/fork

--- end forwarded text


-- 
-----------------
R. A. Hettinga <mailto: rah@ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'