平成29年度 秋期 午前Ⅱ 問4

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

解説

同じハッシュ値の異なる二つのメッセージを見つけにくい性質です。

ハッシュ関数の安全性には、何を探すのが難しいかによって別々の性質があります。ハッシュ値が与えられて、その元になったメッセージを探す難しさは原像計算困難性（一方向性）と呼ばれます。これに対して衝突発見困難性は、どれでもよいので同じハッシュ値になる異なる二つのメッセージの組を探す難しさを指します。したがって、ハッシュ値が一致する二つのメッセージの探索に要する計算量が大きいことによる困難性、という記述が正解です。SHA-256 について計算量を述べた選択肢は、何を探すのかと、その目安の値の両面から確かめます。

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

• アSHA-256 の衝突発見困難性を示す，…：一致する組を探すという対象は合っています。しかし計算量を256の2乗としています。誕生日攻撃を考えると、出力256ビットの衝突探索の目安は2の128乗であり、256の2乗ではありません。
• イSHA-256 の衝突発見困難性を示す，…：ハッシュ値から元を探す話をしており、これは衝突ではなく原像の探索です。2の256乗という値もその目安であり、衝突発見困難性を示す計算量の説明になっていません。
• ウ衝突発見困難性とは，ハッシュ値が与えられ…：与えられたハッシュ値から出発して元を探す難しさを述べています。これは一方向性を表す性質の説明であり、どれでもよい二つの一致を探す性質とは別物です。