情報処理安全確保支援士試験 情報処理安全確保支援士試験 令和5年度春期 午前Ⅱ 問4: ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。

問題本文

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

選択肢

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

正解

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

解説

衝突発見困難性とは、同じハッシュ値になる異なる2つのメッセージの組を見つけるのが計算量的に困難な性質を指す。これはハッシュ値から元を求める原像計算困難性とは別概念。誕生日のパラドックスにより、出力長nビットなら衝突発見の計算量はおよそ2のn/2乗となる。エが衝突の定義を正しく述べており正解。実務ではデジタル署名の偽造耐性の根拠となる性質である。

選択肢ごとの解説

• ア.計算量を256の2乗とするのは誤り。SHA-256の衝突探索はおよそ2の128乗程度である。
• イ.2の256乗で元を求める困難性は原像計算困難性の話で、衝突発見困難性の説明ではなく誤り。
• ウ.ハッシュ値から元を発見する困難性は原像計算困難性の定義で、衝突発見困難性ではなく誤り。
• エ.ハッシュ値が一致する2つの元の発見が困難という記述が衝突発見困難性の定義どおりで正しい。