2
$\begingroup$

The Wikipedia article for the AES S-Box gives an alternate equation for the affine part of the S-Box transformation:

$$b_{out} = (b_{in} \times 31_d) \operatorname{mod} 257_d \oplus 99_d$$

It is not very clear in the article, but it turns out from the paper (as cited in the article) that the multiplication is to be carried out over a finite-field with polynomial $257 = 100000001_b$ for the modular reduction.

How could such an identity have been derived, since the AES specification makes no mention of the use of this other finite-field polynomial $100000001_b$? Is there any more information about where it comes from?

$\endgroup$
3
$\begingroup$

That alternate form, I think, makes things even more confusing than the standard form.

Since the matrix involved is circulant, the affine part of the AES S-box can be represented as $$ b_o = b_i \oplus (b_i \lll 1) \oplus (b_i \lll 2) \oplus (b_i \lll 3) \oplus (b_i \lll 4) \oplus 99\,, $$ where $\oplus$ is xor and $\lll$ is bit left rotation. So far so good. But mathematically, it is awkward to describe rotation as "moving bits".

So instead, we can treat a byte as a polynomial with coefficients modulo 2, that is, $\mathbb{F}_{2}[x]$, and a byte is $x^7\cdot c_7 + \ldots + x \cdot c_1 + c_0$, where the $c_i$ coefficients are the bits of the byte. What happens when we multiply by $x$? This is simply a left shift operation: $$ x(x^7\cdot c_7 + \ldots + x \cdot c_1 + c_0) = x^8\cdot c_7 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + 0\,. $$ Now, if we reduce this polynomial by $x^8 + 1$, which means that we replace $x^8$ by $1$ wherever available, we get $$ 1\cdot c_7 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + 0 = x^7 \cdot c_6 + \ldots + x^2 \cdot c_1 + x\cdot c_0 + c_7 \,, $$ which is precisely a rotation left by $1$. You can verify that the same principle works for any rotation value: multiplying by $x^k$ and reducing by $x^8 + 1$ rotates the polynomial by $k$ positions.

Therefore, we can understand the affine transformation of the AES S-box as a multiplication in the ring $\mathbb{F}_{2}[x]/(x^8 + 1)$: $$ b_o = b_i \cdot (1 + x + x^2 + x^3 + x^4) + 99 \in \mathbb{F}_{2}[x]/(x^8 + 1)\,. $$ In other words, this modulus only exists to describe bit rotation cleanly, in an algebraic way.

Converted to decimal, this becomes $b_o = b_i \cdot 31 \bmod 257 \oplus 99 $, but that form, to me, loses all its descriptive value.

$\endgroup$
0
$\begingroup$

The decimal value 31 is obtained from the first column of the transformation matrix (00011111). The next column is left rotated (00111110) which is could be expressed by 2*31. This applies for the other columns (left rotation) until it exceeds the field such as 16*31 mod 255

here are some calculation:

(8*31) %255 = 248 (11111000) ,the fourth column

(16*31) % 255= 241 (11110001) the fifth column.

I think 257 is a mistake and should be 255

enter image description here

$\endgroup$
  • $\begingroup$ I have verified the equation and there is no mistake. Note that you seem to have overlooked the part of my question where I say that the multiplication by $31_d$ is a finite-field multiplication - the modulus ($257_d$) is the finite-field reduction polynomial. $\endgroup$ – conchild Aug 16 '18 at 23:14

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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