Rijndael，数字小于 0x1B 的 Mixcolumns 算法，维基百科 C 程序错误？
Rijndael, Mixcolumns algorithm for numbers less than 0x1B, wikipedia C program wrong?
我开始在 FPGA 中实现 AES 128 位算法并收集信息我在 wiki 中找到了一个 C 算法，想检查 mixcolumns 步骤是如何工作的，但我认为它不是在计算 mod 操作正确的方式。下面的程序执行 b[c] ^= 0x1b & h; 和变量 h 如果它设置了 MSB 则它使它成为 0xFF 否则 0x00 我一直无法理解 为什么？，对于任何数字高于 0x7F 将通过 XOR，其余将保持原样 ，我假设因为 MOD 操作将给出相同的数字，因为除数高于被除数，但我可以说它不应小于 0x7F，但应小于或等于 0x8A。在此先感谢您的见解。
维基百科Link.
void mixCol(uint8_t * r)
{
uint8_t a[4];
uint8_t b[4];
uint8_t h;
for(int c=0;c<4;c++)
{
a[c] = r[c];
/* h is 0xff if the high bit of r[c] is set, 0 otherwise */
h = (uint8_t)((int8_t)r[c] >> 7); /* arithmetic right shift, thus shifting in either zeros or ones */
b[c] = r[c] << 1; /* implicitly removes high bit because b[c] is an 8-bit char, so we xor by 0x1b and not 0x11b in the next line */
b[c] ^= 0x1B & h; /* Rijndael's Galois field, The xor is not applied when is less than 0x80 */
}
r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
printf("%X %X\n",b[0],h);
}
int main()
{
uint8_t col1[4] = {0x80,0xbf,0x5d,0x80};
mixCol(col1);
return 0;
}
为清楚起见重写（并更正模运算）。简答：
Why does the modulo operation only examine one bit (bit 8, 0x80)?
有问题的运算实现了 GF(28) 乘以 2 关于减少多项式 0x11B.
因为被乘数只有第二位设置（位 1；2 = 21），乘法步骤减少到左移一位。因为另一个被乘数是一个 8 位值，它被限制在 0..255（0x00 到 0xFF）范围内，所以乘积被限制在 0..510（0x00 到 0x1FE）范围内的偶数。
除数0x11B的大小为9位，乘积也最多为9位。这意味着模步骤也减少为单个位检查。从逻辑上讲，检查是值在左移一位后是否设置了第九位。 （之所以测试在位移后是& 0x100，而不是位移后是≥ 0x11B，是因为GF(2[=212中模运算的差异=]N) 和正常算术。如果模运算与正常算术相同，那么 ≥ 确实会被使用。但它没有。)
实现不是在大于 8 位的变量上操作，而是在移位之前检查第八位。因为结果也被限制为八位，所以操作减少到
result = (byte & 0x80) ? (byte << 1) ^ 0x1B : (byte << 1);
记住，在GF(2N) no-one可以听到你尖叫 乘法、加法、减法、除法、取模等算术运算与我们习惯的不同。
GF(2N)算术中，每个值v（一个非负整数) 表示一个 多项式 。如果我们将v的二进制数标记为bk，然后
v = 2N-1bN-1 + 2N-1 bN-1 + .. + 21 b1 + 20b0
表示多项式
bN-1 x N-1 + bN-2 xN-2 + ... + b1 x1 + b0x0
因为系数bk只能是0或1，这是一个具有 2N 个元素的特征 2 有限域，也称为伽罗华域 GF(2N).
要理解的关键是我们不关心 x 有什么值；我们甚至不关心 x 是什么类型，除了 x0 = 1。我们真的对由非负整数值 v 表示的多项式进行运算，因此我们的基本算术运算——加法（和减法）、乘法和除法（因此还有模运算）——在 v 上的工作方式与在常规算术上的工作方式不同。
因为多项式系数bk是二进制的，我们有
xk + xk = 0
而不是 2xk 也不 xk+1。我们的基本算术运算不会"carry"到下一个更高的系数（二进制数）。 （我将在下面将其称为 "no-carry"。）
加法和减法（+和-）：
在GF(2N中，这些是使用exclusive-or[=435完成的=] 对 v 的操作。 （当有多个项时，结果基本上是输入的 even parity；0 如果有偶数个 1 二进制数字，如果 1 是奇数。 )
unsigned long gf2n_add(const unsigned long a, const unsigned long b)
{
return a ^ b;
}
unsigned long gf2n_sub(const unsigned long a, const unsigned long b)
{
return a ^ b;
}
乘法 (⋅):
由于多项式乘法规则，我们可以用long multiplication来描述GF(2N)乘法，除了我们执行 exclusive-or 操作而不是加法。
/* Note: we ignore overflow, and instead assume that a and b
are small enough for the result to not overflow. */
unsigned long gf2n_mul(unsigned long a, const unsigned long b)
{
unsigned long result = 0UL;
while (b) {
if (b & 1)
result ^= a;
a <<= 1;
b >>= 1;
}
return result;
}
除法和模数（/和%）：
为了可读性，我将在这个答案中对 GF(2N) 模运算使用 ∅。 （您可能不会在其他任何地方看到以这种方式使用空集字符；我只是没有想到任何更好的方法。）
GF(2N) 中的除法实现为 inv 的乘法rse，而且相当复杂；幸运的是，我们这里不需要它。但是，它确实会影响我们确实需要的模运算。
finite field arithmetic shows an example of modulo operation in GF(2N). It is very similar to long division 上的维基百科文章。
我们从复制到结果的原始红利开始。只要结果至少有与除数一样多的二进制数字，我们 exclusive-OR 将除数左移的结果，使其最高位集与结果中的最高位集对齐。
注意，因为no-carry，我们这里不使用比较运算符（≥），只看结果中设置的最高位
因为exclusive-OR操作会影响我们检查的位，所以我们必须按降序检查位。与其反复左移除数，不如使用我们左移一次的临时值，然后循环将临时值右移一位，并在每个循环中测试一位：
/* ceil(log2(v+1)) */
int bits(unsigned long v)
{
int result = 0;
while (v) {
v >>= 1;
result++;
}
}
unsigned long mod(unsigned long v, unsigned long m)
{
/* mod(v,0) is undefined; we'll just return 0. */
if (!m)
return v;
if (v > m) {
const int v_size = bits(v);
const int m_size = bits(m);
/* High has only the highest bit in v set. */
unsigned long high = 1UL << (v_size - 1);
/* Mask is m shifted left so that its highest
bit matches the value of high. */
unsigned long mask = m << (v_size - m_size);
/* Number of bits we need to examine. */
int i = v_size - m_size + 1;
/* As an example, if
v = 110101 in binary
m = 101 in binary
then at this point,
v_size = 6
m_size = 3
high = 100000 in binary
mask = 101000
i = 4.
For i steps:
If v has the bit corresponding to high set,
i.e. (v & high) is nonzero, then:
v = v exclusive-or mask
shift high right
shift mask right
Return v
*/
while (i--) {
if (high & v)
v ^= mask;
high >>= 1;
mask >>= 1;
}
return v;
}
if (v < m)
return v;
/* v == m */
return 0UL;
}
一个例子肯定能阐明这个想法。让我们计算（二进制）1010001 ∅ 1001（十进制，这是 81 ∅ 9）。请注意，（中间）结果中设置的最高位决定了 exclusive-or 是否完成；它们代表的值是 not compared:
1010001
^ 1001
──┴───────
0011001
^ 1001
────┴─────
01011
^ 1001
─────┴────
0010 (2 digits; less than 4), so
══════════
10
因此，1010001 ∅ 1001 = 10（二进制）；在十进制中，81 ∅ 9 = 2。（根据正常算术规则，81 % 9 = 0。）
值得注意的是，这是从高位到低位进行的，并且只检查剩下的最高有效位；我们不使用 > 或 ≥ 比较值。检查了 （被除数中的二进制位数）-（除数中的二进制位数）+ 1 位，以及尽可能多（最多 exclusive-or ^ 操作已经完成exclusive-OR 操作，总的来说。
乘法 (×) 关于由 c 表示的不可约多项式：
在 Rijndael 中，乘法是关于多项式 x8 + x 的不可约多项式4 + x3 + x1 + x0，表示为值 283（十进制，十六进制为 0x11B）。
本质上，a×b（相对于c）只是
(a ⋅ b) ∅ c
对 GF(2N) 算法使用上述定义。
澄清一下：
* 和 ^ 表示正常的算术运算，
<< 是左移位（对应算术乘以2）， >> 是右移位，
⋅ 仍然用于 GF(2N) 乘法，
× 对于 GF(2N) 与一些减少多项式的乘法，
∅ 用于 GF(2N) 模运算，以及
+ 和 - 指的是正常的算术加法和减法。
让我们看看 OP 试图实现的功能，以及它在 Rijndael mix columns 操作中的定义。
我们可以看到，我们只将（相对于由 0x11B 表示的 Rijndael 多项式）每个值乘以 1（表示多项式 x0）、2（表示多项式x1）、或3（表示多项式x1 + x0):
⎡ r0 ⎤ ⎡ 2 3 1 1 ⎤ ⎡ a0 ⎤
⎢ r1 ⎥ = ⎢ 1 2 3 1 ⎥ ⎢ a1 ⎥
⎢ r2 ⎥ ⎢ 1 1 2 3 ⎥ ⎢ a2 ⎥
⎣ r3 ⎦ ⎣ 3 1 1 2 ⎦ ⎣ a3 ⎦
将上面的运算按照GF(2N)的算术规则展开，我们有
r0 = (a0 × 2) ^ (a1 × 3) ^ (a2 × 1) ^ (a3 × 1)
r1 = (a0 × 1) ^ (a1 × 2) ^ (a2 × 3) ^ (a3 × 1)
r2 = (a0 × 1) ^ (a1 × 1) ^ (a2 × 2) ^ (a3 × 3)
r3 = (a0 × 3) ^ (a1 × 1) ^ (a2 × 1) ^ (a3 × 2)
请注意，在 GF(2N) 中，对于 N ≥ 2，3 = 1 ^ 2，意思是a3 × 3 = a3 ^ (a3 × 2) = (a3 × 2) ^ a3。如果我们用临时变量b0来表示a0 × 2，我们可以用
a0 × 1 = a0
a0 × 2 = b0
a0 × 3 = b0 ^ a0
a1、a2 和 a3 也类似。然后函数简化为
b0 = a0 × 2
b1 = a1 × 2
b2 = a2 × 2
b3 = a3 × 2
r0 = ( b0 ) ^ ( a1 ^ b1 ) ^ ( a2 ) ^ ( a3 )
r1 = ( a0 ) ^ ( b1 ) ^ ( a2 ^ b2 ) ^ ( a3 )
r2 = ( a0 ) ^ ( a1 ) ^ ( b2 ) ^ ( a3 ^ b3 )
r3 = ( a0 ^ b0 ) ^ ( a1 ) ^ ( a2 ) ^ ( b3 )
并且由于 ^ 是可交换的（顺序无关紧要），我们可以将结果重写为
r0 = a1 ^ a2 ^ a3 ^ b0 ^ b1
r1 = a0 ^ a2 ^ a3 ^ b1 ^ b2
r2 = a0 ^ a1 ^ a3 ^ b2 ^ b3
r3 = a0 ^ a1 ^ a2 ^ b3 ^ b0
让我们看看如何计算 a0 × 2、a1 × 2、a2 × 2 和 a3 × 2，关于约简多项式 0x11b。请记住，根据 × 的定义，它们分别等同于 (a0 ⋅ 2) ∅ 0x11b、(a1 ⋅ 2) ∅ 0x11b、(a2 ⋅ 2) ∅ 0x11b 和 (a3 ⋅ 2) ∅ 0x11b。
⋅ 2 部分很简单，因为它实际上只是将值左移一位二进制数字。因为a0..a3是8位值，在0x00和0xFF之间，包括，移位后的最大值是0x1FE（或111111110 in二进制）。
现在，回想一下GF(2N中是如何实现模运算的。在这里，被除数的二进制数要么与约简多项式的位数相同，要么更少；因此，循环减少为单个位测试：
b0 = a0 << 1;
b1 = a1 << 1;
b2 = a2 << 1;
b3 = a3 << 1;
if (b0 & 0x100) b0 ^= 0x11B;
if (b1 & 0x100) b1 ^= 0x11B;
if (b2 & 0x100) b2 ^= 0x11B;
if (b3 & 0x100) b3 ^= 0x11B;
除了因为 b0 .. b3 是只有 8 位大小，上面的方法行不通。解决办法当然是在换班前做位测试。由于第 9 位 (0x100) 无论如何都会被丢弃，exclusive-oring 与 0x11B 等同于 0x1B:
if (a0 & 0x80)
b0 = (a0 << 1) ^ 0x1B;
else
b0 = (a0 << 1);
b1、b2 和 b3 也类似。
不幸的是，if 子句在大多数常见硬件上相对较慢。为了加快操作速度，我们可以使用一个表达式，如果在参数中设置了位 7，则产生 0x1B，否则为零：
#define F(v) ((v & 0x80) ? 0x1B : 0x00)
然后
b0 = (a0 << 1) ^ F(a0);
b1 = (a1 << 1) ^ F(a1);
b2 = (a2 << 1) ^ F(a2);
b3 = (a3 << 1) ^ F(a3);
在使用 two's complement 表示负整数的体系结构中，我们可以避免使用三元运算符（实际上是伪装的 if），因为将值转换为带符号的 8 位类型，将它除以 128（所有理智的 C 编译器将实现右移 7 位；C 中有符号二进制右移的结果是 implementation-dependent），然后转换回无符号 8 位整数类型，产生0xFF 如果设置了高位，则 0x00 否则。幸运的是，如果 C 编译器支持 int8_t 类型，标准规定它必须使用二进制补码！
#define NMASK(v) ((uint8_t)((int8_t)(v) / 128))
b0 = (a0 << 1) ^ (NMASK(a0) & 0x1B);
b1 = (a1 << 1) ^ (NMASK(a1) & 0x1B);
b2 = (a2 << 1) ^ (NMASK(a2) & 0x1B);
b3 = (a3 << 1) ^ (NMASK(a3) & 0x1B);
（请注意，如果在硬件中实现，(NMASK(v) & 0x1B) == (NMASK(v & 0x80) & 0x1B)，即只检查一个输入位，并产生五个位，全部为零或一。
维基百科 implementation example 和 OP 正是这样做的。本质上：
a0 = input_byte_0
a1 = input_byte_1
a2 = input_byte_2
a3 = input_byte_3
b0 = (a0 << 1) ^ (0x1B & (uint8_t)( (int8_t)a0 / 128 ))
b1 = (a1 << 1) ^ (0x1B & (uint8_t)( (int8_t)a1 / 128 ))
b2 = (a2 << 1) ^ (0x1B & (uint8_t)( (int8_t)a2 / 128 ))
b3 = (a3 << 1) ^ (0x1B & (uint8_t)( (int8_t)a3 / 128 ))
output_byte_0 = a1 ^ a2 ^ a3 ^ b0 ^ b1
output_byte_1 = a0 ^ a2 ^ a3 ^ b1 ^ b2
output_byte_2 = a0 ^ a1 ^ a3 ^ b2 ^ b3
output_byte_3 = a0 ^ a1 ^ a2 ^ b3 ^ b0
在 FPGA 实现中将字节扩展为单独的位时，我不确定是否应该为每个单独的输出位扩展表达式（这应该很简单；我会亲自编写一个 awk 脚本或做一些其他事情对我来说是艰苦的工作），或者是否使用中间状态来减少 look-up 表的大小。我自己还没有机会玩 FPGA。
我开始在 FPGA 中实现 AES 128 位算法并收集信息我在 wiki 中找到了一个 C 算法，想检查 mixcolumns 步骤是如何工作的，但我认为它不是在计算 mod 操作正确的方式。下面的程序执行 b[c] ^= 0x1b & h; 和变量 h 如果它设置了 MSB 则它使它成为 0xFF 否则 0x00 我一直无法理解 为什么？，对于任何数字高于 0x7F 将通过 XOR，其余将保持原样 ，我假设因为 MOD 操作将给出相同的数字，因为除数高于被除数，但我可以说它不应小于 0x7F，但应小于或等于 0x8A。在此先感谢您的见解。
维基百科Link.
void mixCol(uint8_t * r)
{
uint8_t a[4];
uint8_t b[4];
uint8_t h;
for(int c=0;c<4;c++)
{
a[c] = r[c];
/* h is 0xff if the high bit of r[c] is set, 0 otherwise */
h = (uint8_t)((int8_t)r[c] >> 7); /* arithmetic right shift, thus shifting in either zeros or ones */
b[c] = r[c] << 1; /* implicitly removes high bit because b[c] is an 8-bit char, so we xor by 0x1b and not 0x11b in the next line */
b[c] ^= 0x1B & h; /* Rijndael's Galois field, The xor is not applied when is less than 0x80 */
}
r[0] = b[0] ^ a[3] ^ a[2] ^ b[1] ^ a[1]; /* 2 * a0 + a3 + a2 + 3 * a1 */
r[1] = b[1] ^ a[0] ^ a[3] ^ b[2] ^ a[2]; /* 2 * a1 + a0 + a3 + 3 * a2 */
r[2] = b[2] ^ a[1] ^ a[0] ^ b[3] ^ a[3]; /* 2 * a2 + a1 + a0 + 3 * a3 */
r[3] = b[3] ^ a[2] ^ a[1] ^ b[0] ^ a[0]; /* 2 * a3 + a2 + a1 + 3 * a0 */
printf("%X %X\n",b[0],h);
}
int main()
{
uint8_t col1[4] = {0x80,0xbf,0x5d,0x80};
mixCol(col1);
return 0;
}
为清楚起见重写（并更正模运算）。简答：
Why does the modulo operation only examine one bit (bit 8, 0x80)?
有问题的运算实现了 GF(28) 乘以 2 关于减少多项式 0x11B.
因为被乘数只有第二位设置（位 1；2 = 21），乘法步骤减少到左移一位。因为另一个被乘数是一个 8 位值，它被限制在 0..255（0x00 到 0xFF）范围内，所以乘积被限制在 0..510（0x00 到 0x1FE）范围内的偶数。
除数0x11B的大小为9位，乘积也最多为9位。这意味着模步骤也减少为单个位检查。从逻辑上讲，检查是值在左移一位后是否设置了第九位。 （之所以测试在位移后是& 0x100，而不是位移后是≥ 0x11B，是因为GF(2[=212中模运算的差异=]N) 和正常算术。如果模运算与正常算术相同，那么 ≥ 确实会被使用。但它没有。)
实现不是在大于 8 位的变量上操作，而是在移位之前检查第八位。因为结果也被限制为八位，所以操作减少到
result = (byte & 0x80) ? (byte << 1) ^ 0x1B : (byte << 1);
记住，在GF(2N) no-one可以听到你尖叫 乘法、加法、减法、除法、取模等算术运算与我们习惯的不同。
GF(2N)算术中，每个值v（一个非负整数) 表示一个 多项式 。如果我们将v的二进制数标记为bk，然后
v = 2N-1bN-1 + 2N-1 bN-1 + .. + 21 b1 + 20b0
表示多项式
bN-1 x N-1 + bN-2 xN-2 + ... + b1 x1 + b0x0
因为系数bk只能是0或1，这是一个具有 2N 个元素的特征 2 有限域，也称为伽罗华域 GF(2N).
要理解的关键是我们不关心 x 有什么值；我们甚至不关心 x 是什么类型，除了 x0 = 1。我们真的对由非负整数值 v 表示的多项式进行运算，因此我们的基本算术运算——加法（和减法）、乘法和除法（因此还有模运算）——在 v 上的工作方式与在常规算术上的工作方式不同。
因为多项式系数bk是二进制的，我们有
xk + xk = 0
而不是 2xk 也不 xk+1。我们的基本算术运算不会"carry"到下一个更高的系数（二进制数）。 （我将在下面将其称为 "no-carry"。）
加法和减法（+和-）：
在GF(2N中，这些是使用exclusive-or[=435完成的=] 对 v 的操作。 （当有多个项时，结果基本上是输入的 even parity；0 如果有偶数个 1 二进制数字，如果 1 是奇数。 )
unsigned long gf2n_add(const unsigned long a, const unsigned long b)
{
return a ^ b;
}
unsigned long gf2n_sub(const unsigned long a, const unsigned long b)
{
return a ^ b;
}
乘法 (⋅):
由于多项式乘法规则，我们可以用long multiplication来描述GF(2N)乘法，除了我们执行 exclusive-or 操作而不是加法。
/* Note: we ignore overflow, and instead assume that a and b
are small enough for the result to not overflow. */
unsigned long gf2n_mul(unsigned long a, const unsigned long b)
{
unsigned long result = 0UL;
while (b) {
if (b & 1)
result ^= a;
a <<= 1;
b >>= 1;
}
return result;
}
除法和模数（/和%）：
为了可读性，我将在这个答案中对 GF(2N) 模运算使用 ∅。 （您可能不会在其他任何地方看到以这种方式使用空集字符；我只是没有想到任何更好的方法。）
GF(2N) 中的除法实现为 inv 的乘法rse，而且相当复杂；幸运的是，我们这里不需要它。但是，它确实会影响我们确实需要的模运算。
finite field arithmetic shows an example of modulo operation in GF(2N). It is very similar to long division 上的维基百科文章。
我们从复制到结果的原始红利开始。只要结果至少有与除数一样多的二进制数字，我们 exclusive-OR 将除数左移的结果，使其最高位集与结果中的最高位集对齐。
注意，因为no-carry，我们这里不使用比较运算符（≥），只看结果中设置的最高位
因为exclusive-OR操作会影响我们检查的位，所以我们必须按降序检查位。与其反复左移除数，不如使用我们左移一次的临时值，然后循环将临时值右移一位，并在每个循环中测试一位：
/* ceil(log2(v+1)) */
int bits(unsigned long v)
{
int result = 0;
while (v) {
v >>= 1;
result++;
}
}
unsigned long mod(unsigned long v, unsigned long m)
{
/* mod(v,0) is undefined; we'll just return 0. */
if (!m)
return v;
if (v > m) {
const int v_size = bits(v);
const int m_size = bits(m);
/* High has only the highest bit in v set. */
unsigned long high = 1UL << (v_size - 1);
/* Mask is m shifted left so that its highest
bit matches the value of high. */
unsigned long mask = m << (v_size - m_size);
/* Number of bits we need to examine. */
int i = v_size - m_size + 1;
/* As an example, if
v = 110101 in binary
m = 101 in binary
then at this point,
v_size = 6
m_size = 3
high = 100000 in binary
mask = 101000
i = 4.
For i steps:
If v has the bit corresponding to high set,
i.e. (v & high) is nonzero, then:
v = v exclusive-or mask
shift high right
shift mask right
Return v
*/
while (i--) {
if (high & v)
v ^= mask;
high >>= 1;
mask >>= 1;
}
return v;
}
if (v < m)
return v;
/* v == m */
return 0UL;
}
一个例子肯定能阐明这个想法。让我们计算（二进制）1010001 ∅ 1001（十进制，这是 81 ∅ 9）。请注意，（中间）结果中设置的最高位决定了 exclusive-or 是否完成；它们代表的值是 not compared:
1010001
^ 1001
──┴───────
0011001
^ 1001
────┴─────
01011
^ 1001
─────┴────
0010 (2 digits; less than 4), so
══════════
10
因此，1010001 ∅ 1001 = 10（二进制）；在十进制中，81 ∅ 9 = 2。（根据正常算术规则，81 % 9 = 0。）
值得注意的是，这是从高位到低位进行的，并且只检查剩下的最高有效位；我们不使用 > 或 ≥ 比较值。检查了 （被除数中的二进制位数）-（除数中的二进制位数）+ 1 位，以及尽可能多（最多 exclusive-or ^ 操作已经完成exclusive-OR 操作，总的来说。
乘法 (×) 关于由 c 表示的不可约多项式：
在 Rijndael 中，乘法是关于多项式 x8 + x 的不可约多项式4 + x3 + x1 + x0，表示为值 283（十进制，十六进制为 0x11B）。
本质上，a×b（相对于c）只是
(a ⋅ b) ∅ c
对 GF(2N) 算法使用上述定义。
澄清一下：
* 和 ^ 表示正常的算术运算，
<< 是左移位（对应算术乘以2）， >> 是右移位，
⋅ 仍然用于 GF(2N) 乘法，
× 对于 GF(2N) 与一些减少多项式的乘法，
∅ 用于 GF(2N) 模运算，以及
+ 和 - 指的是正常的算术加法和减法。
让我们看看 OP 试图实现的功能，以及它在 Rijndael mix columns 操作中的定义。
我们可以看到，我们只将（相对于由 0x11B 表示的 Rijndael 多项式）每个值乘以 1（表示多项式 x0）、2（表示多项式x1）、或3（表示多项式x1 + x0):
⎡ r0 ⎤ ⎡ 2 3 1 1 ⎤ ⎡ a0 ⎤
⎢ r1 ⎥ = ⎢ 1 2 3 1 ⎥ ⎢ a1 ⎥
⎢ r2 ⎥ ⎢ 1 1 2 3 ⎥ ⎢ a2 ⎥
⎣ r3 ⎦ ⎣ 3 1 1 2 ⎦ ⎣ a3 ⎦
将上面的运算按照GF(2N)的算术规则展开，我们有
r0 = (a0 × 2) ^ (a1 × 3) ^ (a2 × 1) ^ (a3 × 1)
r1 = (a0 × 1) ^ (a1 × 2) ^ (a2 × 3) ^ (a3 × 1)
r2 = (a0 × 1) ^ (a1 × 1) ^ (a2 × 2) ^ (a3 × 3)
r3 = (a0 × 3) ^ (a1 × 1) ^ (a2 × 1) ^ (a3 × 2)
请注意，在 GF(2N) 中，对于 N ≥ 2，3 = 1 ^ 2，意思是a3 × 3 = a3 ^ (a3 × 2) = (a3 × 2) ^ a3。如果我们用临时变量b0来表示a0 × 2，我们可以用
a0 × 1 = a0
a0 × 2 = b0
a0 × 3 = b0 ^ a0
a1、a2 和 a3 也类似。然后函数简化为
b0 = a0 × 2
b1 = a1 × 2
b2 = a2 × 2
b3 = a3 × 2
r0 = ( b0 ) ^ ( a1 ^ b1 ) ^ ( a2 ) ^ ( a3 )
r1 = ( a0 ) ^ ( b1 ) ^ ( a2 ^ b2 ) ^ ( a3 )
r2 = ( a0 ) ^ ( a1 ) ^ ( b2 ) ^ ( a3 ^ b3 )
r3 = ( a0 ^ b0 ) ^ ( a1 ) ^ ( a2 ) ^ ( b3 )
并且由于 ^ 是可交换的（顺序无关紧要），我们可以将结果重写为
r0 = a1 ^ a2 ^ a3 ^ b0 ^ b1
r1 = a0 ^ a2 ^ a3 ^ b1 ^ b2
r2 = a0 ^ a1 ^ a3 ^ b2 ^ b3
r3 = a0 ^ a1 ^ a2 ^ b3 ^ b0
让我们看看如何计算 a0 × 2、a1 × 2、a2 × 2 和 a3 × 2，关于约简多项式 0x11b。请记住，根据 × 的定义，它们分别等同于 (a0 ⋅ 2) ∅ 0x11b、(a1 ⋅ 2) ∅ 0x11b、(a2 ⋅ 2) ∅ 0x11b 和 (a3 ⋅ 2) ∅ 0x11b。
⋅ 2 部分很简单，因为它实际上只是将值左移一位二进制数字。因为a0..a3是8位值，在0x00和0xFF之间，包括，移位后的最大值是0x1FE（或111111110 in二进制）。
现在，回想一下GF(2N中是如何实现模运算的。在这里，被除数的二进制数要么与约简多项式的位数相同，要么更少；因此，循环减少为单个位测试：
b0 = a0 << 1;
b1 = a1 << 1;
b2 = a2 << 1;
b3 = a3 << 1;
if (b0 & 0x100) b0 ^= 0x11B;
if (b1 & 0x100) b1 ^= 0x11B;
if (b2 & 0x100) b2 ^= 0x11B;
if (b3 & 0x100) b3 ^= 0x11B;
除了因为 b0 .. b3 是只有 8 位大小，上面的方法行不通。解决办法当然是在换班前做位测试。由于第 9 位 (0x100) 无论如何都会被丢弃，exclusive-oring 与 0x11B 等同于 0x1B:
if (a0 & 0x80)
b0 = (a0 << 1) ^ 0x1B;
else
b0 = (a0 << 1);
b1、b2 和 b3 也类似。
不幸的是，if 子句在大多数常见硬件上相对较慢。为了加快操作速度，我们可以使用一个表达式，如果在参数中设置了位 7，则产生 0x1B，否则为零：
#define F(v) ((v & 0x80) ? 0x1B : 0x00)
然后
b0 = (a0 << 1) ^ F(a0);
b1 = (a1 << 1) ^ F(a1);
b2 = (a2 << 1) ^ F(a2);
b3 = (a3 << 1) ^ F(a3);
在使用 two's complement 表示负整数的体系结构中，我们可以避免使用三元运算符（实际上是伪装的 if），因为将值转换为带符号的 8 位类型，将它除以 128（所有理智的 C 编译器将实现右移 7 位；C 中有符号二进制右移的结果是 implementation-dependent），然后转换回无符号 8 位整数类型，产生0xFF 如果设置了高位，则 0x00 否则。幸运的是，如果 C 编译器支持 int8_t 类型，标准规定它必须使用二进制补码！
#define NMASK(v) ((uint8_t)((int8_t)(v) / 128))
b0 = (a0 << 1) ^ (NMASK(a0) & 0x1B);
b1 = (a1 << 1) ^ (NMASK(a1) & 0x1B);
b2 = (a2 << 1) ^ (NMASK(a2) & 0x1B);
b3 = (a3 << 1) ^ (NMASK(a3) & 0x1B);
（请注意，如果在硬件中实现，(NMASK(v) & 0x1B) == (NMASK(v & 0x80) & 0x1B)，即只检查一个输入位，并产生五个位，全部为零或一。
维基百科 implementation example 和 OP 正是这样做的。本质上：
a0 = input_byte_0
a1 = input_byte_1
a2 = input_byte_2
a3 = input_byte_3
b0 = (a0 << 1) ^ (0x1B & (uint8_t)( (int8_t)a0 / 128 ))
b1 = (a1 << 1) ^ (0x1B & (uint8_t)( (int8_t)a1 / 128 ))
b2 = (a2 << 1) ^ (0x1B & (uint8_t)( (int8_t)a2 / 128 ))
b3 = (a3 << 1) ^ (0x1B & (uint8_t)( (int8_t)a3 / 128 ))
output_byte_0 = a1 ^ a2 ^ a3 ^ b0 ^ b1
output_byte_1 = a0 ^ a2 ^ a3 ^ b1 ^ b2
output_byte_2 = a0 ^ a1 ^ a3 ^ b2 ^ b3
output_byte_3 = a0 ^ a1 ^ a2 ^ b3 ^ b0
在 FPGA 实现中将字节扩展为单独的位时，我不确定是否应该为每个单独的输出位扩展表达式（这应该很简单；我会亲自编写一个 awk 脚本或做一些其他事情对我来说是艰苦的工作），或者是否使用中间状态来减少 look-up 表的大小。我自己还没有机会玩 FPGA。