解説

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

要点まとめ

• 結論：衝突発見困難性とは、異なるメッセージが同じハッシュ値になる組み合わせを見つけるのが困難な性質です。
• 根拠：SHA-256のような安全なハッシュ関数は、衝突を見つけるために膨大な計算量が必要であり、これがセキュリティの基盤となっています。
• 差がつくポイント：衝突発見困難性は「同じハッシュ値を持つ異なるメッセージの発見」であり、「元のメッセージの発見」とは異なる概念である点を正確に理解することが重要です。

正解の理由

よくある誤解

解法ステップ

1. 衝突発見困難性の定義を確認する（異なるメッセージが同じハッシュ値になること）。
2. SHA-256のハッシュ長（256ビット）から計算量の目安を理解する。
3. 衝突発見困難性は「同じハッシュ値を持つ異なるメッセージの発見」であることを認識する。
4. 選択肢の説明が定義と合致しているかを比較する。
5. 正しい説明をしている選択肢を選ぶ。

選択肢別の誤答解説

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

補足コラム

• 原像困難性：ハッシュ値から元のメッセージを見つける困難性。
• 第二原像困難性：特定のメッセージに対して異なるメッセージを見つける困難性。
• 衝突発見困難性：異なるメッセージ同士で同じハッシュ値を見つける困難性。
  SHA-256はこれらを高いレベルで満たすため、広く使われています。

FAQ