04:14:27)追加された行はこの色です。削除された行はこの色です。[#l3ddbfd1][定理]鳩の巣原理~n+1羽の鳩がn個の巣に入るとすれば、2羽以上の鳩が入る巣が少なくともひとつは存在する。[系]~ハッシュ値がκビットの場合、Hを2SUP{κ};+1回計算すると、必ず衝突ペアが求まる。[証明]κビットは、2SUP{κ};通りの組み合わせがある。よって、y=H(x)において、yは2SUP{κ};ある。~(xを鳩の数、yを巣の数と思えばよい)つまり、2SUP{κ};+1を考えると少なくともひとつは重複するものがある。(Q.E.D.)[定理]κより大きいメッセージをκビットに圧縮すると、必ず衝突ペアが存在する。[証明]鳩の巣原理により、κ+1ビット分計算すると、衝突ペアが存在する。これは、鳩の数をκ+1、巣の数をκとすれば明らか。鳩の巣原理より、366人集まると、誕生日が一致するペアが必ず(確率1で)存在する。誕生日は365通りからランダムに選ばれるので、直感的には誕生日が一致するペアが存在する確率はとても低いように感じる。実際には高い確率で誕生日が一致するペアが存在する。これを''バースディパラドックス''と呼ぶ。[定理]~q個のボールをn個のバケツにランダムに投げ入れたと仮定する。~このとき、2個以上のボールが入るバケツが少なくともひとつ存在する確率をPSUB{coll};とすると、次のようになる。0.3");[証明]q個のボールから2つ選ぶときのペアの総数はSUB{q};CSUB{2};である。バケツがn個あり、それらからひとつ選択するので、1/nである。\frac{q^{2}}{n}");[系]~ハッシュ値がκビットの場合、Hを2SUP{κ/2};回計算すると、0.3以上の確率で衝突ペアが求まる。[証明]y=H(x)において、xをボールの数、yをバケツの数と思えばよい。40人のクラスで同じ誕生日のペアが存在する確率を計算してみる。すると、次のようになる。よって、88%で誕生日が衝突するようなペアが存在するということである。して想像していた確率と数学的な確率が異なっているので、バースディパラドックスと呼ばれる所以である。[問]任意のビット列から40ビットのハッシュ値を求めるハッシュ関数を考える。~q個のビット列をランダムに選び、ハッシュ値を求め、衝突を見つけたい。~衝突が見つかるような確率を1/2以上とするために、必要なビット列の個数qを求めよ。[解答]PSUB{coll};=1/2とすると、次のようになる。[#b8062828]-『現代暗号の基礎数理』-ゼミ。