C++でSHA-256暗号化を実装する（１）

概要

SHA-256で暗号化する処理をGPUを使用して並列処理を行います。GPU用にSHA-256処理をコーディングする前に、CPUでSHA-256処理をコーディングしてソースコードの検証を行います。

今回はSHA-256の前段処理となる「パディング処理」を実装します。

要件定義

文字列を暗号化すると全く違う文字列でも、処理結果が同一の暗号が生成されることが発生します。この現象を暗号衝突といいます。衝突しないように文字列を成型する必要があり、この処理を「パディング処理」といいます。

基本設計

本処理では入力データを1ブロック64バイト単位に分割します。
入力データの最後に0x80を追加します。
ブロック内で入力データがコピーされない余りの箇所は0x00で埋めます。
最後のブロックの57バイト目から8バイトを入力データのビット数を入力します。
最後のブロックは8バイトと入力データの最後の0x80の合計9バイトは確保しなければならない為、入力データが55バイトを超える場合は2ブロック以上となります。
ブロックを格納する領域はメモリを動的に確保します。

用語の定義として下記のようになります。

用語	意味
メッセージ	入力データ
ブロック	処理結果の単位
ブロックサイズ	１つのブロックの長さ（６４バイト）

詳細設計

処理を行う手順を下記に示します。

1.確保するメモリの量を計算

まずメモリを確保するイメージとして下記のようなデータ構造を想定します。2次元のchar型の配列とし、64バイトのcharの配列をn個作成します。ブロックの数は入力データに応じて可変個となるため、charの配列へのポインタをn個確保します。

何個のブロックが必要なのかは下記の計算で求められます。
計算結果の小数点部分は切り上げとします。
$ ブロック個数 = (入力データの長さ+1バイト+8バイト) ÷ 64 $

2.確保したブロックに入力データをコピーします。

コピーを開始する位置をPとしPから64バイト分をコピーします。
Pから64バイト分をコピーできない場合、つまり入力データの終端まで来た場合はPから入力データ終端までをコピーします。
入力データの終端に来た場合は0x80を追加します。
最後のブロックの場合はブロックの後ろから4バイト分に入力データのビット長を格納します。

実装

コーディングしたソースコードは下記のようになります。

#define MESSAGE_BLOCK_SIZE 64

/**
    パディング処理

    処理内容：入力データを64バイトごとに分割し、最後のブロックにビット数を追加します。
    ブロックは動的にメモリを確保します。ブロックを使用し終わったらメモリを開放する必要があります。

    引数：入力データ
    戻り値：ブロック配列
*/
unsigned char** padding(char* input ) {

    //  入力データの長さを取得する
    int intLength = strlen(input);

    //  振り分けるブロックの個数を計算する
    //  (MESSAGE_BLOCK_SIZE-1)は切り上げのために必要
    int intBlock = ( intLength + 9 + (MESSAGE_BLOCK_SIZE-1)) / MESSAGE_BLOCK_SIZE;
    std::cout << "block:" << intBlock << std::endl;

    //  ブロック個数分のポインタを確保する
    unsigned char** output = (unsigned char**)malloc(sizeof(char*) * (intBlock+1));

    int intP = 0;
    for ( int intI=0; intI<intBlock; intI++ ) {

        //  ブロック個数分のメモリを確保する
        output[intI] = (unsigned char*)malloc(sizeof(char) * MESSAGE_BLOCK_SIZE);

        //  コピーする長さを計算する
        int intCopyLength = intLength - intP;

        //  コピーする長さがブロック長を超える場合はブロック長を設定する
        if (intCopyLength > MESSAGE_BLOCK_SIZE) {
            intCopyLength = MESSAGE_BLOCK_SIZE;
        }
        else {
            //  コピーする長さがマイナスの場合は0とする
            if (intCopyLength < 0) {
                intCopyLength = 0;
            }
        }

        //  コピーする長さがブロックより短い場合
        if (intCopyLength < MESSAGE_BLOCK_SIZE) {
            //  ブロックをクリアする
            memset(output[intI], 0, sizeof(char) * MESSAGE_BLOCK_SIZE);
        }

        //  入力データをコピーする場合
        if (intCopyLength > 0) {
            //  実際にデータをコピーする
            memcpy(output[intI], &input[intP], sizeof(char) * intCopyLength);

            //  コピーした長さがメッセージブロックより小さい場合はコピーした文字列の終端に0x80を入れる
            if (intCopyLength < MESSAGE_BLOCK_SIZE) {
                output[intI][intCopyLength] = 0x80;
            }
        }

        //  入力データをコピーしない場合
        else {
            //  入力データの長さがMESSAGE_BLOCK_SIZEで割り切れる場合は0x80を追加できていないため最後のブロックの先頭に追加する
            if (intLength % MESSAGE_BLOCK_SIZE == 0) {
                output[intI][0] = 0x80;
            }
        }

        //  最後のブロックの場合
        if (intI == intBlock - 1) {
            //  最後の４バイトに文字列長（ビット）を入れる
            int intBitLength = intLength * 8;

            std::cout << "bit:" << intBitLength << std::endl;
            output[intI][MESSAGE_BLOCK_SIZE - 4] = (unsigned char)(intBitLength >> 24 & (unsigned char)0xff);
            output[intI][MESSAGE_BLOCK_SIZE - 3] = (unsigned char)(intBitLength >> 16 & (unsigned char)0xff);
            output[intI][MESSAGE_BLOCK_SIZE - 2] = (unsigned char)(intBitLength >> 8 & (unsigned char)0xff);
            output[intI][MESSAGE_BLOCK_SIZE - 1] = (unsigned char)(intBitLength & (unsigned char)0xff);
        }

        intP = intP + MESSAGE_BLOCK_SIZE;
    }

    //  ブロック配列の最後にNULLを入れる
    output[intBlock] = NULL;

    std::cout << std::endl;

    return output;
}

