Asymmetric Key sizes

[lists@notatla.demon.co.uk]

Denis.Russell@ncl.ac.uk:

> I didn't get a clear feeling for what the prudent target should be. Paul
> says (above) that 768-bit keys should be OK now against "reasonable"
> attack. Does this mean the worst realistic case that we can think of for
> the present, and into the "foreseeable" future - a few years? How much more
> prudent would 1024 bits be? What about putting things the other way round?
> What's the problem with everyone going for 2048 now and (presumably)
> putting things so far out of reach that attackers just give up?

See www.usenix.org/events/sec99 which I think is where I found
the following as part of a larger article "Factoring: Facts and Fables".

   To argue his point, Lenstra extrapolated current factoring
   capabilities. In 1994, a QS factored an RSA-129 modulus. This required
   5,000 MIPS years for stage 1 (sieving) and two days on a 16K MasPar
   for stage 2 (matrix). Then in 1996, an NFS factored a 130-digit number
   in less than 700 MIPS years for stage 1 (68 hours and 700MB). However,
   stage 2 required much more computation time, even on a Cray C-90.
   Extrapolating these figures, Lenstra believes factoring a 512-bit
   number with a QS would require 500,000 MIPS years for sieving and four
   days (and 1GB of space) on a Cray C-90 for the matrix. Substituting
   NFS, sieving would take 20,000 MIPS years, and matrix computations
   would take three months (and 4GB of space). Therefore, 512-bit moduli
   are not long enough for current technology. But factoring 1,024-bit
   moduli seems hopeless. Just to sieve, the QS would require 1015 MIPS
   years, and the NFS would take 1011 MIPS years. Lenstra concludes that
   512-bit QS factorization is feasible, 512-bit NFS factorization is
   hardly feasible, and 1,024-bit factorization is hopeless.

Which brings me to the following code announcements:
       pgp553i (Windoze 95/98/NT) is on my website and
       FBN_funcs.c should join it around midnight GMT.
/*
 *  Fixed Big Number library
 *    http://www.notatla.demon.co.uk/CRYPTO/FBN_funcs.c
 *
 *  This is integer arithmetic code for up to 1024 bits
 *  (with intermediate results up to 2048 bits).
 *  This is what I mean by 'Fixed Big Number' - not arbitrary sizes.
 *  It has been tested against 'bc' for some calculations of each
 *  type, but not right up to the size limits.   This code is simple
 *  and not especially fast.
 *
 *  FBN_powmod() is effectively RSA.  This code contains no
 *  primality testing which you would need to generate RSA keys.
 *
 *  Parts of this code are derived from the book "Applied Cryptography"
 *  2nd ed by Bruce Schneier.
 *
 *  Distribution and use is free; no GPL, Berkeley or other licences
 *  apply.   The RSA patent in the U.S is due to expire September 2000.
 *  More details at http://cwis.kub.nl/~frw/people/koops/lawsurvy.htm.
 *
 *  Enail any bug reports to me please.
 *       Antonomasia <ant@notatla.demon.co.uk>   13Feb1999
 */