Sage, Galois field and Irreducible PolynomialsSage provides a level of abstraction of maths that sits on top of Python. It is open source, and can be installed [here]: 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(\(2^p\))). 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^8\)) we will use the irreducible polynomial of \(x^8+x^4+x^3+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^6 = x^6\) \(x^6 + x^6 = 0\) \(x^6 + x^6 + x^6= x^6\) and for multiply: \(x^3 \times x^4 = x^7 \) \(x^2 \times x^2 = x^4 \) AddingIf we have 19 (10011 = \(x^4+x+1\)) and 67 (1000011 — \(x^6+x+1\)), if we add: \((x^4+x+1)+(x^6+x+1)=x^6+x^4\) 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) MultiplyingFor multiply: \((x^4+x+1) \times (x^6+x+1)=x^{10}+x^7+x^6+x^5+x^4+x^2+1\) For GF(\(2^8\)), we can use an irreducible polynomial of \(x^8+x^4+x^3+x+1\) for the multiplication, and where we divide by this polynomial and take the remainder. Note that \(x^8+x^4+x^3+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^7+x^4+x^3+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) DivideIf 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 divideIf we have an input value 101101 of \(y=x^5+x^3+x^2+1\), and we multiply by \(h=x^4+x+1\), we get: r = y.h = (x^5+x^3+x^2+1) × (x^4+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 examplesHere 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/hprint(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"x * x= {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) x * x= 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) |