From msuinfo!agate!spool.mu.edu!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!news.mit.edu!jis Sun Oct 17 19:55:49 1993 Path: msuinfo!agate!spool.mu.edu!bloom-beacon.mit.edu!senator-bedfellow.mit.edu!news.mit.edu!jis From: jis@big-screw.MIT.EDU (Jeffrey I. Schiller) Newsgroups: sci.crypt Subject: Re: High speed p*q factorization ??? Date: 10 Oct 1993 22:50:19 GMT Organization: Massachusetts Institute of Technology Lines: 28 Distribution: world Message-ID: References: <750255440snx@aip.nl> NNTP-Posting-Host: big-screw.mit.edu In-reply-to: nevries@aip.nl's message of Sun, 10 Oct 93 12:17:20 GMT Here is a message that I posted on alt.security.pgp outlining some recent computations that I have done: --- Btw. I did some computations to determine how long it should take to factor different length keys using the best technology available today (mpqs). Using the fact that rsa120 was factored with an effort equivalent to 830 MIP-YEARS I computed that: rsa129 (429 bits): 4,600 MIP-YEARS (this is currently being worked on!) a 512 bit key 420,000 MIP-YEARS (safe for a little while!) a 700 bit key 4,200,000,000 MIP-YEARS (seems pretty safe to me!) a 1024 bit key 2.8 x 10^15 MIP-YEARS (Wow!) Nothing like exponential processes. There are factoring algorithms which may prove faster then mpqs when applied to larger numbers (i.e., the gnfs algorithm). However these are still exponential algorithms and I doubt if they will do any better then knock a few orders of magnitude off the work required to factor that 1024 bit key! Of course if a polynomial time algorithm is discovered, all bets are off, regardless of your key length! -Jeff