From: ahaley@eoe.co.uk (Andrew Haley)
Newsgroups: sci.crypt,alt.security,alt.security.pgp
Subject: Re: pgp2.0 - what is an appropriate key length?
Date: 28 Sep 92 08:59:58 GMT
Organization: EO Europe Limited, Cambridge, UK
X-Newsreader: TIN [version 1.1 PL6]

Rob Stampfli (res@colnet.cmhnet.org) wrote:
: To date, I have seen 8 public keys cross my path, and 7 of those have
: been derived using a 1024 bit modulus.  (At least I think pgp reports the
: modulus length, and not the individual prime's lengths.)  I, too, have
: chosen to use a 1024 bit key, although the pgp and RSA documents state
: that keys in the 500-600 bit range provide adequate security for the
: individual.  (The RSA doc reserves 1000+ bits for special purpose keys,
: such as those belonging to a trusted authenicator.)  Unfortunately,
: decrypting a 1024 bit key often takes my poor overworked Unix-PC 5 minutes,
: so using the shorter key would be a big win.  (512 bytes implies 1/8 the
: decrypt time, right?)
: 
: Could someone who is knowledgeable about the current state of the art
: with respect to factoring the product of two primes please comment on
: what is an adequate length?  I believe a 512 bit modulus implies the
: primes would each be in the ballpark of 77 decimal digits, which I
: believe is a difficult, but not impossible factoring problem today.
: I'll admit, I'm not well versed in this area, so I am looking for
: someone to educate me.
: -- 
: Rob Stampfli  rob@colnet.cmhnet.org      The neat thing about standards:
: 614-864-9377  HAM RADIO: kd8wk@n8jyv.oh  There are so many to choose from.


The best thing I can do is to mention two references (one of which
you've already seen, but it's worth quoting here):

1.  _Public-Key Cryptography, State of the Art and Future Directions_,
ed. by Beth, Frisch, and Simmons.  This is the report of a workshop
involving the world's leading experts in the field, and is the closest
you're going to get to an authoritative statement.  The report says:

"For the most applications a modulus size of 1024 bit for RSA should
achieve a sufficient level of security for 'tactical' secrets for the
next ten years.  This is for long term secrecy purposes, for short
term authenticity purposes 512 bit might suffice in this century.

"Please note: Although the participants of the workshop feel best
qualified in their respective areas, this statement (with respect to
long lasting security) should be taken with caution."

2.  RSA Data Security's FAQ:

"Rivest estimates that a 512-bit modulus, currently the most common
modulus length, can be factored with an $8.2 million effort today,
less in the future.  Those with extremely valuable data (or large
potential damage from digital forgery) should use a modulus of, say
700 or 800 bits in length.  A certifying authority should use a modulus
of 1000 bits or more, because the validity of many other key pairs
depends on the security of one central key."


Rivest's calculations (in July's CACM) are worth looking at.  From
what I can see, some of the calculations are dubious; the time taken
to perform modular arithmetic seems unrealistically low, so the $8.2
million figure should not be taken as exact.  I guess he's just erring
on the side of caution.

RSA Data Security recommend that a key be expired every two years.

If PGP users are acting as certifying authorities for each other, the
1024 bit modulus seems to be required.  A whole chain of fraudulent
keys could result from a single bad certificate.

On the other hand, AFAIK PGP only uses a 128 bit hash to protect its
key certificates, so an attack on the hash function would be easier
than attacking the modulus.  Am I wrong about PGP in this respect?
Does PGP use some extra method to protect its certificates?


Andrew.