RSA Number

Numbers contained in the ``factoring challenge'' of RSA Data Security, Inc. An additional number which is not part of the actual challenge is the RSA-129 number. The RSA numbers which have been factored are RSA-100, RSA-110, RSA-120, RSA-129, and RSA-130 (Cowie et al. 1996).

RSA-129 is a 129-digit number used to encrypt one of the first public-key messages. This message was published by R. Rivest, A. Shamir, and L. Adleman (Gardner 1977), along with the number and a $100 reward for its decryption. Despite belief that the message encoded by RSA-129 ``would take millions of years of break,'' RSA-129 was factored in 1994 using a distributed computation which harnessed networked computers spread around the globe performing a multiple polynomial Quadratic Sieve Factorization Method. The effort was coordinated by P. Leylad, D. Atkins, and M. Graff. They received 112,011 full factorizations, 1,431,337 single partial factorizations, and 8,881,138 double partial factorizations out of a factor base of 524,339 Primes. The final Matrix obtained was $188,346\times 188,346$ square.

The text of the message was ``The magic words are squeamish ossifrage'' (an ossifrage is a rare, predatory vulture found in the mountains of Europe), and the Factorization (into a 64-Digit number and a 65-Digit number) is

$114381625757888867669235779976146612010218296\cdots$
$\cdots 7212423625625618429357069352457338978305971\cdots$
$\cdots 23563958705058989075147599290026879543541$
$= 3490529510847650949147849619903898133417764\cdots$
$\cdots 638493387843990820577\cdot 3276913299326\cdots$
$\cdots 6709549961988190834461413177642967992\cdots$
$\cdots 942539798288533$

(Leutwyler 1994, Cipra 1995).

References

Cipra, B. ``The Secret Life of Large Numbers.'' What's Happening in the Mathematical Sciences, 1995-1996, Vol. 3. Providence, RI: Amer. Math. Soc., pp. 90-99, 1996.

Cowie, J.; Dodson, B.; Elkenbracht-Huizing, R. M.; Lenstra, A. K.; Montgomery, P. L.; Zayer, J. A. ``World Wide Number Field Sieve Factoring Record: On to $512$ Bits.'' In Advances in Cryptology--ASIACRYPT '96 (Kyongju) (Ed. K. Kim and T. Matsumoto.) New York: Springer-Verlag, pp. 382-394, 1996.

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

Klee, V. and Wagon, S. Old and New Unsolved Problems in Plane Geometry and Number Theory, rev. ed. Washington, DC: Math. Assoc. Amer., p. 223, 1991.

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

Leyland, P. ftp://sable.ox.ac.uk/pub/math/rsa129.

RSA Data Security. ${}^{\scriptstyle\circledRsymbol}$ A Security Dynamics Company. http://www.rsa.com.

Taubes, G. ``Small Army of Code-breakers Conquers a 129-Digit Giant.'' Science 264, 776-777, 1994.

Weisstein, E. W. ``RSA Numbers.'' Mathematica notebook RSANumbers.m.