Math 455.1  •  5 April 2009

The RSA 1977 challenge

Copyright © 2009 by Murray Eisenberg.  All rights  reserved.

The challenge

In one of Martin Gardner's 1977 "Mathematical Games" columns in Scientific American, a challenge was posed involving the RSA public-key cryptosystem:   To decrypt a particular ciphertext c given the public key (n, e) that was used.

Rivest estimated that it would take 4 × (10^16) years to factor n (and hence crack the cipher).  So Rivest suggested a  $100 prize to anybody who could decrypt the ciphertext before April 1, 1982.

The ciphertext:

c=96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154;

The public key:

{n,e}= {114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541, 9007};

Note:

c<n

So the encryption method treated the numeric equivalent of the plaintext as a single integer and did not break it into shorter blocks!

Do you dare to try to factor n directly?

FactorInteger[n]

Character encoding and decoding

This RSA system used a 27-character alphabet—the usual A through Z together with a blank.  The blank is coded numerically as 0.  The letters are coded with A as 1, B as 2, etc., and Z as 26.

alph=Characters[" ABCDEFGHIJKLMNOPQRSTUVWXYZ"];
toCharacter[n_]:=alph[[n+1]] /;IntegerQ[n]&&0≤n≤26
SetAttributes[toCharacter,Listable]
toNumber[ch_]:=First[Flatten[Position[alph,ch]]]-1/;MemberQ[alph,ch ]
SetAttributes[toNumber,Listable]

Solution

In 1994, Atkins, Graff, Lenstra, and Leyland factored n and decrypted the challenge ciphertext.

Factoring n

Atkins, Graff, Lenstra, and Leyland:
• devised and a way to break up part of the problem into a large number of smaller problems.
• recruited and obtained the assistance of 600 people who, using 1600 computers in their spare time over a 7-month period, worked on these smaller problems and e-mailed results to a central computer.
• using those results, with an additional 57 hours of computing obtained the prime factorization of n:

p= 3490529510847650949147849619903898133417764638493387843990820577;

q= 32769132993266709549961988190834461413177642967992942539798288533;

p q==n

{PrimeQ[p], PrimeQ[q]}

Decrypting the message

The next step in decrypting the message is to find the multiplicative inverse of e modulo (p - 1)(q - 1):

d=PowerMod[e,-1,(p - 1)(q - 1)]

Since the encryption was done with just a single block, the numeric form of the plaintext is therefore the single large integer
	t = (c^d) mod n.

t=Mod[(c^d),n]

Oops—out of memory!  Let's try something much more efficient:

t=PowerMod[c,d,n]

Now decode that number to characters:

to2Digits[{j_,k_}]:=10 j+k

nums=Map[to2Digits,Partition[IntegerDigits[t],2]]

StringJoin[toCharacter[nums]]