ハッシュ関数...ハッシュ値を生成する関数
ハッシュ値...ある値をハッシュ関数にかけた数、以下の特徴を持つ
・あるハッシュ関数において文字数が同じである
・不可逆である
・不確定性を持たない
・入力値とハッシュ値が連動しない
上記条件を満たすために、ハッシュ関数は基本、以下のプロセスを踏む
1:パディング
2:初期化ベクトル(Initialization vector)の定義
3:圧縮関数にかける
ハッシュアルゴリズム...ハッシュ値を求めるアルゴリズム
| ハッシュアルゴリズム | 詳細 |
|---|---|
| MD5(Message Digest Algorithm 5) | 任意データから128bits固定長ハッシュ値を生成する |
| SHA(Secure Hash Algorithm) | 一群の関連した暗号的ハッシュ関数、NISTによって標準のハッシュ関数に定められている |
| SHA-0 | 最初のSHAだが、すぐにSHA-1に差し替えられた |
| SHA-1 | NSAによってSHA-0を修正して設計された。20bits固定長ハッシュ値を生成する。 NISTは2030年を持って仕様廃止を予定している |
| SHA-2 | SHA-1を改良したもの、SHA-224、256、384、512/224、512/256の6種類あり、224、256、384、512bitsのハッシュ長を選択できる |
| SHA-3 | keccakを用いた暗号学的ハッシュ関数。MD5への攻撃成功の確認、SHA-1への攻撃の論理的確立を受けたNISTによるコンペティションで生まれた |
| Merkle-Damgård | 任意値の入力を固定長のハッシュ値に変換するハッシュ関数 |
| 関連用語 | 詳細 |
|---|---|
| NIST(National Institude Standard of Technology) 米国国立標準技術研究所 |
米国商務省傘下の物理研究所、サイバーセキュリティにおいては標準やガイドライン、ベストプラクティスの作成などを主な活動としている |
| NSA(National Security Egency) アメリカ国家安全保障局 |
アメリカ国防省の情報機関CIAに対して、電子的な情報収集活動を行う、内部に国立コンピュータ保安センタでコンピュータセキュリティの調査研究を行う |
| keccak | 55w(1,2,4,8,16,32,64)の立方体を用いるハッシュ関数 |
ハッシュ関数を組む
上記条件を満たすハッシュ関数を組む
[1] 入力値のパディング
#include <stdint.h>
#include <string.h>
void padding(uint8_t *plaintext,size_t plaintext_size,uint8_t *box,size_t box_size){
memset(box,0,box_size); //0埋め
memcpy(box,plaintext,plaintext_size); //plaintextの埋め込み
//plaintextの終端に1ビットを付与する
if(plaintext_size < box_size){
box[plaintext_size] = 0x80; //0x80=10000000
}else{
printf("over flow\n");
}
//入力値のビット長を格納領域の端に挿入
uint64_t bit_length = (uint64_t)plaintext_size*8;
for(int i=0;i<8;i++){
box[box_size-1-i] = (bit_length >> (i*8)) & 0xFF;
}
//デバッグ
for(int i=0;i<box_size;i++){
printf("%d\n",box[i]);
}
}
[2] ハッシュ値の生成
今回は線形合同法を用いる
uint64_t hash(uint8_t *box,size_t box_size){
uint64_t A = 6364136223846793005;
uint64_t B = 18446744073709551557;
uint64_t hash = box[0];
for(int i=1;i<box_size;i++){
hash = (A*hash+box[i]) % B;
}
return hash;
//デバッグ
/*for(int i=0;i<box_size;i++){
printf("%d\n",box[i]);
}*/
}
main
main(){
uint8_t plaintext[100];
printf("平文を入力してください(最大99文字)\n> ");
scanf("%99s",&plaintext);
size_t plaintext_size = strlen((char*)plaintext);
uint8_t box[128];
size_t box_size = sizeof(box);
padding(plaintext,plaintext_size,box,box_size);
printf("%016llx\n", (unsigned long long)hash(box, box_size));
}
出力結果
出力結果は64ビット以内の64ビット型であり、単純な近似による連動は起きていない(ただし、アルゴリズム的に衝突する値の逆算は容易)
> gura
68ff81a4cb4ca26b
[gura@localhost ~]$ ./hash
平文を入力してください(最大99文字)
> gura
68ff81a4cb4ca26b
[gura@localhost ~]$ ./hash
平文を入力してください(最大99文字)
> guraa
790aad19cd01f3a8
[gura@localhost ~]$ ./hash
平文を入力してください(最大99文字)
> g
ff604b724baa5ceb
[gura@localhost ~]$ ./hash
平文を入力してください(最大99文字)