# How can I find the multiplicative inverse in the first transformation of the SubBytes() transformation in AES?

In FIPS-197 §5.1.1, it says the first transformation in the SubBytes() transformation is:

1. Take the multiplicative inverse in the finite field $\text{GF}(2^8)$ described in Sec. 4.2; the element $\{00\}$ is mapped to itself.

Looking at Sec. 4.2, it says that for a given non-zero polynomial $b(x)$ you can find the inverse $b(x)^{-1}$ by using the extended Euclidean algorithm. My question is basically: how do you do this?

I've looked at a ton of examples, Wikipedia has one in $\text{GF}(2^8)$, but I still just don't understand.

Let $b(x) = x^6+x^4+x+1$, Rijndael has $m(x)=x^8+x^4+x^3+x+1$.

From the relation: $$b(x)a(x)+m(x)c(x)=1 \iff b^{-1}(x) \equiv a(x)\pmod{m(x)}$$ I can't figure out what $a(x)$ and $c(x)$ are.

The higher level explanations maybe assume you know some things, and the basic explanations
only use simple integers with Euclid's algorithm, so it's a frustrating place for a beginner.

• If a computation is done in a finite field, there is IMHO barely a possibility to appropriately re-formulate that in terms of common arithmetic operations (for the purpose of rendering it easier to comprehend). You would have to either learn the basics of finite fields or take the results of others for granted, I am afriad. – Mok-Kong Shen Jun 21 '14 at 9:45
• It may not be pretty to formulate that way (it is possible) but that is not his issue, it is a clarity of comprehension since the document does not identify the variables – Richie Frame Jun 21 '14 at 10:01

They are referring to the formula for Bézout's identity which calculates the greatest common divisor, extended to a finite field, where 1 is the multiplicative neutral element.

From the relation $b(x)a(x)+m(x)c(x)=1$, $$b^{-1}(x)=a(x)\mod m(x)$$ I cant figure out what $a(x)$ and $c(x)$ are?

In this case, $b(x)$ is the element for which the inverse is desired, and $a(x)$ is the coefficient for some $c(x)$ that results in the equation being correct. Since $a(x)$ must be in the field, it is reduced modulo $m(x)$, becoming the inverse of $b(x)$. The actual calculation of the extended Euclidean algorithm does not require $c(x)$ to find $a(x)$, but it must exist in the formula for the reduction above to be correct:

$$b(x)a(x)+m(x)c(x)=1$$

$$(b(x)a(x) \mod\ m(x)) + (m(x)c(x) \mod\ m(x)) = 1 \mod\ m(x)$$

$$m(x)c(x) \mod\ m(x) = 0$$

$$b(x)a(x) \mod\ m(x) = 1 \mod\ m(x)$$

$$a(x) \mod\ m(x)={1/b(x)}\mod\ m(x)$$

$$a(x) \mod\ m(x)=b^{-1}(x)$$

Any resultant inverse can be multiplied by $b(x)$ to check for correctness, as the result should be 1 modulo $m(x)$. In practice, the multiplicative inverse is calculated using log/antilog tables for non zero elements:

$$a(x) \mod\ m(x)=log^{-1}(255 - log(b(x)))$$

Since the tables are calculated using exponentiation modulo $m(x)$, the resultant $a(x)$ is already reduced and within the field.

Since the inverse is only used in calculation of the sbox, it is not used in most AES implementations, since the precalculated sbox is stored as a table and not generated on the fly.

• How would i go about calculating $\log b(x)$? Do i turn the polynomial $b(x) = x^6+x^4+x+1$ into its binary form: $01010011$ then the decimal form: $83$ do the logarithms that way or? I tried doing this in wolfram: $2^{255-\log_2(83) \mod 283} \mod 283$ but dont think i get the right answer... – alwaysanxious Jun 23 '14 at 6:57
• You need to create a logarithm table using exponentiation within the field. The values you are processing are not regular numbers, but a polynomial in a finite field; you cannot perform regular arithmetic on them. – Richie Frame Jun 23 '14 at 7:25