情報処理安全確保支援士試験 2023年 春期 午前2 問04

解説

衝突発見困難性とは何か？

• ハッシュ関数は多くの異なる入力から固定長の出力を生成するため、理論的には異なる入力であっても同じハッシュ値になることがあります。これを「衝突」と呼びます。
• 衝突発見困難性とは、この「衝突する異なるメッセージのペア」を見つけることが非常に難しい（計算量が大きい）ことを意味します。
• つまり、攻撃者が容易に異なるメッセージ同士で同じハッシュ値を作ることができないことが、ハッシュ関数の安全性を支えています。

選択肢の検討

• アの「最大計算量は 256 の 2乗」は間違いです。SHA-256のハッシュ値は256ビットですが、衝突発見は計算量が$2^{128}$程度かかるとされており、単純に256の2乗ではありません。
• イの「元のメッセージの発見に要する計算量」は「衝突発見困難性」ではなく、「元メッセージ発見（事前画像困難性）」の話であり内容が異なります。
• ウの説明は「元のメッセージの発見」に関するものであり、「衝突発見困難性」を説明したものではありません。
• エは「衝突発見困難性」について正しく説明しており、「同じハッシュ値を持つ異なるメッセージを見つけるのに大きな計算量が必要」と正確に述べています。

計算量の目安

• SHA-256の場合、
  • 衝突発見困難性の計算量はおよそ$2^{128}$回のハッシュ計算が必要とされています（誕生日攻撃の理論による）。
  • **元メッセージの発見（事前画像困難性）**は約$2^{256}$回が必要です。

まとめ