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, 2015 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, 2015 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, 2015 at 11:56
  • $\begingroup$ Good comment. I'll try it! $\endgroup$
    – null
    Dec 20, 2015 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, 2015 at 16:58

1 Answer 1

Reset to default
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, 2015 at 12:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .