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個確保します。
![キャプチャ.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/514807/644e0da0-f8a8-705a-1f26-504719572fd4.png)

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

### 2.確保したブロックに入力データをコピーします。
![キャプチャ5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/514807/c814f26f-4623-b304-0b4e-7ee006c68bc6.png)
コピーを開始する位置をPとしPから64バイト分をコピーします。
Pから64バイト分をコピーできない場合、つまり入力データの終端まで来た場合はPから入力データ終端までをコピーします。
入力データの終端に来た場合は0x80を追加します。
最後のブロックの場合はブロックの後ろから4バイト分に入力データの**ビット長**を格納します。

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

```c++

#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バイト以上をコピーする場合は追加で１ブロックが必要となります。