What's the latest in factoring?

-----BEGIN PGP SIGNED MESSAGE-----

Hi all,

First, I want to say that because I've heard that traffic on this list is
heavy, and I don't have time to file away 40 messages a day, you must
write to me personally in order for me to see the message.  My PGP key is
provided at the end of this message.

What is the latest factoring breakthrough (at least in the civilian
world?)  I had heard a while back that the most recent event was
accomplished by Samuel Wagstaff of Purdue University, whose team factored
(3^349-1)/2, which is a 167-digit number (about 552 bits).  Is there
anything more recent?  Also, whereas 1024 bits was the commonly accepted
threshhold for key lengths more than two years ago, what's the threshhold
now?  Because I have DOS (and like it) I use PGP 2.63ix, when should I
retire my 1024-bit key?  I don't expect anybody to answer that I should
do so immediately, but can someone give me an idea on what people are
doing in regard to key length?

Sincerely,

Alan Tu


-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv
Comment: Requires PGP version 2.6 or later.

iQCVAwUBNN0kkJezmBrl2RXhAQGxnAP9HyIvtTcOeN77s3p80OmSefhagtfxQGEm
H3NqWzxrqEvfODat63UFDVxcf28cSSog3666Icys1nLY9JhNSFZrruejbRIJ6P4o
AKHfxBwUSO00GvSyCl9nI5VjJDoRG2elDZf7iPP1M9h+IoTXuSDpdWnL9uBpqhvi
SFg4sXOKEOA=
=co6G
-----END PGP SIGNATURE-----

Type Bits/KeyID    Date       User ID
pub  1024/E5D915E1 1997/04/27 Alan Tu <atu5713@compuserve.com>
                              Alan Tu <102534.2165@compuserve.com>

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.3i
Comment: Requires PGP version 2.6 or later.

mQCNAzNivkwAAAEEALdGUXD3j+RioIirVG46N6LaGD3YMMVVT5Mjwr5JojQsDICy
856I06Ugo/Fqid2A/os7v/gwE+Sj/WhMERgTsTejUZtsucTpS9sae+cc27Fjjq1l
hOnqcLZqnHDDNyn3+jesVFPLnRlSoHbmcBK1XDW/SJT1anZz55ezmBrl2RXhAAUR
tCBBbGFuIFR1IDxhdHU1NzEzQGNvbXB1c2VydmUuY29tPokAlQIFEDOguk6Xs5ga
5dkV4QEBBF8D/1B0ePqlMavWEUMP0uTmyvWFI7jooAcih6uHZFo2u+u3EzE2Is8X
EoLHg39DhjleTHPu6TnGsWIiwDYEslzYeVw/Cglx6eliYIr/qs7peEywuhtZsEFH
ln6yR9IE6rX3b3GCvPSQ5uPhXWrd2kWaZvG4rQ4Oj1m3yTrFaPRqCBPvtCRBbGFu
IFR1IDwxMDI1MzQuMjE2NUBjb21wdXNlcnZlLmNvbT6JAJUDBRAzyUJWl7OYGuXZ
FeEBAc4TBACT8gLtyE0C8NBGs9aDa9kHfeNzN8VbNfUpoOiWi4duAAZFiAt/e+ji
J2BUMLIY8kzm2WX4mVzpKYjvea5TtHeQgbESV1HVZ5k7abENMUYz5nSMloOE+bb+
XRzgGgFF3htGXDJNywlLNgoYi5vTMT0pbGlCzOu215Cc4mFls2w1iA==
=CM85
-----END PGP PUBLIC KEY BLOCK-----

On Sat, 7 Feb 1998, Alan Tu wrote:

>anything more recent?  Also, whereas 1024 bits was the commonly accepted
>threshhold for key lengths more than two years ago, what's the threshhold
>now?  Because I have DOS (and like it) I use PGP 2.63ix, when should I
>retire my 1024-bit key?  I don't expect anybody to answer that I should
>do so immediately, but can someone give me an idea on what people are
>doing in regard to key length?
>
>Sincerely,
>
>Alan Tu

8192 bits is used now.  you can generate 8192 bit keys with PGP 2.6.3ui
(the unofficial international version).

check out "PGP Projects" at http://www.westfalen.de/hugo/pgp/
or "The Unofficial International PGP Home Page" at
http://members.tripod.com/~Crompton/pgp.htm
for info and download.

[note:  you can of course generate MUCH larger keys, but i'm attempting to
be practical for a change]

Regards,

TATTOOMAN 

/-=-=-=-=-=-=-=-=-=-=-=-[   TATTOOMAN   ]-=-=-=-=-=-=-=-=-=-=-=-\  
| NC State Computer Science Dept   VP of The  E. H. A. P. Corp. |
| jkwilli2@adm.csc.ncsu.edu        http://www.hackers.com/ehap/ |
| jkwilli2@unity.ncsu.edu          ehap@hackers.com             |
| WWW---[   http://152.7.11.38/~tattooman/                      |
| FTP---[   ftp://152.7.11.38/pub/personal/tattooman/           | 
| WW2---[   http://www4.ncsu.edu/~jkwilli2/                     |                           
| W3B---[   http://152.7.11.38/~tattooman/w3board/              |
| PGP---[   http://www4.ncsu.edu/~jkwilli2/pgp.asc              |
|       35 E1 32 C7 C9 EF A0 AB  9D FE 8E FC 2D 68 55 44        |
\-=-=-=-=-=-=-[   http://152.7.11.38/~tattooman/  ]-=-=-=-=-=-=-/

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