{VERSION 2 3 "SUN SPARC SOLARIS" "2.3" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 }{CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }
{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" 
-1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 
0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 
0 0 0 0 0 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 0 256 1 {CSTYLE "
" -1 -1 "times" 1 18 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 
0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 256 "" 0 "" {TEXT -1 0 "" }{TEXT 257 33 "Fiat Sha
mir Protocol Calculations" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 30 "Gene
rate a random 12 digit num" }{TEXT 256 0 "" }{TEXT -1 3 "ber" }{TEXT 
-1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "rand();" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 87 "Generate the next prime after the product of th
ree  randomly generated 12 digit numbers" }{TEXT -1 0 "" }}{PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 37 "p:=nextprime( rand()*rand()*rand() );" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Generate another one" }{TEXT -1 0 
"" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "q:=nextprime( rand()*rand()*ra
nd() );" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Form the product " }
{TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "n:=p*q;" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 21 "Number of digits of n" }{TEXT -1 0 "" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "evalf( log(n)/log(10) );" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "Factoring 24 digit numbers in Mapl
e is not hard" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "m1:=nextprime(rand
());\nm2:=nextprime(rand());\nm:=m1*m2;" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "ifactor(m);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" 
}{TEXT 258 22 "Don't do this command!" }}{PARA 0 "" 0 "" {TEXT -1 72 "
If you try to factor n, though, you will wait a very long time in Mapl
e." }{TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "ifactor(n);" }
}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "The hidden key is a random numbe
r modulo n" }{TEXT -1 0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "s:=ran
d()&^10 mod n;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 61 "It's very likel
y, but check that s and n are relatively prime" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 10 "igcd(s,n);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "Th
e public key consists of n and v=s^2 mod n" }{TEXT -1 0 "" }}{PARA 0 "
> " 0 "" {MPLTEXT 1 0 17 "v:= s &^ 2 mod n;" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 28 "save p,q,n,s,v,`secret.mpl`;" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 61 "Fiat-Shamir Protocol:\n   First we need a random b
it generator" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "randombit:=rand(0..
1):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Check it out:" }{TEXT -1 
0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "for i to 5 do randombit()  o
d;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 40 "Now we need our random numb
er generator:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "msg:=rand(n):" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "Try it out:" }{TEXT -1 0 "" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "msg();" }}}{SECT 0 {PARA 3 "" 0 "" 
{TEXT -1 25 "The actual protocol cycle" }}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 80 "Our first inquiry, after the computer has been notified t
hat user with key (n,v)" }}{PARA 0 "" 0 "" {TEXT -1 20 "     wants to \+
log on" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "r:=msg() mod n;" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 11 "We send r^2" }{TEXT -1 0 "" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "x:= r &^ 2 mod n;" }}}{EXCHG {PARA 
0 "" 0 "" {TEXT -1 35 "The computer randomly selects a bit" }{TEXT -1 
0 "" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "b:=randombit();" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 60 "If 0 the computer asks for r, and checks \+
that r^2 matches v." }}{PARA 0 "" 0 "" {TEXT -1 65 "If 1 the computer \+
asks for rs, and checks that (rs)^2 matches x*v" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 132 "if b=0 then\n       y:= r mod n;\n       y &^ 2 mod \+
n;\n       x;\nelse\n       y:= r*s mod n;\n       y &^ 2 mod n;\n    \+
   x*v mod n;\nfi;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Now repeat the cycle" }}}}}{MARK "
1 1 0" 7 }{VIEWOPTS 1 1 0 1 1 1803 }