- #1
qxcdz
- 8
- 0
I'm trying to implement AES as practice for my C++ skills, but I've come across a confusing problem that I think belongs here rather than in programming.
Rijndael's finite field is GF(28), with reducing polynomial x8+x4+x3+x+1
There is a step in the algorithm that takes a polynomial a(x)=a3x3+ a2x2+a1x+a0 with coefficients in GF(28), and multiplies it by a polynomial b(x)=b3x3+ b2x2+b1x+b0
and reduces it modulo x4+1, to get d(x)=d3x3+ d2x2+d1x+d0
This operation is equivalent, if a is a constant polynomial, according to the text, to the matrix multiplication:
\left( \begin{array}{c}<br /> d_0 \\<br /> d_1 \\<br /> d_2 \\<br /> d_3 \end{array} \right)=<br /> \left( \begin{array}{cccc}<br /> a_0 & a_3 & a_2 & a_1 \\<br /> a_1 & a_0 & a_3 & a_2 \\<br /> a_2 & a_1 & a_0 & a_3 \\<br /> a_3 & a_2 & a_1 & a_0 \end{array} \right)<br /> \left( \begin{array}{c}<br /> b_0 \\<br /> b_1 \\<br /> b_2 \\<br /> b_3 \end{array} \right)
it gives the constant polynomial a(x) as a(x)=\{03\}x^3+\{01\}x^2+\{01\}x+\{02\}, and the inverse polynomial a^{-1}(x)=\{0b\}x^3+\{0d\}x^2+\{09\}x+\{0e\} (all numbers in curly braces are hexadecimal).
Now, being as I'm using a computer to do this, and proper polynomial handling is hard to do, I'm using the matrix multiplication to do the calculation. Now, if I'm thinking about this properly, then the matrix representations of a(x) and a^{-1}(x) should have a product that is a unit matrix. But, if my calculations (done by my program) are correct, then:
<br /> \left( \begin{array}{cccc}<br /> \{02\} & \{03\} & \{01\} & \{01\} \\<br /> \{01\} & \{02\} & \{03\} & \{01\} \\<br /> \{01\} & \{01\} & \{02\} & \{03\} \\<br /> \{03\} & \{01\} & \{01\} & \{02\} \end{array} \right)<br /> \left( \begin{array}{cccc}<br /> \{0e\} & \{0b\} & \{0d\} & \{09\} \\<br /> \{09\} & \{0e\} & \{0b\} & \{0d\} \\<br /> \{0d\} & \{09\} & \{0e\} & \{0b\} \\<br /> \{0b\} & \{0d\} & \{09\} & \{0e\} \end{array} \right)=<br /> \left( \begin{array}{cccc}<br /> \{01\} & \{00\} & \{e5\} & \{00\} \\<br /> \{00\} & \{01\} & \{00\} & \{e5\} \\<br /> \{e5\} & \{00\} & \{01\} & \{00\} \\<br /> \{00\} & \{e5\} & \{00\} & \{01\} \end{array} \right)<br />
Which is almost a unit matrix, but not quite. And, when I use these polynomials to calculate the function, and then the inverse, I get a different polynomial to my input. I checked my matrix multiplication algorithm, it seems to be working fine.
Two other matrices that should have a unit matrix product (for another step in the algorithm) do. I'm definitely doing finite field arithmetic. I'm using a logarithm table for my multiplication, base three, which I know for a fact is a generator. I can't find anything wrong with the procedure, so I'm asking you guys if you could please tell me why it doesn't work.
Rijndael's finite field is GF(28), with reducing polynomial x8+x4+x3+x+1
There is a step in the algorithm that takes a polynomial a(x)=a3x3+ a2x2+a1x+a0 with coefficients in GF(28), and multiplies it by a polynomial b(x)=b3x3+ b2x2+b1x+b0
and reduces it modulo x4+1, to get d(x)=d3x3+ d2x2+d1x+d0
This operation is equivalent, if a is a constant polynomial, according to the text, to the matrix multiplication:
\left( \begin{array}{c}<br /> d_0 \\<br /> d_1 \\<br /> d_2 \\<br /> d_3 \end{array} \right)=<br /> \left( \begin{array}{cccc}<br /> a_0 & a_3 & a_2 & a_1 \\<br /> a_1 & a_0 & a_3 & a_2 \\<br /> a_2 & a_1 & a_0 & a_3 \\<br /> a_3 & a_2 & a_1 & a_0 \end{array} \right)<br /> \left( \begin{array}{c}<br /> b_0 \\<br /> b_1 \\<br /> b_2 \\<br /> b_3 \end{array} \right)
it gives the constant polynomial a(x) as a(x)=\{03\}x^3+\{01\}x^2+\{01\}x+\{02\}, and the inverse polynomial a^{-1}(x)=\{0b\}x^3+\{0d\}x^2+\{09\}x+\{0e\} (all numbers in curly braces are hexadecimal).
Now, being as I'm using a computer to do this, and proper polynomial handling is hard to do, I'm using the matrix multiplication to do the calculation. Now, if I'm thinking about this properly, then the matrix representations of a(x) and a^{-1}(x) should have a product that is a unit matrix. But, if my calculations (done by my program) are correct, then:
<br /> \left( \begin{array}{cccc}<br /> \{02\} & \{03\} & \{01\} & \{01\} \\<br /> \{01\} & \{02\} & \{03\} & \{01\} \\<br /> \{01\} & \{01\} & \{02\} & \{03\} \\<br /> \{03\} & \{01\} & \{01\} & \{02\} \end{array} \right)<br /> \left( \begin{array}{cccc}<br /> \{0e\} & \{0b\} & \{0d\} & \{09\} \\<br /> \{09\} & \{0e\} & \{0b\} & \{0d\} \\<br /> \{0d\} & \{09\} & \{0e\} & \{0b\} \\<br /> \{0b\} & \{0d\} & \{09\} & \{0e\} \end{array} \right)=<br /> \left( \begin{array}{cccc}<br /> \{01\} & \{00\} & \{e5\} & \{00\} \\<br /> \{00\} & \{01\} & \{00\} & \{e5\} \\<br /> \{e5\} & \{00\} & \{01\} & \{00\} \\<br /> \{00\} & \{e5\} & \{00\} & \{01\} \end{array} \right)<br />
Which is almost a unit matrix, but not quite. And, when I use these polynomials to calculate the function, and then the inverse, I get a different polynomial to my input. I checked my matrix multiplication algorithm, it seems to be working fine.
Two other matrices that should have a unit matrix product (for another step in the algorithm) do. I'm definitely doing finite field arithmetic. I'm using a logarithm table for my multiplication, base three, which I know for a fact is a generator. I can't find anything wrong with the procedure, so I'm asking you guys if you could please tell me why it doesn't work.
