平成29年度秋期 情報処理安全確保支援士 午前Ⅱ 問4

午前II 問04：ハッシュの「同じ指紋を見つける難しさ」を押さえよう

衝突発見困難性とは、別々の2つのメッセージなのに、同じハッシュ値になる組合せを見つけるのが現実的にはとても難しい、という性質だよ。たとえるなら、違う人なのにまったく同じ指紋をもつペアを探し出すのがほぼ無理、というイメージだね。

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

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

衝突発見困難性

元のメッセージを 1 つ求める困難性ではなく、同じハッシュ値になる別々のメッセージ 2 つを探す困難性が衝突発見困難性です。

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

確認ポイント

• 元メッセージ探索は原像計算困難性です。
• 衝突は「二つのメッセージ」の問題です。
• 一致する二つのメッセージ探索の困難性を選ぶ。

正解

エ

出典

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

選択肢ア

不正解だよ。SHA-256の衝突探しは、同じ番号札を持つ別人を探すようなものだけど、必要な計算量は「256の2乗」みたいな小さい話ではないよ。誕生日の一致が意外と起きやすいのと同じ考えで、衝突探索は一般に約2の128乗回くらいが目安になるんだ。

選択肢イ

不正解だよ。「ハッシュ値から元のメッセージを探す」のは、落ちている鍵穴だけを見て元の鍵を作るような話で、これは原像探索の説明だよ。2の256乗という規模感はSHA-256の原像探索には合っているけど、衝突発見困難性の説明ではないんだ。

選択肢ウ

不正解だよ。これは「ハッシュ値から元のメッセージを探しにくい」という説明で、衝突発見困難性ではなく原像計算困難性の話だよ。たとえるなら、レシート番号から買い物かごの中身を当てるのが難しい、という別の難しさなんだ。

選択肢エ（正解）

正解だよ。衝突発見困難性は、同じ受付番号になる別々の申込書を2枚見つけるのがものすごく大変、という性質だよ。つまり「違うメッセージなのに同じハッシュ値になるペア」を探しにくいことを指すんだ。