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

問題本文

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

選択肢

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

正解

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

解説

衝突発見困難性とは、同じハッシュ値になる異なる二つのメッセージの組を見つけるのが計算量的に困難である性質。誕生日のパラドックスにより、出力長nビットなら約2の(n/2)乗の計算量で衝突が見つかるとされ、原像探索の2のn乗より弱い。設問はこの性質の定義を問うており、二つのメッセージの探索困難性を述べたエが正しい。実務では署名の偽造防止に直結し、衝突が現実的になったMD5やSHA-1は非推奨となった。

選択肢ごとの解説

• ア.衝突探索の計算量は約2の128乗であり、256の2乗とする値も性質の説明も誤り。
• イ.計算量2の256乗は原像探索の目安で、衝突発見困難性を示す説明としては誤り。
• ウ.ハッシュ値から元を探す困難さは原像計算困難性の説明で、衝突発見困難性ではなく誤り。
• エ.同じハッシュ値になる二つのメッセージの探索が困難という衝突発見困難性の定義どおりで正解。