Addition, Multiplication, and Division in Galois Fields GF(2^m)

[00:00:01]okay so let's look at a topic called a gawa or a gallows field and we're going to perform some operations addition multiplication and division and hopefully we'll be able to understand how we use gallows fields to be able to simplify our our computation with inside cryptography and in areas like data communications before we do that we need to understand what a group a ring at the field actually is so with and within cryptography we define what's called a finite field or our gallows field or g f the number of elements that we hold becomes our gallows field number so in this case we might have seven uh elements that's a finite field of seven elements and what should happen is that we form a ring with those uh elements so that we never go outside of the ring we will ring round for our operations are roll over so within our finite field uh in this case we have seven elements so we might have uh an object or an entity a and another one b and we're going to map that into another group through some sort of operation and it's this operation that defines our field to make a field then we must perform certain operations so additive we might take an entity in one group add some add another one to it and then we'll map to some another value with inside the the the ring and in cryptography we need to make sure that there is unique mappings from one group into another we can also provide a subtraction we might subtract a from b and that will map into our our group we should be able to multiply and also divide and then we have the operations the a something b is equal to b something a there and that operation might be add subtract multiply or divide it doesn't matter if we do a something b or b something a and we also get the operation where b something c something a is equal to a something b something c and we could replace these operations here and still get the same result another operation that we need to perform is the inverse where we take an entity from our group and then whenever we perform an operation such as a multiply and we take the inverse then the result will be one okay so our gallows field allows us to be able to limit the number of entities that we have within our group and then perform these operations within our finite field so with the gallius field we identify we can have two different types we can have a gallows field of p where p is a prime number so we might have gf of 7 or 2 or 3. so with a gallows field of 2 we only have two entities a zero or a one okay so we might take a and b either a zero or a one and we'll map to an output of z and that's also equal to zero or a one so a gallows field is like binary operations but on a single bit value the other uh gala gala s fields is where we take a prime number and raise it to a power of m in this case we'll have uh p a prime number to the power of m so what example here is 2 to the power of 4 will give us 16 different elements we could go they could go for example from 0 up to 15 and because we have a ring we will go round again and the great advantage of this is that it limits the number of bits or the number of uh elements that we're operating on at a time so it should significantly reduce the complexity and the speed because we're only looking at very small elements the gaf of two is very common and is often known as modulo 2 operations as we'll see in a little minute so with module 2 operations we basically just have two simple things we have an xor or we have a multiplication operation this is known as xor and this is known as an and or a multiply operation this is also known as an add operation but the thing with modulo 2 is that we don't have any carries so normally when we would do our adding we would have a carry over for each of the the units but in module 2 we only look at one bit value at time and the same goes for our and operation so this keeps it very simple when that we don't have to worry about the carry operation that we have so in modulo 2 edition it's similar to an adder but we forget about the carry over from the one plus one so one exclusive r1 gives us zero zero exclusive or zero because the zero zero exclusive r with a one gives us one one and a zero gives us one and one and the one gives us zero with modulo two we ignore that there's a one carried over because normally we would have a one here but we ignore that with the multiplication that's with the and operation a zero times zero gives us zero zero times one gives us zero one times zero gives us zero and one times one gives us 1. if we look at addition when it comes to multiple bits we take each one at a time so 1 add 1 gives us 0 and we forget about the carry now 1 0 gives us a 1 and so on and we only look at the columns there we never look at the carry that we would do in normal addition with the multiplication 1 times 1 is 1 1 times 0 is 0 and so on here we have a 1 times 1 so it gives us this one there and with this we keep it simple and it can become fast and the great thing with this is that we can run these in parallel these operations because we're not depending on the carry forwards and but that we would normally have in our normal addition and multiplication so within this uh gallows field we can have 2 to the power of m so 2 is the prime number 2 to the power of 4 will give us 16 different elements and we can then represent our bits as a polynomial equation so if you remember that a polynomial equation looks a bit like this 5 plus 2 x squared plus 4 x cubed and so on these are polynomial powers that that we have our field here what we have is that we can represent our bit patterns with a polynomial value and then the advantage with that is that we can operate as with polynomials on our our calculations so in this case we have our ones and that's x and that's x squared x cubed and so on so in this case one zero zero becomes x squared one zero 1 becomes x squared plus 1 1 1 0 becomes x squared plus x and we can see we can represent bit values as a polynomial value then when we're adding if we're adding x squared plus x squared that becomes a zero because they cancel each other out as we have with xor operations so it's with these operations that we can then perform our adding and multiplying operations okay so let's take an example where we have a equal to one one or decimal 7 that will be x squared plus x plus 1 and the b value is x plus 1 which is 0 1 1 and binary and then what we have is a bit pattern called a primitive in this case uh it's called an irreducible primitive and it's a bit like a prime number in in our normal uh a a representation of integers if we have a value of 16 it's equal to 2 times 2 times 2 times 2 14 becomes equal to 2 times 7.

