Computer Security and Cryptography

13.9 THE RSA CHALLENGE

RSA Data Security Incorporated (Redwood City) supplies encryption protocols using the RSA algorithm. As the strength of RSA appears to depend upon the intractability of factoring n = pq for suitably large prime numbers, the RSA Factoring Challenge was set up in March 1991; it consists of a list of numbers, each the product of two primes of roughly comparable size. There are 42 numbers in the challenge; the smallest length is 100 digits and they increase in steps of 10 digits to 500 digits.

TABLE 13.13 The RSA Challenge

Number	Date Factored
RSA-100	April 1991
RSA-110	April 1992
RSA-120	June 1993
RSA-129	April 1994
RSA-130	April 1996
RSA-140	February 1999
RSA-155	August 1999

Figure 13.2 RSA-129.

Table 13.13 gives some of the results in the RSA Challenge. RSA-129 (Fig. 13.2) appears in Martin Gardner's article [Gardner, 1977] in Scientific American; the factorization of RSA-129 was posed as the first RSA Challenge with a prize of $100 for the solution.

The message THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE⁴ was enciphered with RSA-129 using the public key e = 9007 and private key

d=106698614368578024442868771328920154780709906633937862801226224496631
   063125911774470873340168597462306553968544513277109053606095

The factorization of RSA-129 used the double large prime variation of the multiple polynomial quadratic sieve factoring method. The ...