Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 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?

Ive looked at ton of examples, Wikipedia has one in $\text{GF}(2^8)$, but I still just dont 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$, $$b^{-1}(x)=a(x)\mod m(x)$$ I cant 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.

share|improve this question
2  
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 at 9:45
1  
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 at 10:01

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
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 at 6:57
1  
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 at 7:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.