RC4算法的分析.pdf

1、1987年，RonRivest為RSA數(shù)據(jù)安全公司設(shè)計了RC4算法，該算法與眾多流密碼的算法的設(shè)計思想不同，安全性高，而且更易于軟件實現(xiàn)，正是由于該算法具有了線性反饋移位寄存器等其它流密碼算法所不具有的特性，因而得到非常廣泛的應用.在國際著名的安全協(xié)議標準SSL中，該算法用來確?；ヂ?lián)網(wǎng)傳輸中的保密性，而且它也被集成于MicrosoftWindows，LotusNotes，AppleAOCE，OracleSecureSQL等，另外，該算法

2、也被選為蜂窩數(shù)字數(shù)據(jù)包規(guī)范的一部分. 在得到廣泛應用的同時，該算法的安全性分析也成為一個重要的研究方向.自從該算法被公開之日起，針對該算法的很多攻擊方法也應運而生.包括針對該算法PRGA過程的攻擊，弱密鑰方案，偽隨機數(shù)的隨機性分析等等，詳見§1.3節(jié)研究進展.目前很多人對PRGA過程進行了分析[13、14、24]，其中比較著名的就是Knudsen等人在1998年公布的攻擊方法[13]，雖然該方法在不知道初始內(nèi)部狀態(tài)時的復雜度很高

3、，但是在攻擊者得到一部分內(nèi)部狀態(tài)的信息時卻變得非常有效. Knudsen等人研究發(fā)現(xiàn)，該算法的攻擊復雜度不僅取決于已知初始內(nèi)部狀態(tài)中的信息的多少，還取決于這些信息的分布狀況.但是這些已知信息的多少和分布狀況如何決定復雜度卻是一個尚未解決的問題.本文正是針對這個問題而進行的一些分析. 本文共分兩章. 在第一章中，作者首先在§1.1中詳細介紹了RC4算法的背景，包括密碼學中的一些概念，流密碼和分組密碼的關(guān)系，流密碼的

4、加密過程、分類、隨機性，RC4算法在流密碼中的地位等；然后作者在§1.2中對RC4算法的過程進行了描述，主要是該算法的兩個部分KSA和PRGA的操作過程；最后在§1.3中作者對RC4算法近年來的研究進展就行了簡單的描述. 在第二章中，作者在§2.1首先引入了Knudsen等人1998年提出的攻擊方法，該方法分三步來進行： Step1：檢查St-1[i，]是否已被賦值過(a)如果有值，跳到step2. (b)否則，

5、用2n-at個未出現(xiàn)的值逐一對St-1[it]賦值，更新at，然后跳到step2. Step2：檢查Zt是否等于at中的某個值，即是否在內(nèi)部狀態(tài)中已知的值中(a)如果等于，我們可以計算出St[jt].如果此時不出現(xiàn)矛盾，t+1，跳到step1. (b)如果不等于，跳到step3. Step3：檢查St-1[jt]是否已經(jīng)被賦值過(a)如果沒有，逐一對St-1[jt]賦值，更新at.接著檢查是否出現(xiàn)矛盾.如果沒有矛

6、盾，t+1，然后跳到step1. 然后作者詳細介紹了其對應的復雜度的計算公式，由此可以得到已知初始內(nèi)部狀態(tài)部分隨機值的復雜度.在§2.2中作者針對初始內(nèi)部狀態(tài)的不同取值類型進行了深入的分析.首先定義了三種基本類型： 定義2.1如果一個初始狀態(tài)中已知連續(xù)a個位置的值是已知的，并且指針it正好指向這a個位置中的某一個，我們把這種內(nèi)部狀態(tài)定義為類型Ⅰ；如果內(nèi)部狀態(tài)中連續(xù)a+a'個值中只有一個未知的間斷點，其他均為已知，我們把這

7、種初始狀態(tài)記為類型Ⅱ；如果已知內(nèi)部狀態(tài)中兩段連續(xù)的值，分別為a和a'個，這兩段值中間有a"個連續(xù)的未知位置，那么我們稱這種初始狀態(tài)為類型Ⅲ. 針對這三類基本類型，作者提出了新的研究方法，并得出了一些結(jié)論：推論2.1類型Ⅰ的復雜度(→)某個內(nèi)部狀態(tài)的復雜度，即等價于已知a+△a個值時初始狀態(tài)對應的復雜度. 推論2.2 類型Ⅱ以Pr=a∑t=1(1/2n+at/22n-at/23n)的概率(→)complex*(a+

8、a',a+a'+1)，此處at表示初始指針到達it時所有能夠得到的所有已知值的總數(shù)，a1=a+a'. 推論2.3如果t=a+1時的正確值能夠得到，則，類型Ⅱ的平均復雜度(→)complex*(a+a'+1，a+a'+1)+(1+2n-a-a')/2，此處(1+2n-a-a')/2表示在t=a+1處的平均賦值次數(shù). 推論2.4類型Ⅲ以a+a"-1Πr=a(r∑t=1Prt)的概率(→)complex*(a+a',a+a'+