令和3年度春期 情報処理安全確保支援士 午前Ⅱ 問3

午前II 問03：ハッシュ関数の「衝突発見困難性」を見分けよう

ハッシュ関数の衝突発見困難性とは、たとえば「同じ整理番号が付いてしまう別々の荷物を2つ探す」のがすごく大変、という性質だよ。つまり、内容が違う2つのメッセージなのに、同じハッシュ値になる組合せを見つけるには、とても大きな計算量が必要になるんだ。

この問題で問われていること

この問題では、「あるハッシュ値から元のメッセージを探すのが難しい」という原像計算困難性と、「同じハッシュ値になる別々のメッセージを2つ探すのが難しい」という衝突発見困難性を、きちんと区別できるかがポイントだよ。

衝突発見困難性

ハッシュ値が与えられて元メッセージを求めにくい性質は原像計算困難性であり、衝突発見困難性とは別です。

異なる 2 メッセージ\n-> 同じハッシュ値を見つけにくい

確認ポイント

• 元メッセージ発見困難性とは別の性質です。
• 衝突は二つのメッセージの問題として捉える。
• 同じハッシュ値になる二つのメッセージ発見の困難性を選ぶ。

正解

エ

出典

問題文と解答は IPA 公開の過去問題冊子・解答例を基にしています。

選択肢ア

これは間違いだよ。SHA-256のハッシュ値は256ビットだけど、衝突を探す大変さは「256×256」みたいな小さい話じゃないんだ。たとえるなら、256個のロッカーを探すのではなく、天文学的な数の鍵の組合せから「同じロッカーを開ける別々の鍵」を探す感じだよ。衝突探索は誕生日攻撃の考え方で、およそ2の128乗回くらいが目安になるよ。

選択肢イ

これは間違いだよ。ハッシュ値から元のメッセージを探す話は「原像計算困難性」であって、「衝突発見困難性」ではないんだ。たとえるなら、衝突は「同じ番号札になる別々の人を2人探す」話、原像は「この番号札の持ち主を探す」話だよ。2の256乗という目安はSHA-256の原像探索の話としては近いけど、衝突発見困難性の説明としてはズレているよ。

選択肢ウ

これは間違いだよ。ハッシュ値が与えられて、そこから元のメッセージを探す大変さは「原像計算困難性」だよ。衝突発見困難性は、元の1つを探す話ではなく、「同じハッシュ値になる別々のメッセージを2つ探す」話なんだ。合鍵でたとえると、これは「この鍵穴に合う鍵を1本探す」話で、衝突は「違う形なのに同じ鍵穴を開ける鍵を2本見つける」話だよ。

選択肢エ（正解）

これは、用語が「和突発見困難性」となっているなら間違いだよ。正しくは「衝突発見困難性」だね。内容としては「ハッシュ値が一致する二つの異なるメッセージを見つけにくいこと」で、これは衝突発見困難性の説明そのもの。たとえるなら、別々の書類なのに同じ受付番号になる組合せを探すのがすごく大変、という性質だよ。