在8位平台上的AES有限域乘法

Question

“Rijndael设计”第4.1.1节“有限域乘法”(第53页)指出

方程4.1是如何形成的，并转化为方程4.2?

在第2.1.6节“多项式和拜特斯”(第15页)中，方程2.27和2.28，x的最高幂为7，而在上述方程4.1和4.2中，为8。

在下一行中，它声明

乘以02的乘法表示xtime(x)。xtime可以通过shift操作和条件XOR操作来实现。

从方程2看，似乎所有的值都给出了1位的左圆旋转，但条件XOR是什么呢？如何使用shift操作和条件XOR操作实现这种乘法？

Answer 1

I.多项式表示

b_7b_6b_5b_4b_3b_2b_1b_0表示\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}是\texttt{00000010}，因此是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

或b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}

这相当于b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1 = b_7\ \ \ b_6b_5b_4b_3b_2b_1b_0\texttt{0}

II. x^8 + x^4 + x^3 + x + 1:

的模数还原

这导致了两个问题：

• 你失去了信息:你不能倒置S盒子(在AES的情况下，这将是被指定的)。
• 上位不适合字节。

这就是为什么会有\bmod m(x)。

在Rijndael规范中，我们把字节看作多项式。字节加法被定义为相应多项式的加法。为了定义字节乘法，我们使用以下不可恢复多项式作为约简多项式：m(x) = x^8 + x^4 + x^3 + x + 1。(2.29，第16页)

因此，我们将减少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)。

注：

x^8 + x^4 + x^3 + x + 1 \equiv 0 \mod m(x)

通过a \equiv c \mod m \iff a - b \equiv c - b \mod m我们有

x^8 \equiv - x^4 - x^3 - x - 1 \mod m(x)

因为-1 = 1 in \operatorname{GF}(2)

x^8 \equiv x^4 + x^3 + x + 1 \mod m(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 \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=

按权力分组会导致：

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=

在其他方面：

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和\oplus

\operatorname{GF}(2)上的加法等价于XOR (\oplus)，因此我们找到了前面的公式：

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

最后，b_7b_6b_5b_4b_3b_2b_1b_0的\texttt{02}乘法可以看作是：

(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus \texttt{000}b_7b_7\texttt{0}b_7b_7

或有条件的异或：

(b_7b_6b_5b_4b_3b_2b_1b_0 \ll 1) \oplus b_7\cdot(\texttt{00011011})