碰撞攻擊

碰撞攻擊分為生日攻擊和中間相遇攻擊。①生日攻擊。目標是從N個點X1 ，X2，…，Xn中找出2個相等的點。其方法是隨機從N個點中選取n個點，通過對這n個點的存儲和按大小排序，找出其中相等的點。算法的計算量近似為n，當任意2個點相等的概率都是1/n時，選擇n=(2n)1/2時算法成功的概率近似為0.632，存儲量和計算量都是(2n)1/2，效率最高。②中間相遇攻擊。目標是採取隨機從N元集合S中選取1個m元子集和1個n元子集的方法，找出2個集合的1個交點。其方法是先隨機選取集合S的m個不同點，並將它們按大小排序和存儲，然後再隨機選1個點，並檢查它是否為已存儲的點。若是，算法成功；若不是，繼續隨機選新的點並檢查它是不是已存儲的點。當隨機選N個點後仍沒有找到所要的點，算法以失敗結束。這一算法的計算量近似為m+n，當S中任意2點相等的概率都是1/n 時，這2個子集交集不空的概率近似為1-emn/N。一般選擇m=n=N1/2，算法成功的概率近似為0.632，存儲量和計算量都是N1/2，效率最高。碰撞攻擊大大降低了窮舉攻擊的計算量，可解決許多具體的密碼分析問題。碰撞攻擊還可與分割攻擊等密碼分析方法結合，降低破譯密碼的計算量。

發佈者：中國軍事百科全書編審室 ^[1]