簡介
生日攻擊其實是一個機率論的問題，也就是說一個看起來很難發生的事情，事實上它發生的機率卻很大。這種主觀上和事實上的機率差距，讓随機攻擊成功的幾率變的更高，這樣的攻擊就叫做生日攻擊。
生日問題的由來
生日問題也叫做生日悖論，它是這樣這樣描述的。
假如随機選擇n個人，那麼這個n個人中有兩個人的生日相同的機率是多少。如果要想機率是100%，那麼隻需要選擇367個人就夠了。因為隻有366個生日日期（包括2月29日）。
如果想要機率達到99.9% ，那麼隻需要70個人就夠了。50%的機率隻需要23個人。
對于現在的幼稚園小朋友來說，一個班上差不多有30人，那麼将會有大于50%的幾率，班上有兩個人的生日是一樣的。
聽起來是不是很神奇？跟我們第一映像中的基數是不是要少很多。
我們看一張機率圖：
在實際應用中，可以應用生日問題中的機率模型，進而減少碰撞攻擊的複雜度，或者來評估一個hash函數中可能出現碰撞攻擊的幾率。
怎麼計算呢？
假如P(A) 是生日相同的機率，那麼P(A) = 1 – P(A’) ，其中P(A’)是生日不同的機率。
一個人生日不同的機率是365/365,兩個人生日不同的機率就是365/365 * 364/365 ,依次類推。
我們可以得到23個人生日不同的機率大概就是 0.492703。
也就是說23個人中有兩個人生日相同的機率可以大于50%。
再看一張表來個更加直覺的描述：
生日問題的衍生
生日問題的取值範圍是在一年的365天之内，也就是說生日隻可能有365種可能性。
我們将這個問題擴充一下到一般的情況，假設有一個函數f，它的輸出範圍是H，那麼我們的攻擊就是找到兩個不同的x，y，讓f(x)=f(y)。
這時候，我們可以稱x和y發生了碰撞。
根據機率論的公式，我們想要達到50%的幾率，那麼需要嘗試的次數是:
生日攻擊的應用
生日攻擊一般應用在數字簽名中。一般來說為了對機密消息進行簽名，因為加密的限制，如果消息很大的情況下，不可能對所有的消息進行簽名，通常會對消息計算hash值，然後對這個hash值進行簽名。
比如有人想做一個欺詐性的合同，那麼會在原合同的基礎上進行修改，不斷的進行嘗試，進而找到一個修改後的合同，讓合同和之前合同的hash是一樣的，進而導緻兩者的簽名也是一樣的。
怎麼抵禦這種攻擊呢？根據我們生日攻擊的公式，當然是将簽名方案使用的哈希函數的輸出長度選擇得足夠大，以使生日攻擊在計算上變得不可行。
本文已收錄于 http://www.flydean.com/birthday-attack/