{VERSION 5 0 "IBM INTEL NT" "5.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 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 "Geneva" 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 "Heading 2" -1 4 
1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 
4 4 3 0 3 0 2 2 0 1 }{PSTYLE "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Gene
va" 1 12 0 0 0 1 2 1 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" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{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 "Title" -1 18 1 {CSTYLE "" -1 -1 "Geneva" 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 }
{PSTYLE "Author" -1 19 1 {CSTYLE "" -1 -1 "Geneva" 1 12 0 0 0 1 2 2 2 
2 2 2 1 1 1 1 }3 1 0 0 8 8 1 0 1 0 2 2 0 1 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 9 "Using RSA" }}{PARA 19 "" 
0 "" {TEXT -1 38 "\251 Mike May, S. J., 2002, maymk@slu.edu" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart:" }}}{SECT 0 {PARA 4 
"" 0 "" {TEXT -1 32 "Setting up RSA to encode numbers" }}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 269 "The first thing to do to use RSA is to find tw
o large primes.  For this worksheet we will be looking for primes that
 are about 80 digits long.  (I chose 80 digits bacause that is what ea
sily fits on one line.)  We do this with the rand and nextprime functi
ons in Maple." }}}{EXCHG {PARA 0 "> " 1 "" {MPLTEXT 1 0 83 "M1 := rand
(10^80)();\nM2 := rand(10^80)();\nP1 := nextprime(M1);\nP2 := nextprim
e(M2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M1G\"[p&3AA1K!Q0$QvYn(*=(
e%eNcVhDuuptIjV.F$p56K\"3p'>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M2G
\"[pgTfp\"RqX!\\zrzjr[v+JbE&>\")f#4u.!eX<#Rh0Vgo<7u" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%#P1G\"[pdAAi?.Q0$QvYn(*=(e%eNcVhDuuptIjV.F$p56K\"3p
'>" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P2G\"[p8Ufp\"RqX!\\zrzjr[v+Jb
E&>\")f#4u.!eX<#Rh0Vgo<7u" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 318 "The
 use of a random number function in the selection of the primes is int
ended to make them hard to guess.  The output has been converted to Ma
ple input so that we can work with repeatable computations.  (To conve
rt to Maple input I had to copy the output to a simpletext document th
an copy fromthere back into Maple.)" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 359 "M1 := 1966908132111069327034363307369747425614356355
8458718976746753\\\n830538032062222085;\nM2 := 74121768604305613921745
580037409259811952655310075487163797179\\\n490457039169594160;\nP1 := \+
19669081321110693270343633073697474256143563558458718976746753\\\n8305
38032062222257;\nP2 := 74121768604305613921745580037409259811952655310
075487163797179\\\n490457039169594213;" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%#M1G\"[p&3AA1K!Q0$QvYn(*=(e%eNcVhDuuptIjV.F$p56K\"3p'>" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#M2G\"[pgTfp\"RqX!\\zrzjr[v+JbE&>\")
f#4u.!eX<#Rh0Vgo<7u" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P1G\"[pdAAi?
.Q0$QvYn(*=(e%eNcVhDuuptIjV.F$p56K\"3p'>" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%#P2G\"[p8Ufp\"RqX!\\zrzjr[v+JbE&>\")f#4u.!eX<#Rh0Vgo<7u" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 100 "I need to compute the product of \+
the two primes and the product of one less than each of the primes." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "n := P1*P2;\nn2 := (P1-1)*
(P2-1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%\"nG\"[uT()*pqt$yA%yUKf;R
[&*>!)p(e*>D0W`n$=hNo(o=-o/'\\:1BO2b(\\!)H_(RV;'[#=\"\\\"f^E.)H'eof\"3
T$>dOEM%42zX\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#n2G\"[usA=vCI$G@X
\\)QDIj?9:z9\\J6zLBkBE_V'p0xwo>0<_Iit]v\\!)H_(RV;'[#=\"\\\"f^E.)H'eof
\"3T$>dOEM%42zX\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 318 "I now need \+
to decide on a value for e, the encrypting number.  SInce e will be pu
blic, I don't need to worry about random generation.  I can consider n
umbers that will be easy to work with mathematically.  It seems that t
he best criterion for mathematical ease is that e represented base 2 s
hould be almost all zeroes." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
35 "e:= 2^16+1;  isprime(e); gcd(e,n2);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%\"eG\"&Pb'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 306 "Recall that we had to make sure that e is relatively pri
me to n2.  That is easier because we have chosen e to be prime.  Now w
e need to compute d, the multiplicative inverse of e mod n2.  We could
 do that directly with the extended Euclidean algorithm, but we will j
ust use the modular arithmetic of Maple." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 22 "d := eval(1/e mod n2);" }}{PARA 12 "" 1 "" {XPPMATH 
20 "6#>%\"dG\"jt8H5j)=*z>[O-c%zE#*4va#[4'*[y`u34\"*\\&4A&y,C$=$Hyxg]:7
tr_exJ%ft![KOA5>aUV4sSy]l?ZZo4A*)H!=M" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 57 "We are ready to define encoding and decoding proceedures.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 79 "encoder := (a,e,n) -> P
ower(a,e) mod n:\ndecoder := (a,d,n) -> Power(a,d) mod n:" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 107 "We obviously want to check that the proc
edures reverse each other, at least for a small sample of messages." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "m1 := encoder(5,e,n);p1 :=
decoder(m1,d,n);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#m1G\"jthU()Q&pT
;&R:R5\\t5kY;'4+FU(o&>H'y4VCBsi$Qd@p\\!fy&=$)[$RxX[O1adOa%)eR16gX#)y%G
q\\ysd/dGl#)*pY%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#p1G\"\"&" }}}
{SECT 0 {PARA 5 "" 0 "" {TEXT -1 9 "Exercises" }}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 236 "1)  The chosen primes let us encode and decode message
s that are numbers approximately in the range of 0 to 10^159.  Randoml
y pick 5 numbers in that range and verify that encoding and decoding a
ct as inverse operations on these numbers." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 202 "2)  Of the
 numbers found so far, explain which numbers I want to publish, which \+
ones I want to save but keep secret, and which ones I want to destroy \+
and forget if I am using RSA as a public key system." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 281 "
3)  Randomly pick two primes of your own in the 1-10^80 range and prep
are your own keys.  Test that your keys encrypt and decrypt on two num
bers of your choice.  (You probably don't want to reuse the names n, e
, or d, since we will continue to use these numbers in later exercises
." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 141 "4)  Post your public key and modulus to the bulleti
n board so that others in the class can send you messages.  (Do not po
st your secret key.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 
"" {TEXT -1 37 "Encoding messages rather than numbers" }}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 534 "Now we want to turn our attention to encoding \+
messages.  Following the pattern from earlier work, if we want to turn
 our message into into a single number, the trick is to use convert to
 change a message from ASCII to a string of decimal equivalents, then \+
convert each of the decimal numbers into a two digit hex number, conca
tenate (string together) the hex numbers into one big number, then con
vert it back to a decimal number.  We can then encode our message numb
er, convert it to a hex number and store it in some reasonable form." 
}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 370 "Recall
 that we had a problem with hex conversion before.  If the decimal equ
ivalent of the ASCII charachter is less than 16, the hex number is onl
y one digit long, and we want to assume characters contribute 2 hex di
gits to keep placement straight.  (In particular the \"return\" charac
ter is equivalent to 13.)  The procedure twodigithex converts with a t
wo digit output." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "twodigi
thex := a -> substring(convert(a+256,hex),2..3):" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 43 "We are ready to start with a small message." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 74 "mess1 := \"Good morning Mr. \+
Phelps,\nThis morning we look at RSA.\n3rd line\";" }}{PARA 12 "" 1 "
" {XPPMATH 20 "6#>%&mess1GQinGood~morning~Mr.~Phelps,|+This~morning~we
~look~at~RSA.|+3rd~line6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "We \+
want a procedure to convert this to a number." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 553 "shortconverter := proc(messagestring)\n  local \+
stringofhex, lengthofmess, hexstring, i:\n    #First we convert the AS
CII string to a list of decimal equivalents\n    #Then we convert thed
ecimal numbers to hex equivalents\n  stringofhex := map(twodigithex, c
onvert(messagestring,bytes)):\nprint(stringofhex);\n  lengthofmess := \+
nops(stringofhex):\nprint(lengthofmess);\n    #Now we concatenate the \+
hex numbers\n  hexstring := cat(seq(stringofhex[i],i=1..lengthofmess))
:\n    #Finally we convert the big number back to decimal\n  convert(h
exstring,decimal,hex):\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 34 "messnum1 := shortconverter(mess1);" }}{PARA 12 "" 1 "" {XPPMATH 
20 "6#7jn%#47G%#6FGF%%#64G%#20G%#6DGF%%#72G%#6EG%#69GF*%#67GF'%#4DGF)%
#2EGF'%#50G%#68G%#65G%#6CG%#70G%#73G%#2CG%#0AG%#54GF0F+F4F'F(F%F)F*F+F
*F,F'%#77GF1F'F2F%F%%#6BGF'%#61G%#74GF'%#52G%#53G%#41GF.F6%#33GF)F&F'F
2F+F*F1" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#i" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%)messnum1G\"`tpso.:Vv[AjL,EXiSmw$RR&[Vo]T*o$)*eIb[qz?
d,:e&G1>Kuc2A#=(3()GHP7o22#Hh&y%fs1JtzSx)3d" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 74 "Next we want to encode our number and convert it to hex
 for easy handling." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "sech
ex1 := convert(encoder(messnum1,e,n),hex);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%(sechex1G%_s622ED113512082D85F0D6C7504B962D337173151B
AF504F469586953300258AFFE7ED152E360ECF742152D71E8F60BB1CB5AC17F8022798
960A3FB8DCE6796C1E2C1G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 325 "This d
oes not look very easy to copy back and forth.  (I am sure I would mak
e a mistake if I tried to type a copy of a string that long.)  To give
 a nice form to the output, I want to pad the message out with leading
 zeroes, then break it into blocks of a nice size.  For today, I think
 10 characters forms a nice block size." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 16 "length(sechex1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
\"$K\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 68 "sechex2 := cat(se
q(\"0\",counter = 1..(140-length(sechex1))),sechex1);" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#>%(sechex2GQgs00000000622ED113512082D85F0D6C7504B9
62D337173151BAF504F469586953300258AFFE7ED152E360ECF742152D71E8F60BB1CB
5AC17F8022798960A3FB8DCE6796C1E2C16\"" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 58 "secmess := [seq(substring(sechex2,10*i-9..10*i),i=1..
14)];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(secmessG70Q+00000000626\"Q
+2ED1135120F'Q+82D85F0D6CF'Q+7504B962D3F'Q+37173151BAF'Q+F504F46958F'Q
+6953300258F'Q+AFFE7ED152F'Q+E360ECF742F'Q+152D71E8F6F'Q+0BB1CB5AC1F'Q
+7F80227989F'Q+60A3FB8DCEF'Q+6796C1E2C1F'" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 161 "Now we want to verify that we can put the message back t
ogether and decode it.  We define a procedure for converting the vecto
r of hexblock into a single number." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 93 "hexvectodec := (hexvec,size) -> \n         convert(ca
t(seq(hexvec[i],i=1..size)),decimal,hex):" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 106 "Now we can convert our message back to a decoded number.
  We should get an answer equal to messnum1 above." }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 48 "newnum1 := decoder(hexvectodec(secmess,14),
d,n);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(newnum1G\"`tpso.:Vv[AjL,EX
iSmw$RR&[Vo]T*o$)*eIb[qz?d,:e&G1>Kuc2A#=(3()GHP7o22#Hh&y%fs1JtzSx)3d" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "convert(newnum1,hex);" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#%gr476F6F64206D6F726E696E67204D722E205
068656C70732C0A54686973206D6F726E696E67207765206C6F6F6B206174205253412
E0A337264206C696E65G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 76 "We also w
ant a procedure for turning the decoded number back into a message." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 591 "numtostring := proc(bignu
m)\nlocal hexstr1, listlength, declist, i:\n#convert to a hex string\n
hexstr1 := convert(bignum,hex):\n#make sure the hex string has even le
ngth\nif (length(hexstr1) mod 2) = 1 then hexstr1 := cat(`0`,hexstr1) \+
fi;\n#compute the number of characters\nlistlength := length(hexstr1)/
2:\n#convert to a vector of decimal numbers\ndeclist := linalg[vector]
(listlength);\nfor i from 1 to listlength do\ndeclist[i] := convert(su
bstring(hexstr1,2*i-1..2*i),decimal,hex);\nod;\n#convert the vector to
 a list, then to an ASCII string\nconvert(convert(convert(declist,list
),bytes),name);\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "nu
mtostring(newnum1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#%inGood~morning
~Mr.~Phelps,|+This~morning~we~look~at~RSA.|+3rd~lineG" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 212 "There is one more issue to deal with.  F
or the procedures above to work, we have to restrict ourselves to mess
ages that encode as numbers less than n.  A message of length t encode
s as a numebr less than 256^t.  " }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 
9 "Exercises" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "5)  What is the ma
ximum length of a message that we can encode with n chosen as above?" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 90 "6)  Enter a message of about 50 characters and encode i
t Using the n and e defined above. " }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 64 "7)  Verify th
at you can decrypt the message with the secret key." }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 180 "
8)  For the rest of this worksheet, Fr. May's modulus is\n145790709434
263657193410815968586298032651591491182486164339\\\n752298049755073623
061549604680218687683561183675344052519958\\" }}{PARA 0 "" 0 "" {TEXT 
-1 40 "7698019954839165932427842278373706998741" }}{PARA 0 "" 0 "" 
{TEXT -1 25 "and his encrypting key is" }}{PARA 0 "" 0 "" {TEXT -1 6 "
65537." }}{PARA 0 "" 0 "" {TEXT -1 73 "Encrypt your short message and \+
send it to him through the bulletin board." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "9)  Obtain
 the public keys of two othe people in the class and send them a short
 encrypted message via the bulletin board." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "10)  Respon
d to the messages you get with encrypted messages." }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "11)
  Make a shorter RSA worksheet that you can use as an application for \+
encrypting and decrypting." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
0 "" }}}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0
" 0 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }