{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 "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 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 8 
2 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 "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 }{PSTYLE "Author" -1 19 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 8 8 1 0 1 0 2 2 0 1 }{PSTYLE "Headi
ng 3" -1 256 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 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 21 "Pseudo random strings" }}
{PARA 19 "" 0 "" {TEXT -1 36 "\251Mike May, S.J., 2002, maymk@slu.edu
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 4 "" 
0 "" {TEXT -1 13 "Preliminaries" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
344 "The book talks of using a pseudo random string as a means of encr
yption.  To be able to to use this technique we first need some prelim
inaries.  In particular we need procedures for XOR on a pair of bits. \+
 That procedure is used to XOR bytes.  The procedure parses or reads a
 0 or 1 string as a number, add mod 2, then convert back to a string.
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 180 "bitXOR := (bit1,bit2) \+
-> convert(((parse(bit1)+parse(bit2)) mod 2),string):\nbyteXOR := (byt
e1,byte2) -> \n          cat(seq(bitXOR(substring(byte1,i), substring(
byte2,i)), i=1..8)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "byt
eXOR(\"01001101\", \"01100110\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q
)001010116\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 403 "We also want a n
umber of procedures to convert between data types.  The messages will \+
start out as ASCII characters.  To use an XOR procedure we will want e
ach character to be represented as a byte string composed of eight bit
s, with leading zeroes printed.  To store ciphertext we will want to u
se two character hex strings.  Thus we need procedures to go from char
acter to binary string to hex string." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 164 "charToBinByte := proc(character)\n   local binChar:
\n   binChar := convert(op(convert(character, bytes))+256,binary):\n  \+
 substring(convert(binChar,string),2..9):\nend:" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 106 "binToHexByte := binString ->\n   substring(co
nvert(convert(parse(binString),decimal,binary)+256,hex),2..3):" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "s1 := charToBinByte(\"\\n\")
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s1GQ)000010106\"" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "h1 := binToHexByte(s1);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%#h1G%#0AG" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 40 "We also want procedures to convert back." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "hexToBinByte := hexString ->\n   s
ubstring(convert(convert(convert(hexString, decimal,hex)+256,binary),
\n       string),2..9):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "
binByteToChar := binString -> \n        convert([convert(binString,dec
imal,binary)],bytes):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "s2
 := hexToBinByte(h1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s2GQ)00001
0106\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "binByteToChar(s2)
;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#Q\"|+6\"" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 133 "We also need routines from the conversion worksheet t
hat can arrange the hex strings into words and break the words back in
to pieces." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 417 "blocker := p
roc(hexvec,bsize)\nlocal numCharacters, paddingNum, numWords, i, j, te
mp, hexblock;\ntemp := hexvec;\nnumCharacters :=linalg[vectdim](hexvec
);\nnumWords := ceil(numCharacters/bsize);\npaddingNum := numWords*bsi
ze - numCharacters;\ntemp := [op(temp),seq(\"00\",j = 1..paddingNum)];
\nhexblock := array(1..numWords, \n   [seq( cat(seq(temp[bsize*i + j],
 j = 1..bsize)), i=0..numWords-1)]):\nconvert(hexblock,list):\nend:" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 121 "unblocker := (hexblock,bs
ize) ->\n   map(hexString -> seq(substring(hexString,2*j-1..2*j), j = \+
1..bsize),\n      hexblock):" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 25 
"Setting up Blum-Blum-Shub" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 241 "To \+
set up the Blum-Blum-Shub method of producing a pseudorandom string, w
e first need to produce a pair of primes.  We want primes congruent to
 3 mod 4.  Since we want to harvest 4 bits at each step we would like \+
the primes to be about 1000." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 177 "p := nextprime(rand(1000..10000)());\nwhile ((p mod 4) = 1) do \+
p := nextprime(p) od;\nq := nextprime(rand(1000..10000)());\nwhile ((q
 mod 4) = 1) do q := nextprime(q) od;\nn := p*q;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"pG\"%(G#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG
\"%x7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"qG\"%z7" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#>%\"nG\"(t]#H" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
49 "To make this more predictable we can fix p and q." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "p := 5323;\nq := 7411;\nn := p*q;" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"pG\"%B`" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%\"qG\"%6u" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"nG\"
)`([%R" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 63 "Next we need a seed.  T
he seed should be relatively prime to n." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 57 "x0:= rand(n)();\nwhile (igcd(x0,n)>1) do x:= rand(n)(
) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G\")n]VM" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 106 "Once again, we then fix the seed so that
 we can get the same result on repeated runnings of the worksheet." }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "x0 := 8288583;" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%#x0G\"($e)G)" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 141 "Now we produce a procedure that takes a key, runs two ro
unds of the procedure to produce a key byte and a new seed to use in t
he next round.." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 254 "nextKey
Byte := proc(modulus, key)\n   local stream, x1, x2:\n   x1 := Power(k
ey,2) mod modulus:\n   stream := convert(x1 mod 16, hex):\n   x2 := Po
wer(x1, 2) mod modulus:\n   stream := cat(stream, convert(x2 mod 16, h
ex)): \n   [x2, hexToBinByte(stream)];\nend:" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 29 "oneStep := nextKeyByte(n,x0);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%(oneStepG7$\")nfBGQ)011011116\"" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 37 "oneStep := nextKeyByte(n,oneStep[1]);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(oneStepG7$\"(5eG$Q)011000106\"" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "This lets us produce a string of b
ytes to use as a key." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 108 "x
1 := x0:\nfor i from 1 to 20 do\nnextStep := nextKeyByte(n,x1):\nx1 :=
 nextStep[1]:\nprint(i, nextStep[2]);\nod:" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6$\"\"\"Q)011011116\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$
\"\"#Q)011000106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"$Q)111100106
\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"%Q)110011006\"" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6$\"\"&Q)011011016\"" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6$\"\"'Q)111100016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"(Q)101
001006\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\")Q)001110016\"" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6$\"\"*Q)111111016\"" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6$\"#5Q)010110106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$
\"#6Q)110010106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#7Q)001011116\"
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#8Q)011011116\"" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6$\"#9Q)110111116\"" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6$\"#:Q)001111006\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#;Q)01010100
6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#<Q)110010016\"" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6$\"#=Q)110110116\"" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6$\"#>Q)111110106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$\"#?Q)10011
1106\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 
{PARA 4 "" 0 "" {TEXT -1 34 "Encryption and Decryption with BBS" }}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 83 "We are ready to use this to encode
 a message.  First we create a message to encode:" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 141 "mess1 := \"AZaz Good morning Mr. Phelps.  Y
our job today, should you choose\nto accept it, is to learn to use Blu
m-Blum-Shub encryption. AZaz\";" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&
mess1GQ\\sAZaz~Good~morning~Mr.~Phelps.~~Your~job~today,~should~you~ch
oose|+to~accept~it,~is~to~learn~to~use~Blum-Blum-Shub~encryption.~AZaz
6\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "messlength := length
(mess1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+messlengthG\"$H\"" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 107 "We encrypt the message and write \+
the code as words of 8 hex characters corresponding to 4 ASCII charact
ers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 261 "x1 := x0:\ncipher1
 := []:\nfor i from 1 to messlength do\n  oneStep := nextKeyByte(n,x1)
:\n  oneByte := byteXOR(oneStep[2], charToBinByte(substring(mess1,i)))
:\n  hexByte := binToHexByte(oneByte):\n  x1 := oneStep[1]:\n  cipher1
 := [op(cipher1), hexByte]:\nod:\ncipher1;" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#7]s%#2EG%#38G%#93G%#B6G%#4DGF'%#CBG%#56G%#99G%#7AG%#A7G
%#40G%#1DG%#B1G%#55G%#3AG%#AEG%#FBG%#B7G%#ECG%#48G%#92G%#A8G%#B8G%#C9G
%#F4G%#EDG%#BFGF)%#6BG%#61G%#86G%#08G%#BEGF=%#00G%#D9G%#A1G%#69G%#5FG%
#D5G%#44G%#91G%#63G%#4BG%#FAG%#97GFN%#67G%#2FG%#CFG%#98GFJ%#29G%#59GFN
%#80G%#BAGF+FBF(%#F7G%#81G%#EFG%#25G%#13G%#28G%#94GFI%#96G%#5BG%#0AG%#
3CGFH%#42G%#D7G%#A2GFfn%#F9G%#AAG%#E4G%#6FG%#30GF?FfnF>FYFjnFJFao%#70G
%#C3G%#09G%#4CGF0%#21G%#06G%#8AG%#32G%#50GFP%#90GFjo%#E0GF]pFR%#3BGFgn
%#F2G%#77GF`p%#20GF(%#89G%#16G%#74GF-Fho%#E1GFfp%#E5G%#F0G%#43G%#6CG%#
F3G%#E3G%#B2GFZ%#1BG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "cod
e := blocker(cipher1,4);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%codeG7C
%)2E3893B6G%)4DB6CB56G%)997AA740G%)1DB1553AG%)AEFBB7ECG%)4892A8B8G%)C9
F4EDBFG%)CB6B6186G%)08BEED00G%)D9A1695FG%)D5449163G%)4BFA97FAG%)672FCF
98G%)442959FAG%)80BA9908G%)4DF781EFG%)25132894G%)D5965B0AG%)3C5F42D7G%
)A213F9AAG%)E46F306BG%)13BF815BG%)44AA70C3G%)094CB121G%)068A3250G%)679
006E0G%)50CF3B28G%)F2773B20G%)4D891674G%)A74CE174G%)E5F0436CG%)F3E3B2E
FG%)1B000000G" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 34 "To decrypt we re
verse the process." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "ciphe
r2 := unblocker(code,4);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(cipher2
G7`s%#2EG%#38G%#93G%#B6G%#4DGF)%#CBG%#56G%#99G%#7AG%#A7G%#40G%#1DG%#B1
G%#55G%#3AG%#AEG%#FBG%#B7G%#ECG%#48G%#92G%#A8G%#B8G%#C9G%#F4G%#EDG%#BF
GF+%#6BG%#61G%#86G%#08G%#BEGF?%#00G%#D9G%#A1G%#69G%#5FG%#D5G%#44G%#91G
%#63G%#4BG%#FAG%#97GFP%#67G%#2FG%#CFG%#98GFL%#29G%#59GFP%#80G%#BAGF-FD
F*%#F7G%#81G%#EFG%#25G%#13G%#28G%#94GFK%#96G%#5BG%#0AG%#3CGFJ%#42G%#D7
G%#A2GFhn%#F9G%#AAG%#E4G%#6FG%#30GFAFhnF@FenF\\oFLFco%#70G%#C3G%#09G%#
4CGF2%#21G%#06G%#8AG%#32G%#50GFR%#90GF\\p%#E0GF_pFT%#3BGFin%#F2G%#77GF
bp%#20GF*%#89G%#16G%#74GF/Fjo%#E1GFhp%#E5G%#F0G%#43G%#6CG%#F3G%#E3G%#B
2GFfn%#1BGFFFFFF" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 261 "x1 := \+
x0:\ndecipher1 := []:\nfor i from 1 to messlength do\n  oneStep := nex
tKeyByte(n,x1):\n  oneByte := byteXOR(oneStep[2], hexToBinByte(cipher2
[i])):\n  oneChar := binByteToChar(oneByte):\n  x1 := oneStep[1]:\n  d
ecipher1 := [op(decipher1), oneChar]:\nod:\ndecipher1;" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#7]sQ\"A6\"Q\"ZF%Q\"aF%Q\"zF%Q\"~F%Q\"GF%Q\"oF%F+Q
\"dF%F)Q\"mF%F+Q\"rF%Q\"nF%Q\"iF%F/Q\"gF%F)Q\"MF%F.Q\".F%F)Q\"PF%Q\"hF
%Q\"eF%Q\"lF%Q\"pF%Q\"sF%F3F)F)Q\"YF%F+Q\"uF%F.F)Q\"jF%F+Q\"bF%F)Q\"tF
%F+F,F'Q\"yF%Q\",F%F)F9F5F+F;F7F,F)F?F+F;F)Q\"cF%F5F+F+F9F6Q\"|+F%F>F+
F)F'FAFAF6F8F>F)F0F>F@F)F0F9F)F>F+F)F7F6F'F.F/F)F>F+F)F;F9F6F)Q\"BF%F7
F;F-Q\"-F%FCF7F;F-FDQ\"SF%F5F;F=F)F6F/FAF.F?F8F>F0F+F/F3F)F$F&F'F(" }}
}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "cat(op(decipher1));" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#Q\\sAZaz~Good~morning~Mr.~Phelps.~~You
r~job~today,~should~you~choose|+to~accept~it,~is~to~learn~to~use~Blum-
Blum-Shub~encryption.~AZaz6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 274 
"Since we would like to be able to do this with arbitrary messages, we
 produce procedures for encryption and decryption.  The encryption pro
cedure should take a message, a modulus (the n value), an initial key \+
(the x0 value) and the number of ASCII characters in a code word." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 484 "BBSEncrypter := proc(messag
e, modulus, key1, blocksize)\n   local messlength, x1, cipher1, oneSte
p, oneByte, hexByte, i:\n   messlength := length(message);\n   x1 := k
ey1:\n   cipher1 := []:\n   for i from 1 to messlength do\n      oneSt
ep := nextKeyByte(modulus,x1):\n      oneByte := byteXOR(oneStep[2], c
harToBinByte(substring(message,i))):\n      hexByte := binToHexByte(on
eByte):\n      x1 := oneStep[1]:\n      cipher1 := [op(cipher1), hexBy
te]:\n   od:\n   blocker(cipher1,blocksize);\nend:" }}}{EXCHG {PARA 0 
"> " 0 "" {MPLTEXT 1 0 41 "cipherText := BBSEncrypter(mess1,n,x0,4);" 
}}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%+cipherTextG7C%)2E3893B6G%)4DB6CB5
6G%)997AA740G%)1DB1553AG%)AEFBB7ECG%)4892A8B8G%)C9F4EDBFG%)CB6B6186G%)
08BEED00G%)D9A1695FG%)D5449163G%)4BFA97FAG%)672FCF98G%)442959FAG%)80BA
9908G%)4DF781EFG%)25132894G%)D5965B0AG%)3C5F42D7G%)A213F9AAG%)E46F306B
G%)13BF815BG%)44AA70C3G%)094CB121G%)068A3250G%)679006E0G%)50CF3B28G%)F
2773B20G%)4D891674G%)A74CE174G%)E5F0436CG%)F3E3B2EFG%)1B000000G" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 99 "The decryption routine needs the s
ame set of information with the plaintext replaced by ciphertext." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 541 "BBSDecrypter := proc(codeTe
xt, modulus, key1, blocksize)\n   local cipher2, messlength, x1, oneSt
ep, oneByte, oneChar, decipher1, i;\n   cipher2 := unblocker(codeText,
blocksize):\n   messlength := nops(cipher2):\n   x1 := key1:\n   decip
her1 := []:\n   for i from 1 to messlength do\n      oneStep := nextKe
yByte(modulus,x1):\n      oneByte := byteXOR(oneStep[2], hexToBinByte(
cipher2[i])):\n      oneChar := binByteToChar(oneByte):\n      x1 := o
neStep[1]:\n      decipher1 := [op(decipher1), oneChar]:\n   od:\n   d
ecipher1;\n   cat(op(decipher1));\nend:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 32 "BBSDecrypter(cipherText,n,x0,4);" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#Q_sAZaz~Good~morning~Mr.~Phelps.~~Your~job~today,~shoul
d~you~choose|+to~accept~it,~is~to~learn~to~use~Blum-Blum-Shub~encrypti
on.~AZaz|dxH|dy6\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 142 "Note that \+
the extra characters correspond to filling out the last code word with
 spaces.  This is one reason to have an end of message string." }}}
{SECT 0 {PARA 256 "" 0 "" {TEXT -1 9 "Exercise:" }}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 177 "1) Use BBS to encrypt a message and post it to the \+
bulletin board.  You need to post the encrypted message, the modulus, \+
and the initial key.  Respond to someone else's message." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" 
{TEXT -1 37 "Using Linear Feedback Shift Registers" }}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 143 "To set up a linear feedback shift register we sta
rt with the polynomial that corresponds to a recurrence relation defin
ing the linear feedback." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 
"p1 := x^8 + x^4 +x^3 + x^2 + 1:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
193 "We can turn it into a matrix that works on a block of bits, shift
ing then up one place and using the linear feedback for the last bit. \+
 To do that we want the transpose of the companion matrix." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "m1 := linalg[transpose](linalg[comp
anion](p1,x));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#m1G-%'matrixG6#7*
7*\"\"!\"\"\"F*F*F*F*F*F*7*F*F*F+F*F*F*F*F*7*F*F*F*F+F*F*F*F*7*F*F*F*F
*F+F*F*F*7*F*F*F*F*F*F+F*F*7*F*F*F*F*F*F*F+F*7*F*F*F*F*F*F*F*F+7*!\"\"
F*F3F3F3F*F*F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "If we now take
 the nth power of the matrix we have one that replaces a byte of bits \+
with the next byte." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "shif
tMat := map(modp, evalm(m1^8),2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>
%)shiftMatG-%'matrixG6#7*7*\"\"\"\"\"!F*F*F*F+F+F+7*F+F*F+F*F*F*F+F+7*
F+F+F*F+F*F*F*F+7*F+F+F+F*F+F*F*F*7*F*F+F*F*F+F+F*F*7*F*F*F*F+F+F+F+F*
7*F*F*F+F+F*F+F+F+7*F+F*F*F+F+F*F+F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 101 "If we start with 8 bits of the key string, we get the next 8 b
its by multiplying by the matrix mod 2." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 82 "keyVect := vector([1,1,0,1,0,1,1,0]);\nv2 := map(modp
, evalm(shiftMat&*keyVect),2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(k
eyVectG-%'vectorG6#7*\"\"\"F)\"\"!F)F*F)F)F*" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"!\"\"\"F)F*F*F)F)F)" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 45 "We want a procedure to do this automatica
lly." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "shiftWord := (mat, \+
vect) -> map(modp, evalm(mat&*vect),2);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%*shiftWordGf*6$%$matG%%vectG6\"6$%)operatorG%&arrowGF)-%$mapG6
%%%modpG-%&evalmG6#-%#&*G6$9$9%\"\"#F)F)F)" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 87 "This lets us produce a bit string that would continue for
 255*8 bits without repeating." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 71 "v2 := keyVect;\nfor i from 1 to 10 do\nv2 := shiftWord(shiftMa
t, v2);\nod;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G%(keyVectG" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"!\"\"\"F)F*F*F
)F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"!\"\"
\"F*F*F*F*F)F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vectorG6#7*
\"\"\"\"\"!F)F)F)F)F*F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'ve
ctorG6#7*\"\"!\"\"\"F*F*F)F*F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
#v2G-%'vectorG6#7*\"\"!\"\"\"F)F)F)F)F*F*" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"!\"\"\"F*F)F)F)F*F*" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"\"F)\"\"!F*F)F)F)F*
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"!\"\"\"F*F
)F)F)F*F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vectorG6#7*\"\"
\"F)\"\"!F)F*F*F)F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#v2G-%'vector
G6#7*\"\"!F)\"\"\"F)F*F)F)F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 126 "
We also want procedures to convert between a vector of bits and the st
ring formed by concatenating the elements of the vector." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 158 "binByteToVector := binByte -> \n  \+
  vector([seq(parse(substring(binByte,i)), i=1..8)]);\nvectorToBinByte
 := vect ->\n    cat(seq(convert(v1[i],string), i=1..8));" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%0binByteToVectorGf*6#%(binByteG6\"6$%)operato
rG%&arrowGF(-%'vectorG6#7#-%$seqG6$-%&parseG6#-%*substringG6$9$%\"iG/F
:;\"\"\"\"\")F(F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%0vectorToBinB
yteGf*6#%%vectG6\"6$%)operatorG%&arrowGF(-%$catG6#-%$seqG6$-%(convertG
6$&%#v1G6#%\"iG%'stringG/F8;\"\"\"\"\")F(F(F(" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 91 "We are ready to use this stream to encrypt a message. \+
 Let's repeat the message from above." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 35 "mess1;\nmesslength := length(mess1);" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#Q\\sAZaz~Good~morning~Mr.~Phelps.~~Your~job~today,
~should~you~choose|+to~accept~it,~is~to~learn~to~use~Blum-Blum-Shub~en
cryption.~AZaz6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+messlengthG\"$
H\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 304 "v1:= keyVect:\nciph
er1 := []:\nfor i from 1 to messlength do\n  oneStep := vectorToBinByt
e(v1):\n  oneByte := byteXOR(oneStep, charToBinByte(substring(mess1,i)
)):\n  hexByte := binToHexByte(oneByte):\n  v1 := shiftWord(shiftMat,v
1):\n  cipher1 := [op(cipher1), hexByte]:\nod:\ncipher1;\ncode := bloc
ker(cipher1,4);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7]s%#97G%#02G%#1CG%
#C7G%#54G%#04G%#0CG%#A1G%#06G%#F2G%#44G%#3CG%#C9G%#53G%#93G%#08G%#C4G%
#27G%#18G%#80G%#AAG%#DFG%#5BG%#AEG%#E5G%#E2G%#55G%#B3G%#E7G%#17G%#00G%
#F4G%#C3G%#C5G%#89G%#5AG%#82G%#E9G%#A5G%#BCG%#B1G%#CBG%#36G%#C6G%#0FG%
#57G%#D4G%#BEG%#2EG%#61G%#DEGFF%#6DGFV%#6EGF=%#74GF/%#28GFI%#FDG%#01G%
#32G%#3EGF1%#15G%#99G%#D5G%#B0GFX%#ECG%#5CG%#FBGF/%#85GF5%#98G%#DBGF0%
#F3G%#FFG%#3DG%#23GFJ%#33G%#90G%#4AG%#7BG%#70G%#56G%#B7G%#77G%#4BG%#FC
G%#F7GFE%#D7G%#E3G%#AFG%#87GFbp%#76GFgo%#31G%#7AG%#E4GF5F\\o%#8AGFep%#
A6GFQ%#38G%#5FG%#C1GFapF>%#81GFT%#40GFW%#1EGF`qFZ%#69G%#F8GF]qF*%#1FG
" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%codeG7C%)97021CC7G%)54040CA1G%)
06F2443CG%)C9539308G%)C4271880G%)AADF5BAEG%)E5E255B3G%)E71700F4G%)C3C5
895AG%)82E9A5BCG%)B1CB36C6G%)0F57D4BEG%)2E61DE89G%)6DDE6EE2G%)743C28E9
G%)FD01323EG%)531599D5G%)B06EEC5CG%)FB3C8527G%)98DBC9F3G%)FF3D23A5G%)3
3904A7BG%)7056B777G%)4BFCF7C5G%)D7E3AF87G%)D7763331G%)7AE427B0G%)8A87A
657G%)385FC1F7G%)55812E40G%)6D1E4028G%)69F85F0CG%)1F000000G" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 49 "Decryption reverses the process wi
th the same key" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 327 "cipher2
 := unblocker(code,4);\nv1 := keyVect:\ndecipher1 := []:\nfor i from 1
 to messlength do\n  oneStep := vectorToBinByte(v1):\n  oneByte := byt
