RSA Coding Continued

For homework you read RSA Coding. Let's use the same methods in order to analyze the coded message from the article that we discussed on Tuesday. The following were made public in the article:

Coded Message

9686961375462206147714092225435588290575999
1124574319874695120930816298225145708356931
476622883989628013391990551829945157815154

Encoding Number e

9007

Composite Number n

1143816257578888676692357799761466120102182
9672124236256256184293570693524573389783059
7123563958705058989075147599290026879543541
Gardner said that it would millions of years in order to decode the message at 1977 computer speeds. In order to decode the message, we need d since the decoded message would equal message ^d mod n. There is no way to solve for d unless we can first decompose n into its prime factors p and q. But, this takes a lot of computer power. One could work for years and years and still never find p and q. We need p and q so that we can solve e d mod (p-1)(q-1) = 1 for d. In 1993, Arjen Lenstra a Belcore formed an international group to factor n and break the code. With 600 volunteers using 1600 workstations, mainframes, and supercomputers they broke the code in 6 months by factoring the 129 digit number n. In April 26, 1994, the presented the results and collected their $100 prize.

Factors of n
p = 32769132993266709549961988190834461413177642967992942539798288533 and
q = 3490529510847650949147849619903898133417764638493387843990820577 . You can check to see that pq = n.

Decoding Number d Once we have p and q, we can solve for
d = 106698614368578024442868771328920154780709906633937862801226224496631063125911
774470873340168597462306553968544513277109053606095 I solved for d by using a computer algebra system called Maple.

Decoding the Message We then compute message ^ d mod n via the square and reduce algorithm, as computers can not compute this directly since the number message ^ d is too big. The decoded message is
200805001301070903002315180419000118050019172105011309190800151919090618010705

Turning the Decoded Message into Words Finally, we change the decoded message into letters via the conversion
00->_   01->a   02->b   03->c   04->d   05->e   06->f   07->g   08->h   09->i   10->j   11->k   12->l   13->m   14->n   15->0   16->p   17->q   18->r   19->s   20->t   21->u   22->v   23->w   24->x   25->y   26->z.
We obtain the message THE_MAGIC_WORDS_ARE_SQUEAMISH_OSSIFRAGE