セキュリティ計算問題

誕生日問題（birthday problem）のハッシュ衝突への応用に関する記述として、最も適切なものはどれか。

ア.nビットのハッシュ関数で衝突確率が50%を超えるのに必要なメッセージ数は、約2^n個である。

イ.nビットのハッシュ関数で衝突確率が50%を超えるのに必要なメッセージ数は、約n/2個である。

ウ.nビットのハッシュ関数で衝突確率が50%を超えるのに必要なメッセージ数は、約2^(n/2)個であり、128ビットハッシュの場合約2^64個のメッセージで衝突が期待できる。正解

エ.ハッシュの衝突確率は使用するメッセージ数に比例して線形に増加し、2^n個を超えると初めて衝突が発生する。

解説

誕生日のパラドックスは「クラスに23人いれば同じ誕生日の人がいる確率は50%超」という驚き。365日から366人必要と思いがちですが半分以下で済む。これと同じ原理でハッシュも「全空間の平方根（2^(n/2)）」で衝突が期待できます。

なぜウが正解か

ウが正解。誕生日問題より、N種類の値がある空間で衝突確率が50%を超えるのに必要なサンプル数は約√N個。nビットハッシュはN=2^n個の異なるハッシュ値を持つため、衝突が50%以上になるメッセージ数 ≈ √(2^n) = 2^(n/2)個。128ビットハッシュ：2^(128/2) = 2^64 ≒ 1.8×10^19個で衝突50%。このため誕生日攻撃に対してはn/2ビットのセキュリティ強度しか持たないとされる。

なぜアは間違いか

2^n個は「ハッシュ値の総数（全空間）」であって衝突50%に必要なメッセージ数ではない。誕生日問題の答えは√(2^n) = 2^(n/2)個と大幅に少ない。2^nは誕生日問題を知らずに直感で答えた場合の典型的な誤り。

なぜイは間違いか

n/2個は「ビット数の半分の個数」という全く根拠のない誤答。誕生日問題は指数関数的な計算であり、nビットの半分という線形的な発想ではなく、2^(n/2)という指数計算が必要。

なぜエは間違いか

ハッシュ衝突確率はメッセージ数に対して線形ではなく、誕生日問題の原理により非線形（急速に上昇する）に増加する。また「2^n個を超えると初めて衝突」は誤りで、2^(n/2)個程度で50%の衝突確率に達する。

出典: AI生成問題（学習用）

← 前の問題

共通鍵暗号において、鍵長を56ビット（DES）から128ビット（AES）に変更した場合、総当たり攻撃に必要な試行回数（セキュリティ強度）は理論上何倍になるか。

次の問題 →

楕円曲線暗号（ECC: Elliptic Curve Cryptography）の特徴として、最も適切なものはどれか。

セキュリティの問題を解くこの分野の問題一覧を見る