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

問題文

ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち、適切なものはどれか。

選択肢

ア：SHA-256の衝突発見困難性を示す、ハッシュ値が一致する二つの元のメッセージの発見に要する最大の計算量は、256の2乗である。

イ：SHA-256の衝突発見困難性を示す、ハッシュ値の元のメッセージの発見に要する最大の計算量は、2の256乗である。

ウ：衝突発見困難性とは、ハッシュ値が与えられたときに、元のメッセージの発見に要する計算量が大きいことによる、発見の困難性のことである。

エ：衝突発見困難性とは、ハッシュ値が一致する二つの元のメッセージの発見に要する計算量が大きいことによる、発見の困難性のことである。（正解）

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

要点まとめ

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

正解の理由

選択肢エは「衝突発見困難性とは、ハッシュ値が一致する二つの元のメッセージの発見に要する計算量が大きいことによる発見の困難性」と正確に説明しています。
衝突とは異なる2つの入力が同じハッシュ値を持つことを指し、その発見が困難であることが衝突発見困難性の本質です。
他の選択肢は計算量の誤りや、衝突発見困難性の定義を混同しているため不適切です。

よくある誤解

衝突発見困難性を「元のメッセージを特定する困難性」と混同しやすいですが、これは「原像困難性」と呼ばれる別の性質です。
また、計算量の単位や指数の扱いを誤解しやすい点にも注意が必要です。

解法ステップ

衝突発見困難性の定義を確認する（同じハッシュ値を持つ異なる入力の発見困難性）。
SHA-256のハッシュ長（256ビット）から計算量の目安を理解する（衝突発見は約 $2^{128}$ の計算量）。
選択肢の説明と計算量の表現を比較し、正しいものを選ぶ。
「元のメッセージの発見」と「衝突発見」の違いを明確に区別する。
正確な定義に合致する選択肢を選択する。

選択肢別の誤答解説

ア：計算量を「256の2乗」と表現し誤り。衝突発見の計算量は約 $2^{128}$ であり、256の2乗（65536）とは桁違いに小さい。
イ：元のメッセージの発見に要する計算量を $2^{256}$ とし、衝突発見困難性の説明として誤り。これは原像困難性に近いが、問題は衝突発見困難性。
ウ：衝突発見困難性を「元のメッセージの発見」と誤って説明。これは原像困難性の説明であり、衝突発見困難性とは異なる。
エ：衝突発見困難性の正しい定義を示しているため正解。

補足コラム

ハッシュ関数の安全性は主に「原像困難性」「第二原像困難性」「衝突発見困難性」の3つの性質で評価されます。

原像困難性：ハッシュ値から元のメッセージを見つける困難性。
第二原像困難性：特定のメッセージに対し、同じハッシュ値を持つ別のメッセージを見つける困難性。
衝突発見困難性：任意の2つの異なるメッセージで同じハッシュ値を持つものを見つける困難性。
SHA-256はこれらの性質を高いレベルで満たすため、広く安全なハッシュ関数として利用されています。

FAQ

Q: 衝突発見困難性と原像困難性はどう違いますか？
A: 衝突発見困難性は「同じハッシュ値を持つ異なるメッセージの発見が難しいこと」、原像困難性は「ハッシュ値から元のメッセージを特定するのが難しいこと」です。

Q: SHA-256の衝突発見に必要な計算量はどのくらいですか？
A: 約

2^{128}

回の計算が必要とされ、現実的には非常に困難です。

Q: 衝突が見つかると何が問題ですか？
A: デジタル署名やデータ整合性の信頼性が損なわれ、セキュリティリスクが生じます。

関連キーワード: ハッシュ関数、衝突発見困難性、SHA-256, 原像困難性、第二原像困難性、計算量、セキュリティ

← 前の問題へ次の問題へ →

\ せっかくなら /

情報処理安全確保支援士を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！