1. 序章

ハッシュ は、可変長のデータ入力を、ハッシュまたはダイジェストと呼ばれる固定長の出力に変換するプロセスです。 ハッシュは、データベースへのパスワードの保存からインターネット経由で送信されるメッセージへの署名まで、現代のコンピューティングでさまざまなアプリケーションを使用しています。

ただし、ハッシュがどのように機能するかによって、衝突が発生する可能性があります。 要約すると、衝突とは、異なる入力に対して同じハッシュが生成されることです。 次に、ハッシュアルゴリズムは、衝突を回避するように設計でき、衝突耐性が弱くまたは強くなります。

このチュートリアルでは、弱いハッシュ衝突耐性と強いハッシュ衝突耐性について説明します。最初に、ハッシュについて簡単に説明します。 そのため、特にハッシュ衝突を調査し、弱い衝突耐性と強い衝突耐性について詳しく説明します。 最後に、弱い衝突耐性と強い衝突耐性の両方が特に関係するユースケースを紹介します。

2. ハッシュの概要

要約すると、ハッシュは、データを固定長のコードにマップするプロセスとして理解できます。 全体的なプロセスは、ハッシュメカニズムへの入力として生データを提供することで構成されます。ハッシュメカニズムは、特定のハッシュ関数を介して生データを処理し、出力としてハッシュを生成します。

次の画像は、ハッシュプロセスの概要を示しています。

ハッシュ関数が一方向の処理であることを強調することは重要です。 これは、これらの関数が元のデータを入力として与えられたハッシュを計算できることを意味します。 ただし、ハッシュコードを入力として指定した場合、元のデータを復元することはできません。

ハッシュには、コンピューティングでいくつかの用途があります。 最も関連性の高いハッシュアプリケーションの中で、パスワードの保存、データの整合性の検証、およびキー/値のデータ構造の作成を引用できます。

  • パスワードの保存：パスワードをプレーンテキストで保持する代わりに、パスワードのハッシュのみをデータベースに保存することができます。 したがって、攻撃者がデータベースにアクセスした場合、パスワードを回復するためにハッシュを処理する必要があります（通常、ブルートフォースまたはレインボーテーブル戦略を使用）。
  • データ整合性の検証：データ整合性検証を有効にするために、既知のオープンハッシュメカニズムが入力として提供されたデータへのハッシュを生成します。 したがって、このデータをそれぞれのハッシュコードで利用できるようにすることができます。 このようにして、データを取得したすべての人がハッシュを再計算し、提供されたものと比較できます。一致する場合、データは正しいです。
  • キー/値データ構造：一部のプログラミング言語は、キー/値関係に基づいたデータ構造を提供します。 これらのデータ構造は、ハッシュテーブルを使用して、汎用データ（値）を一意のキーにリンクします。 したがって、それぞれのキーを要求する特定の保存されたデータ（値）にアクセスできます

利点はありますが、ハッシュの固有の特性にもいくつかの課題があります。 これらの課題の1つは、次のセクションで説明するハッシュ衝突です。

3. ハッシュ衝突

つまり、異なるデータ入力がハッシュメカニズムによって処理された後に同じハッシュになると、衝突が発生します。 ただし、ここで、衝突は問題ではなく、ハッシュメカニズムの固有の特性であることに注意する必要があります。

衝突は、ハッシュが（長さに関係なく）任意の入力を固定長のコードにマップするという事実が原因で発生します。 したがって、使用可能な入力の無限セットと使用可能な出力の有限セットがあるため、ハッシュメカニズムは最終的に繰り返しハッシュを生成します。

次に、説明されているシナリオを高レベルで示した画像です。

衝突が受け入れられない場合に衝突を解決する手法があります。たとえば、置換リストを使用して、特定のオフセットでハッシュをシフトできます。 この手法は通常、ハッシュテーブルで使用されます。

別の手法は、システムでハッシュメカニズムの階層を採用することで構成されます。 したがって、衝突が発生した場合は、別のハッシュメカニズムを使用してハッシュを再作成できます。

