5

我在此处的 GCM SP-800-38D 文档中为块乘法（算法 1）提供了 C 代码。第 11-12 页。

完成代码后，我想看看是否有任何方法可以测试代码。您可以在我提供的代码下方找到附件。请注意，我使用 24 位块代替了 128 位块，仅用于测试目的。如有必要，我将不胜感激。

void BLK_MUL (u8 *val_1,u8 *val_2, u8 *out_val)
{ 

    u8 xdata R_val = 0xE1;     
    u8 xdata Z_val[3],V_val[3];
    u8 mask_b   = 0x80;        
    u16 i;  u8 j;           
    bit rnd;                

    for(j=0;j<3;j++,++val_2)    
    {
        Z_val[j]=0x00;      
        V_val[j]=*val_2;    
    }       


    for(i=0;i<24;i++)
    { 
        if (*val_1 & mask_b)
        {
            for(j=0;j<3;j++)    
                Z_val[j]^=V_val[j]; 
        }
        if (!(V_val[2] & 0x01))
        {//if LSB of V_val is 0
            for(j=0;j<3;j++)
            { //V_val = rightshift(V_val)
                if (j!=0)
                    if (V_val[2-j] & 0x01)
                        V_val[3-j] |= 0x80;
                V_val[2-j]>>=1;          
            }
        }
        else
        {//if LSB of V_val is 1
            for(j=0;j<3;j++)
            {//V_val = rightshift(V_val)
                if (j!=0)
                    if (V_val[2-j] & 0x01)
                        V_val[3-j] |= 0x80;
                V_val[2-j]>>=1;          
            }
            V_val[0]^=R_val; //V_val = rightshift(V_val) ^ R                
        }
        if(mask_b & 0x01)   { val_1++; rnd=1;}  
        mask_b >>= 1;                       
        if (rnd)    { mask_b=0x80; rnd=0; } 
    }

    STR_CPY(out_val,Z_val,3);   

    return ;        
}


void main()
{

    code unsigned char val_1[3] ={  0x2b,0x7e,0x15  };
    code unsigned char val_2[3] ={  0x39,0x25,0x84  };
    unsigned char out[3];

    BLK_MUL (val_1,val_2,out);

    return;
}
4

6 回答 6

9

在某些时候，您当然必须根据测试向量检查您的代码。但是您可以执行很多测试，而无需知道或计算任何测试向量。

首先，GF(2^128) 中的乘法是可交换的。因此，您可以使用任何输入计算 BLK_MUL(val_1, val_2, out1) 和 BLK_MUL(val_2, val_1, out2) 并且应该得到相同的结果。由于您的代码以不同的方式使用 val_1 和 val_2 这已经是一个很好的测试。

然后您可以使用该乘法是可分配的，即您可以测试 (x+y)*z = (x*z)+(y*z)，（其中 GF(2^128) 中的加法是通过异或对应的两个值的字节一起）。

最后，一旦你实现了整个字段 GF(2^128)，你也可以利用它的顺序是 2^128-1。即，如果您从值 x 开始，然后将其平方 128 次，那么您应该得到 x。

一些额外的评论：

使用方程式进行测试（仅使用测试向量）的优点是您可以轻松运行大量测试。因为以这种方式添加测试相当容易，所以我经常首先使用稀疏输入（例如，仅在输入中设置单个位）进行一些简单的测试。如果出现问题，这有助于快速识别错误。

您当前的代码使用临时变量作为结果。这确实是一个好主意，因为它确保了复制安全。我认为一个好的单元测试也应该涵盖这种情况。即，您可能想要两次计算相同的结果：一次输入和输出指向不同的内存位置，一次输出与输入的内存相同。

此外，其他答案中至少有一个谈到了优化。我认为如果你重构代码，那么你应该寻找有意义的组件来重用，而不是盲目地寻找看起来很像的代码片段。由于 GF(2^128) 是一个域，当然域中的加法和乘法是有意义的分量。另一个有意义的组件是多项式 x 的乘法（这是在加密中非常常用的东西）。

于 2012-05-18T15:32:20.877 回答
5

GCM 模式的测试向量可以在这里找到，这里有一堆 NIST 测试向量。

于 2012-05-18T22:56:45.440 回答
4

A test example for GF(2^128) can be found at: PCLMULQDQ CPU instruction, page 78

于 2013-04-09T13:09:38.073 回答
3

谢谢@jack 和@emboss。根据杰克的建议，我对该功能进行了测试，结果证明是正确的。希望这对其他人有用，但仍然会感谢任何建议和更正。:) 见下面的主要代码：

