From: Steve Pope on
Jaco Versfeld <jaco.versfeld(a)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).

Yes, I just checked it, and it's not primitive, and it does not
generate GF 256.

>According to my knowledge, you need a primitive polynomial in order to
>construct a "proper" Galois field (or extended Galois field).

>Why can we use an irreducible polynomial for AES, would it not cause
>problems (not every element will have an inverse, similar as when we
>construct a ring mod x, where x is a composite)?

Depends how they used it. I do not know where it is in the AES
algorithm. If it's part of just generating a keystream or hash
function, nobody cares if it isn't primitive. But you could not use
it for coding however.

In any case you're right this poly does not generate the field.

Steve
From: bogilvie on
----------------------------------------
spope33(a)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(a)mauve.rahul.net (Stephen P. Pope)
>
> Jaco Versfeld <jaco.versfeld(a)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(a)mathworks.com

First  |  Prev  | 
Pages: 1 2
Prev: biquad for resonant lowpass
Next: NJ, MA or NC