Can you summarize the following document?
        
  舉個例子,想象一位老師問一個有30名學生的班級(n = 30)每個人的生日在哪一天(為簡便,此處省略閏年)以確定是否有兩個學生同一天生日(對應碰撞 )。從直覺角度考慮,機率看起來很小。若老師選擇特定日期(例如9月16日),則至少有一名學生在那天出生的概率是formula_4,約為7.9%。但是,與我們的直覺相反的是,至少一名學生和另外"任意"一名學生有著相同生日的概率大約為70.63%(n = 30時),從方程 formula_5中可看出。

  給定函式formula_6,攻擊目標是找到符合formula_7的兩個不同輸入formula_8。這一對formula_8被稱之為碰撞。用於找到一對碰撞的方法僅需要評估函式formula_6的隨機或偽隨機選擇的不同輸入值,直到攻擊者找到相同的結果至少兩次為止。由於生日問題,這種方法的效率不高。明確的說,若函式formula_11所擁有的formula_12的不同輸出有著相同可能性且formula_12足夠大的話,我們將期望在評估函式平均大約formula_14個不同個自變數後才能得到符合formula_7的不同一對自變數formula_16和formula_17。  思考下面一個實驗。從下列的"H"數集中我們將隨機均勻地選擇"n"個值,因此將允許重複。使"p"("n"; "H")成為此實驗中至少一個值被選擇多於一次的概率。則概率可估計為  使"n"("p"; "H")為我們將選擇的最小數值,這種情況下找到碰撞的概率至少為 "p"。通過顛倒上方的表示式,我們得到了下列估計公式:  將碰撞概率設為0.5我們將得到  使"Q"("H")成為我們在尋找首次碰撞前所期望的值的數量。此數量可通過下列公式進行估計:  舉個例子,若使用64位雜湊,則估計將有1.8 × 10個不同的輸出。若這些輸出均可能發生(理想情況下),則攻擊者“僅僅”需要約50億次嘗試(5.38 × 10)就能通過暴力攻擊生成碰撞。此值被稱為 生日界限(birthday bound)而對於"n"位密碼則需要2次。下列舉出其他例子  顯而易見,若函式的輸出不平均分佈,碰撞則可能將被更快找到。雜湊函式的“平衡”概念量化了其能抵禦生日攻擊(攻擊平均的金鑰分佈)的次數。然而,確定雜湊函式的平衡將需要計算所有輸入,因此這種方法對於諸如MD及SHA系的流行雜湊函式是不切實際的。 當計算formula_22中的子表示式formula_23翻譯到常見的程式語言如codice_1下,公式由於有效位丟失對較小的formula_24的計算精度不高。例如,當codice_2(如C99中一樣)可用時,應直接使用可達到相同效果的表示式codice_3。 If this is not done, the first column of the above table is computed as zero, and several items in the second column do not have even one correct significant digit.

  下列是能準確生成上方表格中大多數數值的Python函式:  from math import log1p, sqrt  def birthday(probability_exponent, bits):  若程式碼儲存在命名為codice_4的檔案中,您可和下面的例子一樣互動執行此程式:

  一項經驗法則可適用於此關係中的心算流程  可改寫為  或  此公式在概率小於等於0.5時有效。  此近似方案在使用指數時可輕易使用。例如,假設您正構建32位雜湊(formula_28)且希望碰撞概率為100萬分之一(formula_29),則最多我們需要多少份文件?  即與正確答案93次近似。

  數碼簽章可對生日攻擊十分敏感。設想一條被首次計算formula_31(formula_6為密碼雜湊函式)所簽名的資訊,且隨後又使用了一些金鑰來簽名formula_31。假設愛麗絲與鮑伯牽涉到簽名詐騙合同。馬洛裡準備了一份正常合同formula_34和一份偽造合同formula_35。她隨後發現formula_34所在的位置數可在不改變原意的情況下(如插入逗號、清空行、在句後增加一兩個空格、替換同義詞等等)被更改。通過結合這些更改,她可新建諸多formula_34的變體且均為正常合同。  相似情況下,馬洛裡也為偽造合同formula_35新建了諸多變體。她隨後應用雜湊函式到所有變體直到她找到與正常合同有著相同雜湊值formula_39的偽造合同位置。她隨後將正常合同帶給鮑勃簽名。在鮑勃簽名完後,馬洛裡將簽名取下並依附到偽造簽名上。此簽名“證實了”鮑勃簽署了偽造合同。  此例中,攻擊概率與原始的生日問題稍有不同,因為馬洛裡將在尋找兩份具有相同雜湊的正常合同與偽造合同時將一無所獲。馬洛裡的策略是生成一份偽造和一份正常的合同。生日問題公式適用於formula_40為合同對數的情況下。但馬洛裡所生成的雜湊數實際上為formula_41。  為避免這種攻擊,用於簽名方案的雜湊函式的輸出長度應夠大以從計算角度防止生日攻擊。換言之,位數應為防止普通暴力破解所需位數的兩倍。  除了使用更大的位數長度外,簽名者(鮑勃)可以在簽名前做出一些隨機且無害的更改,並且在自己的手上留下一份合同副本以在法庭上展示出他的簽名與正常合同上的匹配,而不匹配偽造合同。  離散對數 Pollard Rho 演算法是一項使用生日攻擊以計算離散對數的演算法。
生日攻擊是一種密碼學攻擊手段,所利用的是概率論中生日問題的數學原理。這種攻擊手段可用於濫用兩個或多個集團之間的通訊。此攻擊依賴於在隨機攻擊中的高碰撞概率和固定置換次數(鴿巢原理)。使用生日攻擊,攻擊者可在formula_1中找到雜湊函式碰撞,formula_2為原像抗性安全性。然而,量子計算機可在formula_3內進行生日攻擊(雖然飽受爭論)。