{VERSION 6 0 "IBM INTEL LINUX" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 
11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 
0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Tit
le" -1 18 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 
}3 1 0 0 12 12 1 0 1 0 2 2 19 1 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 7 "RSA-129" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 20 "There is one famous " }{XPPEDIT 18 0 "129;" "6#
\"$H\"" }{TEXT -1 14 " digit number " }{XPPEDIT 18 0 "n;" "6#%\"nG" }
{TEXT -1 31 " in the literature, called RSA-" }{XPPEDIT 18 0 "129;" "6
#\"$H\"" }{TEXT -1 84 ", which was used as a challenge to anyone to br
eak the message encrypted using this " }{XPPEDIT 18 0 "n;" "6#%\"nG" }
{TEXT -1 5 " and " }{XPPEDIT 18 0 "e = 9007;" "6#/%\"eG\"%2!*" }{TEXT 
-1 98 ".  That is, to break the message, one has to factor the number \+
below into a product of two primes " }{XPPEDIT 18 0 "p;" "6#%\"pG" }
{TEXT -1 5 " and " }{XPPEDIT 18 0 "q;" "6#%\"qG" }{TEXT -1 19 ", in or
der to find " }{XPPEDIT 18 0 "phi(n);" "6#-%$phiG6#%\"nG" }{TEXT -1 
27 " and then find the inverse " }{XPPEDIT 18 0 "d;" "6#%\"dG" }{TEXT 
-1 15 " of the number " }{XPPEDIT 18 0 "e;" "6#%\"eG" }{TEXT -1 8 " mo
dulo " }{XPPEDIT 18 0 "phi(n);" "6#-%$phiG6#%\"nG" }{TEXT -1 2 ". " }
{TEXT -1 50 "This number, called in the literature RSA_129  is:" }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 141 "RSA_129 := 1143816257578888676692357799761466120102182967212423
6256256184293570693524573389783059712356395870505898907514759929002687
9543541:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 13 "The exponent " }{XPPEDIT 18 0 "e;" "6#%\"eG" }{TEXT -1 
20 " used to encrypt is:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "e:=9007;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"eG\"%2!*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }
}{PARA 0 "" 0 "" {TEXT -1 109 "Using the assignment of letters A=01, B
=02, ... , Z=26 with a blank being 00, the RSA-encrypted message was: \+
" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 134 "C := 96869613754622061477140922254355882905759991124
5743198746951209308162982251457083569314766228839896280133919905518299
45157815154:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "
" {TEXT -1 11 "The number " }{XPPEDIT 18 0 "n;" "6#%\"nG" }{TEXT -1 
48 " is known to be the product of a 64-digit prime " }{XPPEDIT 18 0 "
p;" "6#%\"pG" }{TEXT -1 22 " and a 65-digit prime " }{XPPEDIT 18 0 "q;
" "6#%\"qG" }{TEXT -1 141 ". A $100 prize was offered by the M.I.T gro
up of Ronald L. Rivest, Adi Shamir, and Leonard Adleman for any one wh
o could decrypt the message " }{XPPEDIT 18 0 "C;" "6#%\"CG" }{TEXT -1 
66 ". That is, factor the above 129-digit (426-bit) number, then find \+
" }{XPPEDIT 18 0 "phi(n);" "6#-%$phiG6#%\"nG" }{TEXT -1 24 ", then fin
d the inverse " }{XPPEDIT 18 0 "d;" "6#%\"dG" }{TEXT -1 5 " of  " }
{XPPEDIT 18 0 "`mod`(e,phi(n));" "6#-%$modG6$%\"eG-%$phiG6#%\"nG" }
{TEXT -1 11 ".  To find " }{XPPEDIT 18 0 "d;" "6#%\"dG" }{TEXT -1 30 "
 we need to be able to factor " }{XPPEDIT 18 0 "n;" "6#%\"nG" }{TEXT 
-1 9 " so that " }{XPPEDIT 18 0 "n = p*q;" "6#/%\"nG*&%\"pG\"\"\"%\"qG
F'" }{TEXT -1 14 ", The number  " }{XPPEDIT 18 0 "n;" "6#%\"nG" }
{TEXT -1 772 " and the prize announcement can be found in Martin Gardn
er's delightful article in the August 1977 edition of Scientific Ameri
can. Given the state of computer power in 1977, Rivest, Shamir, and Ad
leman estimated it would take some 20,000 years to factor it. The numb
er was factored in March 1994 by Atkins et al. using the resources of \+
1600 computers (which included two fax machines) from the Internet. Th
e factoring took about 4000 to 6000 MIPS years of computation over an \+
eight-month period. It was factored using the quadratic sieve factorin
g method and, according to Lenstra, will perhaps be the last large num
ber to be factored using the quadratic sieve since the general number \+
field sieve is now more efficient for numbers of this size and larger.
\nThe primes are:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 70 "p := 349052951084765094914784961990389813341
7764638493387843990820577:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
71 "q := 3276913299326670954996198819083446141317764296799294253979828
8533:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "RSA_129-p*q;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}{PAGEBK }{PARA 11 "" 0 "" 
{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "phi_RSA_129
:=(p-1)*(q-1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,phi_RSA_129G\"\\s
KWV!4V'fH6Tvm$R7bM?Kv&G([Jt`>;ussW**G%=ciDOU7s'H=-,7m9w*zdBpw')))yvD;Q
9\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "d:=e^(-1) mod phi_RS
A_129;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"dG\"\\s&41O04rF8XaoRb1BY
(fo,Mt3Zu<\"f7j5j'\\CiA,G'y$Rj1*42ya,#*G8xoGWC!y&oVh)p1\"" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "M:=C&^d mod RSA_129;" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%\"MG\"io02,=14>>:+3>48,0@<>+0=,+>/=:B+.42,8+03
?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 
109 "Next we have to translate the numbers back to letters and blanks.
 We need the following functions to do this:" }}{PARA 0 "" 0 "" {TEXT 
-1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 50 "`crypt/alphabet` \+
:= `ABCDEFGHIJKLMNOPQRSTUVWXYZ `:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 276 "to_number := proc(st, string) \nlocal ll, nn, ss, ii
;  \nll := length(st);\nif ll = 0 then RETURN(0) fi; \nnn := 1;\nfor i
i to ll do \nss := searchtext(substring(st, ii .. ii),\n              \+
   `crypt/alphabet`);\nif ss=27 then ss:=00 fi;\nnn := 100*nn + ss \no
d;\nnn - 10^(2*ll) \nend:\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
282 "from_number := proc(nn, integer) \nlocal ss, mm, ll, pp, ii, ans;
 mm := nn;\nll:=trunc((length(mm)+1)/2);\nans := ``; for ii to ll do m
m := mm/100;\npp := 100*frac(mm);\nif pp=00 then pp:=27 fi;\nss := sub
string(`crypt/alphabet`, pp..pp);\nans := cat(ss, ans); mm := trunc(mm
)\nod; ans end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 46 "Now we ca
n see what the message M really says:" }}{PARA 0 "" 0 "" {TEXT -1 0 "
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "from_number(M);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#%HTHE~MAGIC~WORDS~ARE~SQUEAMISH~OSSIFR
AGEG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 192 "An ossifrage is an old w
ord for an osprey which is a large hawk that feeds only on fish. To pr
ove that the offer of $100 actually came from the M.I.T group, the fol
lowing signature was added: " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 134 "SIG:=1671786115038084424601
5271389168398245436901032358311217835038446929062655448792237114490509
578608655662496577974840004057020373:" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 32 "SIG was encoded with the \+
secret " }{XPPEDIT 18 0 "d;" "6#%\"dG" }{TEXT -1 84 " found above. So \+
if we raise SIG to the power 9007, it should tell us the signature." }
}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 22 "SIG&^9007 mod RSA_129;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"do>=
,77:/+/0=/9@3+09:+>94B+=0A7:>+?>=4'" }}}{EXCHG {PARA 11 "" 1 "" {TEXT 
-1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "from_number(%);" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#%FFIRST~SOLVER~WINS~ONE~HUNDRED~DOLL
ARSG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{MARK "10 3 0" 0 }
{VIEWOPTS 0 0 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }