0
$\begingroup$

I want to invert matrix $A$ in the finite field $\mathbb{F} = \mathbb{F}_2[x]/p(x)\mathbb{F}_2$ with $p(x)=x^8+x^4+x^3+x+1$. This finite field is used by the encryption scheme AES.

$A = \begin{pmatrix} x^6+x^4+x^2+x+1 & x^5+x^3+1 & x^5+x^2+1 \\ x^7+x^4+x & x^4+x & x^2+1 \\ x^6+x^4+x^3+1 & x^6+x^3+x & x^4+x^3 \end{pmatrix} $

For inverting $A$ I am supposed to use the Gaussian algorithm. The first step would be to divide the first row by its first entry, i.e. $x^6+x^4+x^2+x+1$.

How do I find the solution of such divisions, for example $(x^5+x^3+1)/(x^6+x^4+x^2+x+1)$. The finite field contains $2^8$ elements. Hence it is impossible for me to first calculate the multiplication table.

$\endgroup$
5
  • $\begingroup$ Do you have to do it by hand? $\endgroup$ – AHusain Dec 20 '15 at 11:49
  • $\begingroup$ Yes, I do. As this is Rijndael's finite field I suppose I can use some lookup tables, but I don't know how to make use of them to answer my question. They only provide multiplicative inverses, but do not help to do a division of two field elements. $\endgroup$ – null Dec 20 '15 at 11:51
  • 1
    $\begingroup$ Well if you have inverses, you have the division because multiplication isn't too bad. $(x^5 + x^3 + 1)*(x^6 + x^4 + x^2 + x + 1 )^{-1}$ $\endgroup$ – AHusain Dec 20 '15 at 11:56
  • $\begingroup$ Good comment. I'll try it! $\endgroup$ – null Dec 20 '15 at 12:09
  • $\begingroup$ Unless you are aiming to implement this on a device that is extremely low on memory, you could (IMHO should) build logarithm tables converting the field multiplication and division to (modular) integer addition and subtraction. See this Q&A I prepared for referrals where I try to explain how to use discrete logarithm tables for field operations. $\endgroup$ – Jyrki Lahtonen Dec 20 '15 at 16:58
2
$\begingroup$

You have to find the inverse of elements. This is done with the *extended euclidean algorithm. Here is the top left corner as an example:

enter image description here

As a Bézout relation is \begin{multline*} (x^7 + x^6 + x^4 + x^3 + x)(x^6 + x^4 + x^2 + x + 1) \\+(x^5 +x^4 + x^3 + x + 1)(x^8 + x^4 + x^3 + x + 1 ) =1 \end{multline*} one has in $\mathbf F_2[x]/(x^8 + x^4 + x^3 + x + 1 )$: $$(x^6 + x^4 + x^2 + x + 1)^{-1}=x^7 + x^6 + x^4 + x^3 + x.$$

$\endgroup$
1
  • $\begingroup$ Is there any why to simply look up the inverse of an element in GF(2^8)? I cannot find a lookup table. $\endgroup$ – null Dec 21 '15 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.