RSA-129

There is one famous 129  digit number n  in the literature, called RSA- 129 , which was used as a challenge to anyone to break the message encrypted using this n  and e = 9007 .  That is, to break the message, one has to factor the number below into a product of two primes p  and q , in order to find phi(n)  and then find the inverse d  of the number e  modulo phi(n) . This number, called in the literature RSA_129  is:

>    RSA_129 := 114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541:

The exponent e  used to encrypt is:

>    e:=9007;

e := 9007

Using the assignment of letters A=01, B=02, ... , Z=26 with a blank being 00, the RSA-encrypted message was:

>    C := 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154:

The number n  is known to be the product of a 64-digit prime p  and a 65-digit prime q . A $100 prize was offered by the M.I.T group of Ronald L. Rivest, Adi Shamir, and Leonard Adleman for any one who could decrypt the message C . That is, factor the above 129-digit (426-bit) number, then find phi(n) , then find the inverse d  of   `mod`(e,phi(n)) .  To find d  we need to be able to factor n  so that n = p*q , The number   n  and the prize announcement can be found in Martin Gardner's delightful article in the August 1977 edition of Scientific American. Given the state of computer power in 1977, Rivest, Shamir, and Adleman estimated it would take some 20,000 years to factor it. The number was factored in March 1994 by Atkins et al. using the resources of 1600 computers (which included two fax machines) from the Internet. The factoring took about 4000 to 6000 MIPS years of computation over an eight-month period. It was factored using the quadratic sieve factoring method and, according to Lenstra, will perhaps be the last large number to be factored using the quadratic sieve since the general number field sieve is now more efficient for numbers of this size and larger.
The primes are:

>    p := 3490529510847650949147849619903898133417764638493387843990820577:

>    q := 32769132993266709549961988190834461413177642967992942539798288533:

>    RSA_129-p*q;

0

>    phi_RSA_129:=(p-1)*(q-1);

phi_RSA_129 := 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432
phi_RSA_129 := 114381625757888867669235779976146612010218296721242362562561842899447272741619537331487285753220345512393667541112959643090434432

>    d:=e^(-1) mod phi_RSA_129;

d := 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095
d := 106698614368578024442868771328920154780709906633937862801226224496631063125911774470873340168597462306553968544513277109053606095

>    M:=C&^d mod RSA_129;

M := 200805001301070903002315180419000118050019172105011309190800151919090618010705

Next we have to translate the numbers back to letters and blanks. We need the following functions to do this:

>    `crypt/alphabet` := `ABCDEFGHIJKLMNOPQRSTUVWXYZ `:

>    to_number := proc(st, string)
local ll, nn, ss, ii;  
ll := length(st);
if ll = 0 then RETURN(0) fi;
nn := 1;
for ii to ll do
ss := searchtext(substring(st, ii .. ii),
                 `crypt/alphabet`);
if ss=27 then ss:=00 fi;
nn := 100*nn + ss
od;
nn - 10^(2*ll)
end:

>    from_number := proc(nn, integer)
local ss, mm, ll, pp, ii, ans; mm := nn;
ll:=trunc((length(mm)+1)/2);
ans := ``; for ii to ll do mm := mm/100;
pp := 100*frac(mm);
if pp=00 then pp:=27 fi;
ss := substring(`crypt/alphabet`, pp..pp);
ans := cat(ss, ans); mm := trunc(mm)
od; ans end:

>   

Now we can see what the message M really says:

>    from_number(M);

`THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE`

An ossifrage is an old word for an osprey which is a large hawk that feeds only on fish. To prove that the offer of $100 actually came from the M.I.T group, the following signature was added:

>    SIG:=16717861150380844246015271389168398245436901032358311217835038446929062655448792237114490509578608655662496577974840004057020373:

SIG was encoded with the secret d  found above. So if we raise SIG to the power 9007, it should tell us the signature.

>    SIG&^9007 mod RSA_129;

6091819200019151222051800230914190015140500082114041805040004151212011819

>    from_number(%);

`FIRST SOLVER WINS ONE HUNDRED DOLLARS`