How to represent the elements of the Galois filed GF(2^8) and perform arithmetic in NTL library

867 views Asked by At

I am new to NTL library for its GF2X, GF2E, GF2EX, etc. Now, I want to perform multiplication on the Galois field GF(2^8). The problem is as following:

Rijndael (standardised as AES) uses the characteristic 2 finite field with 256 elements, 
which can also be called the Galois field GF(2^8). 
It employs the following reducing polynomial for multiplication:
x^8 + x^4 + x^3 + x^1 + 1.

For example, {53} • {CA} = {01} in Rijndael's field because

(x^6 + x^4 + x + 1)(x^7 + x^6 + x^3 + x)
= (x^13 + x^12 + x^9 + x^7) + (x^11 + x^10 + x^7 + x^5) + (x^8 + x^7 + x^4 + x^2) + (x^7 + x^6 + x^3 + x)
= x^13 + x^12 + x^9 + x^11 + x^10 + x^5 + x^8 + x^4 + x^2 + x^6 + x^3 + x
= x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x

and
x^13 + x^12 + x^11 + x^10 + x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 + x modulo x^8 + x^4 + x^3 + x^1 + 1
=   (11111101111110 mod 100011011)
=   {3F7E mod 11B} = {01}
=   1 (decimal)

My question is how to represent the reducing polynomial x^8 + x^4 + x^3 + x^1 + 1 and the polynomials x^6 + x^4 + x + 1 and x^7 + x^6 + x^3 + x in NTL. Then perform multiplication on these polynomials, and get the result {01}.

This is a good example for me to use this library.

1

There are 1 answers

9
rcgldr On BEST ANSWER

Again, I don't know NTL, and I'm running Visual Studio 2015 on Windows 7. I've downloaded what I need, but have to build a library with all the supplied source files which will take a while to figure out. However, based on another answer, this should get you started. First, initialize the reducing polynomial for GF(256):

GF2X P;                      // apparently the length doesn't need to be set
SetCoeff(P, 0, 1);
SetCoeff(P, 1, 1);
SetCoeff(P, 3, 1);
SetCoeff(P, 4, 1);
SetCoeff(P, 8, 1);
GF2E::init(P);

Next, assign variables as polynomials:

GF2X A;
SetCoeff(A, 0, 1);
SetCoeff(A, 1, 1);
SetCoeff(A, 4, 1);
SetCoeff(A, 6, 1);

GF2X B;
SetCoeff(B, 1, 1);
SetCoeff(B, 3, 1);
SetCoeff(B, 6, 1);
SetCoeff(B, 7, 1);

GF2X C;

Looks like there is an override for multiply so this would work assuming that the multiply override is based on the GF(2^8) extension field GF2E::init(P).

C = A * B:

As commented after the question, NTL is more oriented to large fields. For GF(256) it would be faster to use bytes and lookup tables. For up to GF(2^64), xmm register intrinsics with carryless multiply (PCLMULQDQ) can be used to implement finite field math quickly without tables (some constants will be needed, the polynomial and it's multiplicative inverse). For fields greater than GF(2^64), extended precision math methods would be needed. For fields GF(p^n), where p != 2 and n > 1, unsigned integers can be used with lookup tables. Building the tables would involve some mapping between integers and GF(p) polynomial coefficients.