{VERSION 2 3 "IBM INTEL NT" "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 "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 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 "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 1 0 0 0 0 0 0 0 2 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Warni ng" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 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 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "restart; with(numthe ory):" }}{PARA 7 "" 1 "" {TEXT -1 33 "Warning, new definition for orde r" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 164 "Fun notebook to demonstrate a simple exponential private key cipher. Go to bottom, define subrou tines \"euclidsolve\" and \"powmod\" first, then begin execution below :" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "First step: choose a large \+ prime p:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "p := nextprime(89284029 4); \n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"*,.%G*)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 105 "Choose an encryption key \"encryptkey\" \+ which is relatively prime to phi(p) = p-1. I'll just pick a prime." } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "encryptkey := nextprime(23289);\ng cd(encryptkey, p-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+encryptkeyG \"&\"HB" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 73 "Here we compute the deciphering key, by solving en cryptkey*x = 1 mod p-1:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 " decryptkey := euclidsolve(encryptkey, p-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+decryptkeyG\"*6L&zb" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 95 "A quick check to make sure we really have a solution to e ncryptkey*decryptkey = 1 mod (phi(n)):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "decryptkey*encryptkey mod (p-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "Now let's convert a text string into ascii integers, one letter at a time." }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 52 "message := convert(`number theory is fun`, ' bytes');" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(messageG76\"$5\"\"$<\" \"$4\"\"#)*\"$,\"\"$9\"\"#K\"$;\"\"$/\"F*\"$6\"F+\"$@\"F,\"$0\"\"$:\"F ,\"$-\"F'F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "Encrypt the messag e:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "encryptmess := [seq(powmod(me ssage[k], encryptkey, p), k=1..nops(message))];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%,encryptmessG76\")aQr&)\"*^&>(*z\"*_3')e)\"*Pr<[%\"* \"o\")3*)\"*AZ\"Hg\"*&[4zB\"*>N6$z\"*?%*f<%F*\"*%>E7sF+\"*gK9-'F,\"*-a ;h)\"*W=q&fF,\"*aNFf(F'F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "Decr rypt the message:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 112 "origmess := [ seq(powmod(encryptmess[k], decryptkey, p), k=1..nops(encryptmess))];\n writebytes(default, origmess):" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)o rigmessG76\"$5\"\"$<\"\"$4\"\"#)*\"$,\"\"$9\"\"#K\"$;\"\"$/\"F*\"$6\"F +\"$@\"F,\"$0\"\"$:\"F,\"$-\"F'F&" }}{PARA 6 "" 1 "" {TEXT -1 20 "numb er theory is fun" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 320 "This is the only \"hard\" part: C ompute the decryption key \"decryptkey\", by solving ex = 1 mod(p-1). \+ This can be done by running Euclid's Algorithm; it's not the most eff icient way, but it works. Here's a procedure into which one feeds inte gers a and b and receives on output the smallest positive solution to \+ ax=1 mod b." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 187 "euclidsolve := proc(a, b)\n\nlocal m,nn,q,r,i,k,s,t,s1,t1,decryptkey;\nm := array (1..500): nn := array(1..500): \nq := array(1..500): r := array(1..500 ):\n\nnn[1] := max(a,b): m[1] := min(a,b):" }}{PARA 0 "" 0 "" {TEXT -1 20 "Euclidean Algorithm." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 149 "for i from 1 to 100 do\n q[i] := floor(nn[i]/m[i]):\n r[i] := nn[i] - q [i]*m[i]:\n if r[i] = 0 then break; fi:\n nn[i+1] := m[i]: m[i+1] := r[i]:\nod:" }}{PARA 0 "" 0 "" {TEXT -1 78 "Compute the magic s and t \+ in t*m[1] + s*nn[1] = 1 by chasing Euclid backward." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 103 "s := 1: t := -q[i-1]:\nfor k from i-2 to 1 by - 1 do\n s1 := t; t1 := s-q[k]*t;\n s := s1; t := t1;\nod:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "if a < b then decryptkey := t else decryp tkey := s; fi:" }}{PARA 0 "" 0 "" {TEXT -1 71 "Make sure decryption ke y is positive---if not, add multiples of phi(n)." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "if decryptkey < 0 then decryptkey := decryptkey - flo or(decryptkey/b)*b; fi:\ndecryptkey;\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 82 "Define the powmod function for fast powers: Compute b^a \+ mod m using power method." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 166 "powmo d := proc(b,a,m)\nlocal n,p,pp:\nn := a: p := 1: pp := b:\nwhile n>0 d o\n if n mod 2 = 1 then p := p*pp mod m fi;\n pp := pp^2 mod m:\n n := floor(n/2);\nod:\np;\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "12 7 0" 88 }{VIEWOPTS 1 1 0 1 1 1803 }