{VERSION 4 0 "APPLE_PPC_MAC" "4.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 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 
0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 0 1 0 0 0 
0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 261 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
262 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 266 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
267 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" 18 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
272 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{CSTYLE "" -1 276 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
277 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 
0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 0 0 0 0 1 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }
{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 "Heading 1" 0 3 1 
{CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }1 0 0 0 8 4 0 0 
0 0 0 0 -1 0 }{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 
0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 8 2 0 0 0 0 0 0 -1 0 }{PSTYLE "Headi
ng 3" 4 5 1 {CSTYLE "" -1 -1 "" 1 12 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }0 0 
0 -1 0 0 0 0 0 0 0 0 -1 0 }{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 "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 
0 0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Autho
r" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 
}3 1 0 0 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 257 1 {CSTYLE "" -1 
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 
0 1 }{PSTYLE "Normal" -1 258 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 
2 1 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Normal" -1 
259 1 {CSTYLE "" -1 -1 "Times" 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 "Title" -1 260 1 {CSTYLE "" -1 -1 "Ti
mes" 1 18 0 0 0 1 2 1 2 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 5 "" 0 "" {TEXT 256 43 "The RSA Public Key Crypto
graphic Scheme    " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 96 "Suppose Alice wants Bob t
o send her a secret message using the RSA scheme. Here's what she does
." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 38 "1. S
he finds two large primes p and q." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 33 "2. She forms the product m = pq.\n" }}
{PARA 0 "" 0 "" {TEXT -1 69 "3. She chooses a positive integer e which
 is relatively  prime to m.\n" }}{PARA 0 "" 0 "" {TEXT -1 16 "4. She c
omputes " }{XPPEDIT 18 0 "phi(m) = (p-1)*(q-1);" "6#/-%$phiG6#%\"mG*&,
&%\"pG\"\"\"F+!\"\"F+,&%\"qGF+F+F,F+" }{TEXT -1 2 ".\n" }}{PARA 0 "" 
0 "" {TEXT -1 52 "5. She computes the inverse, call it d, of e modulo \+
" }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 2 ".\n" }}
{PARA 0 "" 0 "" {TEXT -1 92 "6. She sends the pair of numbers [m,e] to
 Bob. This pair of numbers may be made public, but " }{TEXT 257 11 "th
e numbers" }{TEXT -1 8 " p,q, d " }{TEXT 259 3 "and" }{TEXT -1 1 " " }
{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"mG" }{TEXT -1 1 " " }{TEXT 258 
23 "should be kept secret! " }{TEXT -1 19 " We call [m,e] the " }
{TEXT 262 10 "public key" }{TEXT -1 12 " and d, the " }{TEXT 271 11 "p
rivate key" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 
0 "" 0 "" {TEXT -1 106 "7. She tells Bob how to use Maple to convert t
he text of his message into a sequence of positive integers " }
{XPPEDIT 18 0 "a[1];" "6#&%\"aG6#\"\"\"" }{TEXT -1 3 " , " }{XPPEDIT 
18 0 "a[2];" "6#&%\"aG6#\"\"#" }{TEXT -1 10 ", . . . , " }{XPPEDIT 18 
0 "a[k];" "6#&%\"aG6#%\"kG" }{TEXT -1 46 " each less than m. The metho
d is shown below. " }{TEXT 260 31 "This method can be made public." }}
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 50 "8. She te
lls Bob to compute for each i the number " }{XPPEDIT 18 0 "b[i] = `mod
`(a[i]^e,m);" "6#/&%\"bG6#%\"iG-%$modG6$)&%\"aG6#F'%\"eG%\"mG" }{TEXT 
-1 51 " and tells him to send her the sequence of numbers " }{XPPEDIT 
18 0 "b[1];" "6#&%\"bG6#\"\"\"" }{TEXT -1 2 ", " }{XPPEDIT 18 0 "b[2];
" "6#&%\"bG6#\"\"#" }{TEXT -1 9 ", . . ., " }{XPPEDIT 18 0 "b[k];" "6#
&%\"bG6#%\"kG" }{TEXT -1 23 ". He need not keep the " }{XPPEDIT 18 0 "
b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 64 " 's secret after he has  comput
ed them. But, he should keep the " }{XPPEDIT 18 0 "a[i];" "6#&%\"aG6#%
\"iG" }{TEXT -1 10 "'s secret." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 27 "9. Now when Alice gets the " }{XPPEDIT 
18 0 "b[i];" "6#&%\"bG6#%\"iG" }{TEXT -1 28 " 's from Bob, she compute
s  " }{XPPEDIT 18 0 "`mod`(b[i]^d,m);" "6#-%$modG6$)&%\"bG6#%\"iG%\"dG
%\"mG" }{TEXT -1 34 " and this will turn out to be the " }{XPPEDIT 18 
0 "a[i];" "6#&%\"aG6#%\"iG" }{TEXT -1 82 "'s. Then she can use Maple t
o convert these back into text as we illustrate below." }}{PARA 0 "" 
0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" 
{TEXT -1 157 "We now illustrate this using two randomly chosen primes \+
with 20 decimal digits. We first generate two 20 digit random numbers \+
and then use the Maple command " }{TEXT 276 9 "nextprime" }{TEXT -1 
56 " to obtain the smallest primes greater than each number:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "N:=rand(10^19..10^20 -1)();
\nM:=rand(10^19..10^20 -1)();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"N
G\"5Q0$QvYn(*=(=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG\"5o<7uHs&3A
A$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "p:=nextprime(N);\nq:=
nextprime(M);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"5^0$QvYn(*=(=
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"54=7uHs&3AA$" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "m:=p*q;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"mG\"Hfne>g6p7OPn<h-QtW;.'" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 10 "length(m);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"
#R" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "PHI:=(p-1)*(q-1);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$PHIG\"H+Wj\"HYm??kow6E!QtW;.'" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "e:=rand(10^19..10^20-1)();" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"eG\"5jr[v+JbE&>)" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 200 "If by chance the modular inverse doesn't
 exists you may go back, put the cursor back on the line where e is co
mputed and hit return. After, possibly, a few tries you will obtain a \+
suitable value of e." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "d:=
1/e mod PHI;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"dG\"HFIqDD&*)pd%o#
>Y)*f1jR%f#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Check that ed mod \+
" }{XPPEDIT 18 0 "phi(m)" "6#-%$phiG6#%\"mG" }{TEXT -1 5 " = 1." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "e*d mod PHI;" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "So t
he " }{TEXT 261 10 "public key" }{TEXT -1 32 " sent to Bob and made pu
blic is " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "Public_Key:=[m,
e];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+Public_KeyG7$\"Hfne>g6p7OPn<
h-QtW;.'\"5jr[v+JbE&>)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 32 "The pri
vate key in this case is:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
25 "Private_key:=[p,q,d,PHI];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,Pr
ivate_keyG7&\"5^0$QvYn(*=(=\"54=7uHs&3AA$\"HFIqDD&*)pd%o#>Y)*f1jR%f#\"
H+Wj\"HYm??kow6E!QtW;.'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "In cry
ptography, " }{TEXT 266 10 "plain text" }{TEXT -1 61 " refers to any m
essage that is not enciphered. Contrast with " }{TEXT 267 13 "cipher t
ext. " }{TEXT -1 73 "Now we assign Bob's message to the variable named
 plain_text, as follows:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
231 "plain_text:=\"The following is important:\n\nSo what exactly is t
his new entity, AOL Time Warner, which is intent on completing its lon
g-planned merger in the coming weeks Ñ unless the Federal Trade Commis
sion decides to block it?\"; \n" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%+
plain_textGQaxThe~following~is~important:|.|.So~what~exactly~is~this~n
ew~entity,~AOL~Time~Warner,~which~is~intent~on~completing~its~long-pla
nned~merger~in~the~coming~weeks~|\\x~unless~the~Federal~Trade~Commissi
on~decides~to~block~it?6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 216 "No
te that the text includes new line symbols, \\n, as well as numerous b
lanks.The \\ at the end of each line is just Maple's way of saying tha
t this should all be on one line, but I am forced to break it at this \+
point." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "List1:=convert(pl
ain_text,bytes);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&List1G7bx\"#%)
\"$/\"\"$,\"\"#K\"$-\"\"$6\"\"$3\"F,F+\"$>\"\"$0\"\"$5\"\"$.\"F)F.\"$:
\"F)F.\"$4\"\"$7\"F+\"$9\"\"$;\"\"#(*F/F5\"#e\"#8F8\"#$)F+F)F-F'F6F5F)
F(\"$?\"F6\"#**F5F,\"$@\"F)F.F1F)F5F'F.F1F)F/F(F-F)F(F/F5F.F5F<\"#WF)
\"#l\"#z\"#wF)F&F.F2F(F)\"#()F6F4F/F(F4F=F)F-F'F.F;F'F)F.F1F)F.F/F5F(F
/F5F)F+F/F)F;F+F2F3F,F(F5F.F/F0F)F.F5F1F)F,F+F/F0\"#XF3F,F6F/F/F(\"$+
\"F)F2F(F4F0F(F4F)F.F/F)F5F'F(F)F;F+F2F.F/F0F)F-F(F(\"$2\"F1F)\"$4#F)
\"$<\"F/F,F(F1F1F)F5F'F(F)\"#qF(FCF(F4F6F,F)F&F4F6FCF(F)\"#nF+F2F2F.F1
F1F.F+F/F)FCF(F;F.FCF(F1F)F5F+F)\"#)*F,F+F;FDF)F.F5\"#j" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "List2:=convert(List1,base, 256,m);
" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&List2G70\"H]Infs9?!f'ywdc\\Y@6m
y%\"HYzGnAjlqq:m['GH'>9pp%\"H_BAn\"f'yCGi*QP%=Y_&[Ga\"GtV)e]I=%[]r(*>H
$[V([W\"*\"Hvv%oI]8X#>43.$*)zUQl`6\"H)e=jRH-VaR\"GO#zX0*f.>&\"HZMk!>*R
m8us2W/S7Rtk1&\"HY:&4=:M%43VjV#>()Q%)fSf\"H'=m<#)*yJgKSDUaLB)o\"or\"\"
H.4&HF@ByVhco3%zv'Qm!>%\"HpmF*)*=@@2p'Riq$[w\"p2U&\"H!*3<peHcXh;XozGcu
NVh\"\"H7m:4M$R$>%H(\\9%eng_Jj9\",$>cx\"4%" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 41 "Now we apply the mapping which send x to " }{XPPEDIT 18 
0 "`mod`(x^e,m);" "6#-%$modG6$)%\"xG%\"eG%\"mG" }{TEXT -1 67 " to each
 number in List2. This can be done using the Maple command " }{TEXT 
264 5 "map. " }{TEXT -1 113 " I will illustrate it before using it. Fi
rst we let f denote any mapping. We let L1 denote the list [1,2,3,4,5]
 ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "L1:=[1,2,3,4,5];" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#L1G7'\"\"\"\"\"#\"\"$\"\"%\"\"&" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L2:=map(f,L1);" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%#L2G7'-%\"fG6#\"\"\"-F'6#\"\"#-F'6#\"\"$-F'6#
\"\"%-F'6#\"\"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "Define f to be
 the function " }{XPPEDIT 18 0 "f(x) = x^2;" "6#/-%\"fG6#%\"xG*$F'\"\"
#" }{TEXT -1 28 " and let's see what happens:" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 10 "f:=x->x^2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
\"fGR6#%\"xG6\"6$%)operatorG%&arrowGF(*$)9$\"\"#\"\"\"F(F(F(" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "L3:=map(f,L1);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%#L3G7'\"\"\"\"\"%\"\"*\"#;\"#D" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 27 "Now we redefine f  so that " }{XPPEDIT 
18 0 "f(x,e,m) = `mod`(x^3,m);" "6#/-%\"fG6%%\"xG%\"eG%\"mG-%$modG6$*$
F'\"\"$F)" }{TEXT -1 67 ".  We use the binary exponentiation method im
plemented by Maple as " }{TEXT 265 17 "Power(x,e) mod m." }{TEXT -1 
104 "  This allows us to implement in Maple the two functions E and D \+
described in the corollary on page 149." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 29 "f:=(x,e,m)->Power(x,e) mod m;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"fGR6%%\"xG%\"eG%\"mG6\"6$%)operatorG%&arrowGF*-%$mo
dG6$-%&PowerG6$9$9%9&F*F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "We
 illustrate that the  functions given by " }{TEXT 268 3 "e,m" }{TEXT 
-1 19 " and that given by " }{TEXT 269 3 "d,m" }{TEXT -1 49 " are inve
rses of each other. Starting with x = 5:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 31 "x:=5;\ny:=f(5,e,m);\nz:=f(y,d,m);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%\"xG\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"yG
\"HGPMg`kMZT=X4U5TrJ\"H[" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"zG\"\"
&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "Now we can apply this to Lis
t2 to obtain the enciphered list of numbers we will send to Alice:" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "cipher_text:=map(f, List2,e
,m);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,cipher_textG70\"HGys_z`3$3N
6Wg%=1Xbmb\"\"H50'RI9w*))GAQgdr$=Bc%*G\"H'4]7:_&[,jF`eY%)zkn8E\"\"HS')
*3mIZ%*)4!*4'G\"[>cb?t#\"HwBI$R$)*eJ+oKqGJ*4>OF9\"GWC[+rtGdV'Qn8;?A(>'
p#\"H(*=w*Gix0geFk)**)Rk(pf#[\"HY4o$4%zw6I8/,\"z=v%QK,#\"H8M@$3Si>\\\"
eZs(f&pgi#HP\"HXle%[e@k'R2\"[:5@YF]MA\"Hy6G>\\!eV\\wj33E#4cx2h$\"H]t%4
q*)*f%=z;[,)fg\"oE$=#\"H;YyF]Lo'eI['e<POb')>&\\\"Hn]=c8bV'ps\\xON+P$)*
)y\\" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 204 "Now Bob sends this to Al
ice and the whole world for that matter. But since only Alice has the \+
secret  private key, only she will be able to decipher the message. We
 show now how she deciphers the message:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 34 "decipher1:=map(f,cipher_text,d,m);" }}{PARA 12 "" 1 "
" {XPPMATH 20 "6#>%*decipher1G70\"H]Infs9?!f'ywdc\\Y@6my%\"HYzGnAjlqq:
m['GH'>9pp%\"H_BAn\"f'yCGi*QP%=Y_&[Ga\"GtV)e]I=%[]r(*>H$[V([W\"*\"Hvv%
oI]8X#>43.$*)zUQl`6\"H)e=jRH-VaR\"GO#zX0*f.>&\"HZMk!>*Rm8us2W/S7Rtk1&
\"HY:&4=:M%43VjV#>()Q%)fSf\"H'=m<#)*yJgKSDUaLB)o\"or\"\"H.4&HF@ByVhco3
%zv'Qm!>%\"HpmF*)*=@@2p'Riq$[w\"p2U&\"H!*3<peHcXh;XozGcuNVh\"\"H7m:4M$
R$>%H(\\9%eng_Jj9\",$>cx\"4%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 41 "decipher2:=convert(decipher1,base,m,256);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%*decipher2G7bx\"#%)\"$/\"\"$,\"\"#K\"$-\"\"$6\"\"$3\"
F,F+\"$>\"\"$0\"\"$5\"\"$.\"F)F.\"$:\"F)F.\"$4\"\"$7\"F+\"$9\"\"$;\"\"
#(*F/F5\"#e\"#8F8\"#$)F+F)F-F'F6F5F)F(\"$?\"F6\"#**F5F,\"$@\"F)F.F1F)F
5F'F.F1F)F/F(F-F)F(F/F5F.F5F<\"#WF)\"#l\"#z\"#wF)F&F.F2F(F)\"#()F6F4F/
F(F4F=F)F-F'F.F;F'F)F.F1F)F.F/F5F(F/F5F)F+F/F)F;F+F2F3F,F(F5F.F/F0F)F.
F5F1F)F,F+F/F0\"#XF3F,F6F/F/F(\"$+\"F)F2F(F4F0F(F4F)F.F/F)F5F'F(F)F;F+
F2F.F/F0F)F-F(F(\"$2\"F1F)\"$4#F)\"$<\"F/F,F(F1F1F)F5F'F(F)\"#qF(FCF(F
4F6F,F)F&F4F6FCF(F)\"#nF+F2F2F.F1F1F.F+F/F)FCF(F;F.FCF(F1F)F5F+F)\"#)*
F,F+F;FDF)F.F5\"#j" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "Finally she
 converts the numbers back to text and sees what message Bob sent her:
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "decipher3:=convert(deci
pher2,bytes);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%*decipher3GQaxThe~f
ollowing~is~important:|.|.So~what~exactly~is~this~new~entity,~AOL~Time
~Warner,~which~is~intent~on~completing~its~long-planned~merger~in~the~
coming~weeks~|\\x~unless~the~Federal~Trade~Commission~decides~to~block
~it?6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT 272 24 "Breaking
 the RSA scheme:" }{TEXT -1 135 "  To decipher the message it is belie
ved that one must be able to find the private key d given only the pub
lic key [m,e]. If one knows " }{XPPEDIT 18 0 "phi(m);" "6#-%$phiG6#%\"
mG" }{TEXT -1 46 " then Maple quickly computes d by the command " }
{TEXT 263 8 "1/e mod " }{XPPEDIT 270 0 "phi(m);" "6#-%$phiG6#%\"mG" }
{TEXT -1 30 ".  It is known that computing " }{XPPEDIT 18 0 "phi(m);" 
"6#-%$phiG6#%\"mG" }{TEXT -1 488 " is the same order of difficulty as \+
factoring m. If m is the product of two 100 digit primes, say, then m \+
is 200 digits long and current factoring algorithms are unable to fact
or such numbers within a reasonable time.  Don't ask Maple to factor s
uch a number for you unless you want to wait a long time -- years or c
enturies, depending on the size of the number and luck. Factoring algo
rithms always depend on luck. After all one might guess the factors. B
ut this would be very unlikely. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}
{PARA 0 "" 0 "" {TEXT -1 6 "It is " }{TEXT 273 8 "believed" }{TEXT -1 
183 " but not proved that breaking the  RSA scheme is equivalent to fa
ctoring the modulus m. The best algorithm known at present for factori
ng such large, difficult numbers, is called the " }{TEXT 277 38 "Numbe
r Field Sieve Factoring Algorithm" }{TEXT -1 419 ". The record it has \+
achieved is the factorization of a number of 140 decimal digits, which
 took several months on a rather large network of workstations, follow
ed by several days of labor on a super-computer. Numbers as large as 2
00 decimal digits now seems to be out of reach of current theory and t
echnology. For even better security one may of course increase the siz
e of the initial primes and hence the size of m. " }}{PARA 0 "" 0 "" 
{TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 247 "There are many sources o
f information on the RSA scheme. It is important not only for sending \+
data securely but also can be used to \"sign\" electronically submitte
d documents. For more information see for example any of the many book
s available on " }{TEXT 278 14 "cryptography. " }{TEXT -1 150 " Just s
earch on this key word using Web Luis or on your favorite search engin
e. There is now a company that controls the use of the RSA scheme call
ed " }{TEXT 279 21 "RSA Data Security Inc" }{TEXT -1 25 ". whose websi
te's URL is " }{TEXT 280 29 "http://www.rsasecurity.com/. " }{TEXT -1 
90 "Both Netscape and Internet Explorer contain security software from
 RSA Data Security Inc. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "
" 0 "" {TEXT 274 15 "RSA Exercise 1." }{TEXT -1 98 "  Alice sent a mes
sage to Bob using the RSA scheme. The public key used to encode the me
ssage was " }}{PARA 0 "" 0 "" {TEXT -1 22 "                      " }}
{PARA 0 "" 0 "" {TEXT -1 44 "               [m,e] = [2885500349, 37813
]. " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 26 "Th
e enciphered message was" }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{PARA 0 "
" 0 "" {TEXT -1 185 "             [563138230, 1266232333, 8056785, 221
2264067, 2797153755].\n\nDecipher this message. [In this case it is po
ssible since m is easy to factor using Maple's ifactor procedure.]\n\n
" }{TEXT 275 15 "RSA Exercise 2." }{TEXT -1 340 "  Find, using Maple, \+
a triple [m,e,d] where m is the product of two 100 decimal digit prime
s, e is a random number of 100 decimal digits and d is the inverse of \+
e modulo d. Use this to encipher some message of your choice of at lea
st three lines length using the RSA scheme. Then decipher the encipher
ed text to obtain the original message." }}{PARA 0 "" 0 "" {TEXT -1 0 
"" }}}}{MARK "38 9 0" 19 }{VIEWOPTS 0 0 0 1 1 1803 1 1 1 1 }
{PAGENUMBERS 1 0 2 33 152 1 }