ホーム > 情報処理安全確保支援士試験 > 2016年 春期
情報処理安全確保支援士試験 2016年 春期 午前2 問05
ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち、適切なものはどれか。
ア：SHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256の2乗である。
イ：SHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2の256乗である。
ウ：衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。
エ：衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。（正解）
解説
ハッシュ関数の衝突発見困難性に関する問題【午前2 解説】
要点まとめ
- 結論：衝突発見困難性とは、同じハッシュ値を持つ異なるメッセージを見つける困難さを指します。
- 根拠：ハッシュ関数は固定長の値に変換し、異なる入力が同じ出力になる「衝突」を見つけるのは計算量的に難しいためです。
- 差がつくポイント：衝突発見困難性と元のメッセージ探索（原像探索）の違いを正確に理解することが重要です。
正解の理由
選択肢エは「衝突発見困難性」を正しく説明しています。衝突発見困難性とは、異なる2つのメッセージが同じハッシュ値を持つペアを見つけることが難しい性質です。これはハッシュ関数の安全性の重要な指標であり、計算量的に非常に大きな負荷がかかるため、実用上はほぼ不可能とされています。
よくある誤解
衝突発見困難性と原像探索困難性（ハッシュ値から元のメッセージを探すこと）を混同しやすい点に注意が必要です。両者は異なる概念であり、計算量も異なります。
解法ステップ
- ハッシュ関数の基本性質を確認する（固定長出力、不可逆性）。
- 衝突発見困難性の定義を理解する（同じハッシュ値を持つ異なる入力の探索困難性）。
- 原像探索困難性との違いを整理する（元のメッセージを探す困難性）。
- 選択肢の説明文がどちらの性質を指しているかを判別する。
- 計算量の表現が正しいかを確認し、最も適切な選択肢を選ぶ。
選択肢別の誤答解説
- ア：計算量の表現が誤り。衝突探索の計算量は程度であり、256の2乗ではない。
- イ：これは原像探索困難性の説明であり、衝突発見困難性とは異なる。
- ウ：衝突発見困難性ではなく、原像探索困難性の説明になっている。
- エ：衝突発見困難性の正しい説明であり、正解。
補足コラム
ハッシュ関数の安全性は主に「原像困難性」「第二原像困難性」「衝突発見困難性」の3つの性質で評価されます。SHA-256の場合、衝突発見困難性は約の計算量が必要とされ、これは「誕生日攻撃」の理論に基づいています。
FAQ
Q: 衝突発見困難性と原像探索困難性はどう違いますか？
A: 衝突発見困難性は異なる2つの入力が同じハッシュ値になる組み合わせを探す困難さ、原像探索困難性はハッシュ値から元の入力を特定する困難さです。
A: 衝突発見困難性は異なる2つの入力が同じハッシュ値になる組み合わせを探す困難さ、原像探索困難性はハッシュ値から元の入力を特定する困難さです。
Q: SHA-256の衝突発見に必要な計算量はどのくらいですか？
A: 約回の計算が必要とされ、これは誕生日攻撃の理論に基づく推定値です。
A: 約回の計算が必要とされ、これは誕生日攻撃の理論に基づく推定値です。
関連キーワード: ハッシュ関数, 衝突発見困難性, 原像探索困難性, SHA-256, 誕生日攻撃, 暗号学