{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 }
{CSTYLE "" -1 256 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 0 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 
0 0 2 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 2 0 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 2 0 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 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 "Heading 3" -1 5 1 {CSTYLE "" -1 -1 "Times
" 1 12 0 0 0 1 1 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 "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 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 12 "Baby DES - 1" }}{PARA 19 
"" 0 "" {TEXT -1 37 "\251Mike May, S.J., 2002,  maymk@slu.edu" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 157 "To understand how to do DES, our book (by Trappe \+
and Washington) uses a simplified DES-like system.  For ease of termin
ology we will refer to it as Baby DES." }}{PARA 0 "" 0 "" {TEXT -1 
243 "We would like a worksheet that computes Baby DES for us.  We firs
t walk through the procedure step by step before creating a procedure \+
to do the encryption in a single step.\nBaby DES uses a message string
 of 12 bits and a key string of 9 bits." }}}{SECT 0 {PARA 4 "" 0 "" 
{TEXT -1 0 "" }{TEXT 256 26 "Baby DES done step by step" }}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 163 "The first approach is to walk through th
e procedure step by step.  You should check all the computations here \+
by hand to be sure you understand what is being done." }}{PARA 0 "" 0 
"" {TEXT -1 109 "We start with a sample message and key.\nBaby DES use
s a message string of 12 bits and a key string of 9 bits." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 100 "keyString := \"110110001\";\nmessa
geString := \"101101111001\";\nlength(keyString);\nlength(messageStrin
g);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*keyStringGQ*1101100016\"" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%.messageStringGQ-1011011110016\"" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#\"#7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 168 "We want a function to
 make round keys.  The round key for the ith round starts with the ith
 bit of the key string and continues for 8 bits wrapping around if nec
essary." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 160 "roundKeyMaker :
= proc(keystring, i)\n   local startBit:\n   startBit := ((i-1) mod 9)
 +1:\n   substring(cat(keystring, keystring), startBit..(startBit+7)):
\n   end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "seq([i,roundKe
yMaker(keyString, i)], i=1..3);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$
\"\"\"Q)110110006\"7$\"\"#Q)10110001F&7$\"\"$Q)01100011F&" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 170 "The first part of each round is to break
 the message in half and expand one of the right half from 6 to 8 bits
 by a fixed pattern.  We create functions to do these steps." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 246 "leftHalf := String -> subst
ring(String, 1..6):\nrightHalf := String -> substring(String, 7..12):
\nexpander := String ->  cat(substring(String,1..2), \n    substring(S
tring,4),substring(String,3..4), \n    substring(String,3), substring(
String,5..6)):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 72 "At each step we
 compute our example to verify it has the desired action." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 118 "L0 := leftHalf(messageString);\nR0
 := rightHalf(messageString);\nER0 := expander(R0);\nk1 := roundKeyMak
er(keyString, 1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#L0GQ'1011016\"
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#R0GQ'1110016\"" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#>%$ER0GQ)110101016\"" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%#k1GQ)110110006\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 197 "The
 next step in each round is to XOR the expanded right half with the ro
und key, producing the input for the S boxes.  We create functions to \+
XOR a single bit, and one to use it on longer strings." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 126 "XOR := (a,b) -> if (a=b) then \"0
\" else \"1\" fi:\nxorNbits := (a,b,N) -> \n  cat(seq(XOR(substring(a,
i), substring(b,i)),i=1..N)):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 30 "SInput := xorNbits(ER0, k1,8);" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6#>%'SInputGQ)000011016\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 367 "We \+
need to construct the S boxes.  It will be convenient to make the S bo
xes into tables with the entries indexed by the 4 bit strings used for
 addresses.  We need a function that converts integers to 4 bit binary
 strings.  (Our function adds 16 before converting and then strips off
 the leading bit of the 5 bit string.  This eliminate problems with le
ading zeroes.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 411 "SBoxa :=
\n[\"101\", \"010\", \"001\", \"110\", \"011\", \"100\", \"111\", \"00
0\",\n\"001\", \"100\", \"110\", \"010\", \"000\", \"111\", \"101\", \+
\"011\",\n\"100\", \"000\", \"110\", \"101\", \"111\", \"001\", \"011
\", \"010\",\n\"101\", \"011\", \"000\", \"111\", \"110\", \"010\", \"
001\", \"100\"]:\nindexS1 := x -> substring(convert(convert(x+16, bina
ry),string),2..5):\nS1 := table([seq(indexS1(i-1)=SBoxa[i],i=1..16)]):
\nS2 := table([seq(indexS1(i-1)=SBoxa[i+16], i=1..16)]):" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 175 "It is also useful to see the S boxes wri
tten as an ordered matrix.  Thus we create a procedure for turning a t
able with the 4 bit binary strings as index values into a matrix." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 128 "indexList := matrix([[seq(i
ndexS1(i),i=0..7)],[seq(indexS1(8+i),i=0..7)]]);\nshowAsMatrix := tabl
e -> map(y->table[y],indexList):" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
*indexListG-%'matrixG6#7$7*Q%00006\"Q%0001F+Q%0010F+Q%0011F+Q%0100F+Q%
0101F+Q%0110F+Q%0111F+7*Q%1000F+Q%1001F+Q%1010F+Q%1011F+Q%1100F+Q%1101
F+Q%1110F+Q%1111F+" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "S1box
 = showAsMatrix(S1);\nS2box = showAsMatrix(S2);\n" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#/%&S1boxG-%'matrixG6#7$7*Q$1016\"Q$010F+Q$001F+Q$110F+Q
