寻求C#中GF(2^128)伽罗瓦乘法的逆运算实现方案

首先得明确，AES-GCM用的伽罗瓦域是GF(2^128)，对应的不可约多项式是x¹²⁸ + x⁷ + x² + x + 1（十六进制表示为0x80000000000000000000000000000007，大端存储）。要实现逆运算，最直接的方法是利用费马小定理：在GF(2^n)域中，任何非零元素a的逆元等于a^(2^n - 2)——因为域中元素满足a^(2^n - 1) = 1，两边乘a^-1就得到这个结论。

结合你给出的代码片段（BIT和WPA_GET_BE32），我把完整实现拆成两部分：先补全伽罗瓦乘法（如果你的现有代码里还没完整实现的话），再基于乘法实现逆运算。

1. 补全基础工具函数 #

先把你提到的函数补全，再加上大端存储的辅助函数：

// 你提供的BIT函数
public byte BIT(byte x)
{
    return (byte)(1 << x);
}

// 从字节数组（大端）提取32位无符号整数
public uint WPA_GET_BE32(byte[] buf, int offset)
{
    return (uint)(buf[offset] << 24 | buf[offset+1] << 16 | buf[offset+2] << 8 | buf[offset+3]);
}

// 将32位无符号整数写入字节数组（大端）
public void WPA_PUT_BE32(byte[] buf, int offset, uint value)
{
    buf[offset] = (byte)(value >> 24);
    buf[offset+1] = (byte)(value >> 16);
    buf[offset+2] = (byte)(value >> 8);
    buf[offset+3] = (byte)value;
}

2. GF(2^128)乘法实现 #

逆运算依赖乘法，所以先实现符合AES-GCM标准的伽罗瓦乘法：

// GF(2^128)的不可约多项式：x^128 + x^7 + x^2 + x + 1（大端存储）
private static readonly byte[] _irreduciblePoly = new byte[16]
{
    0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80
};

// 计算两个GF(2^128)元素的乘积
public byte[] Gf128Multiply(byte[] a, byte[] b)
{
    if (a == null || a.Length != 16 || b == null || b.Length != 16)
        throw new ArgumentException("输入必须是16字节的GF(2^128)元素");

    byte[] result = new byte[16];
    byte[] temp = (byte[])a.Clone(); // 用来存储a左移后的临时值

    // 逐位处理b的每一个比特
    for (int byteIdx = 0; byteIdx < 16; byteIdx++)
    {
        for (int bitIdx = 0; bitIdx < 8; bitIdx++)
        {
            // 如果b当前位是1，将temp异或到结果中
            if ((b[byteIdx] & BIT(7 - bitIdx)) != 0)
            {
                for (int i = 0; i < 16; i++)
                {
                    result[i] ^= temp[i];
                }
            }

            // 将temp左移1位，处理进位
            bool carry = (temp[15] & 0x80) != 0; // 最高位是否有进位
            for (int i = 15; i > 0; i--)
            {
                temp[i] = (byte)((temp[i] << 1) | ((temp[i-1] >> 7) & 0x01));
            }
            temp[0] <<= 1;

            // 如果有进位，异或不可约多项式
            if (carry)
            {
                for (int i = 0; i < 16; i++)
                {
                    temp[i] ^= _irreduciblePoly[i];
                }
            }
        }
    }

    return result;
}

3. GF(2^128)逆运算实现 #

基于费马小定理，通过快速幂的方式计算a^(2^128 - 2)：

// 计算GF(2^128)元素的逆元
public byte[] Gf128Inverse(byte[] a)
{
    if (a == null || a.Length != 16)
        throw new ArgumentException("输入必须是16字节的GF(2^128)元素");

    // 检查输入是否为零元素（无逆元）
    bool isZero = true;
    foreach (byte b in a)
    {
        if (b != 0)
        {
            isZero = false;
            break;
        }
    }
    if (isZero)
        throw new InvalidOperationException("零元素没有逆元");

    // 利用公式：逆元 = a^(2^128 - 2) = a^2 * a^4 * a^8 * ... * a^(2^127)
    byte[] current = Gf128Multiply(a, a); // 初始为a^2
    byte[] inverse = (byte[])current.Clone();

    // 依次计算a^4, a^8,...a^(2^127)，并累乘到结果中
    for (int i = 1; i < 127; i++)
    {
        current = Gf128Multiply(current, current); // 平方得到a^(2^(i+1))
        inverse = Gf128Multiply(inverse, current);
    }

    return inverse;
}

测试验证 #

你可以用下面的代码验证逆运算是否正确：

// 测试：单位元的逆元是自身
byte[] unitElement = new byte[16];
unitElement[0] = 0x01;
byte[] invUnit = Gf128Inverse(unitElement);
byte[] product = Gf128Multiply(unitElement, invUnit);
// product应该等于unitElement（第一个字节0x01，其余为0）

// 测试任意非零元素
byte[] testElement = new byte[16] { 0x12, 0x34, 0x56, 0x78, 0x90, 0xab, 0xcd, 0xef, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77, 0x88 };
byte[] invTest = Gf128Inverse(testElement);
byte[] testProduct = Gf128Multiply(testElement, invTest);
// testProduct应该是单位元

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