eXOR(oneStep, hexToBinByte(cipher2[i])):\n  oneChar := binByteToChar(o
neByte):\n  v1 := shiftWord(shiftMat,v1):\n  decipher1 := [op(decipher
1), oneChar]:\nod:\ndecipher1:\ncat(op(decipher1));" }}{PARA 12 "" 1 "
" {XPPMATH 20 "6#>%(cipher2G7`s%#97G%#02G%#1CG%#C7G%#54G%#04G%#0CG%#A1
G%#06G%#F2G%#44G%#3CG%#C9G%#53G%#93G%#08G%#C4G%#27G%#18G%#80G%#AAG%#DF
G%#5BG%#AEG%#E5G%#E2G%#55G%#B3G%#E7G%#17G%#00G%#F4G%#C3G%#C5G%#89G%#5A
G%#82G%#E9G%#A5G%#BCG%#B1G%#CBG%#36G%#C6G%#0FG%#57G%#D4G%#BEG%#2EG%#61
G%#DEGFH%#6DGFX%#6EGF?%#74GF1%#28GFK%#FDG%#01G%#32G%#3EGF3%#15G%#99G%#
D5G%#B0GFZ%#ECG%#5CG%#FBGF1%#85GF7%#98G%#DBGF2%#F3G%#FFG%#3DG%#23GFL%#
33G%#90G%#4AG%#7BG%#70G%#56G%#B7G%#77G%#4BG%#FCG%#F7GFG%#D7G%#E3G%#AFG
%#87GFdp%#76GFio%#31G%#7AG%#E4GF7F^o%#8AGFgp%#A6GFS%#38G%#5FG%#C1GFcpF
@%#81GFV%#40GFY%#1EGFbqFfn%#69G%#F8GF_qF,%#1FGFDFDFD" }}{PARA 12 "" 1 
"" {XPPMATH 20 "6#Q\\sAZaz~Good~morning~Mr.~Phelps.~~Your~job~today,~s
hould~you~choose|+to~accept~it,~is~to~learn~to~use~Blum-Blum-Shub~encr
yption.~AZaz6\"" }}}{SECT 0 {PARA 256 "" 0 "" {TEXT -1 9 "Exercise:" }
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 181 "2) Use LFSR to encrypt a message
 and post it to the bulletin board.  You need to post the encrypted me
ssage, the polynomial, and the initial key.  Respond to someone else's
 message." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "1 0 0" 0 }{VIEWOPTS 1 
1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }