情報処理安全確保支援士試験 情報セキュリティスペシャリスト試験 平成26年度秋期 午前Ⅱ 問2: ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。

問題本文

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

選択肢

• ア.SHA-256 の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256 の 2 乗である。
• イ.SHA-256 の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2 の 256 乗である。
• ウ.ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。
• エ.ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。

正解

エ. ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。

解説

衝突発見困難性とは、同じハッシュ値になる異なる二つのメッセージの組を見つけにくい性質を指す。元のメッセージを逆算しにくい原像計算困難性とは別概念であり、ハッシュ値が一致する二つのメッセージ探索の困難性を述べたエが正解。誕生日攻撃により計算量はおよそ2の(n/2)乗となる。実務では電子署名の偽造防止に直結する重要性質。

選択肢ごとの解説

• ア.衝突探索の計算量は誕生日攻撃で約2の128乗であり、256の2乗ではないので誤り。
• イ.2の256乗で元メッセージを探すのは原像計算困難性の話で、衝突発見困難性ではない。
• ウ.ハッシュ値から元メッセージを探す困難さは原像計算困難性であり、衝突の説明ではない。
• エ.同じハッシュ値になる二つのメッセージを探す困難性で、衝突発見困難性の定義どおり正しい。