At 03:20 AM 2/9/98 -0500, Ken Williams wrote:

8192 bits is used now. you can generate 8192 bit keys with PGP 2.6.3ui (the unofficial international version). ... [note: you can of course generate MUCH larger keys, but i'm attempting to be practical for a change]

There are two countervailing arguments about very long keys; one is that if you understand cryptography well enough to evaluate the issue, you'll know you don't need to bother, but the other is that if you don't understand crypto very well, maybe you should be overly conservative. Remember that factoring difficulty is roughly exponential; adding logn bits about doubles the cracking workload (depending on which factoring method is being used). Factoring a 1024-bit number is _much_ harder than factoring a 512-bit number, and factoring a 2048-bit number is well into age-of-the-universe difficulty level. The practical level of factoring right now is about 512 bits, for either a distributed internet effort or an NSA internal one; in the unlikely event that Moore's law lets us double processing power 100 times in the next 150 years, that means a 1500-bit key could be crackable. So 2048 bits is certainly more than enough for _your_ lifetime. Increasing processing power 2**100 times is likely to be tough :-) After all, features in current microprocessors are on the order of 100 atoms wide. And by the time we've developed the level of nanotechnology needed to speed up processing that much, there'll be tiny audio bugs listening to you type your passphrase into your keyboard and reporting it back to the Central Intelligence Corporation, or picking up the electromagnetic fields from your direct neural interface, so the crypto strength won't matter much. But do you really _need_ to factor the prime number to crack PGP? No. Remember that PGP uses the RSA key to encrypt session keys for IDEA, or for signing MD5 hashes of documents, rather than using it directly. So you can decrypt the message by cracking IDEA, or forge a message by finding MD5 collisions. Cracking IDEA's 128-bit keys was estimated to be about as hard as factoring a 3100-bit number, though improvements to factoring technology may make a 4096-bit number as easy as IDEA. Also, PGP 2.x passphrases are encrypted with IDEA, so if they've got your secring.pgp and can crack 4096-bit keys, you're toast, even if your passphase isn't just your dog's name spelled backwards. Similarly, by the time processing power doubles 100 times making your 1500-bit key insecure, MD5 will be long toasted. Either way, there's no need to go beyond 4096-bit keys ever, with old-style PGP. Even if you're being overly conservative, that's more than enough. Newer versions of PGP dump RSA and IDEA for patent reasons, but they also offer alternatives to IDEA and MD5 which may be stronger. (SHA-1 is stronger than MD5, triple-DES requires immense amounts of storage to reduce it to a strength similar to IDEA, and just being extensible means you can replace algorithms that are obsolete.) The other side of practical is how much work it takes to use long keys, and how many people who want to talk to you use them. The answer to the latter is "Not many" for RSA keys over 2048. The former is about N**2 for decryption and N**3 for key generation, and about linear for encryption with short exponents, so it'll take you 64 times as long (once) to generate the key, and 16 times as long to decrypt or sign anything, compared to the far-more-than-strong-enough 2048-bit key, which is already 4 times as hard to use and 8 times as hard to generate as a 1024. It's not worth the bother, unless you know have a really, really special application that needs to remain secret until long after you've overthrown the government. On the other hand, at least the RSA patent will have expired by then :-) The Diffie-Hellman implementations in PGP 5.x will let you use key lengths up to 4096, but the speed behaviour is a bit different. In particular, key generation is much faster, so generating overkill-length keys isn't as boring. Thanks! Bill Bill Stewart, bill.stewart@pobox.com PGP Fingerprint D454 E202 CBC8 40BF 3C85 B884 0ABE 4639