Galois field GF(2⁸) and Rust

Galois field GF(2⁸) and Rust

In 1831, Évariste Galois 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 theory, along with defining the concept of a finite field. In cryptography, the finite field is one of the major concepts and involves limiting the number of possible values to a limiting factor (p). The values of the field then range from 0 to p-1.

Galois field

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(pn)). 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). An encryption method could thus multiply two values, and where we can then divide by an irreducible polynomial to give a remainder value as the result. This is equivalent to performing a (mod p) operation, and where p is a prime.

For AES, we use GF(2⁸) and have an irreducible polynomial of x⁸+x⁴+x³+x+1. With this, we may multiply by a value within a Galois field and then divide by the sample value in order to produce the original value. If we have 19 (10011 = x⁴+x+1) and 67 (1000011 — x⁶+x+1), the we can add:

x⁴+x+1+x⁶+x+1=x⁶+x⁴ (1010000)

Thus, in GF(2⁸): 10011 + 1000011 = 1010000

For multiply:

(x⁴+x+1)×(x⁶+x+1)=x¹⁰+x⁷+x⁶+x⁵+x⁴+x²+1

For GF(2⁸), 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 result of the multiplication is then x⁷+x⁴+x³+1, and which can be represented by 1001101. Here is the working out:

Thus, in GF(2⁸): 10011 x 1000011 = 1001101

Rust implementation

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 [here]:

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);

}

For the divide operation, we take the multiplicative inverse and multiply it by the given value. Finally, we simply build with:

cargo build

For a run with a=19 and b=67:

cargo run 19 67

we get [here]:

--- GF(2^8) --
19=10011
67=1000011

10011+1000011=1010000
10011-1000011=1010000
10011*1000011=10011001
10011/1000011=10000011

Here is the Rust program:

https://asecuritysite.com/rust/gf01?a1=19&b1=67

If you are intested in Galious fields and irreducible polynomials:

https://asecuritysite.com/encryption/gf

And if you are interested in Rust, try here:

https://asecuritysite.com/rust/