[00:12:08]every value is represented by the multiplication of prime numbers in this case our primitive is a value that's like a prime number it cannot be factorized into other polynomials so we're using a primitive here and what we use that primitive is that if the if the value of the output goes above our limits for the powers then we will divide it by this primitive to be able to get a value which will be within our polynomial space and i'll show that in a little minute so to add it's quite easy because it's it's we add the powers and we have x plus x here these will cancel out and then we'll have then we'll have a 1 there and again 1 plus 1 will cancel out so our end result is x squared now if we multiply we multiply remember multiply that one by that one that one by that one that one by that one that one there and then there and then there so that gives us x times x is x cubed x times 1 is x squared x times x is x squared and so on and now we see that these two cancel out and these two cancel out and we get the value of x to the power of three plus one there is no need for us to develop to divide by the primitive because we are constrained within the polynomial range and the value here is is is less than the polynomial range so we don't need to divide by the primitive so here's here's the results here that we get there's a primitive there's the a and the b value and when we add we get x squared and when we multiply we get x cubed plus one if you look at our code this is the code that will allow us to do this this is our python code and we've got various operations so we're representing our our values as integer arrays here and the same with our primitive we then convert them into the gallows fields here with this method and then after that we can then basically just operate on them with our arithmetic operations okay so we can have a look at this code okay so this is the example here where we have 1 1 1 and 0 1 1 and this is a primitive here we just run that there and there's the output that we get there just to show that we can change that there we go but this is the value here that we get okay so the code that we're using is this code here if you want to see this running then there's a site here but what about the divide operation where we're dividing a by b so for this what we do is that we find the inverse of b multiplied by a so that's equivalent to a divided by b but we take the inverse element and as we have with our field we should be able to find the inverse of our polynomial so in this case we have that and our python program has found out that the inverse is x cubed plus x squared plus x and then we multiply that out and we should get this here so from this we can see that x to the 4 cancel that x to the 3 that cancels but you can see there's still another one there so that will be okay and then x squared let's cancel that there and then we end up with x to the 5 x to the 3 plus x but the result that we get isn't that the reason for that is that we have now a power which is greater than our our primitive power of x to the four so we now take that value and we will divide it by our primitive value and take the remainder as the result so if you remember your long division so x to the power 4 plus x plus 1 goes into x to the 5 plus x to the 3 x times then we multiply that to give x to the five multiply that by that x squared that by that is x so then we subtract them subtract look at that look at that and then that will be removed so we'll end up with x cubed plus x squared which is the result that we have here okay so that's the add the subtract is just the same as as add multiply uh we've seen the operation and then the divides in here so now let's look at another one where we will end up in the same way with a power great greater than or equal to x to the power of 4 when we multiply so with this one we'll take x cubed which is uh 1 x to the 3 you know x to the 2x to 1 and those ones so that will be x to the 3 and then we'll take b as x squared plus one x squared plus one and we'll take the same primitive and we have a gallius field of two to the power of four so our adds it's quite easy it becomes x cubed plus x squared plus one so that's that one correct there now our multiply becomes x cubed times x squared plus 1 and then that becomes x to the 5 and then we'll have x 3. so now we have a power which is greater than x to the power of 4. so we now need to divide that by our primitive so again we do the same x to the x to the power of 5 plus x to the power of 3 divided by x to the power of 4 plus x plus 1 that goes into that x times so we end up with x 5 x squared plus 1 and then we'll subtract them we get nothing here that becomes x to the power of 3 that becomes x to the power of 2 and that becomes x that just becomes x so the minus is just the same as a plus in modulo 2.

[00:20:15]so we can see here that divide operation it gives us this result uh here okay so it's in this way we can make sure that that our values we can do our multiply so this is the multiply in here and we could do the same as we did before with the divide we would find the inverse and then we multiplied the inverse by our a value and then again we'd have to divide by the primitive to give us this result uh here and one example of using gallius fields is an aes encryption and the advantage with this is that we only deal with eight bit values at a time so we operate on a byte value so we end up with a gallius field of two to the power of 8 and then we can represent our values in the form of a polynomial the primitive that's actually used in es is this one here and this is the value that's obviously used to be able to constrain the values that we have so this is the great advantages that we can make our operations run in parallel but only on eight bit values which keeps the circuitry and the speed fast as opposed to running on public key encryption which can take hundreds or thousands of bits at a time okay so that's been an introduction to addition multiplication and division in galvest fields of gf of 2 to the power of m