From: Bill Stewart <bill.stewart@pobox.com>
Date: Tue, 10 Feb 1998 08:49:07 +0800
To: Ken Williams <ATU5713@compuserve.com>
Subject: Re: What's the latest in factoring?
In-Reply-To: <199802072222_MC2-3262-79F5@compuserve.com>
Message-ID: <3.0.5.32.19980209134003.0088b660@popd.ix.netcom.com>
MIME-Version: 1.0
Content-Type: text/plain



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