{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 }{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 }} {SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 37 "Baby DES 3\nStatistical c onsiderations" }}{PARA 19 "" 0 "" {TEXT -1 36 "\251Mike May, S.J., 200 2, maymk@slu.edu" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "restart :\nread `BabyDES.m`:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 202 "This wor ksheet assumes that you have already worked through the first workshee t on Baby DES. That first Baby DES worksheet creates the BabyDES.m. \+ The BabyDES.m file should be in the current directory." }}{PARA 0 "" 0 "" {TEXT -1 162 "This worksheet looks at how effectively Baby DES is when measured from some statistical criteria. These criteria can be \+ used to evaluate other symmetric ciphers." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 432 "For a block cipher to be effective it should be true tha t if we know all but one of the bits in the plaintext block and the ke y, then each bit of the cipher block should still have a 50-50 chance \+ of being either zero or one. Obviously it is too much to ask that pre cisely 50 % of the bits change when we change one bit of the plaintext . We want to test if this is the average behavior and if it seems to \+ follow a random pattern.. " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 24 "Sh ifting each single bit" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 194 "The fir st way to test for random behavior is to ask if we start from a fixed \+ plaintext and key, and change each bit of the plaintext one at a time, do the bits of the ciphertext behave randomly." }}}{SECT 0 {PARA 4 " " 0 "" {TEXT -1 0 "" }{TEXT 256 48 "Counting the number of bits change d in each word" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 369 "A first examina tion looks at how many bits of output are changed if we change each si ngle bit of the input or of the key. Each bit of the output should be changed with a probability of .5.\nTo make our task easier, we want r outines that will easily produce various keys or plaintext messages. \+ Recall that for Baby DES, the input block is 12 bits and the key is 9 \+ bits." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 162 "intToBitKey := i \+ -> \n substring(convert(convert(2^9+i,binary),string),2..10):\nintToB itMessage := i -> \n substring(convert(convert(2^12+i,binary),string) ,2..13):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "zerokey := intT oBitKey(0);\nzeromessage := intToBitMessage(0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(zerokeyGQ*0000000006\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%,zeromessageGQ-0000000000006\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 197 "The first test is to compare the ciphertext obtained fro m the zerokey and zeromessage with the ciphertext obtained by encoding a message with a single bit changed. We start by looking at 2 rounds ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 263 "numRounds := 2;\nciph er0 := BabyDES(zeromessage, zerokey, numRounds);\nfor loc from 0 to 11 do\nmessage := intToBitMessage(2^loc);\ncipher := BabyDES(message, ze rokey,numRounds);\ncomparison := xorNbits(cipher, cipher0, 12);\nprint (loc,message, cipher, comparison);\nod:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*numRoundsG\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(cipher0 GQ-1011000101106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"!Q-000000000 0016\"Q-101000100110F%Q-000100110000F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"\"Q-0000000000106\"Q-101110010011F%Q-000010000101F%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"#Q-0000000001006\"Q-001101110110F% Q-100001100000F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"$Q-00000000100 06\"Q-010111110111F%Q-111011100001F%" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6&\"\"%Q-0000000100006\"Q-011100010110F%Q-110000000000F%" }}{PARA 11 " " 1 "" {XPPMATH 20 "6&\"\"&Q-0000001000006\"Q-001100010110F%Q-10000000 0000F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"'Q-0000010000006\"Q-1011 01010010F%Q-000001000100F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"(Q-0 000100000006\"Q-101110010001F%Q-000010000111F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\")Q-0001000000006\"Q-101000100111F%Q-000100110001F% " }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"*Q-0010000000006\"Q-1001001101 01F%Q-001000100011F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#5Q-01000000 00006\"Q-111100011110F%Q-010000001000F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#6Q-1000000000006\"Q-001100110110F%Q-100000100000F%" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 299 "Ideally we expect the comparison \+ to be half ones and half zeroes with the ones randomly distributed. W ith 2 round Baby DES, we changed an average of 3 bits of output when w e changed one round of input. This is enough less than the hoped for \+ value of 6 bits that we conclude 2 rounds is not enough." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 296 "Obviously Baby DES need more than 2 roun ds to be effective. Before testing more rounds we want to produce pro cedures that will make the results easier to analyze. We want procedu res to convert a bit string into a list of digits and another procedur e to count the number of ones in such a list. " }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 186 "zeroList12 := [seq(0,place=1..12)]:\nbitStrin gToList12 := bitString -> \n [seq(parse(substring(bitString,place)), place=1..12)]:\naddList12 := bitList -> sum(bitList[place], place=1.. 12):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "cipher0;\nbitString ToList12(cipher0);\naddList12(bitStringToList12(cipher0));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q-1011000101106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7.\"\"\"\"\"!F$F$F%F%F%F$F%F$F$F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 160 "We now c ount the number of bits changes by individually changing each bit in t he plaintext message and compute the mean and standard deviation of th ese results." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 225 "diffCount \+ := \n [seq(addList12(bitStringToList12(xorNbits(cipher0,\n Baby DES(intToBitMessage(2^i),zerokey,2),12))),i=0..11)];\nevalf(stats[desc ribe, mean](diffCount));\nevalf(stats[describe, standarddeviation](dif fCount));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*diffCountG7.\"\"$F&F& \"\"(\"\"#\"\"\"F(\"\"%F*F*F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\" +LLL$3$!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+(R$o(\\\"!\"*" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 468 "If each bit was changed with a pr obability of .5, then we expect the entries of diffCount to look like \+ they were produced by a random binomial probability distribution based on 12 tries with a probability of .5. The expected value is (12)*(.5 )=6. The expected standard deviation is sqrt(12*.5*.5) = 1.732. Sinc e we are modeling random behavior we don't expect 6 every time. We do however expect it to be close to the average value. (We will return \+ to this later.)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 189 "We want to ge neralize the procedure above so that we can input a key, a message and a number of rounds and we look at the change caused by changing each \+ bit of the plaintext, one at a time." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 460 "changeEachBitMessage := proc(message, key, rounds)\n local cipher0, diffCount, newMessage, changebits, pos:\n cipher0 \+ := BabyDES(message, key, rounds):\n diffCount := vector(12):\n for pos from 0 to 11 do\n newMessage := xorNbits(message, intToBitMe ssage(2^pos), 12):\n changebits := xorNbits(cipher0, BabyDES(newM essage, key, rounds), 12):\n diffCount[pos+1] := addList12(bitStr ingToList12(changebits)):\n od:\n convert(diffCount,list);\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 144 "count1 := changeEachBitM essage(zeromessage, zerokey,2);\nevalf(stats[describe, mean](count1)); \nevalf(stats[describe, standarddeviation](count1));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%'count1G7.\"\"$F&F&\"\"(\"\"#\"\"\"F(\"\"%F*F*F(F( " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+LLL$3$!\"*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#$\"+(R$o(\\\"!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 141 "We can try Baby DES with a variable number of rounds and see h ow many rounds we need for the behavior to look like bits are randomly changed." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 224 "for rounds fr om 2 to 10 do\n countList := changeEachBitMessage(zeromessage, zeroke y,rounds):\n print(rounds,countList, evalf(stats[describe, mean](coun tList)),\n evalf(stats[describe, standarddeviation](countList))): \nod:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"#7.\"\"$F%F%\"\"(F#\"\"\" F#\"\"%F(F(F#F#$\"+LLL$3$!\"*$\"+(R$o(\\\"F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"$7.\"\"%\"\"'F%\"\"&\"\"#\"\"\"F'F'F&\"\"(F%F#$\"+L LLLV!\"*$\"+Be\"*\\;F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"%7.\"\"& \"\"*\"\"(\"\"'\"\"$\"\"#\"\")F#F#F'F+F#$\"+LLL$e&!\"*$\"+4'\\#R@F." } }{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"&7.F#\"#5\"\"'F&F&\"\"%\"\")F&\" \"$F#\"\"(F($\"+nmmmh!\"*$\"+&o=\"==F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"'7.\"\"%\"\")F#F&F#\"\"&F#\"\"(F(F#F%F&$\"++++]i!\"*$\"+()yn h8F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"(7.\"\"$F#\"\"&\"\")\"\"%F (F#\"\"'F'F)F&F($\"+LLL$e&!\"*$\"+dL60;F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\")7.\"\"&F#\"\"$\"\"'F'F%F#\"\"(F'F%F(\"\"%$\"+LLLLe !\"*$\"+lS\\i9F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"*7.\"\"(F%\"\" %F&\"\"'F'F&F'F'F'F%\"\"&$\"+nmmmc!\"*$\"+(fTb5\"F+" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&\"#57.\"\"'F%F%\"\"#F%\"\"(\"\"%F(F%F'F%F%$\"+++++b! \"*$\"+6tV%Q\"F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 114 "At this firs t level of analysis, it looks like 5 rounds of Baby DES changes bits w ith a probability of about .5. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 29 "Random bino mial distributions" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 342 "If each bit is changed with a probability of .5, then the sum of a collection of \+ bits should produce a binomial distribution. Maple lets us produce ra ndom numbers from such a distribution. We have been looking at number s that we hope are the result of counting the number of successes in 1 2 trials, each of which has a .5 chance of success." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 110 "stats[random,binomiald[12, .5]](1);\nsta ts[random,binomiald[12, .5]](5);\n[stats[random,binomiald[12, .5]](12) ];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6'\"\"&F#\"\"'F$\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# 7.\"\"$\"\"(\"\"'F%\"\"&F'F%F$\"\"%\"\"*\"\")F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "Consider the results of 10 fake lists in the form ga thered in the last section" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 210 "for counta from 1 to 10 do\nfakeList := [stats[random,binomiald[1 2, .5]](12)]:\n print(counta,fakeList, evalf(stats[describe, mean](fa keList)),\n evalf(stats[describe, standarddeviation](fakeList))): \nend do:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"\"7.\"\"(\"\")\"\"*\" \"%F(\"\"'F)\"\"&F*F%F&F%$\"+LLLLj!\"*$\"+$3.ca\"F-" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&\"\"#7.\"\"&\"\"(F&F&F%F#\"\"%F&F'F&F'\"#5$\"++++]d! \"*$\"+$>Qj/#F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"$7.\"\"'\"\"(F% \"\"&\"\")\"#5\"\"%F'F&F&F&F%$\"+++++l!\"*$\"+++++:F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"%7.F#\"\")\"\"&\"\"'\"\"(F#F'F'F%F(F%F'$\"++++ ]i!\"*$\"+()ynh8F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"&7.\"\"'\"#5 F%F&\"\"%\"\")F#\"\"$F'F%F'F%$F%\"\"!$\"+FV[)>#!\"*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&\"\"'7.\"\"%\"\"&\"\"(F'F&F'F%\"\"#\"\"$F#F%F'$\"+LLL $3&!\"*$\"+Us@c;F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"(7.\"\"$\"\" %F#F&F#\"#5F#F&F#F&\"\"&\"\"'$\"+nmmmc!\"*$\"+]hIH>F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\")7.F#\"\"'\"\"&\"\"*\"\"(\"\"%F#F(F'F#F#F%$\"+ LLL$3(!\"*$\"+(R$o(\\\"F," }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"\"*7.\" \"%\"\"$\"\"(\"\"&F(\"\"'F'\"\")F(F)F&F($\"+LLLL`!\"*$\"+&)>r!\\\"F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&\"#57.\"\"'\"\"(F&F%F#\"\")F&\"\"&\" \"$F'F(F'$\"+nmmmm!\"*$\"+ZZ,[ " 0 "" {MPLTEXT 1 0 302 "for counter from 1 t o 10 do\n message := intToBitMessage(rand(2^12)()):\n key := intTo BitKey(rand(2^9)()):\n countList := changeEachBitMessage(message, ke y, 5):\n print(message, key, countList, evalf(stats[describe, mean]( countList)),\n evalf(stats[describe, standarddeviation](countList) )):\nod:" }}{PARA 11 "" 1 "" {XPPMATH 20 "6'Q-0001001011106\"Q*1000010 00F$7.\"\"%\"\"&\"\"(F'\"\"'\"\"*\"\")F*F(\"\"#F(F($\"+++++b!\"*$\"+Qc x-=F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6'Q-0100101111006\"Q*010011011F $7.\"\"&\"\")F'F(\"\"'\"\"#F)\"\"(F)F+F+F+$\"+nmmmh!\"*$\"+*=IBd\"F." }}{PARA 11 "" 1 "" {XPPMATH 20 "6'Q-0100011000006\"Q*100000111F$7.\"\" $\"\"(\"\"'\"\")F)F(\"\"&F*F*F'F*F)$\"++++]i!\"*$\"+nW0Q " 0 "" {MPLTEXT 1 0 202 "meanList := list():\nfor count fro m 1 to 40 do\n fakeList := [stats[random,binomiald[12, .5]](12)];\n \+ meanList[count] := evalf(stats[describe, mean](fakeList));\nod:\nmea nList := convert(meanList, list):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 464 "What we have done is produce a sampling distribution. The meanLi st should have the same mean, 6, with a standard distribution that is \+ the old predicted standard deviation divided by the square root of th e size of the list. Thus the predicted standard deviation is sqrt(12* .5*.5/12)=.5. In that computation the first 12 is the number of bits \+ collected in defining the binomial distribution and the second 12 is t he number of sample taken with that distribution." }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 88 "meanList;\nstats[describe, mean](meanList); \nstats[describe, standarddeviation](meanList);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7J$\"+LLLL[!\"*$\"+LLLLeF&$\"++++]iF&$\"+nmmmmF&$\"+nmm m^F&$\"+nmm;uF&$\"\"'\"\"!F'$\"+LLL$e'F&F-$\"\"&F3$\"+nmmmhF&$\"+LLL$e &F&F1$\"+LLLL`F&F1$\"+nmmmcF&$\"+++++bF&F@F8$\"\"(F3F>$\"+LLL$3'F&$\"+ LLL$3&F&F'$\"+++++lF&F1F8F)F6$\"+LLLLjF&$\"++++]dF&FJFLF4F1$\"+nmm;fF& F@FDF)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+)**\\(=f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+g%Q>[&!#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 126 "We can now do the same thing with samples obtained from \+ the number of bits changed when changing each bit of a random message. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 518 "changeEachBitMessage2 \+ := proc(message, key, rounds)\n local cipher0, diffCount, newMessage , changebits, pos:\n cipher0 := BabyDES(message, key, rounds):\n d iffCount := vector(12):\n for pos from 0 to 11 do\n newMessage \+ := xorNbits(message, intToBitMessage(2^pos), 12):\n changebits := xorNbits(cipher0, BabyDES(newMessage, key, rounds), 12):\n diffC ount[pos+1] := addList12(bitStringToList12(changebits)):\n od:\n d iffCount := convert(diffCount,list):\n evalf(stats[describe, mean](d iffCount));\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 335 "meanL ist := list():\nfor count from 1 to 40 do\n message := intToBitMessa ge(rand(2^12)()):\n key := intToBitKey(rand(2^9)()):\n countList : = changeEachBitMessage2(message, key, 5):\n meanList[count] := count List:\nod:\nmeanList := convert(meanList, list);\nstats[describe, mean ](meanList);\nstats[describe, standarddeviation](meanList);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%)meanListG7J$\"\"&\"\"!$\"+++++b!\"*$\"+++ +]_F+$\"++++]dF+$\"+nmmmhF+$\"+nmm;\\F+F)$\"\"'F($\"+LLLLeF+F)$\"+nmm; fF+$\"+++++lF+$\"+LLL$e'F+FFDFB$\"+LLL$3&F+F@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+0+DJe! \"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+mF_P`!#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "It seems that the bits are behaving randomly fr om this perspective." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }} }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 55 "Counting the number of words fo r which a bit is changed" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 222 "We in itially asked if we change the plaintext one bit at a time, how many b its are changed in each new ciphertext. The other obvious way to arra nge the data asks in how many of the ciphertexts is a particular bit c hanged." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 454 "changeEachBitMe ssage3 := proc(message, key, rounds)\n local cipher0, diffCount, new Message, changebits, pos:\n cipher0 := BabyDES(message, key, rounds) :\n diffCount := [seq(0,i=1..12)]:\n for pos from 0 to 11 do\n \+ newMessage := xorNbits(message, intToBitMessage(2^pos), 12):\n \+ changebits := xorNbits(cipher0, BabyDES(newMessage, key, rounds), 12): \n diffCount := zip(`+`,diffCount,bitStringToList12(changebits)): \n od:\n diffCount:\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "changeEachBitMessage3(zeromessage, zerokey,5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7.\"\")\"\"%\"\"*F%\"\"'\"\"$F'F&F$F'\"\"&F'" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 112 "If we do this for a number of wor ds we can then accumulate these changes starting at a number of differ ent words" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 212 "key := intToB itKey(rand(2^9)());\ncountList := []:\nfor count from 1 to 10 do\n m essage := intToBitMessage(rand(2^12)()):\n countList := [op(countLis t), op(changeEachBitMessage3(message, key, 5))]:\nod:\ncountList;" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$keyGQ*1010011006\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7dr\"\"&F$\"\"'F%\"\"(\"\"*F%F%\"\"%F&F%\"\"$F%\" \")F(F&F*F(F(F%F$F)F'F&F&F$F*F%F%F*F&F$F'F*F$F*F%F&F&F$F$F&F)F%F(F'F'F *F)F*F$F&F%F%F&F$F)F(F&F'F%F(F(F%F(F&F$F$F)F*F(F%F*F*F$F%F$F*F%F%F*F'F %F(F(F&F$F&F*F&F*F%F$F$F&F&F%F$\"\"#F&F$F)F(F$F+F*F%F&F%F&F&F&F%F$F(F( F%F(F$F$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 152 "As above, we take th e mean and standard deviation of this list. It is also useful to tall y this list to see the shape of the distribution in countlist." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 133 "evalf(stats[describe, mean] (countList),3);\nevalf(stats[describe, standarddeviation](countList),3 );\nstats[transform,tally](countList);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"$$f!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"$m\"!\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#7*-%'WeightG6$\"\"#F'-F%6$\"\"$\"\"(-F %6$\"\"%\"#;-F%6$\"\"&\"#B-F%6$\"\"'\"#E-F%6$F+F3-F%6$\"\")F/-F%6$\"\" *F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 189 "For comparison, we comput e the probability of each value showing up randomly. For each value o f i from 0 to 12, we want to know the probability that we will get i h eads from 12 coin flips." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "probSeq := [seq([i, evalf(combinat[numbcomb](12,i)/combinat[numbcomb] (12),3)],i=0..12)];" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%(probSeqG7/7$ \"\"!$\"$W#!\"'7$\"\"\"$\"$$H!\"&7$\"\"#$\"$h\"!\"%7$\"\"$$\"$P&F47$\" \"%$\"$@\"!\"$7$\"\"&$\"$$>F=7$\"\"'$\"$E#F=7$\"\"(F@7$\"\")F;7$\"\"*F 77$\"#5F27$\"#6F-7$\"#7F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 111 "Thi s lets us compute the number of times we expect each value of i to sho w up in our collection of 120 numbers." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "expectSeq := map(x->[x[1],x[2]*120],probSeq);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%*expectSeqG7/7$\"\"!$\"&!GH!\"'7$\" \"\"$\"&g^$!\"&7$\"\"#$\"&?$>!\"%7$\"\"$$\"&SW'F47$\"\"%$\"&?X\"!\"$7$ \"\"&$\"&gJ#F=7$\"\"'$\"&?r#F=7$\"\"(F@7$\"\")F;7$\"\"*F77$\"#5F27$\"# 6F-7$\"#7F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 167 "Once again, it lo oks like the behavior is fairly close to random on this test. To gain a better perspective, we repeat the process from 10 randomly chosen p laintexts." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 374 "for i from 1 to 10 do\nkey := intT oBitKey(rand(2^9)());\ncountList := []:\nfor count from 1 to 10 do\n \+ message := intToBitMessage(rand(2^12)()):\n countList := [op(countL ist), op(changeEachBitMessage3(message, key, 5))]:\nod:\nprint(evalf(s tats[describe, mean](countList),3),\n evalf(stats[describe, standard deviation](countList),3),\n stats[transform,tally](countList));\nod: " }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"$-'!\"#$\"$n\"F%7+\"\"#-%'Weigh tG6$\"\"$\"\"&-F+6$\"\"%\"#=-F+6$F.\"#D-F+6$\"\"'\"#C-F+6$\"\"(\"#B-F+ 6$\"\")\"#;-F+6$\"\"*F.-F+6$\"#5F-" }}{PARA 12 "" 1 "" {XPPMATH 20 "6% $\"$o&!\"#$\"$/#F%7,-%'WeightG6$\"\"#\"\"(-F*6$\"\"$\"#5-F*6$\"\"%\"#@ -F*6$\"\"&\"#=-F*6$\"\"'\"#D-F*6$F-\"#9-F*6$\"\")F@-F*6$\"\"*F--F*6$F1 F0\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"$5'!\"#$\"$p\"F%7*-%'Weig htG6$\"\"$\"\"*-F*6$\"\"%\"#7-F*6$\"\"&\"#D-F*6$\"\"'\"#A-F*6$\"\"(\"# G-F*6$\"\")\"#9-F*6$F-F@-F*6$\"#5\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"$(f!\"#$\"$!=F%7,\"\"#-%'WeightG6$\"\"$\"\"&-F+6$\"\"%\"#C-F+ 6$F.\"#B-F+6$\"\"'F5-F+6$\"\"(\"#<-F+6$\"\")\"#;-F+6$\"\"*F?-F+6$\"#5F )\"#6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"$%f!\"#$\"$i\"F%7*-%'Weigh tG6$\"\"$\"\"'-F*6$\"\"%\"#>-F*6$\"\"&\"#B-F*6$F-\"#K-F*6$\"\"(\"#?-F* 6$\"\")\"#5-F*6$\"\"*F?-F*6$F@\"\"#" }}{PARA 12 "" 1 "" {XPPMATH 20 "6 %$\"$7'!\"#$\"$%=F%7,-%'WeightG6$\"\"#F,-F*6$\"\"$\"\"'-F*6$\"\"%\"#:- F*6$\"\"&\"#D-F*6$F0\"#B-F*6$\"\"(\"#A-F*6$\"\")\"#8-F*6$\"\"*\"#5-F*6 $FGF/\"#6" }}{PARA 12 "" 1 "" {XPPMATH 20 "6%$\"$e&!\"#$\"$m\"F%7+-%'W eightG6$\"\"#\"\"%-F*6$\"\"$\"\"(-F*6$F-\"#?-F*6$\"\"&\"#H-F*6$\"\"'\" #F-F*6$F1\"#<-F*6$\"\")\"#7-F*6$\"\"*F,-F*6$\"#5F," }}{PARA 11 "" 1 " " {XPPMATH 20 "6%$\"$%e!\"#$\"$i\"F%7+-%'WeightG6$\"\"#\"\"$-F*6$F-\" \"&-F*6$\"\"%\"#>-F*6$F0\"#@-F*6$\"\"'\"#J-F*6$\"\"(\"#?-F*6$\"\")\"#< -F*6$\"\"*F-\"#5" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%$\"$!f!\"#$\"$t\"F %7+\"\"#-%'WeightG6$\"\"$\"#8-F+6$\"\"%\"#6-F+6$\"\"&\"#@-F+6$\"\"'\"# I-F+6$\"\"(\"#D-F+6$\"\")F2-F+6$\"\"*F5-F+6$\"#5F-" }}{PARA 12 "" 1 " " {XPPMATH 20 "6%$\"$z&!\"#$\"$+#F%7,-%'WeightG6$\"\"#\"\"&-F*6$\"\"$ \"\")-F*6$\"\"%\"#B-F*6$F-\"#>-F*6$\"\"'\"#D-F*6$\"\"(\"#9-F*6$F1F@-F* 6$\"\"*F?-F*6$\"#5F4\"#6" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "This \+ does seem to be close to random behavior. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 28 "Cluster s of plaintext blocks" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 323 "A second way to test for randomness is to fix a key and a starting plaintext a nd look at the aggregated result of encrypting a block of plaintext wo rds. We will look at a block of 32 words obtained by letting 5 consec utive plaintext bits vary. We start with some technical procedures fo r looking at a block of plaintexts." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 180 "makePlainBlock := proc(startPlain,shiftBits)\n loc al intShifts,i:\n intShifts := [seq(i*2^shiftBits,i=0..31)]:\n map (xorNbits,map(intToBitMessage,intShifts),startPlain,12):\nend:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "starter :=intToBitMessage(ra nd(2^12)());\nmakePlainBlock(starter,7);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(starterGQ-1010001011116\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6# 7BQ-1010001011116\"Q-101010101111F%Q-101100101111F%Q-101110101111F%Q-1 00000101111F%Q-100010101111F%Q-100100101111F%Q-100110101111F%Q-1110001 01111F%Q-111010101111F%Q-111100101111F%Q-111110101111F%Q-110000101111F %Q-110010101111F%Q-110100101111F%Q-110110101111F%Q-001000101111F%Q-001 010101111F%Q-001100101111F%Q-001110101111F%Q-000000101111F%Q-000010101 111F%Q-000100101111F%Q-000110101111F%Q-011000101111F%Q-011010101111F%Q -011100101111F%Q-011110101111F%Q-010000101111F%Q-010010101111F%Q-01010 0101111F%Q-010110101111F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 158 "We \+ want a procedure to take each entry in such a block, encrypt it with B aby DES, turn the ciphertext into a list of bits, and add the bits for each position." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 311 "testPla inBlock := proc(startPlain, key, shiftBits)\n local plainBlock, i, d istList:\n plainBlock := makePlainBlock(startPlain, shiftBits):\n \+ distList := [seq(0,i=1..12)]:\n for i from 1 to 32 do\n distLis t := zip(`+`,distList,bitStringToList12(BabyDES(plainBlock[i],key,5))) :\n od:\n distList;\n end:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 78 "Now we can test the procedure with a randomly chosen plaintext, ke y and shift." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 145 "key := int ToBitKey(rand(2^9)());\nstartPlain := intToBitMessage(rand(2^12)());\n shiftBits := rand(8)();\ntestPlainBlock(startPlain, key, shiftBits);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$keyGQ*0110111006\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%+startPlainGQ-1100100111016\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*shiftBitsG\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7.\"#<\"#6F$\"#;\"#:F'F'F$\"#=F$\"#9\"#>" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 263 "To do a better test we repeat the process from a nu mber of randomly chosen starting points. We can take the mean and sta ndard deviation of this distribution. We expect the distribution to h ave a mean of 32*.5=16 and a standard deviation of sqrt(32*.5*.5)=2.82 8." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 410 "distlist := []:\nfor i from 1 to 10 do\nstartPlain := intToBitMessage(rand(2^12)());\nd2li st := testPlainBlock(startPlain, key, shiftBits);\nprint(startPlain,d2 list, evalf(stats[describe, mean](d2list),3),\n evalf(stats[describe , standarddeviation](d2list),3));\ndistlist := [op(distlist), op(d2lis t)]:\nod:\ndistlist;\nevalf(stats[describe, mean](distlist),3);\nevalf (stats[describe, standarddeviation](distlist),3);\n" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&Q-1000001110106\"7.\"#>\"#9\"#;\"#@\"#\"#7\" #;\"#6\"#A\"#F&F)F)\"#8 \"#=F&F($\"$o\"!\"\"$\"$x\"!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&Q-0 100100010106\"7.\"#9\"#;\"#C\"#:\"#=\"#<\"#7\"#?F(\"#6F*F)$F+\"\"!$\"$ 'R!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&Q-0000100110106\"7.\"#8\"#= \"#7\"#<\"#;\"#>\"#:\"#@\"#5F'F'F*$\"$h\"!\"\"$\"$-$!\"#" }}{PARA 11 " " 1 "" {XPPMATH 20 "6&Q-0101001011116\"7.\"#>\"#<\"#:\"#7F&\"#8F(F(F'F &F&\"#?$\"$n\"!\"\"$\"$a#!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&Q-001 1111011006\"7.\"#@\"#=\"#:\"#?F(\"#8\"#BF*\"#9F'F*\"#6$\"$i\"!\"\"$\"$ h$!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&Q-0111111000016\"7.\"#<\"#? \"#;\"#8F)F)F&\"#9F&F&\"#:F&$\"$e\"!\"\"$\"$3#!\"#" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&Q-1101001010106\"7.\"#<\"#8\"#=F&\"#;\"#>F&F(\"#:F&\" #9F,$\"$i\"!\"\"$\"$y\"!\"#" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7dr\"#> \"#9\"#;\"#@\"# " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 4 "" 0 " " {TEXT -1 25 "Pairs of plaintext blocks" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 134 "A final way that we will look at the random behavior is \+ to consider pairs of plaintext words that differ by a fixed but random amount." }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 0 "" }{TEXT 257 47 "Coun ting the number of bits changed in each wor" }{TEXT -1 1 "d" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 96 "We start by looking at how many bits are \+ changed between the ciphertexts of a pair of plaintexts" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "key := intToBitKey(rand(2^9)());" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$keyGQ*0000001106\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "shiftWord := intToBitMessage(rand(2 ^12)());" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*shiftWordGQ-10111101001 16\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 93 "firstWord := intToB itMessage(rand(2^12)());\nsecondWord := xorNbits(firstWord, shiftWord, 12);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*firstWordGQ-0101111100116 \"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%+secondWordGQ-1110001000006\" " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "cipherDiff := xorNbits( BabyDES(firstWord,key,5),BabyDES(secondWord,key,5),12);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%+cipherDiffGQ-0010100011016\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "diffCount := addList12(bitStringToL ist12(cipherDiff));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%*diffCountG\" \"&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "Now we create a procedure \+ to do this with a bunch of pairs" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 490 "pairShiftCounter := proc(key, shiftWord, rounds, num Pairs)\n local countList, firstWord, secondWord, cipherDiff, i:\n \+ countList := table():\n for i from 1 to numPairs do\n firstWord := intToBitMessage(rand(2^12)());\n secondWord := xorNbits(first Word, shiftWord, 12);\n cipherDiff := xorNbits(BabyDES(firstWord, key,rounds),\n BabyDES(secondWord,key,rounds),12);\n c ountList[i] := addList12(bitStringToList12(cipherDiff));\n od:\n c onvert(countList,list):\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 184 "countList := pairShiftCounter(key, shiftWord, 5, 100);\nstats[t ransform,tally](countList);\nevalf(stats[describe, mean](countList)); \nevalf(stats[describe, standarddeviation](countList));" }}{PARA 12 " " 1 "" {XPPMATH 20 "6#>%*countListG7`q\"\"(\"\"'F'F'F'\"\"&F(\"#5F'\" \")F(F*F(\"\"$F'F'F(F'F'F(F'F&\"\"#F&F*F+F'\"\"*F*F*F&F'F'F'F'F&F'F'\" \"%F,F*F.F'F'F)F&F'F'F-F-F.F'F*F*F(F(F&F'F&F(F&F*F'F&F*F(\"\"\"F&F(F*F *F(F*F-F'F(F'F'F(F+F*F(F*F(F*F)F*F&F&F(F&F&F'F*F(F+F-F'F'F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7,\"\"\"-%'WeightG6$\"\"#F(-F&6$\"\"$\"\"%-F &6$F,F+-F&6$\"\"&\"#=-F&6$\"\"'\"#I-F&6$\"\"(\"#;-F&6$\"\")F2-F&6$\"\" *F1-F&6$\"#5F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+++++j!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+/kb< " 0 "" {MPLTEXT 1 0 0 "" }} }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 55 "Counting the number of words fo r which a bit is changed" }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 89 "The ot her way of arranging the data is to look at how many pairs change a pa rticular bit." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 491 "pairShift Counter2 := proc(key, shiftWord, rounds, numPairs)\n local countList , firstWord, secondWord, cipherDiff, i:\n countList := [seq(0,i=1..1 2)]:\n for i from 1 to numPairs do\n firstWord := intToBitMessa ge(rand(2^12)());\n secondWord := xorNbits(firstWord, shiftWord, \+ 12);\n cipherDiff := xorNbits(BabyDES(firstWord,key,rounds),\n \+ BabyDES(secondWord,key,rounds),12);\n countList := zip(` +`,countList,bitStringToList12(cipherDiff));\n od:\n countList:\ne nd:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "countList := pairShi ftCounter2(key, shiftWord, 5, 100);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%*countListG7.\"#[\"#X\"#bF&F&F&\"#^\"#U\"#\\F(\"#W\"#S" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 129 "stats[transform,tally](countList); \nevalf(stats[describe, mean](countList));\nevalf(stats[describe, stan darddeviation](countList));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7*\"#S \"#U\"#W\"#X-%'WeightG6$\"#[\"\"%\"#\\\"#^-F)6$\"#b\"\"#" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#$\"++++vZ!\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #$\"+rqL*R%!\"*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 140 "It should be \+ noted that the expected mean with 100 pairs of plaintext is 100*.5=50 \+ and the expected standard deviation is sqrt(100*.5*.5)=5." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 87 "The ways we have gathered data can obviously be adapted to othe r cryptographic systems." }}{PARA 0 "" 0 "" {TEXT -1 77 "One can also \+ do more sophisticated statistical analyses on the gathered data." }}} {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 }