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

選択肢

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

正解と解説

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

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

選択肢ごとの解説

• ア衝突発見に要する計算量は256の2乗ではなく、およそ2の128乗である。
• イハッシュ値から元のメッセージを求める話は原像計算困難性であり、衝突発見困難性の説明ではない。
• ウ元のメッセージの発見の困難性は原像計算困難性であって、衝突発見困難性とは別の性質である。
• エ正しい。ハッシュ値が一致する二つのメッセージを見つけるのが困難であることが衝突発見困難性である。

同じ分野の他の問題

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