void main()
{

u8 j;
u8 val_1[3] ={  0x2b,0x7e,0x15  };
u8 val_2[3] ={  0x39,0x25,0x84  };
u8 val_3[3] ={  0x23,0x71,0x25  };
u8 val_3_2[3]={ 0x23,0x71,0x25  };
u8 val_4[3] ={  0x33,0x35,0x44  };
u8 val_5[3] ={  0x2e,0x77,0x11  };

u8 out[3];
u8 out_1[3];
u8 out_2[3];
u8 out_3[3];
u8 out_4[3];
u8 out_5[3];

     //PROOF X*Y = Y*X
BLK_MUL (val_1,val_2,out);      //X*Y
BLK_MUL (val_2,val_1,out_1);    //Y*X
            //N.B: out == out_1
     //PROOF (X+Y)*Z = (X*Z)+(Y*Z) 
for(j=0;j<3;j++)    
    val_3[j]^=val_4[j];         //X = X+Y
BLK_MUL (val_3,val_5,out_2);    //(X+Y)*Z
BLK_MUL (val_5,val_3,out_3);    //Z*(X+Y)
            //N.B: out_2 == out_3

BLK_MUL (val_3_2,val_5,out_4);      //X*Z
BLK_MUL (val_4,val_5,out_5);        //Y*Z
for(j=0;j<3;j++)    
    out_4[j]^=out_5[j];         //(X*Z)+(Y*Z)
            //N.B: out_3=out_2=out_4
return;
}
于 2012-05-19T03:12:44.570 回答
2

我不会评论它是否有效或如何测试它，但我可以给你一些编码提示：

  • 函数名通常是小写的
  • 输入数组应该是const...
  • 或者如果您不介意破坏第二个输入数组，那么 V_val 是多余的。
  • 你的变量应该被重命名。调用输入x和y输出z；R_val应该是简单的常数R，mask_b简单mask，v_val简单v。进行这些更改，您的代码将突然变得可读。
  • 删除您添加的评论，它们是多余的
  • 类型u8应该是 uint8_t（来自 stdint.h）或简单的无符号字符。
  • Z_val是多余的；只需使用输出参数z（out_val）
  • 我不知道“xdata”是什么意思
  • i并且j应该是int
  • rnd是多余的

  • 0x01与1- 后者更具可读性。

  • 这些if (!(V_val[2] & 0x01))条款可以简化为：

    v[2]>>=1;  /* EDIT --- missed this out before */
for (j=1; j<3; j++)
{
    if (v[2-j] & 1)
        v[3-j] |= 0x80;
    v[2-j] >>= 1;
}
if (v[2] & 1)
    v[0] ^= R;

  • 这东西：

    if(mask_b & 0x01)   { val_1++; rnd=1;}
mask_b >>= 1;
if (rnd)    { mask_b=0x80; rnd=0; }

    可以简化为（重命名后）

    if ((mask >>= 1) == 0)
{
    x++;
    mask = 0x80;
}
    • 当您直接输出到 z 时，STR_CPY 调用是多余的。而且它的名字看起来像一个字符串副本，这绝对不是需要的。

EDIT2（第一次编辑在上面的for循环之前添加了缺失的行）

您有两个相同循环的副本，一个在if (!(v[2] & 1))子句中，一个在else子句中。后者（else 子句）也有一个v[0] ^= R;. 一份可以省略。循环还特别对待 j==0 ，这就是我从循环中提取它的原因（但在帖子中省略了它）。然后循环仅超过 2 个项目，j==1 和 2。

您可以并且可能应该展开剩余的循环以获得：

    v[2] >>= 1;

    if (v[1] & 1) v[2] |= 0x80;
    v[1] >>= 1;

    if (v[0] & 1) v[1] |= 0x80;
    v[0] >>= 1;

    if (v[2] & 1) v[0] ^= R;
于 2012-05-19T16:20:46.547 回答
2

您还有一个数学考虑，试图将 GF(2^128) 代码用于 GF(2^24)

常数“R_val=0xE1”特定于 GF(2^128)，反映了不可约多项式的低阶指数

    x^128 + x^7 + x^2 + x^1 + 1

它是 GF(2^128) 的流行同构的生成器，通常在密码学中使用。

这等效于位向量 (1 || 120"0" || 10000111)。（每个位反映多项式中出现的“x”的幂。）

低位（高位 128 被消耗以平衡溢出的位）以大端方式写入 x87 或以小端方式表示时写入 xE1。

然而对于 GF(2^24)，似乎不太可能，先验，

    x^24 + x^7 + x^2 + x^1 + 1

是不可约的（但我没有测试过）。
那么，在 G(2^24) 中使用什么是已知的良好、有效的不可约多项式？
根据表http://www.hpl.hp.com/techreports/98/HPL-98-135.pdf GF(2^24) 的最低/最简单的不可约多项式似乎是

    x^24 + x^4 + x^3 + x^1 + 1

它对应于位向量 (1 || 16 "0" || 00011011)。

因此，再次因为高位被消耗以平衡溢出，正确的校正因子，您的 R_val，以小端方式编写将是 R_val = 0xD8

希望您觉得这个有帮助。

于 2013-09-17T06:23:39.667 回答