NSA and ECC parameters

[Bill Stewart]

Sorry if this discussion
At 08:50 AM 10/27/2003 -0800, Major Variola (ret) wrote:
>At 10:01 PM 10/26/03 -0600, J.A. Terranson wrote:
> >On Sun, 26 Oct 2003, Eugen Leitl wrote:
> >>    In the case of the NSA deal, the agency
> >>    wanted to use a 512-bit key for the ECC system. This is the
> >>    equivalent of an RSA key of 15,360 bits."
> >Am I the only one here who finds this "requirement" excessive?  My god: are
> >we looking to keep these secrets for 50 years, or 50000 (or more) years?
>..
>The NSA might be hedging against future algorithmic improvements.
>If tomorrow you could factor numbers (or the ECC equivalent)
>with twice the number of bits, will your spies die?
>Cf. East German Stasi files, and some south-american files being cracked.

"Excessive" implies a cost-benefit analysis -
does anybody know how slow 512-bit ECC calculations are in practice?
If they're similar in speed to 512-bit RSA, it's usually fine;
if they're similar in speed to 15360-bit RSA, that's maybe a bit slow,
but if encryption and decryption are only a bit slower than 2048-bit RSA,
it doesn't usually matter if key generation is slower.

Also, while there are _lots_ of applications where short keys rock,
like James Donald's Crypto Kong signature lines, or dumb smartcards,
512-bit isn't too bad, and there are applications where it's usable
and 4096-bit RSA keys take up too much space (e.g. including any
signed data in a 576-byte TCP/IP packet.)

But more importantly, the algorithms are only starting to be explored.
We've got a few hundred years of understanding about primes and factoring,
and even then the applications of computer technology to factoring
have gotten a big Moore's Law hit since R,S,A,D,H, PRZ, and the Cypherpunks
started messing with them; 384-bit RSA keys have gone the way of Bass-O-Matic.
ECC is a much newer set of theory, especially for the kinds of attacks
cryptographers care about, and it's exposed to risks from
algorithm theory and number-crunching practice.