Operations in Galois Field

In the field of cryptography, galois field has some interesting applications. An important feature of this field is it is a finite field. In simple terms, whatever be the number of operations performed on a set of inputs the output will be in a fixed range. This itself is very useful for us as with the increasing complexity of encoding of data, it is very important for it to not occupy large amount of space yet retain its complexity.

Algebraically, galois field , named in the honor of Évariste Galois, is a finite field consisting of finite numbers which is called its order. You can find information on what constitutes a galois fields and its applications all around the internet. One interesting stuff is elliptical curves over finite field. This has separate field in cryptography called the elliptical curve cryptography. Do check it out if interested. But I suggest understanding galois field before jumping into it as it gets too gibberish and alien if not without a proper foundation.

What I am going to write as a part of this blog is two operations of this field namely addition and multiplication and their implementations as a code.

Addition in Galois Field :

Let us first consider a galois field. An example of such a field will be modulo of a prime number. It is quite often used in cryptography due its difficulty in discrete logarithm problem.                                                                                        ( link : http://en.wikipedia.org/wiki/Discrete_logarithm).

Let us consider the galois filed to be 2m usually represented as GF(2m). The elements of this field can be represented as polynomials.

F = a02m-1+a12m-2+…+am-12+am       with all a’s belonging to {0,1}.

Any number belonging to this field can be represented as above. So basically a’s are series of binary bits. So to represent a number belonging to this field say GF(28), we create a variable of 8 bits. It can represent all the values belonging to this field.

Say we want to add two elements of this field, algebraically it is the sum of the two elements(polynomials) and them coefficient arithmetic mod 2 applied on the polynomial. This could also be expressed as xor of the respective binary bits of the two elements. How ? Just try to add the two elements in their binary form. We see that sum of two 1’s or two 0’s is 0 else it is 1. That is exactly the function of xor. Hence for addition of two elements of the field we can just get it done by applying XOR ( ^ ) on them.

Computationally, Ele1 + Ele2 in GF(2m) = Ele1 ^ Ele2.

Next comes multiplication.

Multiplication is performed more tediously. For the multiplication of two polynomials(elements) f(x) and g(x) we apply mod of a irreducible polynomial of this field n(x) of atleast degree m over their product.

What is a irreducible polynomial? If a polynomial can only be divide by itself and constants then it is called an irreducible polynomial.

This is done to ensure that the product is in the range of the field. This is called as reduction modulo.

So the result of their product can be written as = ( f(p) * g(p) ) modulo ( n(p) )  for GF(pm). We can see that the product depends on the n(p) we choose.

Let me show this using a small example.

Consider the field GF(28). Let us take the product of 24 and 61 in this field with our acting irreducible polynomial as n(p) = 28 + 26 + 23 + 22 + 1.

So product = (24 * 61) mod (n(p))                                                                                             =  ( ( 24 + 23) * ( 25 + 24 + 23 + 22 + 1) ) mod (n(p))                                                 =  ( 29 + 28 + 27 + 26 + 24 + 28 + 27 + 26 + 25 + 23) mod(n(p))                                 =  ( 29 + 2.28 + 2.27 + 2.26 + 25 + 2.24 + 23) mod(n(p))                                           =  ( 29 + 25 + 24 + 23 ) mod(n(p))

Now we divide 29 + 25 + 24 + 23 with 28 + 26 + 23 + 22 + 1. We get the remainder 27 + 25 + 2 which is nothing but 162.

Now let’s see how we can convert this into a working code which calculates the product given two polynomials and the irreducible polynomial. Let us see if we can simplify the above steps.

Now given f(x) = x4 + x3 and g(x) = x5 + x4 + x3 + x2 + 1 ( in this case x=2 ).

f(x) * g(x) can be represented as f(x) * (x5 + x4 + x3 + x2 + 1) mod n(x)                                                            =  ( f(x) * x5 ) mod n(x) + ( f(x) * x4 ) mod n(x) + …

We can start calculating f(x) * x mod n(x) for every iteration ( it becomes f(x) * x after 1st iteration, f(x) *x2 after 2nd iteration  and so on ) and use that value into our result whenever it is required. ( we don’t need all products .. just the ones specified by g(x) i.e. in the above case, we need f(x) , f(x)*x2, f(x)*x3, f(x)*x4, f(x)*x5. So every iteration we just need to calculate the updated f(x) * x.

Another observations is x8 modn(x) =  x8 mod ( x8 + x6 + x3 + x2 + 1) which is nothing but (x6 + x3 + x2 + 1). We can utilize this in our calculation.

Calculating f(x) * x :

Say f(x) = a7a6a5a4a3a2a1a0. If a7 is 0 then f(x) * x will not be above the range and hence the remainder is nothing but f(x). The problem is when a7 is 1. Then f(x) * x would become 1a6a5a4a3a2a1a00. This modulus n(x) would be               (x8 + a6x7+ a5x6+ a4x5+ a3x4+ a2x3+ a1x2+ a0x1) mod n(x) )                                i.e. (a6x7+ a5x6+ a4x5+ a3x4+ a2x3+ a1x2+ a0x1) mod n(x) ) + (x8 mod n(x))

The first part is within the range of our field so it remains the same and the second part we know will be n(x) – x8 ( calculated earlier).

So our result is a6a5a4a3a2a1a00 ^ ( x6 + x3 + x2 + 1).

So here’s a program which does the above :

uint8_t r = 0, t;
while (a && b) {
    if (a & 1)
    r = r ^ b;
    t = b & 0x80;
    b = b << 1;
    if (t)
        b = b ^ 0x4d;
    a = a >> 1;
} 

What does the above algorithm do ?

At every iteration, it checks if the most significant bit of b is 1 before multiplying it with x ( i.e. XOR with 0x80 = x^8). If it is 1, then it xors with n(x) – x^8. In our case, x6 + x3 + x2 + 1 is represented as 0x4d ( hexadecimal format ). If we need this result it stores it in our r variable ( a & 1 –> indicates the coefficient is 1 and that we need that multiplication) else continues with the calculation until a is zero.

Let us run this on our example 24 * 61 mod (x6 + x3 + x2 + 1). Let a = 24 and b = 61.

a) We don’t need this value. Hence continue. 00111101(61) doesn’t have x7 coefficient. Multiplies it with x. The changed polynomial is 01111010. Convert 00011000(24) into 00001100.

b) We don’t need this value. Hence continue. 01111010 doesn’t have x7 coefficient. Multiplies it with x. The changed polynomial is 11110100. Convert 00001100 into 00000110.

c) We don’t need this value. Hence continue. 1111010 has x7 coefficient. Multiplies it with x. The changed polynomial is 11101000 ^ 01001101 which is 10100101. Convert 00000110 into 00000011. We don’t need this multiplication. Hence continue.

d) We need this value. Hence result is 00000000 ^ 10100101 = 10100101 . 10100101 has x7 coefficient. Multiplies it with x. The changed polynomial is 01001010 ^ 01001101 which is 00000111. Convert 00000011 into 00000001.

e) We need this value. Hence the result is 10100101 ^ 00000111 = 10100010. 00000111 doesn’t have x7 coefficient. Multiplies it with x. The changed polynomial is 00001110. Convert 0000001 into 00000000.

f) a is zero therefore end and return the result.

Therefore our result is 10100010. This is nothing but 27 + 25 + 2 = 162.
Tada!! The above algorithm works as galois field multiplier. This algorithm is called as Peasant algorithm.

The complexity for the above algorithm is O(logn). We can further improve this and reduce the time taken for calculation which will be discussed in the future blogs. That’s it for today. Hope you all have a wonderful week !!

Advertisements