AES - Finite Field Multiplication on 8 Bit Platform

Question

Section 4.1.1 "Finite Field Multiplication"(page 53) of "The Design of Rijndael", it states

How the equation 4.1 has been formed and transformed into equation 4.2?

---

In section 2.1.6 "Polynomials and Bytes"(page 15), equation 2.27 and 2.28, highest power of x is 7, whereas in above equations 4.1 and 4.2, it is 8. How?

In next line it states

The multiplication by 02 is denoted xtime(x). xtime can be implemented with a shift operation and a conditional XOR operation.

From Equation 2, it seems all values have been given left circular rotation by 1 bit, but what is Conditional XOR? How this multiplication can be implemented with a shift operation and a conditional XOR operation?

Answer 1

I. Polynomial representation

$b_7b_6b_5b_4b_3b_2b_1b_0$ represent the polynomial in $\operatorname{GF}(2)[X]$: $b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0$ .

$\texttt{02}$ is $\texttt{00000010}$ thus $0x^7+0x^6+0x^5+0x^4+0x^3+0x^2+1x^1+0x^0 = x$.

$b_7x^7+b_6x^6+b_5x^5+b_4x^4+b_3x^3+b_2x^2+b_1x^1+b_0x^0 \cdot x = $
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0$
or $b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$
that is equivalent to $b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1 = b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}$

II. Modulo reduction by $x^8 + x^4 + x^3 + x + 1$:

This leads to two problems:

• you have a loss of information: you cannot invert the S-box (which would be anoying in the case of AES)
• the upper bit does not fit into the byte

That is why there is the $\bmod m(x)$.

In the specification of Rijndael, we consider the bytes as polynomials. Byte addition is defined as addition of the corresponding polynomials. In order to define the byte multiplication, we use the following irredutible polynomial as reduction polynomial:

$m(x) = x^8 + x^4 + x^3 + x + 1$. (2.29, p.16)

Thus we will reduce $b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x)$.

Remark that:
$x^8 + x^4 + x^3 + x + 1 \equiv 0 \mod m(x)$
by $a \equiv c \mod m \iff a - b \equiv c - b \mod m$ we have
$x^8 \equiv - x^4 - x^3 - x - 1 \mod m(x)$
because $-1 = 1$ in $\operatorname{GF}(2)$
$x^8 \equiv x^4 + x^3 + x + 1 \mod m(x)$

Thus (going back to our previous equation):
$b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+\texttt{0}x^0 \mod m(x) = $
$b_7(x^4 + x^3 + x + 1)+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
$b_7x^4 + b_7x^3 + b_7x^1 + b_7x^0+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1= $
grouping by power this leads to:
$b_6x^7+b_5x^6+b_4x^5+b_7x^4 + b_3x^4+b_7x^3 + b_2x^3+b_1x^2+b_7x^1 + b_0x^1+b_7x^0= $
in other terms:
$b_6x^7+b_5x^6+b_4x^5+(b_7 + b_3)x^4+(b_7 + b_2)x^3+b_1x^2+(b_7 + b_0)x^1+b_7x^0$

III. $\ll$ and $\oplus$

Addition over $\operatorname{GF}(2)$ is equivalent to a XOR ($\oplus$) thus we find the previous formula: $b_6x^7+b_5x^6+b_4x^5+(b_7 \oplus b_3)x^4+(b_7 \oplus b_2)x^3+b_1x^2+(b_7 \oplus b_0)x^1+b_7x^0$

In the end the multiplication of $b_7b_6b_5b_4b_3b_2b_1b_0$ by $\texttt{02}$ can be seen as:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus \texttt{000}b_7b_7\texttt{0}b_7b_7$
or with a conditional XOR:
$(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus b_7\cdot(\texttt{00011011})$