$011F+Q$100F+Q$111F+Q$000F+7*F-F0F.F,F2F1F*F/" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#/%&S2boxG-%'matrixG6#7$7*Q$1006\"Q$000F+Q$110F+Q$101F+Q
$111F+Q$001F+Q$011F+Q$010F+7*F.F1F,F/F-F2F0F*" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 133 "Now we can look up the appropriate values in the S bo
xes and concatenate them together.  This result is the output of the f
 function." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "Soutput := ca
t(S1[substring(SInput,1..4)],S2[substring(SInput,5..8)]);" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%(SoutputGQ'1010106\"" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 98 "This value is XORed with the old left, then concatenat
ed with the new left which is the old right." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 60 "L1 := R0;\nR1 := xorNbits(L0,Soutput,6);\nEnd1 :
= cat(L1, R1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#L1GQ'1110016\"" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#R1GQ'0001116\"" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%%End1GQ-1110010001116\"" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 81 "We combine the functions into a single procedure that doe
s one round of Baby DES." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
447 "SingleRound := proc(messString, keyString, round)\n    local roun
dKey, startL, startR, expandR, SInput, SOutput:\n    roundKey := round
KeyMaker(keyString, round):\n    startL := leftHalf(messString):\n    \+
startR := rightHalf(messString):\n    expandR := expander(startR):\n  \+
  SInput := xorNbits(expandR, roundKey,8):\n    SOutput :=\n       cat
(S1[substring(SInput,1..4)], S2[substring(SInput,5..8)]):\n    cat(sta
rtR, xorNbits(SOutput, startL,6));\n  end:" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 40 "SingleRound(messageString, keyString,1);" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#Q-1110010001116\"" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 80 "Now we produce a procedure that does Baby DES with a sp
ecified number of rounds." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 
189 "BabyDES := proc(messString, keyString, numberRounds)\n    local t
emp, i:\n    temp := messString:\n    for i from 1 to numberRounds do
\n        temp := SingleRound(temp, keyString,i) od:\n  end:" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "This lets us see the results round
 by round" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "seq(BabyDES(me
ssageString, keyString,i), i=1..4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
&Q-1110010001116\"Q-000111011001F$Q-011001110100F$Q-110100010101F$" }}
}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 0 "" }{TEXT 259 8 "Exercise" }}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 144 "1)  Do a three round Baby DES enc
ryption on a single 12 bit message with your favorite 9 bit key by han
d.  Verify your work with this worksheet." }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 
257 37 "Baby DES in a single execution group." }}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 178 "While the step by step approach is useful to understan
d what is going on, we want to put everything into a single block of c
ode that can be copied and executed to enable BabyDES." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 1605 "roundKeyMaker := proc(keystring, \+
i)\n   local startBit:\n   startBit := ((i-1) mod 9) +1:\n   substring
(cat(keystring, keystring), startBit..(startBit+7)):\n   end:\nleftHal
f := String -> substring(String, 1..6):\nrightHalf := String -> substr
ing(String, 7..12):\nexpander := String ->  cat(substring(String,1..2)
, \n    substring(String,4), substring(String,3..4), \n    substring(S
tring,3), substring(String,5..6)):\nXOR := (a,b) -> if (a=b) then \"0
\" else \"1\" fi:\nxorNbits := (a,b,N) -> \n  cat(seq(XOR(substring(a,
i), substring(b,i)),i=1..N)):\nSBoxa :=\n    [\"101\", \"010\", \"001
\", \"110\", \"011\", \"100\", \"111\", \"000\",\n     \"001\", \"100
\", \"110\", \"010\", \"000\", \"111\", \"101\", \"011\",\n     \"100
\", \"000\", \"110\", \"101\", \"111\", \"001\", \"011\", \"010\",\n  \+
   \"101\", \"011\", \"000\", \"111\", \"110\", \"010\", \"001\", \"10
0\"]:\nindexS1 := x -> substring(convert(convert(x+16, binary),string)
,2..5):\nS1 := table([seq(indexS1(i-1)=SBoxa[i],i=1..16)]):\nS2 := tab
le([seq(indexS1(i-1)=SBoxa[i+16], i=1..16)]):\nSingleRound := proc(mes
sString, keyString, round)\n    local roundKey, startL, startR, expand
R, SInput, SOutput:\n    roundKey := roundKeyMaker(keyString, round):
\n    startL := leftHalf(messString):\n    startR := rightHalf(messStr
ing):\n    expandR := expander(startR):\n    SInput := xorNbits(expand
R, roundKey,8):\n    SOutput := \n        cat(S1[substring(SInput,1..4
)],S2[substring(SInput,5..8)]):\n    cat(startR, xorNbits(SOutput, sta
rtL,6));\n  end:\nBabyDES := proc(messString, keyString, numberRounds)
\n    local temp, i:\n    temp := messString:\n    for i from 1 to num
berRounds do\n        temp := SingleRound(temp, keyString,i) od:\n  en
d:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "seq(BabyDES(messageSt
ring, keyString,i), i=1..4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&Q-1110
010001116\"Q-000111011001F$Q-011001110100F$Q-110100010101F$" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 178 "We would also like to store the c
ommands in a file so that we can recall them in future sessions.  The \+
file will be called BabyDES.m and will be created in the current direc
tory." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 127 "save roundKeyMake
r, leftHalf, rightHalf, expander, XOR, \n     xorNbits, S1, S2, Single
Round,BabyDES, `BabyDES.m`:\ncurrentdir();" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#Q^o\\\\Summer\\Web~Sites\\dev\\MapleApps\\powertools\\c
ryptography\\worksheets6\"" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" 
}{TEXT 258 52 "Differential Cryptanalysis for three round Baby DES." }
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "We would now like to look at Diff
erential Cryptanalysis for three round Baby DES." }}{PARA 0 "" 0 "" 
{TEXT -1 43 "We start with a key and 4 words to encrypt." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 133 "keyString := \"110110001\";\nmess[
1] := \"101101111001\";\nmess[2] := \"101100111001\";\nmess[3] := \"10
1111111001\";\nmess[4] := \"100101111001\";" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%*keyStringGQ*1101100016\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%%messG6#\"\"\"Q-1011011110016\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%%messG6#\"\"#Q-1011001110016\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%%messG6#\"\"$Q-1011111110016\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%%messG6#\"\"%Q-1001011110016\"" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 74 "We compute three round keys.  The method will prod
uce the three round key." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 
"for i from 1 to 3 do roundKeyMaker(keyString,i) od;" }}{PARA 11 "" 1 
"" {XPPMATH 20 "6#Q)110110006\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q)1
01100016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q)011000116\"" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 182 "For each word we want to produce \+
the encrypted word, the XOR of the left half of the plain text with th
e right half of the cipher text, and the expanded left half of the cip
her text." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 192 "for i from 1 \+
to 4 do\n    mess[i];\n    code[i] := BabyDES(mess[i], keyString,3);\n
    R3L0[i] := xorNbits(leftHalf(mess[i]),rightHalf(code[i]),6);\n    \+
EL3[i] := expander(leftHalf(code[i]));\n od;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#Q-1011011110016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&
%%codeG6#\"\"\"Q-0110011101006\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&
%%R3L0G6#\"\"\"Q'0110016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%$EL3G
6#\"\"\"Q)010101016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q-10110011100
16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%%codeG6#\"\"#Q-011110010100
6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%%R3L0G6#\"\"#Q'1110006\"" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%$EL3G6#\"\"#Q)011111106\"" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#Q-1011111110016\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%%codeG6#\"\"$Q-0111000100016\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%%R3L0G6#\"\"$Q'1111106\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>&%$EL3G6#\"\"$Q)011111006\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#Q-1001011110016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&
%%codeG6#\"\"%Q-1100001110106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%
%R3L0G6#\"\"%Q'0111116\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%$EL3G6#
\"\"%Q)110000006\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 217 "For each p
air of words we want to XOR the expanded left halves of the cipher tex
t.  These will be the difference in inputs to the S boxes.  We also wa
nt to XOR the R3L0 words.  These will be the difference in outputs." }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 174 "for i from 1 to 3 do\nfor
 j from i+1 to 4 do\nEhat[i,j] := xorNbits(EL3[i], EL3[j],8);\nRLhat[i
,j] := xorNbits(R3L0[i], R3L0[j], 6);\nprint([i,j], Ehat[i,j], RLhat[i
,j]);\nod; od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"#Q)00101
0116\"Q'100001F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"$Q)001
010016\"Q'100111F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"%Q)1
00101016\"Q'000110F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"#\"\"$Q)
000000106\"Q'000110F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"#\"\"%Q
)101111106\"Q'100111F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"$\"\"%
Q)101111006\"Q'100001F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 149 "Time \+
to repeat a technical detail.  I want to switch between the integers 0
-15 and the binary strings \"0000\" to \"1111\" without losing leading
 zeroes." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "indexS1 := x ->
 substring(convert(convert(x+16, binary),string),2..5):" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 114 "To use the differentials, I need routine
