良いハッシュ関数とは? 大学のデータ構造コースで多くのハッシュ関数とアプリケーションを見てきましたが、良いハッシュ関数を作成するのは非常に難しいということがほとんどでした。衝突を避けるための経験則として、私の教授は次のように述べています。
function Hash(key)
return key mod PrimeNumber
end
(mod は C および同様の言語の % 演算子です)
素数がハッシュテーブルのサイズになります。これは衝突を回避するためのやや優れた機能であり、高速なものだと思いますが、どうすればより良いものを作ることができますか? 数値キーに対する文字列キーのより良いハッシュ関数はありますか?
ユニバーサル ハッシュには「適切なハッシュ関数」などというものはありません (編。「ユニバーサル ハッシュ」などがあることは知っていますが、それは私が意図したものではありません)。コンテキストに応じて、さまざまな基準がハッシュの品質を決定します。すでに 2 人が SHA について言及しています。これは暗号化ハッシュであり、おそらくあなたが意味するハッシュテーブルにはまったく適していません。
ハッシュ テーブルには非常に異なる要件があります。しかし、データ型が異なればハッシュ化できる情報も異なるため、優れたハッシュ関数を普遍的に見つけることは困難です。経験則として、型が保持するすべての情報を等しく考慮することをお勧めします。これは必ずしも容易ではなく、可能でさえありません。統計上の理由から (したがって衝突)、問題空間、つまり考えられるすべてのオブジェクトにわたって適切な広がりを生成することも重要です。これは、100 から 1050 の間の数値をハッシュする場合、オブジェクトの ~ 90% では、この数字が 0 になるため、最上位の数字がハッシュで大きな役割を果たすようにするのは良くないことを意味します。数字はハッシュを決定します。
同様に、文字列をハッシュするときは、すべての文字を考慮することが重要です。ただし、すべての文字列の最初の 3 文字が同じであることが事前にわかっている場合は除きます。これらを考えると無駄です。
これは、クヌースがThe Art of Computer Programming vol. 3. Julienne Walker のThe Art of Hashing も参考になります。
基本的にあらゆる種類のデータに対して「通常の」ハッシュ テーブル ルックアップを実行するには、Paul Hsieh によるこれが今まで使用した中で最高です。
http://www.azillionmonkeys.com/qed/hash.html
暗号学的に安全な、またはその他のより高度なものに関心がある場合は、YMMV. ハッシュテーブルルックアップ用のキックアス汎用ハッシュ関数が必要な場合は、これが探しているものです。
ハッシュ関数の主な目的は 2 つあります。
何のためにハッシュを使用しているかを知らずにハッシュを推奨することは不可能です。
プログラムでハッシュ テーブルを作成するだけの場合は、アルゴリズムの可逆性やハッキング可能性について心配する必要はありません...これには SHA-1 または AES は完全に不要です。FNVのバリエーション。FNV は、あなたが言及したような単純なプライム mod よりも優れた分散 (したがって、衝突が少ない) を実現し、さまざまな入力サイズにより適応します。
ハッシュを使用して公開情報 (パスワードやドキュメントのハッシュなど) を隠して認証する場合は、公的精査によって精査された主要なハッシュ アルゴリズムのいずれかを使用する必要があります。ハッシュ関数ラウンジは、開始するのに適した場所です.
主な経験則は、自分で転がさないことだと思います。徹底的にテストされたもの、たとえば SHA-1 などを使用するようにしてください。
ここで言っているのは、耐衝突性を持つものを使用したいということです。SHA-2 を使用してみてください。または、宮口プレネル モードの AES のように、一方向圧縮機能で (これまで試したことがない) (優れた) ブロック暗号を使用してみてください。
それに関する問題は、 1) IV を持っている必要があることです
。ヒンチン定数の小数部分の最初の 256 ビットなどを使用してみてください。2）パディングスキームを持っています。簡単。MD5 や SHA-3 (Keccak [「ケチャク」と発音]) などのハッシュから取得します。セキュリティを気にしない場合 (数人の他の人がこれを言っています)、Bob Jenkins による FNV または lookup2 を見てください (実際、私は lookup2 を推奨する最初の人です) また、MurmurHash を試してください。高速です (これを確認してください: .16 cpb ）。
優れたハッシュ関数には次の特性があります。
メッセージのハッシュが与えられると、攻撃者がハッシュが同一であるような別のメッセージを見つけることは計算上不可能です。
メッセージのペア m' と m が与えられた場合、h(m) = h(m') となるようなメッセージを 2 つ見つけることは計算上不可能です。
2 つのケースは同じではありません。最初のケースでは、衝突を見つけようとしている既存のハッシュがあります。2 番目のケースでは、衝突する 2 つのメッセージを見つけようとしています。2 番目のタスクは、誕生日の「パラドックス」により、はるかに簡単になります。
パフォーマンスがそれほど問題にならない場合は、常に安全なハッシュ関数を使用する必要があります。ハッシュで衝突を強制することによって実行できる非常に巧妙な攻撃があります。最初から強いものを使えば防げます。
新しい設計では MD5 または SHA-1 を使用しないでください。私を含むほとんどの暗号学者は、それらが壊れていると考えるでしょう。これらの設計の両方の弱点の主な原因は、上で概説した 2 番目の特性がこれらの構造には当てはまらないことです。攻撃者が 2 つのメッセージ m と m' を生成できる場合、両方が同じ値にハッシュされ、攻撃者に対してこれらのメッセージを使用できます。SHA-1 と MD5 もメッセージ拡張攻撃の影響を受けます。注意しないと、アプリケーションが致命的に弱体化する可能性があります。
Whirpool などの最新のハッシュを使用することをお勧めします。これらのメッセージ拡張攻撃に悩まされることはなく、AES がさまざまな攻撃に対するセキュリティを証明するために使用するのと同じ数学を使用します。
それが役立つことを願っています!