ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。

選択肢

• アSHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256の2乗である。
• イSHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2の256乗である。
• ウ衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量が大きいことによる，探索の困難性のことである。
• エ衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量が大きいことによる，探索の困難性のことである。

正解と解説

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

衝突発見困難性（collision resistance）は、同じハッシュ値になる異なる2つのメッセージの組を見つけるのが計算量的に難しい性質を指す。これに対し、与えられたハッシュ値から元のメッセージを求めにくい性質は原像計算困難性であり、別概念である。誕生日パラドックスにより、出力長nビットのハッシュ関数の衝突探索の計算量は概ね2の（n/2）乗で、SHA-256なら2の128乗程度となる。

選択肢ごとの解説

• アSHA-256の衝突探索は誕生日攻撃により2の128乗程度であり、256の2乗という値は根拠がない。
• イ2の256乗は原像探索に要する計算量であり、しかもそれは衝突発見困難性ではなく原像計算困難性の指標。
• ウハッシュ値から元のメッセージを探す難しさは原像計算困難性の定義であり、衝突発見困難性ではない。
• エ正解。ハッシュ値が一致する二つのメッセージを見つける計算量の大きさを指すのが衝突発見困難性。

同じ分野の他の問題

• SHA-512/256の説明はどれか。2025年度 春期 午前II 問3
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち,適切なものはどれか。2023年度 春期 午前II 問4
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち,適切なものはどれか。2021年度 春期 午前II 問3
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。2019年度 春期 午前II 問4
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。2016年度 春期 午前II 問5