解説

ハッシュ関数の衝突発見困難性に関する問題【午前2 解説】

要点まとめ

• 結論：衝突発見困難性とは、異なるメッセージが同じハッシュ値を持つ「衝突」を見つけることが非常に難しい性質です。
• 根拠：SHA-256のような安全なハッシュ関数では、衝突を見つける計算量は理論上$2^{128}$程度（ハッシュ長の半分の指数）とされており、実用的に困難です。
• 差がつくポイント：衝突発見困難性は「同じハッシュ値を持つ異なるメッセージの探索」であり、元のメッセージを特定する「原像探索困難性」とは異なる点を理解することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 衝突発見困難性の定義を確認する。
2. 衝突とは「異なるメッセージが同じハッシュ値を持つこと」であると理解する。
3. 選択肢の説明が「衝突の探索」に関するものか、「原像探索」に関するものかを区別する。
4. 計算量の概念（$2^{n/2}$が衝突探索の目安）を踏まえ、正しい説明を選ぶ。
5. 選択肢エが衝突探索の困難性を正しく表現しているため正解と判断する。

選択肢別の誤答解説

• ア：計算量を「256の2乗」と誤記。正しくは$2^{128}$程度であり、数値の表現が誤っている。
• イ：元のメッセージ探索（原像探索困難性）に関する説明であり、衝突発見困難性とは異なる。
• ウ：元のメッセージ探索に関する説明で、衝突発見困難性の定義としては不適切。
• エ：衝突発見困難性の正しい定義を述べているため正解。

補足コラム

• 原像困難性：ハッシュ値から元のメッセージを見つける困難さ。
• 第二原像困難性：特定のメッセージに対し、同じハッシュ値を持つ別のメッセージを見つける困難さ。
• 衝突困難性：任意の2つの異なるメッセージで同じハッシュ値を持つペアを見つける困難さ。
  SHA-256はこれらの性質を高いレベルで満たす設計となっています。

FAQ