好久沒(méi)見(jiàn)小明了屹蚊，今天我們繼續(xù)來(lái)聊小明的故事厕氨。小明最近十分勤奮好學(xué)，看了很多數(shù)學(xué)書(shū)籍汹粤，數(shù)學(xué)成績(jī)上升很快命斧，于是被老師提拔為新任班長(zhǎng)。剛好嘱兼，小紅最近快過(guò)生日了国葬，于是小紅就來(lái)問(wèn)小明自己班上，或者隔壁班有沒(méi)有和她生日相同的同學(xué)芹壕。小明知道自己班上有41個(gè)同學(xué)汇四，而隔壁班上的人稍微少一點(diǎn)只有23個(gè)，但是小明手上現(xiàn)在沒(méi)有花名冊(cè)踢涌。于是他對(duì)小紅說(shuō)通孽，我們班上一定有兩個(gè)生日相同的人，隔壁班上有一半的可能有兩個(gè)生日相同的人睁壁，但是我不太確定是不是你背苦。
小紅十分疑惑，問(wèn)他：你怎么這么確定我們班上有生日相同的人潘明，隔壁班上有一半可能有生日相同的人行剂？
小明故作神秘的笑而不語(yǔ)，然后問(wèn)小紅： “你覺(jué)一個(gè)有23個(gè)同學(xué)的班上钳降，有生日相同的同學(xué)的概率是多少厚宰？”
“23/365吧，這個(gè)概率應(yīng)該很小吧”遂填，小紅說(shuō)铲觉。
“但是，你的答案正確的概率更小城菊”溉迹”，小明說(shuō)凌唬。
Why并齐？? OK，right now客税！我們來(lái)回答這個(gè)問(wèn)題吧况褪，首先需要提出一個(gè)概念：生日悖論。什么是生日悖論更耻？其實(shí)就是上文中小明向小紅提的那個(gè)問(wèn)題测垛；在一個(gè)23個(gè)人的人群中，有兩人生日相同的概率是多少秧均？我們直覺(jué)的答案是23/365食侮，但是實(shí)際上号涯，答案應(yīng)該是0.5。同樣锯七，在一個(gè)41人的人群中链快，有兩人生日相同的概率是0.9而不是40/365。這就是所謂的生日悖論眉尸！
是不是感覺(jué)到很奇怪域蜗？
但是，why噪猾？? 要回答這一個(gè)問(wèn)題霉祸，我們只需要做一個(gè)簡(jiǎn)單的計(jì)算：依次考慮每個(gè)人的生日，
第一個(gè)人：365/365袱蜡；
第二個(gè)人丝蹭；364/365；
第三個(gè)人：363/365戒劫；
……
第n個(gè)人：（365-n+1）/365
那么半夷，在一個(gè)n人的群體中，有至少兩人生日相同的概率為1-（365/365 * 364/365 * 363/365……（365-n+1）-365）
從上面的等式我們可以得知：
當(dāng)n=23時(shí)迅细，概率為0.5巫橄；
當(dāng)n=41時(shí)，概率為0.9茵典。
所以湘换，小明才有把握說(shuō)隔壁班上一定有生日相同的人 而自己班上有百分之五十的可能性有生日相同的人。
知道了什么是生日悖論统阿，我們來(lái)接著討論生日攻擊彩倚，也就是本文的重點(diǎn)內(nèi)容。
什么是生日攻擊扶平？
生日攻擊是指在網(wǎng)絡(luò)安全中利用生日現(xiàn)象帆离，找到?jīng)_突的密碼學(xué)哈希函數(shù)值，偽造報(bào)文结澄，攻擊報(bào)文身份驗(yàn)證算法的模式哥谷。（以上解釋來(lái)源于Wiki）
舉例說(shuō)明生日攻擊的形式（同樣來(lái)源于Wiki）。
艾麗斯要通過(guò)某種簽名方案對(duì)文檔的散列值簽名來(lái)簽署一個(gè)電子文檔麻献，假設(shè)散列函數(shù)產(chǎn)生一個(gè)50比特的輸出们妥，她擔(dān)心佛瑞德(Fred)哄騙她簽署另外一個(gè)合同，也許是關(guān)于佛羅里達(dá)的沼澤地勉吻。由于欺騙性的合同和正確的文檔有相同散列值的概率是1 / 250监婶，這大概是1 / 1015，因此艾麗斯感覺(jué)是安全的。佛瑞德可以嘗試許多欺騙性的合同惑惶，但是他找到有相同散列值的合同的可能性非常小煮盼，但是佛瑞德研究了生日問(wèn)題并且照著下面的方法去做，他找到了能夠?qū)ξ臋n進(jìn)行細(xì)微改變的30個(gè)位置：在一行的末尾增加一個(gè)空格带污，略微改變一個(gè)詞的拼寫(xiě)孕似，等等。在每一個(gè)位置他有兩個(gè)選擇刮刑，要么做一個(gè)細(xì)微的改變要么保留原狀，因此他能夠產(chǎn)生230個(gè)本質(zhì)上與原始文檔相同的文檔养渴，同樣他得到230個(gè)欺騙性的合同并且存儲(chǔ)它們的散列值雷绢。考慮最初的生日問(wèn)題理卑，其中r = 230并且n = 250翘紊，我們有).其中λ = 210 = 1024。因此一個(gè)好文檔的版本和一個(gè)欺騙性的合同有相同散列值的概率是藐唠。佛瑞德找到這一對(duì)匹配的文檔帆疟，并且讓艾麗斯簽署其中好的文檔版本，他計(jì)劃將她的簽名附加在欺騙性的合同之上宇立，由于它們有相同的散列值踪宠，因此簽名對(duì)于欺騙性的合同將會(huì)有效，所以佛瑞德會(huì)聲稱艾麗斯同意購(gòu)買沼澤地妈嘹。然而艾麗斯是一個(gè)英語(yǔ)教師柳琢，她堅(jiān)持從一個(gè)句子中刪除一個(gè)逗號(hào)，這樣就和佛瑞德要求她簽名的文檔有著完全不同的散列值润脸，佛瑞德又被挫敗了柬脸，這時(shí)他面臨的問(wèn)題是找到一個(gè)欺騙性的合同和新的正確文檔具有相同的散列值，這根本是不可能的毙驯。
佛瑞德的行為被稱為生日攻擊倒堕，由于生日攻擊有效地將比特?cái)?shù)對(duì)分，在實(shí)際應(yīng)用中只要你認(rèn)為有必要爆价，就可以對(duì)輸出使用兩次散列函數(shù)垦巴。對(duì)于簽名方案的生日攻擊，艾麗斯所做的是一種可取的方法允坚，在簽名電子文檔時(shí)要做一個(gè)小的改動(dòng)魂那。
看過(guò)上文之后相信大家都對(duì)生日攻擊有極大的興趣 下面詳細(xì)解釋生日攻擊的原理。
設(shè)h：X->Y是一個(gè)Hash函數(shù)稠项，X和Y都是有限的涯雅，并且|X|>=2|Y|，記|X|=m展运，|Y|=n活逆。顯然至少有n個(gè)碰撞精刷，問(wèn)題是如何去找到這些碰撞。因?yàn)槲覀冴P(guān)心的是碰撞概率的下界蔗候，所以可以假定對(duì)所有y∈Y怒允，有|h-1(y)|≈m/n。這個(gè)假定是合理的锈遥，這是因?yàn)槿绻窦痟-1(y)( y∈Y)不是近似相等的纫事，那么找到一個(gè)碰撞的概率將增大。
因?yàn)樵窦痟-1(y)( y∈Y)的個(gè)數(shù)都近似相等所灸，并且xI(1<=i<=k)是隨機(jī)選擇的丽惶，所以可將yI=h(xi)，1<=i<=k視作Y中的隨機(jī)元素（yi(1<=i<=k)未必不同）爬立。但計(jì)算k個(gè)隨機(jī)元素y1,y2, .....yk∈Y是不同的概率是一件容易的事情钾唬。依次考慮y1,y2, .....yk。y1可任意地選擇侠驯；y2 ≠y1的概率為1-1/n抡秆；y3 ≠y1 ,y2的概率為1-2/n；.....吟策；yk ≠y1,y2, .....,yk-1的概率為1-(k-1)/n儒士。
因此，沒(méi)有碰撞的概率是（1-1/n）(1-2/n）.....(1-(k-1)/n）檩坚。如果x是一個(gè)比較小的實(shí)數(shù)乍桂，那么1-x≈e-x，這個(gè)估計(jì)可由下式推出：e-x=1-x+x2/2!-x3/3!+ .....⌒Т玻現(xiàn)在估計(jì)沒(méi)有碰撞的概率（1-1/n）(1-2/n）.....(1-(k-1)/n）約為1-e-k(k-1)/2n睹酌。我們?cè)O(shè)ε是至少有一個(gè)碰撞的概率，則ε≈1-e-k(k-1)/2n剩檀，從而有k2-k≈nln(1/(1-ε)2)憋沿。去掉-k這一項(xiàng)，我們有k2≈nln(1/(1-ε)2)沪猴，即k≈sqrt(2nln(1/(1-ε)2))辐啄。
如果我們?nèi)ˇ?0.5，那么k≈1.17 sqrt(n)运嗜。這表明壶辜，僅sqrt(n)個(gè)X的隨機(jī)的元素就能以50%的概率產(chǎn)生一個(gè)碰撞。注意ε的不同選擇將導(dǎo)致一個(gè)不同的常數(shù)因子担租，但k與sqrt(n)仍成正比例砸民。
來(lái)源于生日攻擊，有另外兩種密碼攻擊方法將其改進(jìn)后而應(yīng)用廣泛：中間偶遇攻擊和修正分組攻擊。
中間相遇攻擊是生日攻擊的一種變形岭参，它不比較Hash值反惕，而是比較鏈中的中間變量。這種攻擊主要適用于攻擊具有分組鏈結(jié)構(gòu)的Hash方案演侯。中間相遇攻擊的基本原理為：將消息分成兩部分姿染，對(duì)偽造消息的第一部分從初試值開(kāi)始逐步向中間階段產(chǎn)生r1個(gè)變量；對(duì)偽造消息的第二部分從Hash結(jié)果開(kāi)始逐步退回中間階段產(chǎn)生r2個(gè)變量秒际。在中間階段有一個(gè)匹配的概率與生日攻擊成功的概率一樣悬赏。
在修正分組攻擊中，為了修正Hash結(jié)果并獲得期望的值娄徊，偽造消息和一個(gè)分組級(jí)聯(lián)舷嗡。這種攻擊通常應(yīng)用于最后一個(gè)組，因此也稱為修正最后分組攻擊嵌莉。差分分析是攻擊分組密碼的一種方法。這種攻擊也可用來(lái)攻擊某些Hash算法捻脖。
