5

ブロックの乗算 (アルゴリズム 1) の C コードを GCM SP-800-38D のドキュメントに掲載しています。11-12ページ。

コードを完成させたので、コードをテストできる方法があるかどうかを確認したいと思います。私が提示したコードの下に添付されています。128 ビット ブロックの代わりに、テスト目的のためだけに 24 ビット ブロックを使用したことに注意してください。必要に応じて提案をいただければ幸いです。

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) の加算は、対応する xor 演算によって計算されます)。 2 つの値を合わせたバイト数)。

最後に、フィールド全体 GF(2^128) を実装すると、その次数が 2^128-1 であることを利用することもできます。つまり、値 x から始めて、それを 128 回 2 乗すると、x が返されます。

いくつかの追加コメント:

(テスト ベクトルのみを使用するよりも) テストに方程式を使用する利点は、多数のテストを簡単に実行できることです。この方法でテストを追加するのはかなり簡単なので、最初にまばらな入力 (たとえば、入力に設定された 1 つのビットのみ) を使用して簡単なテストを行うことがよくあります。何か問題がある場合、これはバグを迅速に特定するのに役立ちます。

現在のコードでは、結果に一時変数を使用しています。コピーの安全性が保証されるため、これは確かに良い考えです。良い単体テストもこのケースをカバーするべきだと思います。つまり、同じ結果を 2 回計算したい場合があります。1 回目は入力と出力が異なるメモリ位置を指し、もう 1 回は出力が入力と同じメモリを指している場合です。

さらに、他の回答の少なくとも1つは最適化について語っています。コードをリファクタリングする場合は、そっくりなコード スニペットをやみくもに探すのではなく、再利用する意味のあるコンポーネントを探す必要があると思います。GF(2^128) は体なので、もちろん、体の足し算と掛け算は意味のある要素です。もう 1 つの意味のあるコンポーネントは、多項式 x による乗算です (これは、暗号で非常に頻繁に使用されるものです)。

于 2012-05-18T15:32:20.877 に答える
5

GCM モードのテスト ベクトルはここで見つけることができ、NIST テスト ベクトルはここにあります。

于 2012-05-18T22:56:45.440 に答える
4

GF(2^128) のテスト例は、PCLMULQDQ CPU 命令、78 ページにあります。

于 2013-04-09T13:09:38.073 に答える
3

@jack と @emboss に感謝します。ジャックの提案に従って、関数のテストを実行したところ、正しいことが証明されました。これが他の誰かに役立つことを願っていますが、それでも提案と修正に感謝します。:) 以下の MAIN コードを参照してください。

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

また、GF(2^24) に GF(2^128) コードを使用しようとする数学的な考慮事項もあります。

定数 "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 に答える
2

動作するかどうかやテスト方法についてはコメントしませんが、コーディングのヒントをいくつか紹介できます。

  • 関数名は通常小文字です
  • 入力配列はconst...
  • または、2 番目の入力配列を破棄してもかまわない場合、V_val は冗長です。
  • 変数の名前を変更する必要があります。x入力とy出力を呼び出しますz。R_val単純に定数、、R単純mask_b、mask単純にv_valする必要がありますv。これらの変更を行うと、コードが突然読みやすくなります。
  • 追加したコメントを削除してください。それらは冗長です
  • typeu8は uint8_t (stdint.h から) または単に unsigned char でなければなりません。
  • 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 ループの前に欠落している行を追加していました)

同じループの 2 つのコピーがあり、1 つはif (!(v[2] & 1))句に、もう 1 つはelse句にあります。後者 (else 節) にもv[0] ^= R;. 1部省略可能です。また、ループは j==0 を特別に扱います。そのため、ループから抽出しました (ただし、投稿では省略しました)。ループは、j==1 と 2 の 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 に答える