19 min
Cryptography Fundamentals 4: Finite Fields (aka Galois Fields) ASecuritySite Podcast
-
- Technology
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 val
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 val
19 min