Feistel Cipher - Computerphile

I'm excited for this one we're going to talk about feistel networks I love fossil networks they're brilliant I they're one of those things in cryptography where you just think wow that's very clever that's really elegant and it's not even that complicated and yet you just think that's that's great the fossil network was designed roughly around the 70s when horst feistel who worked for IBM who was a german physicist with the NSA he helped develop the data encryption standard des right now des was as we know from a previous video were placed by aes eventually mostly because of its short key lengths but des a structure of des is something called a feistel cipher or a feistel network and there are a few of these around to fish for example is a feistel cipher 5.so ciphers see use in padding schemes like the padding scheme used for digital signatures on certificates feistel ciphers are used for key schedules they use for in all over cryptography and they're very very cool so I what I wanted to talk about today all right so a feistel cipher is not actually a cycle in and of itself it's essentially a kind of framework for building encryption algorithms it's a structure and then you put in some encryption rounds and a key and things like this and then it turns it into a cipher for you and it has some really neat properties so I'm going to draw it out and then we'll talk about the interesting properties that it has so you start with a block and we're going to split that block in two and then we're going to take this as a right-hand side and this is the left-hand side we're going to take the right-hand side down we're going to put it through some kind of function right which is going to be some kind of pseudo-random function like a hash or an encryption round or something like this okay take out here we're gonna XOR it with the left and then we're gonna bring the left down and we're going to bring the right down here and this is your next block so when you say left you will mean the left-hand side of that block on the right-hand side it have to be exactly half ah very good question so in this case yes but in general no you have unbalanced feistel ciphers where the left and the right are different sizes but for this demonstration they're going to be the same size as near as I can draw it I'm not very good at drawing so the next round is exactly the same we take whatever is new right is we bring it round we go through f we XOR it with the left and we come down here like this and so on and you can repeat this process as many times you like for however many rounds and then at a very end after the last round you flip the output like this now this is a structure for encryption in a sense that you can put in any Fe R and you sort of build yourself a cipher now this effort obviously needs to be somewhat reasonable but what's so incredibly clever about this encryption algorithm is how you decrypt it to decrypt using the same faster cipher you encrypt by putting your block in here it goes through here it goes through here it goes through here and it goes through as many rounds as you want and you get some output to decrypt it you pick that up and you put it in the top and you run it again and even if this F is a one-way hash function that can't be reversed that still decrypts it what I mean like this is this is why I love faster ciphers so we're just going to do it we're going to start with Ln R and we're gonna work through and we'll see that it does actually reverse itself right which is just amazing I mean maybe you've seen a farce inside for maybe nobis happens like I think when the first time I learned about this I thought that is that it's awesome so let's do this this is the left this is the right now for the sake of argument they're the same size in this one the light is going to come down here and it's going to go through this function so we're going to put in a key into this F and with a lot more secure to make these a sub key so lots of different keys for each around so it's going to be key one this is going to be key to like this this F is a round function that combines whatever comes in with the key and mixes it up and sends out here this R comes through this F yeah and it's ex-ored with this l and this comes down to here so this element is L X or F with R and K 1 so I mean that's going to look like gibberish if I like I said this side is fairly straightforward the artists come straight down and turns into and off like that so let's do the next round this is going to come down here and go through here and then it's going to be X sword with this R so this output here is our X or F of this which is L I'm going to run out of space L X or F of rk1 of k2 like that that is that right I think it's what maybe it's a good thing that we didn't do three rounds or four rounds of this because this could take me quite a while by hand this one is going to get copied down so this is going to be L X or f of r and k1 now both of these will look like gibberish we're going to switch them round here I won't draw them in quite yet right but this one comes down here and this one comes down here feel free to animate it sure thanks for that okay so now we're going to see how we can decrypt this back to LMR and all we have to do is take this put it in the top and we have to swap our sub keys around because of course the rounds are happening in a different order so I'm going to draw this exact same structure again on the next piece of paper so that we have something new to work on otherwise I'm going to get very confused so this could be a competition how fast can you draw a feistel cipher from memory so go that I mean they're not nearly wide enough for me to fit myself in all right let's go again I think that's what you know so the keys need to be in a different order so this is going to be k2 coming in here and this is going to be k1 coming in here reversing these keys you know I wouldn't lean not to much important that will be a list of data or something like that very straightforward all right so let's put let's copy our data our cipher text in we thought we're going to do do that and plug them in like this see what I'm doing right so I'm going to draw them in to bear with me this one is going to be over here ah X or F of L X or F are k1 k2 and we'll just pretend that green eyes a little bit further along okay and this one is just L X or F of our k1 and then we're going to see what happens can you remember what it was that's really interesting about X or if you do it again the second time it's the reversible thing right it's a reversible thing that's the key to this whole thing when you ex or something with the same thing again it undoes it okay so what happens here is L F of our k1 is going to come through here and turn into F of L F of our k1 k2 which is this bit so that's going to come in XOR with this and we're just going to get our out again here this gets copied down here so L X or F of our k1 so let's go again our comes in here it becomes F of our k1 X or with this this becomes L or gets passed down here L goes to here or goes to here and this will work for any number of rounds and for any round function all right which is super cool and it's going to be a combination of all of these so this one times this one plus this one times this one plus this one times this one plus this one times this one and then we repeat this process for each of the values so we're taking bits and bytes from all of these in this column jumbling them up moving them around shifting them and there was a reverse inverse matrix

Channel: Computerphile

Views: 165,059

Rating: 4.9756126 out of 5

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Dr Mike Pound, Horst Feistel, Cipher, Cryptography, XOR, 4K, UHD

Id: FGhj3CGxl8I

Length: 7min 30sec (450 seconds)

Published: Wed Feb 19 2020