ただし、ハッシュの衝突を解決するよりも、衝突が発生しないようにすることをお勧めします。 これを実現するには、ハッシュメカニズムが衝突耐性に関する特定のプロパティを保証する必要があります。

次のセクションでは、衝突耐性の特性を調べます。

4. 衝突耐性

ハッシュメカニズムを衝突に対して耐性にすることは、主にハッシュ関数の設計に関連する課題です。 特に、ハッシュ関数が生成できるさまざまなハッシュの数に注意する必要があります。 さらに、これらのハッシュのそれぞれを生成する頻度に注意する必要があります。

したがって、ハッシュメカニズムを必要とする特定の問題を検討してください。 問題に取り組むための優れたハッシュ関数は、各入力に一意のハッシュを提供するのに十分な異なるハッシュを生成できます。

さらに、任意の数の入力を持つセットが与えられると、適切に設計されたハッシュ関数は、最も繰り返されるハッシュと最も繰り返されないハッシュの周波数差が最小になるハッシュのセットを返します。

これらの特性は、ハッシュメカニズムを使用しているときに衝突を回避するために望ましいものです。 ただし、特定の入力または任意の入力の衝突を回避するという観点から、衝突耐性を調べることができます。 これらの機能は、弱い衝突耐性と強い衝突耐性を定義します。

4.1. 弱い衝突耐性

弱い衝突耐性の定義は次のとおりです。入力Xとハッシュ関数H（）が与えられた場合、H（X）= H（X’）である別の入力X’を見つけることは非常に困難です。

言い換えると、入力Xをパラメーターとして使用して、ハッシュH（X）を別の入力X’で複製することは簡単な作業ではありません。

4.2. 強い衝突耐性

強力な衝突耐性の背後にある主な考え方は次のとおりです。ハッシュ関数H（）と2つの任意の入力XおよびYが与えられると、H（X）がH（Y）に等しくなる絶対最小確率が存在します。

強い衝突耐性の場合、弱い衝突耐性のように衝突を検索するためのパラメータはありません。

強い衝突耐性では、任意の入力を考慮しており、このシナリオで衝突する可能性は非常に低くなっています。

5. ハッシュ衝突耐性の使用例

ハッシュの衝突耐性が特に重要になるシナリオはたくさんあります。 これらのシナリオのいくつかでは、弱い抵抗で十分です。 ただし、他のハッシュシナリオでは、強力な衝突耐性が必要になる場合があります。

通常、弱い衝突耐性で十分な例は、パスワードをハッシュとしてデータベースに保存することです。この場合、パスワードを作成した人だけが、ハッシュを生成した入力を知っています。 したがって、ハッシュメカニズムは、同じハッシュを生成する別の入力を見つけることができないため、パスワードを保護します。

一方、強力な衝突耐性が必要な例は、データの整合性をチェックすることです。 このような場合、ハッシュを生成した元の入力にアクセスできます。 したがって、ハッシュを再計算して、提供されたものと比較することができます。 たとえば、このプロセスは通常、ドキュメントにデジタル署名するときに使用されます。

したがって、同じハッシュを生成する任意の入力を見つけることは不可能であると考えています。 このようにして、私たちのデータが元のデータの真のコピーであると信頼できます。

6. 結論

このチュートリアルでは、ハッシュの衝突耐性について学習しました。 最初に、ハッシュ全般について簡単に説明しました。 このようにして、ハッシュ衝突に関する中心的な概念を学びました。 そこで、ハッシュ衝突耐性に関する概念を検討しました。弱いものと強いものです。 最後に、実世界でのハッシュ衝突耐性の特定のユースケースを見ました。

ハッシュは、今日のコンピューティングにとって不可欠なプロセスであると結論付けることができます。 ただし、採用されているハッシュメカニズム/関数に関係なく、衝突が発生する可能性があります。 したがって、これらのメカニズムを正しく設計して、衝突を回避し、弱い抵抗特性または強い抵抗特性を満たす必要があります。