Multiplicative Inverse in AES [duplicate]

Question

I want to calculate the S-box for AES. But I have a problem with the multiplicative inverse step. For example, the inverse of 95 is 8A.

I don't know how to get this result. How is the multiplicative inverse computed?

Answer 1

The inverse in AES is defined over a particular field. All the operation are done in this field. The Rijndael finite field is defined as follow: $GF(2^8) = GF(2)[x]/(x^8 + x^4 + x^3 + x + 1)$.

The "numbers" are a representation of polynomials (a byte represents coefficients of a polynomial):

0x95 = 1001 0101 = $x^7+x^4 + x^2 + 1$

0x8A = 1000 1010 = $x^7+ x^3 + x$

And the product of the two polynomial reduced modulo the irreductible polynomial is 1, as expected.

There are several way to implement the inversion and the affine transformation described in the AES to get the final SBox. Once you get the math, you may choose one way or the other, keep in mind that you can avoid to implement all the algebraic structure and a function taking as input only a byte (cfr: https://en.wikipedia.org/wiki/Rijndael_S-box#Alternate_equation_for_the_affine_transformation)

You may find more information here: https://en.wikipedia.org/wiki/Rijndael_S-box and https://en.wikipedia.org/wiki/Finite_field_arithmetic#Rijndael.27s_finite_field and Galois fields in cryptography