SC情報処理安全確保支援士試験 午前Ⅱ

令和3年度春期 情報処理安全確保支援士 午前Ⅱ 問3

問題文と選択肢を読んで答えを考えてから、下の「正解と解説を見る」で確認しましょう。

問題

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

選択肢

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

午前II 問03:ハッシュ関数の「衝突発見困難性」を見分けよう

ハッシュ関数の衝突発見困難性とは、たとえば「同じ整理番号が付いてしまう別々の荷物を2つ探す」のがすごく大変、という性質だよ。つまり、内容が違う2つのメッセージなのに、同じハッシュ値になる組合せを見つけるには、とても大きな計算量が必要になるんだ。

この問題で問われていること

この問題では、「あるハッシュ値から元のメッセージを探すのが難しい」という原像計算困難性と、「同じハッシュ値になる別々のメッセージを2つ探すのが難しい」という衝突発見困難性を、きちんと区別できるかがポイントだよ。

衝突発見困難性

ハッシュ値が与えられて元メッセージを求めにくい性質は原像計算困難性であり、衝突発見困難性とは別です。

異なる 2 メッセージ\n-> 同じハッシュ値を見つけにくい

確認ポイント

  • 元メッセージ発見困難性とは別の性質です。
  • 衝突は二つのメッセージの問題として捉える。
  • 同じハッシュ値になる二つのメッセージ発見の困難性を選ぶ。
正解と解説を見る

正解

エ

解説

衝突発見困難性とは、ハッシュ値が一致する異なる二つのメッセージを見つけることが計算上困難であるという性質です。

正答

エが正しい。衝突発見困難性は、ハッシュ値が一致する二つの異なるメッセージを見つけることが計算上困難であるという性質です。

誤答の理由

アは、衝突探索の計算量を256の2乗とする点が誤りです。衝突探索は誕生日攻撃の考え方により、おおよそ2の128乗回が目安となる。イとウは、ハッシュ値から元のメッセージを探す話であり、原像計算困難性の説明です。衝突発見困難性の説明ではありません。

整理

原像計算困難性は「ハッシュ値から元のメッセージを探す」、衝突発見困難性は「同じハッシュ値になる別々のメッセージを2つ探す」と区別して覚えるとよい。

選択肢ア

これは不正解だよ。衝突を探す計算量は「256の2乗」ではなく、誕生日攻撃の考え方でおよそ2の128乗回が目安だよ。ハッシュ値が256ビットでも、組合せの効果で探索量は約半分のビット数になると考えると分かりやすいよ。

選択肢イ

これは不正解だよ。ハッシュ値から元のメッセージを探す話は原像計算困難性だよ。衝突発見困難性は、同じハッシュ値になる別々のメッセージを2つ見つける難しさのことだよ。

選択肢ウ

これは不正解だよ。ハッシュ値が与えられて元のメッセージを探す性質は、原像計算困難性だよ。衝突発見困難性は、元を1つ探すのではなく、別々のメッセージを2つ見つける難しさだよ。

選択肢エ(正解)

これは正解だよ。ハッシュ値が一致する二つの異なるメッセージを見つけるのが困難だという、衝突発見困難性の説明だよ。

学習のポイント

衝突発見困難性と原像計算困難性の違いを区別し、衝突探索の計算量の目安を押さえること。

出典:独立行政法人 情報処理推進機構(IPA)令和3年度春期 情報処理安全確保支援士試験 午前Ⅱ 問3(公式資料:問題冊子(PDF) / 解答例)

関連する過去問一覧

IPA Advancedは非公式の学習サイトです。解説にはAIによる補助生成を含む場合があります。公式の問題冊子・解答例・採点講評を優先し、誤りは確認後に訂正します。運営・編集方針