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.
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):
Next, assign variables as polynomials:
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).
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.