[iwar] [fc:How.easy.factoring.is.getting]

RSA-576 Factored
By Eric W. Weisstein

<a href="http://mathworld.wolfram.com/news/2003-12-05/rsa/">http://mathworld.wolfram.com/news/2003-12-05/rsa/</a>

December 5, 2003--On December 3, the day after the announcement of the
discovery of the largest known prime by the Great Internet Mersenne
Prime Search on December 2 (MathWorld headline news: December 2, 2003),
a team at the German Bundesamt für Sicherheit in der Informationstechnik
(Federal Bureau for Security in Information Technology; BIS) announced
the factorization of the 174-digit number

1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564
2298885971 5234665485 3190606065 0474304531 7388011303 3967161996
9232120573 4031879550 6569962213 0516875930 7650257059

known as RSA-576.

RSA numbers are composite numbers having exactly two prime factors
(i.e., so-called semiprimes) that have been listed in the Factoring
Challenge of RSA Security®.

While composite numbers are defined as numbers that can be written as a
product of smaller numbers known as factors (for example, 6 = 2 x 3 is
composite with factors 2 and 3), prime numbers have no such
decomposition (for example, 7 does not have any factors other than 1 and
itself). Prime factors therefore represent a fundamental (and unique)
decomposition of a given positive integer. RSA numbers are special
types of composite numbers particularly chosen to be difficult to
factor, and are identified by the number of digits they contain.

While RSA-576 is a much smaller number than the 6,320,430-digit monster
Mersenne prime announced earlier this week, its factorization is
significant because of the curious property of numbers that proving or
disproving a number to be prime ("primality testing") seems to be much
easier than actually identifying the factors of a number ("prime
factorization"). Thus, while it is trivial to multiply two large
numbers p and q together, it can be extremely difficult to determine the
factors if only their product pq is given. With some ingenuity, this
property can be used to create practical and efficient encryption
systems for electronic data.

RSA Laboratories sponsors the RSA Factoring Challenge to encourage
research into computational number theory and the practical difficulty
of factoring large integers and because it can be helpful for users of
the RSA encryption public-key cryptography algorithm for choosing
suitable key lengths for an appropriate level of security. A cash prize
is awarded to the first person to factor each Challenge number.

RSA numbers were originally spaced at intervals of 10 decimal digits
between 100 and 500 digits, and prizes were awarded according to a
complicated formula. These original numbers were named according to the
number of decimal digits, so RSA-100 was a hundred-digit number. As
computers and algorithms became faster, the unfactored challenge numbers
were removed from the prize list and replaced with a set of numbers with
fixed cash prizes. At this point, the naming convention was also
changed so that the trailing number would indicate the number of digits
in the binary representation of the number. Hence, RSA-576 has 576
binary digits, which translates to 174 digits in decimal.

RSA numbers received widespread attention when a 129-digit number known
as RSA-129 was used by R. Rivest, A. Shamir, and L. Adleman to
publish one of the first public-key messages together with a $100 reward
for the message's decryption (Gardner 1977). Despite widespread belief
at the time that the message encoded by RSA-129 would take millions of
years to break, it was factored in 1994 using a distributed computation
which harnessed networked computers spread around the globe performing a
multiple polynomial quadratic sieve (Leutwyler 1994). The result of all
the concentrated number crunching was decryption of the encoded message
to yield the profound plaintext message "The magic words are squeamish
ossifrage." (For the benefit of non-ornithologists, an ossifrage is a
rare predatory vulture found in the mountains of Europe.)

Factorization of RSA-129 followed earlier factorizations of RSA-100,
RSA-110, and RSA-120. The Challenge numbers RSA-130, RSA-140, RSA-155,
and RSA-160 were also subsequently factored between 1996 and April of
this year. (Amusingly, RSA-150 apparently remains unfactored following
its withdrawal from the RSA Challenge list.) On December 2, Jens Franke
circulated an email announcing factorization of the smallest prize
number RSA-576. The factorization was accomplished using a prime
factorization algorithm known as the general number field sieve (GNFS).
The two 87-digit factors found using this sieve are

3980750 8642406493 7397125500 5503864911 9906436234 2526708406
3851895759 4638895726 1768583317 x 4727721 4610743530 2536223071
9730482246 3291469530 2097116459 8521711305 2071125636 3590397527

which can easily be multiplied to verify that they do indeed give the
original number.

Franke's note detailed the factorization process in which "lattice"
sieving was done by J. Franke and T. Kleinjung using hardware at the
Scientific Computing Institute and the Pure Mathematics Institute at
Bonn University, Max Planck Institute for Mathematics in Bonn, and
Experimental Mathematics Institute in Essen; and "line" sieving was done
by P. Montgomery and H. te Riele at the CWI, F. Bahr and his family,
and NFSNET (which at that time consisted of D. Leclair, Paul Leyland,
and R. Wackerbarth). Post-processing of this data to construct the
actual factors was then done with the support of the BSI.

For their efforts, the team will receive a cash prize of $10,000 from
RSA Security. However, award seekers need not be deterred. As the
following table shows, RSA-640 to RSA-2048 remain open, carrying awards
from $20,000 to $200,000 to whoever is clever and persistent enough to
track them down. A list of the open Challenge numbers may be downloaded
from RSA or in the form of a Mathematica package from the MathWorld
package archive.

number digits prize factored
RSA-100 100 Apr. 1991
RSA-110 110 Apr. 1992
RSA-120 120 Jun. 1993
RSA-129 129 $100 Apr. 1994
RSA-130 130 Apr. 10, 1996
RSA-140 140 Feb. 2, 1999
RSA-150 150 withdrawn? open
RSA-155 155 Aug. 22, 1999
RSA-160 160 Apr. 1, 2003
RSA-576 174 $10,000 Dec. 3, 2003
RSA-640 193 $20,000 open
RSA-704 212 $30,000 open
RSA-768 232 $50,000 open
RSA-896 270 $75,000 open
RSA-1024 309 $100,000 open
RSA-1536 463 $150,000 open
RSA-2048 617 $200,000 open

References

Franke, J. "RSA576."
Privately circulated email reposted to primenumbers Yahoo! Group.

Gardner, M. "Mathematical Games: A New Kind of Cipher that Would Take
Millions of Years to Break." Sci. Amer. 237, 120-124, Aug. 1977.

Leutwyler, K. "Superhack: Forty Quadrillion Years Early, a 129-Digit Code is
Broken." Sci. Amer. 271, 17-20, 1994.

RSA Security®. "RSA Factoring Challenge."
<a href="http://www.rsasecurity.com/rsalabs/challenges/factoring">http://www.rsasecurity.com/rsalabs/challenges/factoring</a>

RSA Security®. "The RSA Challenge Numbers."
<a href="http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html">http://www.rsasecurity.com/rsalabs/challenges/factoring/numbers.html</a>

Weisstein, E. W. RSANumbers.m Mathematica package.

------------------------ Yahoo! Groups Sponsor ---------------------~-->
Buy Ink Cartridges or Refill Kits for your HP, Epson, Canon or Lexmark
Printer at MyInks.com. Free s/h on orders $50 or more to the US & Canada.
http://www.c1tracking.com/l.asp?cid=5511
http://us.click.yahoo.com/mOAaAA/3exGAA/qnsNAA/kgFolB/TM
---------------------------------------------------------------------~->

------------------
http://all.net/

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
Received on Mon Dec 8 06:57:10 2003