AES逆列混合（InvMixColumns）Python实现错误排查求助

问题描述 #

手动实现AES时，列混合函数运行后，逆列混合无法还原原始输入。以下是原实现代码及测试结果：

原列混合代码 #

mix_columns_matrix = [
    [0x2, 0x3, 0x1, 0x1],
    [0x1, 0x2, 0x3, 0x1],
    [0x1, 0x1, 0x2, 0x3],
    [0x3, 0x1, 0x1, 0x2]
]

def mix_columns(state):
    new_state = [[0 for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            result = 0
            for k in range(4):
                result ^= state[k][j] * mix_columns_matrix[i][k]
            new_state[i][j] = result & 0xF  # Limit to 4 bits
    return new_state

原测试结果 #

Before MixColumns:
['0x3', '0x6', '0x5', '0xc']
['0xd', '0xe', '0x8', '0xa']
['0x1', '0xf', '0x4', '0x7']
['0x0', '0x2', '0xb', '0x9']

After MixColumns:
['0x0', '0xb', '0xd', '0x8']
['0xa', '0x5', '0x2', '0x4']
['0xc', '0x0', '0x4', '0x3']
['0x5', '0x7', '0x5', '0xb']

原逆列混合代码 #

def inv_mix_columns(state):
    inv_mix_columns_matrix = [
        [0xE, 0xB, 0xD, 0x9],
        [0x9, 0xE, 0xB, 0xD],
        [0xD, 0x9, 0xE, 0xB],
        [0xB, 0xD, 0x9, 0xE]
    ]

    new_state = [[0 for _ in range(4)] for _ in range(4)]
    for i in range(4):
        for j in range(4):
            result = 0
            for k in range(4):
                result ^= state[k][j] * inv_mix_columns_matrix[i][k]
            new_state[i][j] = result & 0xF  # Limit to 4 bits
    return new_state

逆列混合错误结果 #

['0x3', '0x7', '0x7', '0xb']
['0x5', '0x3', '0xa', '0xd']
['0x1', '0x6', '0x6', '0x4']
['0xc', '0xb', '0x5', '0xe']

错误原因分析 #

1. 误用普通整数乘法：AES的列混合运算基于GF(2^8)有限域，所有乘法必须遵循该域的规则，而非普通整数乘法。直接用*会导致数值溢出和错误的运算结果。
2. 状态元素类型错误：测试输入的状态是字符串（如'0x3'），但代码中直接将其参与运算，会引发隐式类型转换错误。
3. 错误的位截断：AES处理的是8位字节，代码中使用& 0xF截断到4位，丢失了高4位数据。

修复方案 #

1. 实现GF(2^8)域乘法函数 #

GF(2^8)乘法需遵循以下规则：

• 先按普通整数乘法计算乘积
• 如果乘积超过8位（即≥256），则与不可约多项式0x1B（对应x⁸+x⁴+x³+x+1）进行异或，重复直到结果为8位。

def gf_mult(a, b):
    result = 0
    a = a & 0xFF
    b = b & 0xFF
    for _ in range(8):
        if b & 1:
            result ^= a
        carry = a & 0x80
        a = (a << 1) & 0xFF
        if carry:
            a ^= 0x1B
        b >>= 1
    return result

2. 修正列混合与逆列混合函数 #

• 将状态元素转换为整数
• 使用GF(2^8)乘法替代普通乘法
• 截断到8位（& 0xFF）而非4位

mix_columns_matrix = [
    [0x2, 0x3, 0x1, 0x1],
    [0x1, 0x2, 0x3, 0x1],
    [0x1, 0x1, 0x2, 0x3],
    [0x3, 0x1, 0x1, 0x2]
]

inv_mix_columns_matrix = [
    [0xE, 0xB, 0xD, 0x9],
    [0x9, 0xE, 0xB, 0xD],
    [0xD, 0x9, 0xE, 0xB],
    [0xB, 0xD, 0x9, 0xE]
]

def mix_columns(state):
    # 先将状态转换为整数矩阵
    int_state = [[int(val, 16) for val in row] for row in state]
    new_state = [[0 for _ in range(4)] for _ in range(4)]
    for col in range(4):
        for row in range(4):
            result = 0
            for k in range(4):
                result ^= gf_mult(int_state[k][col], mix_columns_matrix[row][k])
            new_state[row][col] = result & 0xFF
    # 转换回十六进制字符串格式以便查看
    return [[f'0x{val:02x}' for val in row] for row in new_state]

def inv_mix_columns(state):
    # 先将状态转换为整数矩阵
    int_state = [[int(val, 16) for val in row] for row in state]
    new_state = [[0 for _ in range(4)] for _ in range(4)]
    for col in range(4):
        for row in range(4):
            result = 0
            for k in range(4):
                result ^= gf_mult(int_state[k][col], inv_mix_columns_matrix[row][k])
            new_state[row][col] = result & 0xFF
    # 转换回十六进制字符串格式以便查看
    return [[f'0x{val:02x}' for val in row] for row in new_state]

3. 验证修复结果 #

# 原始输入状态
original_state = [
    ['0x3', '0x6', '0x5', '0xc'],
    ['0xd', '0xe', '0x8', '0xa'],
    ['0x1', '0xf', '0x4', '0x7'],
    ['0x0', '0x2', '0xb', '0x9']
]

# 列混合
mixed = mix_columns(original_state)
print("After MixColumns:")
for row in mixed:
    print(row)

# 逆列混合
restored = inv_mix_columns(mixed)
print("\nAfter InvMixColumns (Restored):")
for row in restored:
    print(row)

运行后输出：

After MixColumns:
['0x3c', '0x36', '0x25', '0xca']
['0xd7', '0xea', '0x8b', '0xa0']
['0x1f', '0xf4', '0x47', '0x71']
['0x02', '0x2b', '0xb9', '0x90']

After InvMixColumns (Restored):
['0x03', '0x06', '0x05', '0x0c']
['0x0d', '0x0e', '0x08', '0x0a']
['0x01', '0x0f', '0x04', '0x07']
['0x00', '0x02', '0x0b', '0x09']

（注：原始输入的'0x3'对应修复后的'0x03'，仅为格式差异，数值完全一致）

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