AES加密算法(混合列)

Question

在混合列步骤中，使用下面的公式获得第一个元素值。

(1*02)+(2*03)+(3*01)+(4*01)，

其中*02意味着向右移动1位，如果设置了第一个元素的高位，则使用1b的XORing。

什么是“设置”(例如，'b4‘的第一个高位)？如果没有设置，流程会改变吗？

Answer 1

你的困惑来自于从它的实现方面学习算法，而不是从它的数学原理。首先看看这个wiki页面。在底部，您可以看到算法的MixColumns阶段的方程：

$$d_0=2b_0 + 3b_1+1b_2+1b_3\d_1=1b_0 + 2b_1+3b_2+1b_3\d_2=1b_0 + 1b_1+2b_2+3b_3\d_3=3b_0 + 1b_1+1b_2+2b_3$$

看起来很简单，但事实并非如此。我们在伽罗瓦有限域，所以“加”和“减”实际上是相同的操作，称为异或和乘法是非常复杂的，很难逆转。您的问题实际上是关于在实现Galois有限域乘法时可以实现的“捷径”之一。(看看C#示例这里)

我们可以把伽罗瓦乘法分成两步。

首先，我们采用用二进制$$0x53 \cdot 0xCA = 01010011b \cdot 11001010b$编写的两个值，并以与乘两个多项式相同的方式将它们相乘，请记住这里的加法是一个异或运算。$$ (x^6 + x^4 +x+ 1)(x^7 + x^6 + x^3 + x)\=\x^{13} +x^12}+x^11}+x^10}+ x^9 + x^8 + x^6 + x^5 + x^4 + x^3 + x^2 +x$，并将其转换为二进制$$11111101111110b$$

然后，我们获得前一步的结果，并通过一个特定的模块操作来运行它。对于Galois字段，我们运行模$x^8 + x^4 + x^3 +x+ 1$，它可以用二进制形式写成$100011011b$，用十六进制写成$0x11B$。

聪明的头脑们想过了，他们实际上找到了一种同时进行两种操作的方法，因为模基本上是一种环减(在Galois字段中，减法和加法是相同的异或运算)。

这就是为什么在应用该“快捷方式”之后，我们首先测试最重要的位是否等于1(一些程序员也将其称为“设置了位”)，然后减去(XOR) $0x11B$。值$0x11B$使用9位($1000110110亿美元)，在应用此快捷方式时，我们只有8位可用，因此当最重要的位等于0(未设置)时，我们实际上减去(XOR) $0x1B$ ($00011011亿美元)，值低于$x^8 + x^4 + x^3 +x+ 1$，并且不需要减法(XOR)。