【ハッシュ法】意味・特徴・ハッシュ関数の計算

ハッシュ法の意味・特徴・関数について解説します。

[latexpage]

【ハッシュ法とは】データ探索方法
【ハッシュ関数とは】衝突発見困難性、原像計算困難性、第二原像計算困難性

【ハッシュ法とは】データ探索方法

ハッシュ法とは、データ探索方法の1つです。
データの探索キーの値からデータの格納位置をハッシュ関数を用いて直接計算します。
表では、レコードのキー値とハッシュ関数を用いて格納アドレスを求めることでデータにアクセスします。

–	主な特徴
1	探索回数の少ないデータ探索の場合、線形探索・2分探索より探索時間が短い（メリット）
2	連続したデータ探索の場合、探索時間が長くなる（デメリット）
3	線形探索法や2分探索法とは異なり、常に一定の時間で目的のデータを探索することが可能
4	異なるキー値から同じ格納場所が計算されることがある（本来格納されるべき所に格納できない事態が発生）

【ハッシュ関数とは】衝突発見困難性、原像計算困難性、第二原像計算困難性

ハッシュ関数は、入力されたデータをもとに固定長の文字列(ハッシュ値)に変換する関数です。

SHA-256(Secure Hash Algorithm 256)が出力するハッシュ値は256ビットなので、入力データの長さにかかわらず得られるハッシュ値は常に256ビットになります。
衝突が発生する確率は$\frac{1}{2^{256}}$なので、平均で$2^{128}$回の試行で同じハッシュ値を出力する異なる入力を発見できます。

特性	概要
衝突発見困難性（強衝突耐性）	ハッシュ値が一致する2つのメッセージを探索することが困難であること。
原像計算困難性	ハッシュ値hash(M)から元のメッセーMを探すことが困難であること、
第二原像計算困難性（弱衝突耐性）	既知のメッセージM1に対するハッシュ値が与えられた時、ハッシュ値が一致する、hash(M1)＝hash(M2)となるようなメッセージM2を探索することが困難であること。