解説

ハッシュ関数の性質において「衝突発見困難性（Collision Resistance）」とは、「ハッシュ値が一致する二つの異なる元のメッセージを発見することが計算量的に困難であること」（d：正解）。h(M1) = h(M2) となるM1 ≠ M2のペアを見つけることの困難性を指す。SHA-256の場合、衝突発見に要する計算量は誕生日攻撃により約2^128（256ビットの半分）とされる。混同されやすい用語の区別：「原像発見困難性（Preimage Resistance）」：ハッシュ値からの元メッセージの発見困難性（2^256程度）、「第2原像発見困難性（Second Preimage Resistance）」：与えられたM1と同じハッシュ値を持つM2の発見困難性。衝突発見困難性はデジタル署名の安全性の根拠となる重要な性質で、SHA-1は2017年にGoogleが実証的な衝突（SHAttered攻撃）を発見したため現在は非推奨とされている。

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

選択肢 ア

「ハッシュ値が一致する二つの元のメッセージの発見に要する最大の計算量は256の2乗」という記述は誤り。SHA-256の衝突発見困難性の目標計算量は約2^128（誕生日攻撃による）であり、256^2=65536とは全く異なる。また「最大の計算量」という表現も不正確で、「計算量的に困難」という性質を示す尺度として誕生日攻撃計算量が使われる。

選択肢 イ

「SHA-256の衝突発見困難性を示す、ハッシュ値の元のメッセージの発見に要する最大の計算量は2の256乗」という説明は「衝突発見困難性」ではなく「原像発見困難性（Preimage Resistance）」の説明である。衝突発見困難性は2つの異なるメッセージが同じハッシュを持つことの発見困難性であり、元メッセージの復元困難性とは異なる。

選択肢 ウ

「ハッシュ値が与えられたときに元のメッセージの発見に要する計算量が大きいことによる発見の困難性」は「原像発見困難性（Preimage Resistance）」の定義であり衝突発見困難性ではない。衝突発見困難性は任意の同一ハッシュ値を持つメッセージペアの発見困難性を指すため、入力「ハッシュ値なし」から始まる点が異なる。

解くときのポイント

ハッシュ関数の3つの安全性要件を混同しないこと: 原像発見困難性（1つの入力）・第二原像発見困難性（1つの入力に対する別の入力）・衝突発見困難性（任意の2つの入力）。