Polynomial used to create Galois field for AES?
in [DSP]
|
Prev: biquad for resonant lowpass
Next: NJ, MA or NC
From: Jaco Versfeld on 29 Apr 2010 06:56 Hi There, (My apologies for cross-posting) 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). 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)? Your time and help will be greatly appreciated, Jaco
From: Timothy Murphy on 29 Apr 2010 07:21 Jaco Versfeld 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). > > According to my knowledge, you need a primitive polynomial in order to > construct a "proper" Galois field (or extended Galois field). What is a "proper" 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)? I don't think that is right. If p(x) is irreducible and f(x) is a polynomial not divisible by p(x) then there is a polynomial g(x) such that f(x)g(x) = 1 mod p(x). -- Timothy Murphy e-mail: gayleard /at/ eircom.net tel: +353-86-2336090, +353-1-2842366 s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
From: dvsarwate on 29 Apr 2010 07:33 On Apr 29, 5:56 am, Jaco Versfeld <jaco.versf...(a)gmail.com> wrote: .......... > > According to my knowledge, you need a primitive polynomial in order to > construct a "proper" Galois field (or extended Galois field). > No, an irreducible polynomial can be used also, unless you want to use a logarithm table approach in implementing field multiplication and division. Well, one *can* use a log table approach but it is more complicated to set up and requires more arithmetic which negates any speed advantages that log tables provide. > 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)? No, it won't. Try using x^4 + x^3 + x^2 + x + 1 (which is irreducible but not primitive) to construct GF(2^4) and convince yourself that inverses exist. That is, for every nonzero binary polynomial f(z) of degree 4, there is a polynomial g(z) such that f(z)g(z) mod x^4 + x^3 + x^2 + x + 1. Or look at the table in Chapter 4 of Elwyn Berlekamp's Algebraic Coding Theory where the answers are spelled out in detail for your convenience. --Dilip Sarwate
From: dvsarwate on 29 Apr 2010 07:36 On Apr 29, 6:33 am, dvsarwate <dvsarw...(a)gmail.com> wrote: ....... > No, it won't. Try using x^4 + x^3 + x^2 + x + 1 > (which is irreducible but not primitive) to construct > GF(2^4) and convince yourself that inverses > exist. That is, for every nonzero binary polynomial > f(z) of degree 4, there is a polynomial g(z) such that > f(z)g(z) mod x^4 + x^3 + x^2 + x + 1. ...... That last line above should be: f(z)g(z) = 1 mod (x^4 + x^3 + x^2 + x + 1).
From: Jaco Versfeld on 29 Apr 2010 09:26
Thank you very much. I forgot the definition of an irreducible polynomial. So the only difference then between a primitive field and non- primitive field is that the first allows efficient use of log tables? Thank you very much for the help Jaco |