Sage, Galois field and Irreducible Polynomials
Sage, Galois field and Irreducible Polynomials
If you have been involved in serious capture the flags, you’ll often find the solutions are defined not in Python but in Sage. Why? Well, Sage provides a level of abstraction of maths that sits on top of Python. It is open source, and can be installed [here]:
So, let’s look at the core of cryptography: a Galois field. You can find the demo for this article here:
https://asecuritysite.com/sage/sage01
A finite field or Galois field (GF)
A finite field or Galois field (GF) has a finite number of elements, and has an order which is equal to a prime number (GF(p)) or to the power of a prime number (GF(p^n)). For example, GF(2^n) has 2^n elements, and its elements are known as binary polynomials (where the coefficients of the polynomial factors either are either zero or one value.
If n is four, we have 16 output values. GF(p) — the Galois field of p — is also identified as 𝔽p, and where we perform arithmetic operations modulo of a prime (p). With GF(2⁸) we will use the irreducible polynomial of x⁸+x⁴+x³+x+1 and used for AES.
The adding of the polynomial values is equivalent to a binary adder for a single bit, such as:
x⁶ = x⁶
x⁶ + x⁶ = 0
x⁶ + x⁶ + x⁶= x⁶
and for multiply:
x³ × x⁴ = x⁷
x² × x² = x⁴
Adding
If we have 19 (10011 = x⁴+x+1) and 67 (1000011 — x⁶+x+1), if we add:
(x⁴+x+1)+(x⁶+x+1)=x⁶+x⁴
We can check this with Sage, by using:
# Rijndael finite field
k.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
r = (x^4+x+1) + (x^6+x+1)
print(f"(x^4+x+1) + (x^6+x+1)= {r} ({r.integer_representation()})")
We can see that we initially define the irreducible polynomial, and then define the variable name to be used for the polynomials. In this case, it is x.
$ sage 1.sage
(x^4+x+1) + (x^6+x+1)= x^6 + x^4 (80)
Multiplying
For multiply:
(x⁴+x+1)×(x⁶+x+1)=x¹⁰+x⁷+x⁶+x⁵+x⁴+x²+1
For GF(28), we can use an irreducible polynomial of x⁸+x⁴+x³+x+1 for the multiplication, and where we divide by this polynomial and take the remainder. Note that x⁸+x⁴+x³+x+1 is used for AES. We then get:
__x^2____________________________
x^8+x^4+x^3+x+1 | x^{10}+x^7+x^6+x^5+x^4+ x^2+1
x^{10}+ +x^6+x^5+ x^3+x^2
--------------------------------
x^7 +x^4+x^3 +1
The answer is thus x⁷+x⁴+x³+1 and which is 1001101. We can now create Sage code:
# Rijndael finite field
k.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
r = (x^4+x+1) * (x^6+x+1)
print(f"(x^4+x+1) * (x^6+x+1)= {r} ({r.integer_representation()})")
If we run we confirm the result as:
$ sage 1.sage
(x^4+x+1) * (x^6+x+1)= x^7 + x^4 + x^3 + 1 (153)
Divide
If we now try to divide now:
r = (x^6+x+1)/ (x^4+x+1)
print(f"(x^6+x+1)/(x^4+x+1) = {r} ({r.integer_representation()})")
r = (x^4+x+1)/ (x^6+x+1)
print(f"(x^4+x+1)/(x^6+x+1) = {r} ({r.integer_representation()})")
We get:
$ sage 1.sage
(x^6+x+1)/(x^4+x+1) = x^7 (128)
(x^4+x+1)/(x^6+x+1) = x^7 + x + 1 (131)
Multiply and divide
If we have an input value 101101 of y=x⁵+x³+x²+1, and we multiply by h=x⁴+x+1, we get:
r = y.h = (x⁵+x³+x²+1) × (x⁴+x+1)
We can then create the following Sage code:
# Rijndael finite field
k.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
y = (x^5+x^3+x^2+1)
h= (x^4+x+1)
r=y*h
print(f"(x^5+x^3+x^2+1) * (x^4+x+1)= {r} ({r.integer_representation()})")
When we run we get the result of:
$ sage 1.sage
(x^5+x^3+x^2+1) * (x^4+x+1)= x^7 + x^4 + 1 (145)
Now we can divide by our irreducible polynomial and get the orginal value back again:
# Rijndael finite field
k.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
y = (x^5+x^3+x^2+1)
h= (x^4+x+1)
r=y*h
r2=r/h
print(f"{r}/ (x^4+x+1)= {r2} ({r2.integer_representation()})")and get the result of:
$ sage 1.sage
x^7 + x^4 + 1/ (x^4+x+1)= x^5 + x^3 + x^2 + 1 (45)
And, so we can see we can multiply, divide, add and subtract, and for the operations to be reversible.
Some examples
Here are a few examples:
# Rijndael finite field
k.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)
y = (x^5+x^3+x^2+1)
h= (x^4+x+1)
r=y*h
print(f"(x^5+x^3+x^2+1) * (x^4+x+1)= {r} ({r.integer_representation()})")
r2=r/h
print(f"{r}/ (x^4+x+1)= {r2} ({r2.integer_representation()})")r = (x^4+x+1) + (x^6+x+1)
print(f"(x^4+x+1) + (x^6+x+1)= {r} ({r.integer_representation()})")
r = (x^4+x+1) * (x^6+x+1)
print(f"(x^4+x+1) * (x^6+x+1)= {r} ({r.integer_representation()})")
r = (x^6+x+1)/ (x^4+x+1)
print(f"(x^6+x+1)/(x^4+x+1) = {r} ({r.integer_representation()})")
r = (x^4+x+1)/ (x^6+x+1)
print(f"(x^4+x+1)/(x^6+x+1) = {r} ({r.integer_representation()})")
r = (x) * x
print(f"a * a= {r} ({r.integer_representation()})")
r = (x^2) * x
print(f"x^2 * x= {r} ({r.integer_representation()})")
r = (x^2+x) * x
print(f"(x^2+x) * x= {r} ({r.integer_representation()})")
r = (x^2+x) * (x+1)
print(f"(x^2+x) * (x+1)= {r} ({r.integer_representation()})")
r = (x^2+x+1) * (x^2+1)
print(f"(x^2+x+1) * (x^2+1)= {r} ({r.integer_representation()})")
r = (x^3+x+1) * (x^3+x+1)
print(f"(x^3+x+1) * (x^3+x+1)= {r} ({r.integer_representation()})")
r = (x^5+x+1) * (x^3+x+1)
print(f"(x^5+x+1) * (x^3+x+1)= {r} ({r.integer_representation()})")
r = (x^6+x+1) * (x^3+x^2+1)
print(f"(x^6+x+1) * (x^3+x^2+1)= {r} ({r.integer_representation()})")
and the result:
$ sage 1.sage
(x^5+x^3+x^2+1) * (x^4+x+1)= x^7 + x^4 + 1 (145)
x^7 + x^4 + 1/ (x^4+x+1)= x^5 + x^3 + x^2 + 1 (45)
(x^4+x+1) + (x^6+x+1)= x^6 + x^4 (80)
(x^4+x+1) * (x^6+x+1)= x^7 + x^4 + x^3 + 1 (153)
(x^6+x+1)/(x^4+x+1) = x^7 (128)
(x^4+x+1)/(x^6+x+1) = x^7 + x + 1 (131)
a * a= x^2 (4)
x^2 * x= x^3 (8)
(x^2+x) * x= x^3 + x^2 (12)
(x^2+x) * (x+1)= x^3 + x (10)
(x^2+x+1) * (x^2+1)= x^4 + x^3 + x + 1 (27)
(x^3+x+1) * (x^3+x+1)= x^6 + x^2 + 1 (69)
(x^5+x+1) * (x^3+x+1)= x^6 + x^5 + x^2 + x (102)
(x^6+x+1) * (x^3+x^2+1)= x^6 + x^5 + x^4 + x^3 + x (122)
Conclusions
That is the magic of galois fields. At the core is the irreducible polynomials, and where we are able to operate on data, and then reverse the operations. Here is it in Rust:
https://asecuritysite.com/rust/gf01
and for irreducible polynomials: