I actually do want to know how to generate the multiplication inverse (M.I) table, I mean the calculation how the M.I been generated.. such as the M.I of 22 is 5A regarding to the table.. Do you know how to calculate M.I how the 22 will become 5A 
$\begingroup$
$\endgroup$
2
-
6$\begingroup$ Does this answer your question? Multiplicative inverse in $\operatorname{GF}(2^8)$? $\endgroup$– hardyramaCommented Feb 21, 2020 at 9:03
-
$\begingroup$ I have a hardware breakdown here: github.com/bpdegnan/aes/blob/master/aes-sbox/documentation/… $\endgroup$– b degnanCommented Feb 21, 2020 at 16:08
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
22 is the hex encoding of a binary polynomial $f = x^5 + x$ that is used to represent the element of the AES finite field (the field is defined as $F_{2^8} = GF(2)[x] / p(x)$) where $p(x) = x^8+x^4+x^3+x+1$ is the reduction polynomial.
Now, we need to find the multiplicative inverse of $f(x)$, i.e. another polynomial $g(x)$ such that $$ f(x)\cdot g(x) \equiv 1 \pmod{p(x)} $$ We can do this either by using extended Euclid algorithm for polynomials or using the fact that $f^{-1}(x) = f^{254}(x)$ because of the Little Fermat's Theorem.
Using a computational algebra package like e.g. GP/PARI we can compute
p = Mod(1,2)*x^8 + Mod(1,2)*x^4 + Mod(1,2)*x^3 + Mod(1,2)*x + Mod(1,2)
f = Mod(1,2)*x^5 + Mod(1,2)*x
g = Mod(f,p)^-1
and we get the result
Mod(Mod(1, 2)*x^6 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x, Mod(1, 2)*x^8 + Mod(1, 2)*x^4 + Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2))
so we get the reduced polynomial $x^6 + x^4 + x^3 + x$ and this encodes as 5A, the table entry that corresponds to 22.
The only element that does not have its multiplicative inverse is 00, so by convention we define that 00 is mapped to 00 again.
-
$\begingroup$ Your method is not effective to generate the table. One can fill it at most $O(n^2)$ field multiplications. $\endgroup$– kelalakaCommented Feb 21, 2020 at 13:49
-
$\begingroup$ @kelalaka: Yes, but the question was not about efficiency of the generation algorithm (BTW. for this size of the table asymptotic complexity is just a code golf exercise) but about understanding where do these values come from. $\endgroup$– KrisCommented Feb 21, 2020 at 16:38
$\begingroup$
$\endgroup$
4
As pointed in Krystian's comment, a former version of this answer was wrong. See correction at end of that other answer to the similar question that justified closing the present question.
-
1$\begingroup$ You could also call this 'an optimal technique' since you cannot go below linear complexity. One thing that bothers me though is that if we want to consider a general case, you need to find a generator of the group (i.e. how to find
02in general?). Does it increase the complexity? $\endgroup$– KrisCommented Feb 21, 2020 at 16:43 -
$\begingroup$ @Kristian : you are totally right, and it happens that
02is not a generator, thus my code does not even work! Back to the drawing board. $\endgroup$– fgrieu ♦Commented Feb 21, 2020 at 16:55 -
$\begingroup$ I was going to ask that. One needs to have a generator at the hand for this to work. $\endgroup$– kelalakaCommented Feb 21, 2020 at 17:06
-
$\begingroup$ @Kristian: I hopefully got to the bottom of that, and conclude that finding the generator does not change the complexity: it is asymptotically a single field multiplication per entry in the table. See end of that answer. $\endgroup$– fgrieu ♦Commented Feb 22, 2020 at 11:50