I want to calculate the S-box for AES. But I have a problem with the multiplicative inverse step. For example, the inverse of
I don't know how to get this result. How is the multiplicative inverse computed?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
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