Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Topic: Polynomial used to create Galois field for AES?
Replies: 8   Last Post: Aug 11, 2010 3:46 PM

 Messages: [ Previous | Next ]
 Brian Ogilvie Posts: 4 Registered: 12/7/04
Re: Polynomial used to create Galois field for AES?
Posted: Apr 29, 2010 11:36 AM

----------------------------------------
spope33@speedymail.org (Steve Pope) writes:
> Path: news.mathworks.com!newsfeed-00.mathworks.com!news.kjsl.com!wasp.rahul.net!192.160.13.20.MISMATCH!rahul.net!not-for-mail
> Newsgroups: sci.math,comp.dsp
> Subject: Re: Polynomial used to create Galois field for AES?
> Date: Thu, 29 Apr 2010 13:36:22 +0000 (UTC)
> Organization: a2i network
> Originator: spp@mauve.rahul.net (Stephen P. Pope)
>
> Jaco Versfeld <jaco.versfeld@gmail.com> wrote:
>

>>The following polynomial is used to create a "Galois field" GF(2^8)
>>which is specified in the Advanced Encryption Standard (AES): p(x) =
>>x^8 + x^4 + x^3 + x + 1.
>>
>>However, I checked the polynomial (quickly using Matlab) whether it is
>>primitive. It turns out not to be primitive, but still irreducible (I
>>haven't yet confirm this for myself, though).

This is by design in AES, which uses two GF(2^8) polynomials and other
operations to generate the SBOX for the algorithm. The reason an irreducible
but not primitive polynomial is used is that we are trying to make a non-linear
permutation function that has diffusion, spreading input bits to output bits in
an non-linear way. The AES sbox was analyzed to death during the competition to
pick the AES algorithm.

Here is some MATLAB code I have used in the past to generate the AES SBOX--the
gf arithmetic requires Comm Toolbox in MATLAB:

temp = gf(0:255,8,283).^254; % inverses in GF(2^8) with polynomial 283
temp = gf(temp.x,8,257).*31; % now embedded that field into poly=257 field and mult by 31
sbox = bitxor(temp.x,99); % now bitwise xor with 99
sbox = double(sbox);

The AES inverse sbox can be similarly computed.

Hope this helps!

--Brian brian.ogilvie@mathworks.com

Date Subject Author
4/29/10 jaco.versfeld@gmail.com
4/29/10 Timothy Murphy
4/29/10 dvsarwate@gmail.com
4/29/10 dvsarwate@gmail.com
4/29/10 jaco.versfeld@gmail.com
4/29/10 Steve Pope
4/29/10 Brian Ogilvie
4/30/10 I.M. Soloveichik
8/11/10 Larry D'Anna