Cryptography Fundamentals 4: Finite Fields (aka Galois Fields)

I will bet you, that you have a memory of school where you had the “pleasure” or, most likely, the “nightmare” of performing long addition or long subtraction, and where you had carry overs between columns. The units carried over in the tens, the tens into the hundreds, and so on. And, then, you encountered long multiplication with those ever growing list of numbers.  And, please forgive me, you progressed to long division, and you had that divisor dividing into your number and with the bar along the top, and where you put your result, and which those pesky remainders. “Oh, teacher, 61 divided by 9 is 6 remainder 7”. And, didn’t you love throwing away that remainder and just making the answer 6. But, in cryptography, the remainder is the bit we like, and we throw away the other bit. So for us, 61 mod 9 is 7.  So, just take a pause now to just calm yourself for those memories. If you want to leave now, please do so, as we will revisit some of these memories, but, hopefully, we will make things a whole lot more simple. To these additions and multiplications in an electronic circuit or some software code can take many operations. But, just imagine a world where you did not need to carry over values from one column to another, and even where all you had to add or multiply was a 0 and 1, life would be so much easier, and these school nightmares would end for you, and life would be so much happier for your kids in learning maths. For example, if we have a binary adder we have 0+0=0, 1+0=1 and 1+1=0. As we see a simple binary adder just throws away that pesky carry. If we add 1+0+1+1+1+0, we see an answer of 0. But in our normal maths, to add 7+4+3+9+8 requires us to add up the units, and carry over in the 10s column. For simplifying things we turn to Évariste Galois. Évariste Galois — who lived from 1811 to 1832 — 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’s theory — along with defining the concept of a finite field.  Creating the reverse operation As we have seen from the previous podcasts, we have values in a group, and then can operate on these to get another value in the group. So, if we have a group of 0 to 16, we can constrain our values with a (mod p) operation, and where p is a prime number.  For example, if we use a prime number of 17, and we take a value of 2 and then raise that to the power of 5 and take the mod of 17, to get 15: >>> pow(2,5,17)15 For all of the values from 0 to 16, we should (hopefully) get different mappings for the output. This will then allow us to reverse back by taking the inverse operation to the modulo power. This, as we have seen from a previous podcast, is to subtract one from the prime number (PHI=p-1), and perform an inverse of the base modulo of the prime number minus one. A simple Python program gives us the result for the inverse: >>> pow(5,-1,16)13 If we now multiply our result of 15 by 13 and take (mod 17), we magically get our value back again: >>> pow(15,13,17)2 In this way, we aim to reverse our mathematical operations, and where there is no confusion about the reverse operation.  Simplifying things Up to now, we have seen that we have operated on our normal arithmetic operations for the (mod p) such as add, subtract, multiply and divide, but we can simply things even more if we have a field which has 2^n elements, and where if n is 8, we can have 256 elements. 256 elements, for example, is the number of values we can have for a byte of data in a computer system. If so, we can convert our bit values of our integers into a polynomial, and then operate on them as polynomial operations, such as:  (x²+1)+(x) = x²+x+1 This, as we will see, significantly reduces the complexity of our arithmetic operations, and rather than have complex circuits for adding (with carry overs) and multiplying (and where we end up with a value which has more bits than the inputs values), we constrain the calculation within our finite field. Along with this we then just need simple 1-bit adder or multiplication operation. So from complex adding and subtraction circuits in hardware or with software operations, we end up with simple bit operations. This vastly increases the speed of our cryptographic operation.  This is a Galious field, and defined more generally as GF(p^n), and where p is a prime number. But, in most cases, p will be 2. Arithmetic operations Within a finite field, we limit the number of possible values in a group. As we have seen this can be a prime number and where we get a group from 0 to p-1, and where we can perform our mathematic operations with the (mod p) operation. And, so, even though we have a finite field, we still want our maths to still operate as normal. The rules for every element in the group is: Commutative law. This is where (a+b) equals (b+a), and (a*b) equals (b*a). Associative law. This is where a.(b.c) is equal to b.(a.c). Distributive law. This is where a(b+c) is equal to ab+ac. Additive and Multiplicative Identifies (0 and 1). This means that a+0=a, and a times 1 is equal to a. Additive and Multiplicative Inverses. This means that there is an additive inverse where there is a value of b for a so that a+b=0. For multiplicative inverse, there is a value of b for a so that a.b=0. Within our finite field in cryptography, we want all of these to work, so that we can reverse any operation that we can apply.  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(²⁴) 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(²⁸). 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. Oh, and we don’t have prime numbers any more, we have irreducible polynomials or primitive polynomial, and which are polynomials that cannot be factorized into polynomial factors. https://asecuritysite.com/gf/gf2 This operatives in a similar way to our (mod p) operation, and where we can reduce a result into the group, and just take the remainder from a division. 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 + 1b: 1x + 1b^{-1}: 1x^3 + 1x^2 + 1xp: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^2Subtract: 1x^2Multiply: 1x^3 + 1Divide: 1x^3 + 1x^2 For the division, we determine the inverse of b and then multiply by 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(²⁴)), 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^3b: 1x^2 + 1b^{-1}: 1x^3 + 1x + 1p: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2 + 1Subtract: 1x^3 + 1x^2 + 1Multiply: 1x^3 + 1x^2 + 1xDivide: 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 + 1b: 1x^2 + 1b^{-1}: 1x^3 + 1x + 1p: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2Subtract: 1x^3 + 1x^2Multiply: 1x^3 + 1x + 1Divide: 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 + 1b: 1x^3 + 1b^{-1}: 1xp: GF(2^4) [1, 0, 0, 1, 1]Add: 1x^3 + 1x^2 + 1xSubtract: 1x^3 + 1x^2 + 1xMultiply: 1x^3 + 1xDivide: 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(2⁸)), for addition we get x⁴+1x+1 (19–10011b), and for multiplication we get x⁶+x⁵+x⁴+x³+x²+x. a: 1x^2 + 1xb: 1x^4 + 1x^2 + 1b^{-1}: 1x^4 + 1x^2 + 1x + 1p: GF(2^7) [1, 0, 0, 1, 1, 1, 0, 1]Add: 1x^4 + 1x + 1Subtract: 1x^4 + 1x + 1Multiply: 1x^6 + 1x^5 + 1x^4 + 1x^3 + 1x^2 + 1xDivide: 1x^6 + 1x^5 + 1x^4 + 1x With addition, there will be no need for the irreducible 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 sysa=[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+1bval = gf.elm(b) # x# Arithmetic operationsaval + bval # 1x^2 + 1aval - bval # 1x^2 + 1aval * bval # 1x^3 + 1x^2 + 1xaval / bval # 1x^3 + 1xprint ("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) Irreducible Polynomials Within polynomials, the prime number equivalents are known as irreducible, as they cannot be factored. I will come back to irreducible polynomials later in this series, but for now, you can read up on them at: https://asecuritysite.com/gf/gf2 Conclusions And, so, you made it to the end of this podcast. If you managed to understand everything here, you deserve a crypto medal. If not — for most — you should try and read over and eventually, it will sink in — slowly at first, and then you will get bits and pieces of knowledge, and eventually, it will make sense. This is one of the reasons I love cryptography — and teach and research the field — as, every day, I learn, but my learning was so much deeper once I really understand why we did all these complex-looking things, and to get behind the maths. I hope I have not given you nightmares of school and with long multiplication and division, but if I have, I can calm you that the maths we use in cryptography is so much simpler, and where you just have to know how to count just a 0 and a 1. Life is so much more relaxed in crypto space.