単体試験

実際に数パターンのデータを処理して正しくパディングができるかを確認します。

テスト観点

• 入力データが途中で切れていないか、すべてコピーされているか
• 入力データの最後に0x80が挿入されているか
• 最後のブロックの最後の４バイトに入力データのビット長が格納されているか

ブロックを表示するルーチンを作成し、上段に16進数、下段に文字列を表示します。

ケース１：適当な文字列

message:Visual Studio drives me crazy and I am suspecting I am doing something wrong. This is what I do: I installed Visual Studio(Pro '08) a long time ago, I installed the Windows SDK (Win 7 x64), someone emails me a project, it fails to build.

block:4
bit:1896

0:
56697375 616c2053 74756469 6f206472 69766573 206d6520 6372617a 7920616e
64204920 616d2073 75737065 6374696e 67204920 616d2064 6f696e67 20736f6d
V i s u  a l   S  t u d i  o   d r  i v e s    m e    c r a z  y   a n
d   I    a m   s  u s p e  c t i n  g   I    a m   d  o i n g    s o m


1:
65746869 6e672077 726f6e67 2e205468 69732069 73207768 61742049 20646f3a
20492069 6e737461 6c6c6564 20566973 75616c20 53747564 696f2850 726f2027
e t h i  n g   w  r o n g  .   T h  i s   i  s   w h  a t   I    d o :
  I   i  n s t a  l l e d    V i s  u a l    S t u d  i o ( P  r o   '


2:
30382920 61206c6f 6e672074 696d6520 61676f2c 20492069 6e737461 6c6c6564
20746865 2057696e 646f7773 2053444b 20285769 6e203720 78363429 2c20736f
0 8 )    a   l o  n g   t  i m e    a g o ,    I   i  n s t a  l l e d
  t h e    W i n  d o w s    S D K    ( W i  n   7    x 6 4 )  ,   s o


3:
6d656f6e 6520656d 61696c73 206d6520 61207072 6f6a6563 742c2069 74206661
696c7320 746f2062 75696c64 2e800000 00000000 00000000 00000000 00000768
m e o n  e   e m  a i l s    m e    a   p r  o j e c  t ,   i  t   f a
i l s    t o   b  u i l d  . . . .  . . . .  . . . .  . . . .  . . . h

ケース２：64バイトの文字列

message:1234567890123456789012345678901234567890123456789012345678901234

block:2
bit:512

0:
31323334 35363738 39303132 33343536 37383930 31323334 35363738 39303132
33343536 37383930 31323334 35363738 39303132 33343536 37383930 31323334
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2
3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4


1:
80000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000200
. . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .
. . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .

ケース３：56バイトの文字列

message:12345678901234567890123456789012345678901234567890123456

block:2
bit:448

0:
31323334 35363738 39303132 33343536 37383930 31323334 35363738 39303132
33343536 37383930 31323334 35363738 39303132 33343536 80000000 00000000
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2
3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  . . . .  . . . .


1:
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000 000001c0
. . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .
. . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .  . . . .

ケース４：55バイトの文字列

message:1234567890123456789012345678901234567890123456789012345

block:1
bit:440

0:
31323334 35363738 39303132 33343536 37383930 31323334 35363738 39303132
33343536 37383930 31323334 35363738 39303132 33343580 00000000 000001b8
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2
3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 .  . . . .  . . . .

ケース５：199バイトの文字列

message:12345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789

block:2
bit:952

0:
31323334 35363738 39303132 33343536 37383930 31323334 35363738 39303132
33343536 37383930 31323334 35363738 39303132 33343536 37383930 31323334
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2
3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4


1:
35363738 39303132 33343536 37383930 31323334 35363738 39303132 33343536
37383930 31323334 35363738 39303132 33343536 37383980 00000000 000003b8
5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6
7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 .  . . . .  . . . .

総括

文字列をブロック化する際に境界試験が重要なことがわかります。
最後のブロックに56バイト以上をコピーする場合は追加で１ブロックが必要となります。