ハッシュ関数
ハッシュ関数(ハッシュかんすう、hash function)
任意長のビット列から規則性のない固定長のビット列を生成する関数
性質
同じ入力値に対しては必ず同じハッシュ値が出力
ハッシュ値から元の入力値に復元することは十分に困難(一方向性)(原像計算困難性)
異なるビット列から同じハッシュ値が生成されることは非常に低い(衝突困難性)
$ H = h(v)
$ v : 入力値
$ h : ハッシュ関数
$ H : ハッシュ値(nビットのビット列)、ハッシュ関数の戻り値
ハッシュ値の例
19A5 628F 6725 C360 2846 D682 7659 B396 F926 684D(16進数表示)
ハッシュ関数に求められる安全性
要件:
ハッシュ関数$ h において、$ h(M_1) = h(M_2) を満たす入力メッセージ$ \{M_1, M_2 | M_1 \neq M_2\} を探索することが十分に計算量を要し、困難であること。
(言い換え)
同じハッシュ値を生成する2つのメッセージを見つけることは困難
等しいハッシュ値を有する (衝突する) もの$ M_1, M_2 を、衝突ペアという
事実:
衝突をみつけるために必要な計算量は、 ハッシュ値が n ビットであるとき、ハッシュ関数の計算を $ 2^{n/2} 回行うための 計算量を超えない。 ( $ 2^{n/2} ≪ 2^n に注意)
関連:
要件:
ハッシュ関数$ h とハッシュ値$ H が与えられた時に、$ H=h(M) となるようなメッセージ$ M (原像)を探索することが十分に計算量を用し、困難なこと。
(言い換え) 与えられたハッシュ値を生成するメッセージを構築したり見つけたりすることは困難
補足:ハッシュ値の原像は一般に沢山あるが、それらのうちの一つすら具体的に求めることが困難であることを要求している
事実
与えられたハッシュ値に対応する入力を求めるために必要な計算量は、 ハッシュ値がnビットであるとき、ハッシュ関数の計算を$ 2^n 回行うための計算量を超えない。
要件:
入力 メッセージ$ M_1 が与えられたときに、$ H = h(M_1) = h(M_2) かつ$ M_1 ≠ M_2 を満たす$ M_2 (第2原像)を、一つでも求めることが十分に計算量を要し、困難であること。
$ H はハッシュ値
(言い換え)与えられた入力メッセージ$ M_1 があったときに、 計算されたハッシュ値が等しいかつ、$ M_1 とは違う入力メッセージ $ M_2 (第2原像)を1つでも求めることが十分に困難
事実
第2原像をみつけるために必要な計算量は、 ハッシュ値が n ビットであるとき、ハッシュ関数 の計算を $ 2^n 回行うための計算量を超えない。
確認用
Q. ハッシュ関数
Q. ハッシュ値
Q. メッセージダイジェスト
Q. 原像計算困難性
Q. 衝突困難性
Q. 第2原像計算困難性
参考
説明がわかりにくすぎる。
関連
メモ