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

午前II 問04：ハッシュ関数の「衝突発見困難性」って何？

衝突発見困難性は、別々のメッセージなのに同じハッシュ値になる組み合わせを見つけるのがとても難しい、という性質だよ。たとえるなら、違う書類をシュレッダーにかけた結果がまったく同じ見た目になるペアを探すのが難しい、というイメージだね。これは、ハッシュ値から元のメッセージを逆算しにくいという原像計算困難性とは別の話だから、混同しないようにしよう。

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

この問題では、ハッシュ関数の性質を名前だけでなく定義まで正確に区別できるかがポイントだよ。特に、同じハッシュ値になる別メッセージのペアを探しにくいのが衝突発見困難性、ハッシュ値から元データを求めにくいのが原像計算困難性、と整理しよう。

衝突発見困難性

衝突発見は、同一ハッシュになる 2 つの異なる入力を探す問題です。

m1 != m2\nH(m1)=H(m2)\n-> 見つけにくい

確認ポイント

• 与えられたハッシュ値から元文を探すのは原像計算困難性です。
• 計算量の数値自体より定義の違いを押さえる。
• 二つの元メッセージの発見困難性を選ぶ。

正解

エ

出典

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

選択肢ア

これは間違いだよ。SHA-256のハッシュ値は256ビットなので、候補の数は「256の2乗」ではなく「2の256乗」みたいな世界になるよ。ただし、衝突を探す話では誕生日の一致みたいに、だいたい2の128乗回くらいで見つかる可能性を考えるんだ。数字の意味を取り違えているのがポイントだよ。

選択肢イ

これは間違いだよ。2の256乗という大きさは、与えられたハッシュ値から元のメッセージを探す難しさの目安だよ。衝突発見困難性は、同じハッシュ値になる二つの別メッセージを探す難しさなので、説明している対象がずれているよ。窓口番号から本人を探す話と、同じ番号札を持つ二人を探す話は別物だね。

選択肢ウ

これは間違いだよ。これは『このハッシュ値になる元の文を探すのが難しい』という話で、合鍵の番号を見て元の鍵を作るようなイメージだね。これは原像計算困難性の説明であって、衝突発見困難性ではないよ。衝突は『同じ番号になる別々の鍵を2本見つける』話だよ。

選択肢エ（正解）

これは正解だよ。衝突発見困難性は、別々の二つのメッセージなのに同じハッシュ値になる組み合わせを見つけにくい、という性質だよ。たとえるなら、たくさんの人に番号札を配ったときに『同じ番号札を持つ二人』を狙って見つけるのがものすごく大変、というイメージだね。