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 polynomals (where the co-efficients of the polynomial factors either are either zero or one values. If \(n\) is four, we have 16 output values. GF\((p\)) - the Galois field of \(p\) - is also identified as \(\mathbb{F}_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.
Galious Fields in GF(2^8) in Rust |
Method
If 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 \)
For 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 then 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.
Code
First we create the Rust project with:
cargo new gf01
We then go into the gf01 folder and then into the src folder, and edit the main.rs file with:
extern crate isochronous_finite_fields; use isochronous_finite_fields::GF; use std::env; fn main() { let mut val1=7; let mut val2=3; let args: Vec= env::args().collect(); if args.len()> 1 { val1= args[1].clone().parse:: ().unwrap();} if args.len()> 2 { val2 = args[2].clone().parse:: ().unwrap(); } println!("-- GF(2^8) --"); println!("{}={:b}",val1,val1); println!("{}={:b}",val2,val2); // Add two elements of the Galois field GF(2^8) together. let mut res = GF(val1) + GF(val2); println!("\n{:b}+{:b}={:b}",val1,val2,res.0); res = GF(val1) - GF(val2); println!("{:b}-{:b}={:b}",val1,val2,res.0); res = GF(val1) * GF(val2); println!("{:b}*{:b}={:b}",val1,val2,res.0); res = GF(val1) * GF(val2).multiplicative_inverse(); println!("{:b}/{:b}={:b}",val1,val2,res.0); }
Finally we simply build with:
cargo build
For a run with \(a=19\) and \(b=67\):
cargo run 19 67
we get:
--- GF(2^8) -- 19=10011 67=1000011 10011+1000011=1010000 10011-1000011=1010000 10011*1000011=10011001 10011/1000011=10000011