Your Online Security Is Fundamentally Based on x⁸ + x⁴ + x³ + x² + 1
Your Online Security Is Fundamentally Based on x⁸ + x⁴ + x³ + x² + 1
Recently, I had two business students attending my applied cryptography lectures. Why? Because they were interested in blockchain and wanted to know more about how cryptography worked. In fact, they asked more questions in the lecture than all the other students in the whole class. To me, when you get the cross-over between understanding the applications of technology, and how it works — then magic can happen! We basically silo our subjects, and limit any cross-fertilisation of ideas.
There’s a high chance that you are using AES encryption to read this article. As you should know, AES is a symmetric key algorithm and standardized by NIST. But why are you using it now? Well, if you look to add the address bar, you will see it uses “https://”. This means that there is an encryption tunnel between you and the Web server, and it is highly likely that you will be using AES encryption for this. The way it works is that your browser is likely to use a key handshake method of ECDH (Elliptic Curve Diffie Hellman) and where you will share an AES session key. This key is then used once for the session and will encrypt all of the data in the tunnel.
But where does the polynomial of x⁸ + x⁴ + x³ + x² + 1 come in? Well, it is an irreducible polynomial for GF(2⁸). I appreciate that I may have lost you there with some jargon, but basically, it is like the way we use a prime number for our calculations and where:
(a + b) (mod p) = a (mod p) + b (mod p) (mod p)
and where we can operate our normal maths operations of:
(a.b) = (b.a)
a (b+c) = a.b + ac
a^x.a^y = a^{x+y}
and so on. And so a symmetric key method is basically a whole lot of operations that we do in a certain sequence and can then roll them back with the reverse of the operation. This includes using parts of the key for each step. To simplify things, we might multiply our plaintext value by 7 and then add 8, to create our ciphertext. To decrypt, we can then just subtract by 8 and divide by 7.
Overall, a value of 10011 can then be represented in a polynomial form as x⁴+x+1. Every non-prime value can be reduced to a multiplication of prime numbers. For example, 14 is 2×7 and 16 is 2×2×2×2. The same can be done for polynomials in GF(2^n), and where we can factorize a polynomial. Within polynomials, the prime number equivalents are known as irreducible, as they cannot be factored.
In AES, we deal with one byte of data, and so this is an irreducible polynomial for GF(2⁸) comes in, and where we can basically divide by this polynomial at any time and not lose anything. If you are interested, we can generate from [here]:
import galois
import sys
p=2
if (len(sys.argv)>1):
p=int(sys.argv[1])
print(f"Irreducible Poly\n")
for n in range(1,12):
GF = galois.GF(p**n)
print(f"Degree {n}: {GF.irreducible_poly}")and then compute the irreducible polynomials for GF(2^n) [here]:
GF(2^1) Degree 1: x + 1
GF(2^2) Degree 2: x^2 + x + 1
GF(2^3) Degree 3: x^3 + x + 1
GF(2^4) Degree 4: x^4 + x + 1
GF(2^5) Degree 5: x^5 + x^2 + 1
GF(2^6) Degree 6: x^6 + x^4 + x^3 + x + 1
GF(2^7) Degree 7: x^7 + x + 1
GF(2^8) Degree 8: x^8 + x^4 + x^3 + x^2 + 1
GF(2^9) Degree 9: x^9 + x^4 + 1
GF(2^10) Degree 10: x^10 + x^6 + x^5 + x^3 + x^2 + x + 1
GF(2^11) Degree 11: x^11 + x^2 + 1In AES, we have a 128-bit block size and where we can represent our bytes as a 4x4 matrix. The designers for AES were smart and allowed for matrix multiplication with the irreducible polynomial. For this we basically just have to mix up the columns with [here]:
and then do a divide by the irreducible polynomial [here]:
As you see, there are no complex operations used, and we basically have simple adds and XOR operations. This makes AES fast and efficient, and the irreducible polynomial means that we always get the right ciphertext generated and plaintext recovered.
If you are interested in Galois Fields, try here:
and AES:
Go feed your brain!