解説

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

要点まとめ

• 結論：衝突発見困難性とは、同じハッシュ値を持つ異なるメッセージを見つけることが非常に難しい性質です。
• 根拠：SHA-256のような安全なハッシュ関数では、衝突を見つける計算量は理論上非常に大きく、実用的には不可能とされています。
• 差がつくポイント：衝突発見困難性と元のメッセージ探索（逆算困難性）を混同しないことが重要です。

正解の理由

よくある誤解

解法ステップ

1. 問題文の「衝突発見困難性」の定義を正確に理解する。
2. 衝突発見困難性は「同じハッシュ値を持つ異なるメッセージを見つける難しさ」であることを確認。
3. SHA-256のハッシュ長256ビットに対し、衝突発見には約$2^{128}$の計算量が必要なことを知る。
4. 選択肢の説明が衝突発見困難性の定義に合致しているかを判断。
5. 元のメッセージ探索（逆算困難性）と混同している選択肢を除外。
6. 正しく衝突発見困難性を説明している選択肢エを選ぶ。

選択肢別の誤答解説

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

補足コラム

• 逆算困難性：ハッシュ値から元のメッセージを特定するのが困難。
• 衝突発見困難性：異なるメッセージで同じハッシュ値を見つけるのが困難。
• 第二原像困難性：特定のメッセージに対して同じハッシュ値を持つ別のメッセージを見つけるのが困難。
  これらの性質が強いほど、ハッシュ関数は安全とされます。

FAQ