Simplified Data Encryption Standard (DES) Example

so let's look at the algorithm simplified death takes 8 bits of plaintext in and eight bits of ciphertext come out and has a 10 bit key it's really different it's longer than the plaintext block just to make it the steps in the algorithm work correctly and it does some operations with the plaintext and get some intermediate output and then it repeats all of those operations again so we say it goes through two rounds real desk goes through 16 rounds it repeats 16 times we start with a key and we generate some what we call sub keys or round keys that is will generate some keys that we use in different phases in the encryption so there's a key generation algorithm there's an encryption algorithm which will go through the decryption algorithm is essentially the same as encryption but we go backwards we'll see that so what we'll do we'll go through the key generation use an example and then encryption to seal the different operations used this tries to capture those three algorithms all at once in the middle are the steps used to generate keys from our original user chosen key that as the user chooses a 10-bit key then they apply some steps which we'll go through what they are this p10 shift pH shift p8 the output of those two steps are two other keys which we call two sub keys or two round keys k1 and k2 in the diagram why do we generate two sub keys because we said the encryption involves two rounds to two phases of who do something then repeat it and we'll use a different sub key in each round real desk does similar it generates sixteen sub keys every round that uses a different sub key but you start just with one original key to encrypt we take eight bits of plaintext in we do some operations IP F of K using key one a swap the same F of K using key two and some last operation we get ciphertext to decrypt we start with a ciphertext and we do the same operations as encrypt almost encrypt we start with this first IP operation will explain what IP stands for shortly to decrypt we do the same we apply the same function we apply the same swap here the same function again and the inverse operation and we get plaintext if you look closely the blocks for encrypt and decrypt are the same IP F of K swap F of K the inverse IP the only difference is that we use k1 and k2 in a different order for encrypt we'll use K 1 then k 2 to decrypt we first use K 2 and then K 1 where those values are the same let's go through with an example well you will refer to these slides as we go through the operation so I'll flick back through them the example we're going to go through is this one that is we're going to take those 8 bits of plaintext the user chooses the key which is a 10 bit value I just chose a random key here and we're going to encrypt that plaintext and hopefully at the end of the example we end up with those 8 bits of ciphertext that's what we're trying to I'm gonna write it down we'll go through each step and you can write it down but if you look I hope I included at the end of your at the end of the slides the printout of the example maybe we don't have a look because it's sometimes we it's easy to make a mistake in writing down the bits on page 95 you'll see the the example we go through the first thing we do before we do any encrypting we have to generate the sub keys or the round keys we start with our original key our 10 bit value and we're going to from that generate two other keys and then use them in the encryption and decryption so let's do the key generation steps first so we start with the user chosen key we start with what the key will denote as K and the value that we chose those 10 bits we chosen randomly 1 0 and just to make it easier to see that the bits of have a little bit of spacing so that that's the key that the user chooses it's the same one on the slides I hope yes ok 10 bit value and we need to generate two sub keys from that and the way that we do that is using these operations p10 shift pH shift pH so we need to explain what they are or in more detail shown here so this is the key generation algorithm we take ten bits in and the way that the arrows are marked they show the number of bits we'll do in each we'll pass between each step we apply an operation called P 10 P stands for permutation and this we do a permutation of those bits permutation is another word for transposition or rearrange so what p10 means we take ten bits in and then we mix them up that's we do a permutation that way that we mix them up is defined and fixed we always mix them according to the same rules so p10 is actually defined we'll see on the other slides it says move this bit to this position this second bit to this position so when you see a P later we'll see p8 it's also a permutation remember from classical ciphers substitutions and permutations LS is left shift so in binary we can shift the bits left LS 1 is 2 left shift by 1 take your bits shift them to the left where the leftmost bit becomes the rightmost bit he wraps around so like in hardware we can do a left shift on our bits but the left shift takes 5 bits in and produces 5 bits out so in fact we do is the output of p10 we split into two halves p8 is a permutation the shape of this box means that we're going to take 10 bits in and produce 8 bits out all right it's going to throw away 2 of the bits but rearrange the rest left shift 2 is do a left shift by two positions to the left take our five bits move them to the left so left shift is a permutation as well the 10 and p8 the 2p eights of permutations let's go through them so we're just mixing up the bits p10 you have to jump back between the slides is defined here so it's defined in the algorithm it's fixed it never changes the attacker knows what it is the way to read it we have 10 bits that come in we label them we can think the first bit the second after the 10th bit to come in in order what comes out the first bit moves to this position the third bit of the input becomes the first bit on the output the 10th bit on the input moves to the sixth position that's all that it's defining it so we take 10 bits in and we mix them up how do we mix them according to this permutation so let's do that on our 10 bits we've got 10 bits coming in and this case will we'll make it clear or we'll say that let's label them 1 2 3 so there are 10 bits that come in when we apply the permutation p10 using the key as input p10 it's going to produce bits that come out and from that slide the third bit on input is going to move to the first position the third bit on input moves to the first position so that is a bit one will be the first bit in the output the fifth bit moves to the second position we see the five here means the fifth bit from input becomes the second bit that comes out and the fifth bit was a zero zero comes out here and we keep doing that for the the rest what's the next one - is it bit - becomes a third one which was a zero so we're just mixing up these bits get seven which was also a zero bit four we will only draw this once we were not doing for all the permutations but just to highlight the approach therefore was a zero three five two seven four and then the 10th 10 one nine eight six bit ten nine bit one from all over here it's a bit messy eight and six bitte 10 was a zero bid nine was a 1-bit one was as it one bit eight is a zero and bit six is a zero please check that I'm when I make a mistake let me know we're doing is Mick those first ten bits up defined manner defined by Pete same way that the rail fence for the rows column cipher mixed up our letters the rail fence that we wrote them in three three rows for example and read off they're just rearranged us that will permit eights the bits yeah no P p10 is fixed so p10 is defined as part of in this case simplified des and the same in real des there's a P the cameraman the number but there's a permutation which is defined and always used this way so the when it we take these 10 bits in will always and the first step get these 10 bits will always mix them this way so we see that's very simple and you may question well is that secure we're just mixing up and the attacker knows how we mix them up so very simple operation but we need to question is it secure well we'll see on its own is not secure because the attacker can if they know the output they know the permutation they can easily find the input they can go backwards but when we combine it later with some other operations the substitutions will see that the final output is considered secure because the attacker cannot go backwards so this is the idea of combined simple operations yep I switched them did I 1:09 right yeah one becomes before nine right okay correct I put nine before one but I was lucky in that the they both be at once all right so good find my mistakes we get these ten bits we do the next phase of the key generation which is we split it into two halves the left half and the right half and in each half we'll have five bits do a left shift by one position on each half left shift just rotate the the bits wrap around where necessary that is now we consider in two halves to five bit inputs we'll do a left shift by one position on each half left shift just means that the the second bit becomes the first bit the third bit the second bit and the first bit on input will wrap around and become the last bit so note that we do it just on those five bits not on or ten and then we do a left shift on the second half so we move the bits to left so we'll be 1 1 0 0 that's these four bits and the first 0 will end up at the outside so now we have 2 5 bit outputs what's next join those two 5 bit values pass them into P 8 P 8 is another permutation so we're just rearranging the bits left shift is also a permutation what is P 8 go on the right direction sorry wrong way P 8 is defined here it's actually selecting permutate and as we start with 10 bits in one root of 10 bits one and two are discarded we just take the last 8 bits and rearrange them according to this fixed definition of P 8 so let's do p8 on those 10 bits you do p8 and tell me the answer the first two bits are going to be discarded and the last eight bits are going to be rearranged and that the six bit then a third bit then the seventh bit will come first six three and seven and if you keep going for a five ten nine before 8 bit 5 is a 1 and 10 and 9 are both zeros that is the output of p8 and importantly that is sub key k1 or the round key k1 is going to be using round one of our encryption algorithm so that's the value of k1 keep going so we just did p8 at the output of p8 is k1 but what we do to get k2 is we take the previous inputs to p8 do a left shift by two positions and then do p8 to get k2 so let's quickly do that so we'll keep drawing here we take this five values and do a left shift by two positions so we're going to continue with these five and do a left shift by two and that's easy this one will move to the middle position left shift by one two positions and similar we'll do a left shift by two positions on the right five bits and we have three zeroes and the two ones will end up at the end and then take those ten bits and do a p8 again the first two bits will be discarded we rearranged the last eight bits and see what you get p8 six three seven four eight five ten nine bits 653 that's seven and four but a five and the last of its ten or nine and that is k2 all we've done is taken our 10 bit user chosen key and rearranged it according to some fixed algorithm to get to size not so hard that was the easy part and note that the operations we did were all permutations or all-trans positions there were no substitutions there we always just took the same bits in and move them around left shift is a as a permutation p8 and p10 of permutations we're going to use k1 and k2 in both the encryption and they are used also in the decryption so if you receive ciphertext and you need to decrypt if you have the same key you'll generate the same two subkeys k1 and k2 so we use it together so let's do an encryption using our plain text from example and let's have a look at the encryption algorithm here's the details for ten minutes to finish our encryption we'll get started but as an overview we start with eight bits of plaintext we do an initial permutation IP means initial permutation so again it's a permutation it's fixed then this dark gray box is denoted F of K so together we say that some function we take the 8 bits in and produces 8 bits output this is what we call our round function this is one round of our algorithm and the input to that round will be k1 when we finish that round we swap the halves as W swap or switch and as we have two halves of bits and we swap them and then we do the same round function and the the second ray box that's here so exactly the same inside the gray boxes so they're the same functions here but we in the second round we use k2 when that's finished we do the inverse initial permutation in initial permutation is to find the inverse we'll see what that is so you'll see what it is and then we get eight bits of ciphertext out so what we'll do in the example is we will get to will go through the round function once we'll get to here and then I'll leave it to you to do the round function the second time take eight bits in an initial permutation and then we split the eight bits into two halves we'll take the right half and then apply these more operations on that right half EP XOR and others let's try we'll use k1 and k2 during this our plain text I'll just don't notice P the data that the user wants to encrypt we've chosen some values 8 bits of plaintext we do an initial permutation and like p8 and p10 that is also defined where is it here it is initial permutation just a permutation where the second bit becomes the first the sixth bit becomes the second and so on rearrange those bits - 6 3 1 bit 2 bit 6 bit 3 and bit 1 and then four eight five seven bit four eight five and seven the initial permutation is done before the the main function and the opposite is done at the end just before we get the cipher text in in real dest similar there's an initial permutation you do sixteen rounds and then you finish with a inverse initial permutation we split it into two halves so we'll note that we talked about the left half and the right half we will not use the left half yet we'll take the right half and do some operations on that what do we do the right-half the right four bits so that the line through were the four means we've got four bits here we apply these tips EP expand and permutate four bits in eight bits out so we're going to duplicate the bits but also a rearrangement at the same time expand and permutate we take four bits in one two three four and what comes out four one two three two three four one so each bit is duplicated on the upward of EP four one two three note we're working on the right 4 bits 1 0 0 1 4 1 2 3 bit for bit 1 2 & 3 4 1 2 3 and with those same 4 bits on the right half 2 3 4 1 bit 2 3 4 and 1 bit 1 this is actually the start of our function so here was the start of that gray box where we do F that function using k1 is important after they expand and permutate we've got 8 bits we XOR with the key 8 bits exclusive all with k1 k1 we generated in the previous algorithm so we're right down k1 and do an XOR and here's our first different operation key generation use permutate left shift which is also a permutation expand and permutate is a permutate it's a rearrangement of bits XOR is a substitution we're not just rearranging the bits we're replacing bits with other potential bits ok so this is our first substitution exclusive-or here so X or our value with k1 so if we remember k1 from before k1 was 1 0 1 0 0 1 0 0 and we XOR those values exclusive or what do you get remember your exclusive war if they are the same you get 0 if the bits are different you get 1 the same we get 0 same different different same same different different different we get our 8 bits out and then we split that again into two 4-bit values so that was a substitution or how do we know well it's definitely not a permutation because the input width is eight bits but four ones and four zeros the output has five ones and three zeros so we didn't end up with the same bits just mixed up sometimes it's hard to tell it was some replacement of a bit cell so that was a substitution operation and the next operation is also a substitution and we use s boxes in the same way that the permutations were defined we defined we define a special technique a way to replace some bits with other bits to a substitution and these are a key part in in the real desk design and even in other ciphers what we do we start consider the first four bits 0 1 1 0 I write it again over here we and it let's look at the sliders to find there s boxes so we're we're up to we just did the XOR we've got four bits on the Left four bits on the right the four bits on the left are going to be fed into S box s0 the four books on on the right are fed into S box s1 we're going to power on through for the next 10 minutes and finish this example and then we'll take a break after that let's do the s-boxes s0 and it's defined on this slide we have four bits in sync bit one two three four the S boxes s0 and s1 are matrices than they are defined all right so 4 by 4 matrices they are fixed everyone knows what the values are and the way that we use them is that the first and the last bit of the input determines the row of the matrix and the second and third bit determine the column of the matrix we look up that element and that's the output let's consider with our example the row the first and last bit 0 0 row equals 0 0 column the second and third bits 1 1 or you can think row in decimal 0 column 3 if we index our matrix starting at 0 so we have 0 1 2 3 rows 0 1 2 3 columns then we look up the element which is in row 0 column 3 row 0 0 in binary column 1 in binary look it up in the matrix of s1 what do you get his output oh sorry s 0 s 0 row 0 column 3 s 0 row 0 the top row column 3 the last column output 1 0 this value note that we index starting at 0 row 0 1 2 3 column 0 1 2 3 row 0 column 3 output 1 0 mmm yep okay so our input here we have 0 1 1 0 the the the rule is yes the first and last bit tell us it's which row number row 0 0 in binary or in decimal rows 0 sorry convert and the column is the middle two bits 1 1 or if I convert to decimal 1 1 is 3 ok so depends on how you want to think about it in binary or decimal so in in decimal that will be 0 and 3 we just convert so row 0 column 3 which is a fourth column we start index at zero the output will be this element and it's fixed it's always that value for that element 1 0 do it for s 1 with s 1 you take the other four bits you take these four bits apply into s1 the different matrix and see what you get with s1 we take the input is 0 1 1 1 row 0 1 the first and last bit column second and third bit 1 1 or in decimal 1 & 3 look it up in s1 Row 1 and column 3 Row 1 which is the second column column 3 the last column 1 1 comes out this element will not discuss the design of them yet we'll come back when we talk about this why is it like this we have four bits we're at this point we pass into p4 rearrange those four bits p4 is defined to four three one rearrange those four bits we have four bits one two three four rearranged where we have 2 4 3 1 bit 2 4 3 and 1 so we treat those four bits together we get 0 1 1 1 XOR with the left half from the original input where'd it go that is all of this started with these 4 bits we haven't done anything with these 4 bits so let's use them now take these and XOR with our 4 bits that we have currently that's the left half this was the right half expanded and permutated here why don't I'm sorry 1 1 0 1 sorry what 1 0 1 0 X or exclusive or 1 1 0 1 almost there grab the right half grab this half the original right half one zero zero one now we have to forbear values swap them swap the sides actually this is a SWAT operation which is quite simple these four bits will become the last four bits and these four bits become the first four that was actually and then I think we've done all operations necessary let's summarize what we did then we'll have a break we started with the initial permutation we took the right four bits expand and permutate XOR with the key k1 use the two s boxes s0 and s1 we get four bits out apply permutation P for XOR that with the original left half we get four bits out take the original right half and we're actually finished the round now we have eight bits that come out of the round before we do the next round we swap those two halves and then we repeat it all again starting from the expanded permutation you see what's inside the gray box is the same we do the same steps but we'll use K - we'll get eight bits out we'll do the inverse initial permutation and get ciphertext so we got to this point to finish what you do is now you start the set the round function using k2 when you finish that round function then you'll do the inverse initial permutation and you'll end up with eight bits the ciphertext and the eight bits you should get just by luck the two halves are the same and to give you a hint so we can have a break the inverse initial permutation is your homework find it what is it and to give you a hint the end of that function the input is this the end of function the round function using k2 you'll get these eight bits then you'll do the inverse initial permutation and then you'll end up with a ciphertext so your homework if you don't understand the steps you can do them for round two which is exactly the same as round one and then do the inverse initial permutation and we get ciphertext