ハッシュ関数

Hash function

ハッシュ関数に求められること

同じデータに対して必ず同じ値が得られること。(決定論的であること。必須。)

計算が容易、高速であること。

ハッシュ値が可能な限り衝突しないこと。

残念ながら情報量的に「絶対に衝突しない」とは言えない。

2つの異なるデータが同じハッシュ値の時、その2つのデータはほとんど異なっていること。データの一部分を変更したただけでは衝突しないこと。

データの一部分を変更した場合、その変更でハッシュ値は大きく変わること。

データの順番を入れ替えただけで衝突するのはあまりよくない。

単純な足し算、かけ算では衝突してしまう。

ハッシュ値が可能な限り一様に分散する事。(分布に偏りがないこと)

ハッシュ値を部分的に切り出しても一様分布する事。

結果的に乱数のように見えること。

ハッシュ値のサイズが必要十分な程度に短いこと。

長すぎるハッシュ値はハッシュ値自体の保持、比較がコストになる。

暗号で使用する場合、ハッシュ値から元のデータが推測できないこと。

パスワードなどの秘匿データの場合、攻撃者がデータとハッシュ値の表を作り出す事を防ぐこと。

データにソルト(salt, 塩)を混ぜて使うのが一般的

簡単な計算で計算結果が巡回する事がない。(系統図を作ることができないようにする。)

A→B→C→A のように前の値に戻ってしまう事がない。

何度計算しても同じ値になるような値(例えば0)が計算途中で出ることがない。

メモ

乗算、除算は上下のビットに影響を与えるためよく使われるが、演算速度が非常に遅い。

XORは2回やると元に戻ってしまう性質があるため、注意深く使う必要がある。

特に、(0 xor 0) == 0 であるため、計算途中で一度全ビットに0が現れると、何らかの方法で1を差し込まないとうまく行かない。

ビット幅全体に影響を与える方法としてはビット(あるいはワード)単位のシャッフルを使う事が多い。

高速なハッシュ関数では、マスク、シフト、NOT、XOR を組み合わせるのが一般的

素数を使うとよいハッシュ値になりやすい。

現在のCPUではSIMD命令があるのでそれを使って高速化するのが一般的。(CPUアーキテクチャ依存になるため注意)

衝突しない事が(一応)保証される値の例

何らかのユニーク番号払い出し方式によるもの

MACアドレス(正式に付けられたものに限る)

時間(同時刻の時には別途シリアル番号を払い出す)

ハッシュ関数が使われる場面

辞書のキー

オブジェクトの一意キー

これは衝突の可能性があるため、他の衝突しないことが保証される値と混ぜる必要がある。

ハッシュ関数の実装

メモ