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

選択肢

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

正解と解説

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

衝突発見困難性(collision resistance)とは、同じハッシュ値になる二つの異なるメッセージの組を見つけるのが計算量的に困難であるという性質で、エが定義どおり。ハッシュ値から元のメッセージを求めにくい性質は原像計算困難性であり、別の概念である。なお誕生日パラドックスにより、nビット出力の衝突探索の計算量はおよそ2の(n/2)乗であって2のn乗ではない。

選択肢ごとの解説

• ア計算量の見積りが誤り。SHA-256の衝突探索はおよそ2の128乗であり、256の2乗ではない。
• イ元のメッセージの発見は原像計算困難性の話。2の256乗という値もそちらに対応する。
• ウハッシュ値から元のメッセージを探す困難性は原像計算困難性の定義である。
• エ正しい。同一ハッシュ値になる二つのメッセージを見つける困難性が衝突発見困難性。

同じ分野の他の問題

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