ハッシュの歴史
汎用ハッシュ関数は、任意のサイズのデータを次のデータにマップするために使用される特殊なタイプのプログラミング関数です。 固定サイズ. ハッシュ関数は、 圧縮する 大きなファイルを保存するために必要なメモリの量を減らすためのデータ。ハッシュ関数の最も一般的な使用例は、と呼ばれる別の特定のデータ構造です。 ハッシュ表, これは、迅速なデータ検索に広く使用されています。ハッシュ関数は、2つのまったく同じハッシュを検出することにより、テーブルまたはデータベースのルックアップを高速化するのに役立ちます.
また、mp3、PDF、画像などの巨大なファイルのタグを縮小して、これらのかなり大きなファイルタイプの操作を管理しやすくするのにも役立ちます。迅速な識別のために、ハッシュ関数の重要な要件は、それらが 英数字の固定長文字列を出力します.
ハッシュ関数の開始の主な理由はコンテンツを圧縮する必要性から来ましたが、二次的な利点はすぐにハッシュの主食になりました：非常にユニークな識別子。理想的には、複数のメッセージをハッシュする場合、2つの異なるメッセージが同じハッシュを返すことはありません。同じ出力ハッシュをもたらす2つの異なるハッシュメッセージは、 衝突.
データベース管理の観点からは、これは2つの異なるオブジェクトが同じセルに格納されることを意味します。1つが単一に一意の識別子を定義しようとしている場合は適切ではありません。ハッシュ関数を考えれば 無限の入力 （任意の文字列をハッシュできることを意味します）、衝突が実際に発生する理由を正確に導き出すことができます やむを得ない.
鳩の巣原理
暗号数学の中には、 鳩の巣原理 これは、（n）個の要素を（m）個のスペースに収めると n > m, 次に、原則として、3つ以上の要素（n）が占める少なくとも1つのスペース（m）が存在します。.
たとえば、5人の個人が、利用可能な3つのコートカビの1つでコートをチェックします。鳩の巣原理により、保管されているコートの数（n）は利用可能なカブの数（m）よりも多いため、少なくとも1つのカビーが複数のコートを保持することが保証されます.
通常、ソフトウェアエンジニアは、ハッシュ関数に関心があります。 無限の領域 （つまり、可能なすべての長さの入力文字列として使用されます）および 有限範囲. 再び鳩の巣原理に従い、範囲（n）はドメイン（m）よりも小さいため、次のようになります。 少なくとも1つの衝突が存在する必要があります. したがって、効果的なハッシュ関数は、衝突の数を最小限に抑えることだけを目的としています。これが問題になる理由はすぐに明らかになりますが、とりあえず、ハッシュの履歴に戻りましょう。.
ハッシュ関数は厳密にデータベースの維持に由来しますが & 何よりもスピードを優先する管理ニーズにより、その有用性は急速に進化しました。プライバシー、セキュリティを優先するハッシュ関数の特別なブランチ, & 透明性はすぐにフィールドに入りました。この記事の焦点であり続けるハッシュ関数のブランチ：暗号化ハッシュ関数.
暗号化ハッシュ
暗号化ハッシュ関数は、その名前が適切に示すように、完全に中断されていないメッセージの保存を支持します。衝突を最小限に抑えることは他のハッシュ関数、特に暗号化関数にとっては良い習慣ですが、衝突を最小限に抑えることは 要件. 迅速なデータベースまたはテーブルルックアップシナリオのユーティリティを最大化する代わりに、暗号化ハッシュ関数は、コードブレーカー（暗号解読者）が積極的に衝突を引き起こそうとしているという敵対的なシナリオを念頭に置いて構築されています。次に、標準のハッシュ関数表記を定義します & 暗号化の観点からハッシュ関数の原則を確立する.
ハッシュ関数表記
一般的な暗号化ハッシュ関数には、圧縮またはハッシュするメッセージの2つの入力があります（x） & ハッシュの固定長出力を英数字で表す公開鍵. ハッシュ化された結果は、メッセージダイジェストまたは単にダイジェスト（x *）と呼ばれます。これは次のようになります。
H（s、x）= x *
以前は標準だったハッシュ関数を使用して文字列をハッシュする実際の例を見て、この表記法を詳しく見ていきましょう。 MD5. MD5を使用して「HelloWorld！」をハッシュするとします。ストリング。また、デフォルトでは、MD5は常に128ビット（0）の文字列を出力することもわかっています。 & 1）。この表記は次のようになります。
H（128、x）= ed076287532e86365e841e92bfc50d8c
実際、先に進むと & 提供してみてください MD5ハッシュ関数「HelloWorld！」あなた自身あなたはまったく同じ結果のハッシュを見るはずです. 驚くばかり。それでは、衝突の表記法の設定に進みましょう。以前の変数H、s、xに加えて, & x *ここで、2番目のメッセージ（x ’）を紹介します。数値的には、2つの異なるメッセージをハッシュするときに衝突が発生します（x & x ’）は、まったく同じメッセージダイジェスト（x *）になります。
H（128、x）= H（128、x ’）の場合、ハッシュ関数（H）はxで衝突すると言われます & バツ’.
これで、ハッシュ関数暗号化の現在の特徴的な標準の表記法が設定されました。敵が実行可能に（計算上）衝突を引き起こす可能性がある場合, ハッシュ関数はもはや実質的に安全であるとは見なされていません.
次回までのまとめ
最後の数学的定義は、ハッシュ関数の実用性のための魅力的なキャッチ22が存在する場所です。ハッシュ関数は、圧縮の必要性から生じました & ストレージの利便性のために標準化された均一データを出力します。つまり、次の疑似ランダム文字列を吐き出します。 固定長. しかし、作成するために 完全に衝突耐性 ハッシュ関数では、すべてのメッセージ（x）にハッシュ出力が必要です。 入力と同じ長さ. 固定長のハッシュがないと、便利なデータ構造として使用できなくなりますが、固定長を割り当てることで、ハッシュ関数が完全に衝突しないようになります。.
PS —スマートCookieの中には、MD5の例で長さの文字列を返すハッシュ関数を表記していることに気付いた人もいると思います。 128, それでも私たちの「HelloWorld！」ハッシュは 32 英数字の文字列。次回戻ってきます & この違いがどこに生じたのかを説明するために、ハッシュ関数について詳しく説明します。.
