伽罗华域乘法的正确性

Question

我正在开发代码以在 Galois 域 gf(2^8) 中进行算术运算，但我认为我在乘法运算中得到了错误的结果。

private static byte Multiply(byte a, byte b)
{
    byte result = 0;

    while (b != 0)
    {
        if ((b & 1) != 0)
        {
            result ^= a;
        }

        a <<= 1;
        b >>= 1;
    }

    return result;
}

Multiply(1, 2) 的结果给出了正确的值 2，但是 Multiply(240, 249) 给出了 112 而不是预期的 148。

现在我不确定这个值是否适用于俄罗斯农民乘法。

也许有另一种算法可以给出正确的结果？

Answer 1

示例代码：

#define POLY 0x11D

static BYTE GFMpy(BYTE b0, BYTE b1)
{
int i;
int product;
    product = 0;
    for(i = 0; i < 8; i++){
        product <<= 1;
        if(product & 0x100){
            product ^= POLY;}
        if(b0 & 0x80u){
            product ^= b1;}
        b0 <<= 1;}
    return((BYTE)product);
}

使用查找表的示例：

#define POLY (0x11d)
/* all non-zero elements are powers of 2 for POLY == 0x11d */
typedef unsigned char BYTE;
/* ... */
static BYTE exp2[512];
static BYTE log2[256];
/* ... */
static void Tbli()
{
int i;
int b;
    b = 0x01;                   /* init exp2 table */
    for(i = 0; i < 512; i++){
        exp2[i] = (BYTE)b;
        b = (b << 1);           /*  powers of 2 */
        if(b & 0x100)
            b ^= POLY;
    }

    log2[0] = 0xff;             /* init log2 table */
    for(i = 0; i < 255; i++)
        log2[exp2[i]] = (BYTE)i;
}
/* ... */
static BYTE GFMpy(BYTE m0, BYTE m1) /* multiply */
{
    if(0 == m0 || 0 == m1)
        return(0);
    return(exp2[log2[m0] + log2[m1]]);
}
/* ... */
static BYTE GFDiv(BYTE m0, BYTE m1) /* divide */
{
    if(0 == m0)
        return(0);
    return(exp2[log2[m0] + 255 - log2[m1]]);
}

伽罗华域乘法的正确性

Correctness of multiplication in galois field

c#

aes

galois-field

finite-field