s that will XOR the S boxes with themselves shifted an appropriate amo
unt." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 251 "S1hatted := hatstr
ing -> table([seq(indexS1(i)=\n  xorNbits(S1[indexS1(i)],S1[xorNbits(i
ndexS1(i),hatstring,4)],3),i=0..15)]):\nS2hatted := hatstring -> table
([seq(indexS1(i)=\n  xorNbits(S2[indexS1(i)],S2[xorNbits(indexS1(i),ha
tstring,4)],3),i=0..15)]):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 138 "Te
st the code by XORing S1 with itself shifted by \"1000\" (subtract row
s) and S2 with itself shifted by \"0001\" (adjacent pairs of columns).
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 203 "S1hat := S1hatted(subs
tring(\"10000001\",1..4)):\nS2hat := S2hatted(substring(\"10000001\",5
..8)):\nS1box = showAsMatrix(S1);\nS1hat = showAsMatrix(S1hat);\nS2box
 = showAsMatrix(S2);\nS2hat = showAsMatrix(S2hat);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#/%&S1boxG-%'matrixG6#7$7*Q$1016\"Q$010F+Q$001F+Q$110F
+Q$011F+Q$100F+Q$111F+Q$000F+7*F-F0F.F,F2F1F*F/" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#/%&S1hatG-%'matrixG6#7$7*Q$1006\"Q$110F+Q$111F+F*Q$011F
+F.Q$010F+F.F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2boxG-%'matrixG6
#7$7*Q$1006\"Q$000F+Q$110F+Q$101F+Q$111F+Q$001F+Q$011F+Q$010F+7*F.F1F,
F/F-F2F0F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG-%'matrixG6#7$7
*Q$1006\"F*Q$011F+F,Q$110F+F-Q$001F+F.7*F-F-Q$111F+F0F*F*Q$101F+F1" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 217 "We now want to examine the hatte
d S boxes for the correct output values.  The locations with these val
ues will be shifted by the appropriate half of the expansion of L3 to \+
give possibilities for half of the round key." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 343 "goodSvals := proc(hattedSBox, hatVal)\n    loca
l goodValues, i, j:\n    goodValues :=\{\}:\n    for i from 1 to 16 do
\n      if (hattedSBox[indexS1(i)] = hatVal) then \n         goodValue
s := goodValues union \{indexS1(i)\} end if:\n    end do:\n    goodVal
ues;\nend:\nshiftedVals := (goodValues, shiftVal) ->\n   map(x->xorNbi
ts(x,shiftVal,4), goodValues):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 83 
"We can plug in the pairs of words to see which 4 bit string shows up \+
for each pair." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 590 "for i fr
om 1 to 3 do\nfor j from i+1 to 4 do\nS1hat := S1hatted(substring(Ehat
[i,j],1..4));\nS2hat := S2hatted(substring(Ehat[i,j],5..8));\nprint(S1
hat = [[seq(S1hat[indexS1(i)],i=0..7)],[seq(S1hat[indexS1(8+i)],i=0..7
)]]);\nprint(S2hat = [[seq(S2hat[indexS1(i)],i=0..7)],[seq(S2hat[index
S1(8+i)],i=0..7)]]);\ns1 := shiftedVals(goodSvals(S1hat, substring(RLh
at[i,j],1..3)),\n   substring(expander(leftHalf(code[i])),1..4));\ns2 \+
:= shiftedVals(goodSvals(S2hat, substring(RLhat[i,j],4..6)),\n   subst
ring(expander(leftHalf(code[i])),5..8));\nprint([i,j, Ehat[i,j], RLhat
[i,j]], s1, s2);\nend do;\nend do;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
/%&S1hatG7$7*Q$1006\"F'F'F'F'F'F'F'7*Q$111F(Q$110F(F*F+Q$101F(F'F,F'" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG7$7*Q$0116\"Q$000F(Q$101F(F
)F'F)Q$001F(Q$100F(7*F)F*F)F'F,F+F)F'" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6%7&\"\"\"\"\"#Q)001010116\"Q'100001F'<,Q%0000F'Q%0001F'Q%0010F'Q%001
1F'Q%0100F'Q%0101F'Q%0110F'Q%0111F'Q%1000F'Q%1010F'<$F-F2" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#/%&S1hatG7$7*Q$1006\"F'F'F'F'F'F'F'7*Q$111F(Q$1
10F(F*F+Q$101F(F'F,F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG7$7*
Q$1116\"Q$101F(Q$001F(F)F)F'F'Q$011F(7*F)F'F)F*F'F)F+F'" }}{PARA 12 "
" 1 "" {XPPMATH 20 "6%7&\"\"\"\"\"$Q)001010016\"Q'100111F'<,Q%0000F'Q%
0001F'Q%0010F'Q%0011F'Q%0100F'Q%0101F'Q%0110F'Q%0111F'Q%1000F'Q%1010F'
<(F*F-F/Q%1001F'F3Q%1100F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S1hat
G7$7*Q$0016\"Q$011F(F)Q$000F(Q$100F(F+F+Q$101F(7*F)F'F*F)F+F+F,F+" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG7$7*Q$1016\"Q$111F(Q$100F(Q$1
10F(F)F'F+F*7*F)F'F*F+F'F)F+F*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7&\"
\"\"\"\"%Q)100101016\"Q'000110F'<$Q%0110F'Q%1111F'<&Q%0011F'F*Q%1011F'
Q%1110F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S1hatG7$7*Q$0006\"F'F'F
'F'F'F'F'F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG7$7*Q$0106\"Q$
101F(F'F)Q$100F(Q$011F(F*F+7*F)F*F)F*Q$111F(Q$110F(F-F." }}{PARA 12 "
" 1 "" {XPPMATH 20 "6%7&\"\"#\"\"$Q)000000106\"Q'000110F'<2Q%0000F'Q%0
001F'Q%0010F'Q%0011F'Q%0100F'Q%0101F'Q%0110F'Q%0111F'Q%1000F'Q%1001F'Q
%1010F'Q%1011F'Q%1100F'Q%1101F'Q%1110F'Q%1111F'<$F+F-" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#/%&S1hatG7$7*Q$1116\"Q$100F(Q$101F(F'Q$000F(Q$001F
(F+F+7*F'F*F)F'F+F+F,F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG7$
7*Q$1016\"Q$100F(Q$000F(Q$111F(F+Q$110F(F,Q$001F(7*F,F-F+F,F*F+F'F)" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6%7&\"\"#\"\"%Q)101111106\"Q'100111F'<$
Q%0110F'Q%1101F'<&Q%0011F'Q%0100F'Q%1010F'F+" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#/%&S1hatG7$7*Q$1116\"Q$100F(Q$101F(F'Q$000F(Q$001F(F+F+
7*F'F*F)F'F+F+F,F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%&S2hatG7$7*Q$0
106\"F'Q$111F(Q$001F(F'F'Q$011F(Q$101F(7*F'F'F+F,F'F'F)F*" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6%7&\"\"$\"\"%Q)101111006\"Q'100001F'<$Q%0110F'Q%
1101F'<$Q%0011F'Q%1111F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 186 "Look
ing at the (1,4) and (2,4) pairs we see that the first 4 bits are 0110
.  Using the same two pairs of words the second four bits must be 0011
.\n\nWe can automate the comparison process." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 868 "S1hat := S1hatted(substring(Ehat[1,2],1..4));\n
S2hat := S2hatted(substring(Ehat[1,2],5..8));\ngood1 := shiftedVals(go
odSvals(S1hat, substring(RLhat[1,2],1..3)),     \n    substring(expand
er(leftHalf(code[1])),1..4));\ngood2 := shiftedVals(goodSvals(S2hat, s
ubstring(RLhat[1,2],4..6)),     \n    substring(expander(leftHalf(code
[1])),5..8));\nfor i from 1 to 3 do\nfor j from i+1 to 4 do\nS1hat := \+
S1hatted(substring(Ehat[i,j],1..4));\nS2hat := S2hatted(substring(Ehat
[i,j],5..8));\ns1 := shiftedVals(goodSvals(S1hat, substring(RLhat[i,j]
,1..3)),     \n    substring(expander(leftHalf(code[i])),1..4));\ns2 :
= shiftedVals(goodSvals(S2hat, substring(RLhat[i,j],4..6)),     \n    \+
substring(expander(leftHalf(code[i])),5..8));\ngood1 := good1 intersec
t s1:\nprint([i,j],` first bytes left `, good1);\ngood2 := good2 inter
sect s2:\nprint([i,j],` second bytes left `, good2);\nend do;\nend do;
" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&S1hatG-%&TABLEG6#72/Q%11106\"Q$
101F+/Q%0100F+Q$100F+/Q%1011F+Q$110F+/Q%0001F+F//Q%1000F+Q$111F+/Q%111
1F+F//Q%0101F+F//Q%1100F+F,/Q%0010F+F//Q%1001F+F2/Q%0110F+F//Q%1101F+F
//Q%0011F+F//Q%1010F+F7/Q%0000F+F//Q%0111F+F/" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#>%&S2hatG-%&TABLEG6#72/Q%11106\"Q$000F+/Q%0100F+Q$011F+
/Q%1011F+F//Q%0001F+F,/Q%1000F+F,/Q%1111F+F//Q%0101F+F,/Q%1100F+Q$100F
+/Q%0010F+Q$101F+/Q%1001F+F?/Q%0110F+Q$001F+/Q%1101F+FD/Q%0011F+F,/Q%1
010F+F,/Q%0000F+F//Q%0111F+F<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&go
od1G<,Q%00006\"Q%0001F'Q%0010F'Q%0011F'Q%0100F'Q%0101F'Q%0110F'Q%0111F
'Q%1000F'Q%1010F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&good2G<$Q%0011
6\"Q%1000F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"#%3~first~b
ytes~left~G<,Q%00006\"Q%0001F)Q%0010F)Q%0011F)Q%0100F)Q%0101F)Q%0110F)
Q%0111F)Q%1000F)Q%1010F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"
\"#%4~second~bytes~left~G<$Q%00116\"Q%1000F)" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6%7$\"\"\"\"\"$%3~first~bytes~left~G<,Q%00006\"Q%0001F)Q%
0010F)Q%0011F)Q%0100F)Q%0101F)Q%0110F)Q%0111F)Q%1000F)Q%1010F)" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"$%4~second~bytes~left~G<#Q
%00116\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"%%3~first~byte
s~left~G<#Q%01106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"\"\"\"%%4
~second~bytes~left~G<#Q%00116\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$
\"\"#\"\"$%3~first~bytes~left~G<#Q%01106\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6%7$\"\"#\"\"$%4~second~bytes~left~G<#Q%00116\"" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6%7$\"\"#\"\"%%3~first~bytes~left~G<#Q%01106\"
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"#\"\"%%4~second~bytes~left~G
<#Q%00116\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"$\"\"%%3~first~by
tes~left~G<#Q%01106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%7$\"\"$\"\"%%
4~second~bytes~left~G<#Q%00116\"" }}}{SECT 0 {PARA 5 "" 0 "" {TEXT -1 
0 "" }{TEXT 260 9 "Exercise:" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 143 "2
)  Using a three round Baby DES system someone has generated the follo
wing four pairs of plaintext words and cipher text words.  Find the ke
y." }}{PARA 0 "" 0 "" {TEXT -1 32 "[\"011011001011\", \"010001010100\"
]" }}{PARA 0 "" 0 "" {TEXT -1 32 "[\"111011001011\", \"001001010111\"]
" }}{PARA 0 "" 0 "" {TEXT -1 32 "[\"011111001011\", \"110010001101\"]
" }}{PARA 0 "" 0 "" {TEXT -1 32 "[\"011010001011\", \"010101110100\"]
" }}}{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 }