AES逆MixColumns实现异常：十六进制乘法计算错误排查

我正在用C++实现AES算法，目前卡在逆MixColumns函数上。该函数本质是数组与矩阵的点积运算，已完成加密阶段的MixColumns实现，但逆函数输出结果与预期不符。

乘法规则说明 #

• 乘2规则：d4×02 即执行 d4 << 1，若d4最高位为1，则异或0x1B
• 基于此推导的其他乘法逻辑：
  • x×9 = (((x×2)×2)×2) ⊕ x
  • x×11 = (((((x×2)×2)⊕x)×2)⊕x)
  • x×13 = (((((x×2)⊕x)×2)×2)⊕x)
  • x×14 = (((((x×2)⊕x)×2)⊕x)×2)

实现代码 #

void InvMixColumns(unsigned char plainText[4][4])
{
    unsigned char temp[4] = { 0x00,0x00,0x00,0x00 };
    unsigned char newState[4][4] = { {0,0,0,0},
                                     {0,0,0,0},
                                     {0,0,0,0},
                                     {0,0,0,0} };

    int rijndaelMatric[4][4] = { {14,11,13,9},
                                 {9,14,11,13},
                                 {13,9,14,11},
                                 {11,13,9,14} };

    for (int y = 0; y < 4; y++)
    {
        int z = 0;
        for (int i = 0; i < 4; i++)
        {
            temp[i] = 0x00;
        }
        for (int x = 0; x < 4; x++)
        {
            for (int j = 0; j < 4; j++)
            {
                unsigned char constant = 0x00;
                switch (rijndaelMatric[z][j])
                {
                case 9:
                    if ((plainText[j][y] & 0x80) == 0x80)
                        constant = 0x1B;
                    temp[j] = ((((((plainText[j][y] << 1) ^ constant) << 1) ^ constant) << 1) ^ constant) ^ plainText[j][y];
                    break;
                case 11:
                    if ((plainText[j][y] & 0x80) == 0x80)
                        constant = 0x1B;
                    temp[j] = (((((((plainText[j][y] << 1) ^ constant) << 1) ^ constant) ^ plainText[j][y]) << 1) ^ constant) ^ plainText[j][y];
                    break;
                case 13:
                    if ((plainText[j][y] & 0x80) == 0x80)
                        constant = 0x1B;
                    temp[j] = (((((((plainText[j][y] << 1) ^ constant) ^ plainText[j][y]) << 1) ^ constant) << 1) ^ constant) ^ plainText[j][y];
                    break;
                case 14:
                    if ((plainText[j][y] & 0x80) == 0x80)
                        constant = 0x1B;
                    temp[j] = (((((((plainText[j][y] << 1) ^ constant) ^ plainText[j][y]) << 1) ^ constant) ^ plainText[j][y]) << 1) ^ constant;
                    break;
                }
            }
            newState[x][y] = int(temp[0]) ^ int(temp[1]) ^ int(temp[2]) ^ int(temp[3]);
            z++;
        }
    }

    for (int x = 0; x < 4; x++)
    {
        for (int y = 0; y < 4; y++)
        {
            plainText[x][y] = newState[x][y];
        }
    }
}

测试数据 #

输入状态矩阵：
| be | ae | 65 | 1a |
| 4e | 78 | ac | d7 |
| c3 | 25 | 94 | 27 |
| c1 | 76 | 88 | 64 |

预期输出：
| 89 | c2 | 22 | fd |
| 66 | 3b | 6b | 44 |
| 0b | 58 | 62 | c7 |
| 16 | 24 | fe | f0 |

实际输出：
| 89 | c2 | 0f | cb |
| 4b | 16 | 70 | 44 |
| 10 | 43 | 54 | ea |
| 20 | 12 | fe | eb |

错误原因分析 #

核心错误在于乘法实现时，仅根据原始输入值的最高位设置异或常量0x1B，但每次左移操作后的中间结果最高位可能发生变化，需要重新判断是否异或。例如计算x×9时，三次左移操作的中间结果都可能产生新的最高位1，每一步都需要单独检查并处理异或，而非复用原始值的判断结果。

修正方案 #

1. 封装独立的乘2函数，确保每次移位都正确处理最高位：

unsigned char mul2(unsigned char x) {
    unsigned char result = x << 1;
    if (x & 0x80) { // 移位前的x最高位为1，移位后会溢出，需要异或0x1B
        result ^= 0x1B;
    }
    return result;
}

2. 基于mul2函数实现其他乘法，逻辑更清晰且不易出错：

unsigned char mul9(unsigned char x) {
    return mul2(mul2(mul2(x))) ^ x;
}

unsigned char mul11(unsigned char x) {
    return mul2(mul2(mul2(x) ^ x)) ^ x;
}

unsigned char mul13(unsigned char x) {
    return mul2(mul2(mul2(x) ^ x)) ^ x; // 等价于((x*2+x)*2)*2 +x
}

unsigned char mul14(unsigned char x) {
    return mul2(mul2(mul2(x) ^ x) ^ x); // 等价于(((x*2+x)*2)+x)*2
}

3. 修改InvMixColumns函数，调用封装好的乘法函数替代手动嵌套移位：

void InvMixColumns(unsigned char plainText[4][4])
{
    unsigned char newState[4][4] = {0};
    int rijndaelMatric[4][4] = { {14,11,13,9},
                                 {9,14,11,13},
                                 {13,9,14,11},
                                 {11,13,9,14} };

    for (int y = 0; y < 4; y++) { // 遍历每一列
        for (int x = 0; x < 4; x++) { // 遍历每一行
            unsigned char sum = 0;
            for (int j = 0; j < 4; j++) { // 计算矩阵行与状态列的点积
                switch (rijndaelMatric[x][j]) {
                case 9:
                    sum ^= mul9(plainText[j][y]);
                    break;
                case 11:
                    sum ^= mul11(plainText[j][y]);
                    break;
                case 13:
                    sum ^= mul13(plainText[j][y]);
                    break;
                case 14:
                    sum ^= mul14(plainText[j][y]);
                    break;
                }
            }
            newState[x][y] = sum;
        }
    }

    // 将结果复制回原矩阵
    for (int x = 0; x < 4; x++) {
        for (int y = 0; y < 4; y++) {
            plainText[x][y] = newState[x][y];
        }
    }
}

说明 #

修正后的代码通过封装乘2操作，确保每一步移位都正确处理GF(2^8)域下的模运算，同时简化了乘法逻辑，避免了手动嵌套移位带来的错误。

内容的提问来源于stack exchange，提问作者Lachlan