令和3年度 春期 午前Ⅱ 問3

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

解説

衝突発見困難性は、同じハッシュ値になる二つの入力を見つけにくい性質です。

衝突発見困難性は、ハッシュ値が一致する二つのメッセージの組を見つけることが、計算量の面で難しいという性質です。ここで探す対象は、どちらのメッセージも自由に選んでよい二つ組です。与えられたハッシュ値から元のメッセージを探す困難さは、原像計算困難性（一方向性）と呼ばれる別の性質です。二つを探すのか、元を探すのかを区別すれば、定義として正しい記述が決まります。

ほかの選択肢はなぜ違うのか

• アSHA-256 の衝突発見困難性を示す，…：256の2乗は65,536であり、ハッシュ値を計算していけばすぐに届く量です。256ビットの出力で衝突を探す手間は、出力長の半分を指数とする2の128乗程度と見積もられるので、この値は小さすぎます。
• イSHA-256 の衝突発見困難性を示す，…：元のメッセージを見つける手間を述べた記述であり、これは原像を探す困難さの話です。2の256乗という値も原像を探す場合の見積りに当たり、衝突発見困難性を示す値として述べている点で誤りです。
• ウ衝突発見困難性とは，ハッシュ値が与えられ…：ハッシュ値が与えられたときに元のメッセージを見つけにくい性質は、一方向性と呼ばれるものです。衝突発見困難性の定義として述べている点で、性質の名前と中身が食い違っています。