Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:28
Vin McLellan (vin@shore.net)
Thu, 25 Feb 1999 00:42:58 -0500
Thomas Roessler <roessler@guug.de> queried the List:
>Are there any current estimates on the cost and time it takes to
>factor a 512 bit RSA modulus?
Time and money (CPUs, memory, and talent) obviously play off
against one another in such a task.
Jim Gillogly <jim@acm.org> responded:
>Paul Leyland, who has been involved in most of the important factoring
>achievements, estimates that the size of the project with today's
>hardware would be comparable to the RSA-129 effort, which in 1994 found
>the factors of that 426-bit number using 1600 distributed computers
>(about 5000 MIPS-years). He expects such a project to be completed
>within a year or two.
For perspective, recall that while the 1994 factoring of Martin
Gardner's RSA-129 (426-bit) challenge took 4K to 6K MIPS-years of
processing, on 1600 CPUs, over eight months, but it was probably the last
large number to be factored using the Quadratic Sieve method.
Subsequent factoring projects have relied upon the much more
efficient general Number Field Sieve. (In '94, Leyland and his compatriots
in the RSA-129 effort estimated then that factoring a 512-bit RSA modulus
with QS would be 100 times more difficult than their RSA-129 project, but
only 10 times more difficult if they could use the NFS.)
>By comparison, Paul estimates that factoring a 768-bit RSA modulus would
>currently require an effort about the size of the Apollo project.
Leyland has a way with words as well as large integers.
A couple of weeks ago, Leyland and a half-dozen other well-known
factoring champs <http://www.rsa.com/rsalabs/html/rsa140.html> finished
factoring the 140-bit RSA Factoring Challenge Number using the general
Number Field Sieve. The actual sieving took about a month.
Nearly 200 memory-rich workstations -- 125 SGI and Sun (175MHz
average) workstations, and about 60 300MHs PCs -- were used for both line
sieving and lattice sieving. The team of bright guys who tackled RSA-140
also had a big momma (TM) of a CRAY -- the C916 at the SARA Amsterdam
Academic Computer Center, with over 800 MB of main memory -- available for
100 hours to handle the GNFS matrix.
The matrix for RSA-140 ran about 5 million rows by 5 million
columns, with 32 non-zeros per row.
That month of sieving -- described as "8.9 CPU years" on the
workstations; I don't know the MIPS-year equivalent -- doesn't include an
additional 2K hours of pre-processing on four 250MHz CGI processors (using
a new search algorithm developed by Peter Montgomery and Brian Murphy at
the Australian National University) to identify the polynumerals used for
the NFS.
Projections now give us a fairly accurate estimate of the amount to
processing time and memory required to tackle such a task like RSA-512
using GNFS.
With similar pre-processing to select the polynumerals, and with
access to a similar array of computational resources, RSA estimates that
factoring a 512-bit (155 digit) RSA modulus should take about 7.2 times as
much processing time as the RSA-140 project. That's 7.2 months on the same
equipment: 64 CPU-years. (Sorry. I can't independently calculate the
MIPS-year equivalent; admittedly a more useful stat.)
Holding the matrix for a NFS attack on a 512-bit RSA-155 integer is
also expected to require about 2.7 times as much memory as the 810 MB in
C916 main memory that was used when they factored RSA-140. That's a
whopping 2,187 MB.
(By contrast -- again using the stats from the RSA-140 Challenge as
a baseline -- factoring a 1024-bit number is roughly estimated to require
about 40 million times more processing, and 6,300 times as much memory.)
Even for factoring a 512-bit modulus, cost is hard to figure.
If you can be patient -- if what you are seeking will still be
valuable a year or two years hence -- obviously the costs can drop
dramatically.
If you are buying time on a CRAY C916, you'll need a hefty purse.
If you are using idle time on academic machines, the cost may be miniscule
-- but the time-line can run to the moon and back. If you are head of "Z"
at the NSA, with a basement full of CRAYs, the cost will be a predictable
delay in finishing some other computational task on your must-do list.
Suerte,
_Vin
-----
"Cryptography is like literacy in the Dark Ages. Infinitely potent, for
good and ill... yet basically an intellectual construct, an idea, which by
its nature will resist efforts to restrict it to bureaucrats and others who
deem only themselves worthy of such Privilege."
_ A Thinking Man's Creed for Crypto _vbm.
* Vin McLellan + The Privacy Guild + <vin@shore.net> *
53 Nichols St., Chelsea, MA 02150 USA <617> 884-5548
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:28