MathWorld Headline News

RSA-200 Factored

By Eric W. Weisstein

May 10, 2005--On May 9, a team at the German Federal Agency for Information Technology Security (BSI) announced the factorization of the 200-digit number

2799783391 1221327870 8294676387 2260162107 0446786955 4285375600 0992932612 8400107609 3456710529 5536085606 1822351910 9513657886 3710595448 2006576775 0985805576 1357909873 4950144178 8631789462 9518723786 9221823983

known as RSA-200. The team responsible for this factorization is the same one that previously factored the 174-digit number known as RSA-576 (MathWorld headline news, December 5, 2003).

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 they are identified by the number of digits they contain.

While RSA-200 is a much smaller number than the 7,816,230-digit monster Mersenne prime known as M₄₂ (which is the largest prime number known), its factorization is significant because of the curious property 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 also 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 one and five hundred 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 indicates 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 that 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 plain-text message "The magic words are squeamish ossifrage." (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-150, RSA-155, RSA-160, and RSA-576 were also subsequently factored between 1996 and April of 2004.

The factorization of the latest RSA number to fall involved "lattice" sieving 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 of Mathematics in Bonn, and Experimental Mathematics Institute in Essen; and "line" sieving was done by P. Montgomery and H. te Riele at the Dutch Center for Mathematics and Computer Science (CWI) in Amsterdam. Post-processing of this data to construct the actual factors was then done with the support of the BSI. The factorization of RSA-200 was accomplished using a prime factorization algorithm known as the general number field sieve, and the two 100-digit factors found using this sieve are

3532461934 4027701212 7260497819 8464368671 1974001976 2502364930 3468776121 2536794232 0005854795 6528088349 x 7925869954 4783330333 4708584148 0059687737 9758573642 1996073433 0341455767 8728181521 3538140930 4740185467

These numbers can easily be multiplied to verify that their product is indeed equal to the original number.

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.

Postscript:

While a number of RSA challenge number remain unfactored, the RSA challenge and its associated cash awards have since been discontinued.