# 生日攻击

## 数学

${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}}$

${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}$

${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}$

${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}$

（2安全系数）（p）
10−18 10−15 10−12 10−9 10−6 0.1% 1% 25% 50% 75%
16 216 (~6.5 x 104) <2 <2 <2 <2 <2 11 36 190 300 430
32 232 （~4.3 × 109 <2 <2 <2 3 93 2900 9300 50,000 77,000 110,000
64 264 （~1.8 × 1019 6 190 6100 190,000 6,100,000 1.9 × 108 6.1 × 108 3.3 × 109 5.1 × 109 7.2 × 109
128 2128 （~3.4 × 1038 2.6 × 1010 8.2 × 1011 2.6 × 1013 8.2 × 1014 2.6 × 1016 8.3 × 1017 2.6 × 1018 1.4 × 1019 2.2 × 1019 3.1 × 1019
256 2256 （~1.2 × 1077 4.8 × 1029 1.5 × 1031 4.8 × 1032 1.5 × 1034 4.8 × 1035 1.5 × 1037 4.8 × 1037 2.6 × 1038 4.0 × 1038 5.7 × 1038
384 2384 （~3.9 × 10115 8.9 × 1048 2.8 × 1050 8.9 × 1051 2.8 × 1053 8.9 × 1054 2.8 × 1056 8.9 × 1056 4.8 × 1057 7.4 × 1057 1.0 × 1058
512 2512 （~1.3 × 10154 1.6 × 1068 5.2 × 1069 1.6 × 1071 5.2 × 1072 1.6 × 1074 5.2 × 1075 1.6 × 1076 8.8 × 1076 1.4 × 1077 1.9 × 1077

### 源码示例

from math import log1p, sqrt

def birthday(probability_exponent, bits):
probability = 10.0**probability_exponent
outputs = 2.0**bits
return sqrt(2.0*outputs*-log1p(-probability))


\$ python -i birthday.py
>>> birthday(-15, 128)
824963474247.1193
>>> birthday(-6, 32)
92.68192319417072


### 简单估计

${\displaystyle p(n)\approx {n^{2} \over 2H}}$

${\displaystyle H\approx {n^{2} \over 2p(n)}}$.

${\displaystyle n\approx {\sqrt {2H\times p(n)}}}$.

${\displaystyle n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5}$

## 脚注

1. ^ Daniel J. Bernstein. Cost analysis of hash collisions : Will quantum computers make SHARCS obsolete? (PDF). Cr.yp.to. [29 October 2017].
2. ^ Brassard, Gilles; HØyer, Peter; Tapp, Alain. Quantum cryptanalysis of hash and claw-free functions. Springer, Berlin, Heidelberg: 163–169. 20 April 1998 [29 October 2017]. doi:10.1007/BFb0054319.
3. ^ Math Forum: Ask Dr. Math FAQ: The Birthday Problem. Mathforum.org. [29 October 2017].
4. ^ 请参阅上界和下界
5. ^ Jacques Patarin, Audrey Montreuil. Benes and Butterfly schemes revisited . Université de Versailles. 2005 [2007-03-15].
6. ^ Gray, Jim; van Ingen, Catharine. Empirical Measurements of Disk Failure Rates and Error Rates. 25 January 2007. .
7. ^ Archived copy. [2006-05-02]. （原始内容存档于2008-02-23）.
8. ^ Compute log(1+x) accurately for small values of x. Mathworks.com. [29 October 2017].