Galios Fields — GF(2^n)
Galois Fields — GF(2^n)
In 1831, Évariste Galois died of duelling wounds at the age of 20 but left a great legacy. While he was a teenager, he worked on polynomials and laid down the principles of Galois theory, along with defining the concept of a finite field. In cryptography, the finite field is one of the major concepts and involves limiting the number of possible values to a limiting factor (p). The values of the field then range from 0 to p-1, and simply our bit operations.
As we have seen from the previous podcasts, that we map from one set to another for encryption, and then reverse back for decryption. For example, we might multiply by 15 and add 7. To map back, we will then subtract by 7 and divide by 15. But, what happens if we need to constrain the values of our integers into a given number of bits and perform simple modulo-2 operations?
A Galois field
Within a field, we can operate on values in the field using arithmetic operations. We can thus have an infinite field and where we could include all of the possible integers. A Galois field of GF(p^n) has p^n elements. Typically we use GF(2^n). And so GF(2⁴) has 16 values in the field. Let’s say we have GF(2^n) and have a number a∈{0,…,2^n−1}, we can represent it as a vector in the form of a polynomial:
a=a0+a_1 x+a_2 x²…a_{n−1} x^{n−1}
If we use a_n∈{0,1}, this is exactly the same as representing a binary number modulo 2^n. In this, x^n represents bit position n and a_n is the value of the bit at position x^n. If a bit is a zero at a given position, it will be not included in the polynomial equation.
First, let’s talk about modulo-2 operations. For this, an addition is:
0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 =0 (an EX-OR gate)
and for multiply we have:
0*0 = 0, 0*1 = 0, 1*0 = 0, 1*1 =1 (an AND gate)
So, 1011 can be represented by x³+x+1 and 1010 is represented as x³+x. We can then perform arithmetic operations on these polynomial values. So, to add two values of 1010+1100 we can represent this as (x³+x)+(x³+x²) and which is x²+x as we are using modulo 2 addition, and where x³+x³=0. With modulo 2 addition, 0+0=0, 0+1=1, 1+0=1, and 1+1=1.
An example of Galois Fields is within AES (Advanced Encryption Standard) and which uses a finite field GF(2⁸). With AES we operate on bytes (8 bits) in the form of b_7 b_6 b_5 b_4 b_3 b_2 b_1 b_0 and which are operated on a a polynomial of b_7x⁷+b_6x⁶+b_5x⁵+b_4x⁴+b_3x³+b_2x²+b_1x¹+b_0.
A few examples
Let’s take a few examples to illustrate this.
Example 1. For a=x²+x+1 (7–111b) and b=x+1 (3–011b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x² (4–100b), and for multiplication we get x3+1(9–1001b):
Add=(x²+x+1)+(x+1)=x²
Mult=(x²+x+1)×(x+1)=x³+x²+x²+x+x+1=x³+1
As we are using modulo 2 addition, then x+x=0 and x²+x²=0. As the power of the multiplication is not greater than x⁴ and above, there is no need to divide by the primitive polynomial. The following is a sample run:
a: 1x^2 + 1x + 1
b: 1x + 1
b^{-1}: 1x^3 + 1x^2 + 1x
p: GF(2^4) [1, 0, 0, 1, 1]
Add: 1x^2
Subtract: 1x^2
Multiply: 1x^3 + 1
Divide: 1x^3 + 1x^2
For the division, we determine the inverse of b and then multiply ny a. In this case we have a×b^{−1} = (x²+x+1)×(x³+x²+x)=x⁵+x⁴+x³+x⁴+x³+x²+x³+x²+x=x⁵+x³+x. As we have a higher power that the field, we now need to divide by the primitive (x⁴+x+1) and get the remainder:
__x______
x^4 + x+1 | x^5+ x^3 + x
x^5 + x^2 + x
--------
x^3+ x^2
This the result of the divide is then the remainder value of x³+x². You can try the example here.
Example 2. For a=x³ (8–1000b) and b=x²+1 (5–101b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x²+1 (13–1101b), and for multiplication we get x³+x²+x (14–1110b).
Add=(x³)+(x²+1)=x³+x²+1
Mult=(x³)×(x²+1)=x⁵+x³
Now we divide x⁵+x³ by the primitive (x⁴+x+1) and get the remainder:
__x______
x^4 + x+1 | x^5+x^3
x^5 +x^2+x
--------
x^3+x^2+x
Thus the result of the multiplication is the remainder of x³+x²+x.
a: 1x^3
b: 1x^2 + 1
b^{-1}: 1x^3 + 1x + 1
p: GF(2^4) [1, 0, 0, 1, 1]
Add: 1x^3 + 1x^2 + 1
Subtract: 1x^3 + 1x^2 + 1
Multiply: 1x^3 + 1x^2 + 1x
Divide: 1x^2 + 1x + 1
You can try the example here.
Example 3. For a=x³+1 (9–1001b) and b=x²+1 (5–101b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x² (12–1100b), and for multiplication we get x³+x+1 (11–1011b).
Add=(x³+1)+(x²+1)=x³+x²
Mult=(x³+1)×(x²+1)=x⁵+x³+x²+1
Now we divide x⁵+x³+x²+1
by the primitive (x⁴+x+1) and get the remainder:
__x______
x^4 + x+1 | x^5+ x^3+x^2 +1
x^5 +x^2+x
--------
x^3+ x +1
Thus the result of the multiplication is x³+x+1 (11- 1011b).
a: 1x^3 + 1
b: 1x^2 + 1
b^{-1}: 1x^3 + 1x + 1
p: GF(2^4) [1, 0, 0, 1, 1]
Add: 1x^3 + 1x^2
Subtract: 1x^3 + 1x^2
Multiply: 1x^3 + 1x + 1
Divide: 1x^3 + 1x^2
You can try the example here.
Example 4. For a=x²+x+1 (7–0111b) and b=x³+1 (5–1001b) with a primitive of x⁴+x+1 (GF(2⁴)), for addition we get x³+x²+x (14–1110b), and for multiplication we get x³+x (11–1010b).
a: 1x^2 + 1x + 1
b: 1x^3 + 1
b^{-1}: 1x
p: GF(2^4) [1, 0, 0, 1, 1]
Add: 1x^3 + 1x^2 + 1x
Subtract: 1x^3 + 1x^2 + 1x
Multiply: 1x^3 + 1x
Divide: 1x^3 + 1x^2 + 1x
You can try the example here.
Example 5. For a=x²+x (6–110b) and b=x⁴+x²+1 (21–10101b) with a primitive of x⁶+x⁵+x⁴+x³+x²+x (GF(28)), for addition we get x⁴+1x+1 (19–10011b), and for multiplication we get x⁶+x⁵+x⁴+x³+x²+x.
a: 1x^2 + 1x
b: 1x^4 + 1x^2 + 1
b^{-1}: 1x^4 + 1x^2 + 1x + 1
p: GF(2^7) [1, 0, 0, 1, 1, 1, 0, 1]
Add: 1x^4 + 1x + 1
Subtract: 1x^4 + 1x + 1
Multiply: 1x^6 + 1x^5 + 1x^4 + 1x^3 + 1x^2 + 1x
Divide: 1x^6 + 1x^5 + 1x^4 + 1x
With addition, there will be no need for the prime polynomial.
You can try the example here.
The code is:
from galois_field import GFpn
# Generating the field GF(2^4)
# irreducible polynomial. (in this case, x^4 + x+1)
import sys
a=[1,1,0]
b=[0,1,0]
p=[1,0,0,1,1]
if (len(sys.argv)>1):
a=eval("["+sys.argv[1].replace(" ","")+"]")
if (len(sys.argv)>2):
b=eval("["+sys.argv[2].replace(" ","")+"]")
if (len(sys.argv)>3):
p=eval("["+sys.argv[3].replace(" ","")+"]")
try:
gf = GFpn(2,p )
except Exception as e:
print ("Error:" ,e)
sys.exit()
# Generating an element in GF(2^4)
aval = gf.elm(a) # x^2+x+1
bval = gf.elm(b) # x
# Arithmetic operations
aval + bval # 1x^2 + 1
aval - bval # 1x^2 + 1
aval * bval # 1x^3 + 1x^2 + 1x
aval / bval # 1x^3 + 1x
print ("a:\t\t",aval)
print ("b:\t\t",bval)
print ("b^{-1}: ",bval.inverse())
print ("p:\t",gf,p)print ("\nAdd:\t\t",aval + bval)
print ("Subtract:\t",aval - bval)
print ("Multiply:\t",aval * bval)
print ("Divide:\t\t",aval / bval)And here is some on-line code: