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

選択肢

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

正解と解説

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

ハッシュ関数に求められる性質は、原像計算困難性（ハッシュ値から元のメッセージを求めにくい）、第2原像計算困難性、衝突発見困難性の三つに整理される。このうち衝突発見困難性は、同じハッシュ値になる異なる2つのメッセージの組を見つけることが計算量的に難しい性質を指す。誕生日のパラドックスにより、ハッシュ長nビットの関数で衝突を見つける計算量はおおむね2のn/2乗であり、SHA-256なら約2の128乗となる。

選択肢ごとの解説

• アSHA-256の衝突探索に要する計算量は誕生日攻撃により約2の128乗であり、示された値は誤り。
• イ元のメッセージを求める話は原像計算困難性であって、衝突発見困難性の説明になっていない。
• ウこれは原像計算困難性（一方向性）の説明である。
• エ正解。ハッシュ値が一致する2つのメッセージを見つけるのが計算量的に困難であることを指す。

同じ分野の他の問題

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