RC4算法的分析.pdf

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

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

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

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

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

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

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

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