Random Numbers with LFSR (Linear Feedback Shift Register) - Computerphile

well i thought we'd talk about something um which you know i've been looking into anyway because um a part of my cryptography teaching but it's the linear feedback shift register now what i really like about them is it's unbelievably simple in structure and yet it can produce incredibly complicated seemingly output which i think is really really cool they're used a lot so they're used in things like random number generators they are used to an extent for cryptography as well as elements of stream ciphers they're also really easy to code right and we'll have a look at one later an lfsr or a linear feedback shift register is just a set of bits and we're going to have some rules about what we do to move those bits around right so let's start with one that's let's say of length four okay so i'm going to draw my little shift register here right and i'm gonna kind of initialize these at random so i know one zero zero one all right so this is four bits each one can be a zero or a one and um this outputs the bit at the end so this is going to be outputting one and this is called the state so let's see what do we do with this to make it more interesting because at the moment it doesn't do anything well what we're going to do every time we iterate we're going to replace the state with a new one and we're going to begin by shifting everything to the right so 1 0 0 1 shifted 1 to the right becomes 1 0 0 the one disappears and then we have to have something to go in here if you just did this in programming it would become a zero but this is a linear feedback shift register so what we're going to do is feedback some linear combination of these which we call taps right so i'm going to say let's say take this one and this one we're going to xor them together do you remember about xor right and then they're going to come in here so xor is one or the other but not both right so xor of zero and one is one so that's going to be a one right and then this outputs a zero right and then we're going to iterate this over again right and so you can see that this has changed and it's going to change again it's going to change again and let's see how it goes so the next state we're going to shift 1 to the right so 1 uh 1 0 and then 0x or 0 is 0. we're going to go again so zero one one xord is one right so far so good so i'll work my way through these give me a minute because there's actually quite a few of them one zero one and that's zero one one and that's a one oh all ones that's exciting most exciting bit so far for me right let's keep going one one one and that's a zero we're getting there naught one one i mean if i made a mistake it we won't know until the end um and that's a zero and then a zero and this is zero zero one and that's a one right and we're finally thank goodness for that back at the beginning right which was our initial state now this is going to output a 0 a 1 1 0 1 0 1 1 1 1 0 0 0 1 so this is the actual output of our little random number generator so what's interesting about what i've just done right because it's just a load of zeros and ones well the cool thing about this is it took quite a long time to repeat itself and in fact it actually took the maximum amount of time possible if you've got four bits then there are two to the four possible zeros and one combinations you could have but all zeros doesn't appear because you can you can imagine that if you had all zeroes in here it would always stay as all zeros because zero x or zero is zero you'd never get anything interesting so zero never appears all zeroes but this is a period of 15 i think let's check one two three four five six seven eight nine ten eleven twelve thirteen fourteen fifteen oh thank goodness for that um so it's a period of fifteen and that's the maximum of that that's the maximum period for this little shift register here right so actually if you have a shift register which is n bits then the actual period the maximum period you could have is two to the n minus one right which is two to the n all the different combinations of notes and ones minus one which is the zeros which you wouldn't have now you might what what i really what i think is cool about this right is this is an unbelievably simple structure there's nothing to this there's a shift to the right and a little xor and we've got all the possible combinations of notes and ones and this holds essentially for any length of bit of shift register so if i had a 100 bit shift register and i had these taps set up correctly i could go through every possible combination of notes and ones of length 100 before i cycled around again does tap stun for something or is it no taps is just sometimes the word people use for just tapping off these and coming in here right it's got nothing to do with plumbing to my knowledge could we make this more complicated right so let's suppose we had an internal state that started with one zero zero one again let's say we're going to we're going to come off three taps instead and come back round to the beginning right now it looks to me like that's better than that because there's more interesting xor going on it seems to be more powerful so let's whiz through this one we're going to shift towards shift to the right 100 and then one x or zero x or one is zero right so we're going to put that in here and then we're going to shift right again so 01 0 and 0 0 0 0. that's so far so good and then the next one is 001 and 0x or 1 x or 0 is one right and we've already found ourselves back at the beginning right now this is a deterministic random number generator in a sense that if you're in some state and you've got your rule you're always going to produce the exact same state that you had before right it seems obvious so this repeats itself after what one two three has a period of three so choosing these taps is quite important right now mathematically we won't dwell on some maths but there are mathematical ways to choose these taps in such a way that you can guarantee it will produce the maximum period for some lfsr of some length right and that way you can take a lot of the unknowns out of this you don't have to plow through two to the 128 different combinations of bits before you realize oh good it has got a long cycle right um so let's have a go at coding this up it's super straightforward these these um they're not hugely efficient in software because you have to spend a lot of time looping and shifting things around doing a lot of unnecessary xors in hardware you can imagine that you could literally just have some gates here and just do this and each of these could be a flip-flop and maybe that's a good project for steve to build at some point right the cool thing about lfsrs is they are unbelievably easy to program right because all you do is a bit of bit shifting and you basically done it a couple of exors um python allows you to do this python is a slightly odd language in a way to do bit shifting of things in because it has these arbitrary length integers but it works so let's have a go let's do our four bit a little little shift register let's not get too carried away right so state equals a binary value of 101. let's do 20 iterations to begin with so for i in range 20 that's so so far so good and then each time we loop we want to output a value which is you know the current last bit and then we want to um anyone do shifting in fact let's not output a bit let's just output the whole state because then we can see it and we can see the period and things like this i hate string formatting right so let's do a print and then we're going to print our state in binary format which in um we can use using a string format so it's going to be something like 0 4b dot format state right let's see if that works so that should print out our state 20 times but it's not actually updating anything because i haven't coded that so let's see yes it worked one zero zero ones it's the least interesting program ever let's keep going all right so now we need to actually update so what we'll do is we'll do a shift but we'll also we need to calculate the new bit so let's say new bit is equal to and then remember what we wanted to do was calculate some xor of bits one and bit zero we're coming from the right hand side all right so let's do an xor of the state xor is the hat operator in python and in many languages and we're going to also xor it with state shifted one to the right right so what's that doing well let's get my piece of paper if our state was one zero zero one and we're xoring that with our state shifted one to the right then we're xoring that with o one zero zero which means that the output is going to be one one o one but it's the last bit is the one we want so now we're going to just let's put my pen down before i draw all over my brand new laptop and it's permanent as well and then we're going to and that with one and just take the last bit right so that's our new bit now obviously all we need to do now is shift our state to the right and put our bit at the front so we're going to say state is equal to state shifted shifted one to the right okay and then we're going to all that which will essentially set our bit on the left-hand side with our new bit and we're going to shift that into the right position so that's going to be it's in the zero position one two three three three to the left just like that all right and i think that's done that's it so let's just put that out and see what happens uh and that's exactly right so what it does it starts with one zero zero one one one zero zero and it goes on and you can see down here somewhere 15 um iterations on we get one zero zero one right now in in actual fact what you wouldn't do is print out the state because the state doesn't change much between iterations it just moves one to the right only the left bit changes if you're actually using an lfsr for let's say a random number generator you wouldn't output the whole state because all the status is shifted to the right so it would look very similar each time so what we instead do is just output the last value so instead of printing out the whole state we'll just output the last bit so all we need to do is remove this and we'll just say we want to add print out state and one now in python it's very difficult to avoid putting a character turn on the end so i'll just put in end equals nothing right like that and let's try that um and you can see it just prints out now a little binary stream which we could theoretically use as a random number generator or we could use it as a i mean you'd be unwise to use it as a stream cipher but it could be a component of a stream cipher let's make a little bit of a bigger one because that's much more interesting right i'm going to now make 128 bit cipher instead so first of all instead of our state being just one zero zero one which is not very interesting let's make our state one shifted 127 to the left or one right and so that's going to be one zero zero zero one where it's 128 bits long right it's a much bigger lfsr and we don't want to um only output 20 bits so let's just do wild true and just break the whole you know just go on forever and we're still going to print out the state and we're just going to change our taps slightly so i happen to know a set of taps there's a few of different combinations obviously um for this particular lfsr are zero one two and seven if you x or those together then you're gonna get that whole maximum period of two to the n minus one so let's put that in there you go so what i've done is i've got the state which is you know shifted no times then shifted one time shifted two times and shifted seven times and one to get only the last bit and then we're going to do the same thing as before state is state shifted one to the right and then we're going to shift our new bit 127 positions to the left and put it right in on the end right now that should work i mean let's not verify it my coding live but if we if we run it it's just going to start printing out an awesome ones now this lfsr has a period of two to 128 minus one let's say for the sake of argument two to 128. this laptop given that it has to output to the screen is doing probably around a million bits per second we will probably be waiting for 10 20 times the lifetime of the universe before this repeats itself so i don't know how much sd card memory you've got on your camera what's the actual use for the system so these are used all the time for random number generators advanced versions of these are used for some of the most popular random number generators right the statistical randomness of these streams is really really good and what i mean by that is this will appear as random as just flipping a coin right so if you want to just generate coin flips this is a great way to do it this is not cryptographically secure because if you have a large portion of the stream you can just essentially solve a bunch of linear equations and recompute the lfsr generated it and then generate the next sets so it's essentially you can reverse engineer based on some output what the next bits will be which is exactly what you don't want if you've got a stream cipher but if you join some of these things together so let's say you have two stream ciphers that are xored together and maybe they don't always tick over and shift at the same time and things like this if you've got some non-linear combination of stream size of lfsrs then you actually can have something that's pretty pretty robust and this has been used in the past for mobile phone encryption and um you know the trivium cipher is based on this so they do see a lot of use and they're unbelievably quick in hardware which of course is really really useful for low power devices like smart cards and stuff like that do not try this at home absolutely only try this at home oh yeah that's a very good try this at home but not anywhere else at all in some sense remember when we talked about 3d images you could view rgb as in some sense 3d so the first plane is our r g and b or vice versa

Channel: Computerphile

Views: 94,521

Rating: 4.9720755 out of 5

Keywords: computers, computerphile, computer, science, University of Nottingham, Computer Science, Mike Pound, Dr Mike Pound, Random Numbers, Python, XOR, 4K, UHD

Id: Ks1pw1X22y4

Length: 13min 50sec (830 seconds)

Published: Fri Sep 10 2021