1. はじめに
本記事では、バースデーパラドックスとハッシュ値の衝突確率との関係について解説する。
ハッシュ関数には以下の3つが要求される。
- 原像計算困難性
- 強衝突耐性
- 第二原像計算困難性
今回は特に、強衝突耐性の脆弱性評価にバースデーパラドックスが利用できるという点について解説していく。
2. 64 ビット のハッシュ値で十分？
はじめに、ハッシュ値について考える。ハッシュ関数とは、任意の長さの入力に対して固定長の出力（=ハッシュ値）を返す関数であり、データの要約・識別・整合性の検証など様々な分野で広く使われている。
現在主流のハッシュ関数の１つに SHA-256 がある。これは256ビット、すなわち$2^{256}$通りの異なるハッシュ値を生成できる。
$2^{256}$というのは非常に大きく、そのため、ハッシュ値の保持に多くのメモリを必要とする。この点から、ハッシュ長を縮小しても問題がないのではないかという疑問が生じる。
$\longrightarrow$ ビット数をもう少し減らしても問題が無いのでは？
ここで64ビットについて考えてみる。先ほどの$2^{256}$と比較すると桁違いに小さいが、それでも18,446,744,073,709,551,616 (20 桁)はある。約1000京通りもあれば十分に思える。
64ビット にすれば、ハッシュ値の保持に必要なサイズも減り、処理も軽くなりそうだ。
64ビット のハッシュ関数が機能するかどうかを判断する際に、「バースデーパラドックス」というものが使える。
3. バースデーパラドックス
3.1. バースデーパラドックスとは？
バースデーパラドックスとは、「何人あつまれば、その中に誕生日が同一である2人（以上）いる確率が50%を超えるのか？」という問題から生じるパラドックスである。
この問題は鳩の巣原理より、366人（閏年を考えない）があつまれば100%となるが、その5分の1に満たない70人でもこの確率が99.9%を越え、50%を超えるのに必要な人数がわずか23人であるというもの。
23人で50%を超えるというのは、直感に反するものだがこの確率は数学的に証明することができる。
3.2. バースデーパラドックスの数学的証明？
以下の命題について考えてみる。
命題： $D = \{ 1, 2, ..., n \}$の中から重複を許して一様ランダムに$k( \geqq 2)$個の数字を選ぶ。このとき、これらの数字の中に同じ数字が含まれている確率を求める
この問題は余事象について考えると解くことができる。そのため、初めに重複を許さないで一様ランダムに$k( \geqq 2)$個の数字を選ぶ。
このとき、求める確率は以下の様になる。
\dfrac{n}{n} \cdot \dfrac{n-1}{n} \cdot \cdot \cdot \dfrac{n - (k - 1)}{n}
ここから$n$について整理する。
\begin{align*}
\dfrac{n}{n} \cdot \dfrac{n-1}{n} \cdots \dfrac{n - (k - 1)}{n} &= 1 \cdot (1 - \dfrac{1}{n}) \cdot (1 - \dfrac{2}{n}) \cdots (1 - \dfrac{(k - 1)}{n}) \\
&= \prod_{j=1}^{k-1} (1 - \dfrac{j}{n}) \tag{1}
\end{align*}
式(1)で求めたのは、重複を許さないケースだったので余事象を取って
p(n, k) = 1 - \prod_{j=1}^{k-1} (1 - \dfrac{j}{n}) \tag{2}
と求めることができる。
ここで、$1 - x \approx e^{-x}$という近似式を用いると、(2)より、
\begin{align*}
p(n, k) &= 1 - \prod_{j=1}^{k-1} (1 - \dfrac{j}{n}) \\
&\approx 1 - \prod_{j=1}^{k-1} e ^ {\frac{j}{n}} \\
&= 1 - e ^ {- \sum_{j=1}^{k - 1} \frac{j}{n}} \\
&= 1 - e ^ {- \frac{k(k - 1)}{2n}} \\
&\approx 1 - e ^ {- \frac{k^2}{2n}} \tag{3}
\end{align*}
この(3)の近似式を使って、$p(n, k) \geqq \frac{1}{2}$となる条件を求めると、次のようになる。
1 - e ^ {- \frac{k^2}{2n}} \geqq \frac{1}{2} \tag{4}
であるが、この(4)式を解くと、
k \geqq \sqrt{2 \log 2} \cdot \sqrt{n} \approx 1.1774 \sqrt{n} \tag{5}
ここで、再度確認であるが $n$ は全体の数で、 $k$ は選択した数である。つまり、今回の誕生日のケースでは $n$ 日あるなかから、$k$ 日をランダムに選択したときに重複が発生する確率について求めた（=$p(n, k)$）
この確率が50%を超えるときのケースで$n$と$k$の式になっているものが（5）である。
ここで、$n$ = 365 を代入してみる。この時に求められる$k$の値の最小値が、誕生日が重複する確率50%超えるのに必要な数（=$k$）である。
$n$ = 365のとき、
k \geqq 1.1774 \cdot \sqrt{365} \approx 22.49...
となり、$k \geqq 23$ で50%を超えることがわかった。
ここまでは一年間の日にち（= 閏年なしの365日）のうち、ランダムに$k$個選んだとき、重複する確率が50%以上になるときの$k$の値について求めた。
3.3. バースデーパラドックスとハッシュ関数の関係
前節で導出した式（5）より、厳密には以下の様な関係が成り立つ。
k \geqq \sqrt{2 \log 2} \cdot \sqrt{n} \approx 1.1774 \sqrt {n}
この式は、「サイズが$n$である集合からランダムに$k$個を選んだとき、重複する確率が50%を超えるために必要な$k$の個数を示す近似式」である。定数係数（約1.177）は小さく概ね $\sqrt{n}$ のオーダーで衝突が起きるとみなせる。
ここで、2章の64ビットのハッシュ関数に戻り、このハッシュ関数が衝突を起こす確率をバースデーパラドックスより求めてみると、わずか$2^{32}$個のハッシュ値から衝突を見つけられる可能性が高い。$2^{32}$というと、40億程度なので現代のコンピュータであれば数時間から数分程度で探索可能な規模である。
以上より、64ビットのハッシュ関数は、衝突耐性の観点から十分とは言えない。
4. Pythonでの実装
バースデーパラドックスをPythonで実装してみた。コードは以下の通りである。
import random
import matplotlib.pyplot as plt
import numpy as np
class BirthdaySimulator:
def __init__(self, days=365, max_people=100, trials=100):
self.days = list(range(1, days + 1))
self.max_people = max_people
self.trials = trials
self.ratio = []
def __match_count(self, days, people, trials):
count = 0
for i in range(trials):
birthdays = list(random.choices(days, k = people))
if len(birthdays) > len(set(birthdays)):
count += 1
return count / trials
def run(self):
self.ratio = [self.__match_count(self.days, k, self.trials) for k in range(2, self.max_people)]
def plot(self):
population = np.arange(2, self.max_people)
plt.plot(population, self.ratio)
plt.plot(population, 1 - np.exp(-population ** 2 / (2 * 365)))
plt.xlabel('number of people')
plt.ylabel('probability')
plt.show()
def main():
simulator = BirthdaySimulator()
simulator.run()
simulator.plot()
if __name__ == "__main__":
main()
ここで __match_count の
-
peopleは前章の$k$（取り出す個数） -
daysは前章の$n$（全体の日にち） -
trialsは試行回数
である。people 人を選択して、trials回数乱数を発生させたら（= 重複有り）どれくらい重複が発生するのかを調べている。
これを実行した結果は以下の通りである。
この結果から、人数が増えると重複が発生しやすくなる。また、理論的に求めた50%を超える境界（約23人）と、シミュレーション結果が概ね一致していることも確認できる。
5. 結論
バースデーパラドックスを用いると、ハッシュ値の要件である強衝突耐性の脆弱性評価を行うことができる。
6. 参考
[1] Pythonで学ぶ暗号理論
[2] 同じ誕生日の二人組がいる確率について
[3] なぜ「23人いれば同じ誕生日の人がいる確率は50％」なのか
[4] Python Document