平成28年度 春期 情報処理安全確保支援士試験 午前Ⅱ 問5
テクノロジ／セキュリティハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。
出典：平成28年度 春期 情報処理安全確保支援士試験 午前Ⅱ 問5
- アSHA-256 の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256 の 2 乗である。
- イSHA-256 の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2 の 256 乗である。
- ウ衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。
- エ衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。
正解：エ
解説
衝突発見困難性（collision resistance）とは，ハッシュ関数において，ハッシュ値が一致する二つの異なるメッセージの組を探し出すことが計算量的に困難であるという性質のことです。これは，あるハッシュ値から元のメッセージを探す「原像計算困難性」とは異なる性質である点に注意が必要です。
選択肢ごとの解説
- ア誤り。256の2乗という値はSHA-256の衝突発見困難性の計算量の説明として適切ではありません（誕生日攻撃を考慮すると，おおよそ2の128乗程度の計算量が必要とされます）。
- イ誤り。この記述は，ハッシュ値から元のメッセージを探索する「原像計算困難性」の説明であり，衝突発見困難性の説明ではありません。
- ウ誤り。この記述も，ハッシュ値が与えられたときに元のメッセージを探す困難性についてのものであり，衝突発見困難性の定義ではありません。
- エ正しい。衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる探索の困難性のことです。