基于BBS產(chǎn)生器和橢圓曲線的改進(jìn)RC4算法

陳 虹，劉雨朦，肖成龍，郭鵬飛，肖振久

遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島125105

1 引言

RC4（Rivest Cipher 4）算法是一種在電子信息領(lǐng)域加密的技術(shù)手段，由RSA公司在1987年提出，采用由字節(jié)流方式產(chǎn)生的密鑰流序列對信息進(jìn)行加密或解密，是密鑰長度可變的對稱流加密算法。RC4 算法廣泛應(yīng)用于SSL/TLS（Secure Sockets Layer，安全套接層/Transport Layer Security，傳輸層安全）協(xié)議、WEP（Wired Equivalent Privacy，有線等效保密）協(xié)議和WPA（Wi-Fi Protected Access，Wi-Fi保護(hù)接入）協(xié)議等多種網(wǎng)絡(luò)和數(shù)據(jù)傳輸協(xié)議。雖然RC4可以加密傳輸數(shù)據(jù)，但密鑰信息具有不變脆弱性，易被敵手猜測賦值攻擊，安全性受到威脅，因此密鑰流序列的隨機(jī)性大小和是否易破解直接影響到RC4算法的安全與否。

RC4 算法易受包括故障引入攻擊、區(qū)分攻擊和“受戒禮”攻擊在內(nèi)的多種攻擊。1994 年Finney[1]提出對RC4算法的故障引入攻擊，即假設(shè)攻擊者可獲得足夠多的PRGA（Pseudo Random Generation Algorithm，偽隨機(jī)序列生成算法）輸出序列并在RC4的運(yùn)行過程中引入錯誤，那么根據(jù)這些輸出序列就可計算出RC4的初始狀態(tài)，不需要密鑰就可以成功破解RC4 的密文。1998 年Knudsen等[2]提出狀態(tài)猜測攻擊。2000年，F(xiàn)luhrer和Mc Grew[3]通過證明RC4算法密鑰流的任意連續(xù)兩個輸出字不獨(dú)立，給出了對算法的區(qū)分攻擊。2004年P(guān)aul和Preneel[4]提出根據(jù)RC4 密鑰流前兩個輸出字節(jié)存在的偏差進(jìn)行區(qū)分攻擊[5-6]可以恢復(fù)算法的初始狀態(tài)，導(dǎo)致加密信息泄露等嚴(yán)重后果；同年文獻(xiàn)[7]提出對RC4算法的錯誤引入攻擊。2013年，Lucky13[8]針對TLS中CBC（Cipher Block Chaining，密碼分組鏈接）模式出現(xiàn)的漏洞對RC4 算法進(jìn)行攻擊。2014年，Shareef等人[9]提出水印和加密是互補(bǔ)的信息安全工具，并在文獻(xiàn)[9]中使用RC4 算法加密可變大小的圖像，完成了水印和加密算法的組合，認(rèn)為RC4 是最簡單最強(qiáng)大的流密碼；Handa[10]和他的團(tuán)隊設(shè)計了一種在并行加密大量數(shù)據(jù)時的并行執(zhí)行RC4 的方法，命名為PARC4，實(shí)驗(yàn)結(jié)果表明在實(shí)現(xiàn)并行化上效果較好，下一步他們計劃研究替代并行化相同算法的技術(shù)并測量效率；Jindal P 等人[11]則報告了幾個RC4 算法的漏洞并提出了修改的RC4算法MPC4，該算法未修改其基本結(jié)構(gòu)，僅在KSA 和PRGA 部分添加了額外層，結(jié)果表明MPC4 算法在增強(qiáng)安全性的同時產(chǎn)生幾乎相同的加密時間，但該算法對吞吐量和CPU 負(fù)載分析并沒有做出分析。2015年，Mantin I利用RC4算法存在的不變性弱密鑰[12-15]使RC4 算法陷入了“受戒禮”攻擊[15]；同年Vanhoef等在文獻(xiàn)[16]中提出一種方法，僅用9×227個密文就可在75 h 內(nèi)破解采用RC4 加密的存儲在用戶本地終端上的數(shù)據(jù)，成功率高達(dá)94%。2016年，Liu C等人[17]提出了一種基于大數(shù)據(jù)處理的新方法分析RC4 安全性的技術(shù)，通過演示如何應(yīng)用大數(shù)據(jù)分析評估著名的統(tǒng)計特性流密碼發(fā)現(xiàn)：RC4雖然仍是唯一可用的最安全的流密碼協(xié)議，但越來越多的證據(jù)表明RC4不能提供足夠大的安全邊距，RC4 算法亟待改進(jìn)。2018 年，文獻(xiàn)[18]提出了對RC4 算法的明文恢復(fù)攻擊，即高概率對經(jīng)RC4算法加密的明文的前256字節(jié)進(jìn)行恢復(fù)，使RC4算法安全性受到威脅。

本文針對RC4算法易受故障引入攻擊、區(qū)分攻擊和“受戒禮”攻擊等導(dǎo)致安全性降低的問題，提出了一種基于橢圓曲線的RC4 改進(jìn)算法，該算法以隨機(jī)置換為基礎(chǔ)，種子密鑰Key 由隨機(jī)比特產(chǎn)生器產(chǎn)生，同時利用橢圓曲線算法產(chǎn)生的隨機(jī)整數(shù)對狀態(tài)表進(jìn)行非線性運(yùn)算，從而產(chǎn)生用于加解密的流密鑰序列。該算法具有不可逆性、高安全性和隨機(jī)性，能有效抵抗故障引入攻擊、區(qū)分攻擊和“受戒禮”攻擊。

2 RC4算法簡介

RC4 算法是一種基于非線性變換的流密碼算法。從內(nèi)部結(jié)構(gòu)可分為內(nèi)部狀態(tài)S盒、狀態(tài)變換函數(shù)和輸出函數(shù)，RC4內(nèi)部狀態(tài)變化如圖1所示。

從運(yùn)算過程上可分為密鑰編制算法KSA和偽隨機(jī)序列生成算法PRGA。

（1）密鑰編制算法KSA（Key Sehedule Algorithm）：設(shè)置S盒的初始排列，用長度可變的密鑰產(chǎn)生密鑰流生成器的初始狀態(tài)。

（2）偽隨機(jī)序列生成算法PRGA（Pseudo Random Generation Algorithm）：根據(jù)初始狀態(tài)進(jìn)行非線性運(yùn)算，選取隨機(jī)元素，修改S 盒的原始排列順序，產(chǎn)生與明文或密文進(jìn)行非線性運(yùn)算的密鑰流序列。

2.1 密鑰編制算法KSA

RC4 的密鑰編制算法KSA 用于產(chǎn)生密鑰流生成器的初始狀態(tài)，步驟如下：

步驟1 隨機(jī)選取一個字長為l 的密鑰Key，初始化S盒。

步驟2 指針it遍歷S盒中的每一個位置，it每更新一次，jt就會在St-1[it]和Key的作用下產(chǎn)生一個新值。

步驟3 交換St中jt和it對應(yīng)的兩個字節(jié)，經(jīng)過N步遍歷即產(chǎn)生RC4的初始狀態(tài)S0。RC4的密鑰編制算法KSA如下所示：

其中，N=256，S盒表示算法的內(nèi)部狀態(tài)表，每一個S盒中有N 個8比特值，St表示在t 時刻的狀態(tài)表，it和jt表示t 時刻的兩個指針，指向St中的兩個元素。Key表示種子密鑰，l 為其長度，l=K 的比特數(shù)/n,n 表示算法中使用的一個字節(jié)長度，Zt表示t 時刻的密鑰流輸出字節(jié)。

圖1 RC4內(nèi)部狀態(tài)變化過程

2.2 偽隨機(jī)序列生成算法PRGA

偽隨機(jī)序列的生成原理是不斷變換S 盒中的元素位置，同時從中選取隨機(jī)元素輸出，即為偽隨機(jī)序列，構(gòu)成加解密運(yùn)算的密鑰流序列。偽隨機(jī)序列生成原理如圖2所示。

圖2 偽隨機(jī)序列生成原理

PRGA的步驟如下：

步驟1 根據(jù)KSA產(chǎn)生的初始狀態(tài)表S0，初始化指針it和jt。

步驟2 更新算法中的j，同時交換St中it和jt對應(yīng)的字節(jié)。

步驟3 偽隨機(jī)序列生成器不斷變換S 盒中字節(jié)的位置，每次改變后將S中St[it]+St[jt]位置的值輸出，即為密鑰流輸出字節(jié)，輸出的字節(jié)序列是Zt與明文異或加密，與密文異或解密。RC4的偽隨機(jī)序列生成算法PRGA如下所示：

PRGA(S0)

Initialization：

i0=0

j0=0

while（TRUE）

it=(it-1+1)mod N ；

jt=(jt-1+St-1[it])mod N ；

St[it]=St-1[jt],St[jt]=St-1[it]；

Zt=St[(St[it]+St[jt])mod N]；

output Zt

endwhile

其中，N=256,it,jt表示兩個參數(shù)，St表示在t 時刻的狀態(tài)表，Zt表示t 時刻的輸出值。加密時，將Zt與明文異或；解密時，將Zt與密文異或。

3 基于BBS和橢圓曲線的改進(jìn)RC4算法

RC4算法易受錯誤引入攻擊、區(qū)分攻擊和弱密鑰攻擊。RC4 的典型改進(jìn)算法VMPC[19]對RC4 的KSA 部分進(jìn)行改進(jìn)，可以靈活選擇算法步驟，但密鑰流序列隨機(jī)性不高導(dǎo)致安全性降低。文獻(xiàn)[20]利用223輸出值將密鑰流序列與隨機(jī)序列區(qū)分開，獲得了初始狀態(tài)并破解了文獻(xiàn)[19]的VMPC 算法。文獻(xiàn)[21]中，在PRGA 部分增加了自我檢錯步驟抵御狀態(tài)猜測攻擊和錯誤引入攻擊，但密鑰字節(jié)序列的輸出變得復(fù)雜，導(dǎo)致效率降低；文獻(xiàn)[22]對RC4 算法的密鑰流輸出序列的偏差規(guī)律進(jìn)行研究，苑超等人[18]借助該規(guī)律給出了對RC4算法的明文恢復(fù)攻擊。

本文提出的基于BBS產(chǎn)生器和橢圓曲線的RC4改進(jìn)算法同時對KSA 和PRGA 兩部分進(jìn)行改進(jìn)，以隨機(jī)置換為基礎(chǔ)，借助隨機(jī)比特產(chǎn)生器和橢圓曲線生成具有高隨機(jī)性和安全性的密鑰流序列。

3.1 改進(jìn)RC4的密鑰編制算法KSA

改進(jìn)RC4算法的KSA如下所示：

KSA(Key,S)

for i=0 to N-1,a=0 to 30

S[i]=i；

Ba=Xamod 2

Key={B30}

i0=0,j0=0；

where t=1,2,…,N

jt=jt-1+St-1[it-1]+Key[it-1mod l]；

St[it]=St-1[jt],St[jt]=St-1[it]；

it=it-1+1

利用BBS 隨機(jī)比特產(chǎn)生器產(chǎn)生比特序列作為種子密鑰Key進(jìn)行運(yùn)算，通過指針進(jìn)行N步遍歷后生成S盒的初始狀態(tài)S0，步驟如下：

步驟1 從事先準(zhǔn)備好的五位大素數(shù)庫隨機(jī)選取兩個滿足條件的素數(shù)送入BBS產(chǎn)生器進(jìn)行運(yùn)算，生成30位的隨機(jī)比特數(shù)列作為種子密鑰Key，初始化S盒。

步驟2 指針it遍歷S 盒所有位置，it每一次更新，jt都會在和Key的作用下產(chǎn)生一個新值。

步驟3 交換St中it和jt對應(yīng)的兩個字節(jié)，經(jīng)過N步遍歷即產(chǎn)生RC4的初始狀態(tài)S0。

BBS（Blum-Blum-Shub）產(chǎn)生器是已證明的密碼強(qiáng)度最強(qiáng)的偽隨機(jī)數(shù)產(chǎn)生器，它的過程如下：

步驟1 選擇兩個大素數(shù)p,q,滿足p ≡q ≡3(mod 4),令e=p×q。

步驟2 選取一個隨機(jī)數(shù)v，使得v 與e 互素。

步驟3 按以下算法產(chǎn)生比特序列{Ba}：

X0=v2mod e

for a=1 to ∞do{

Xa=

Ba=Xamod 2}

即在每次循環(huán)中取Xa的最低有效位。

3.2 改進(jìn)RC4的偽隨機(jī)序列生成算法PRGA

RC4 算法S 盒中的元素是0～28-1 的全排列，狀態(tài)表的更新通過交換S盒中的兩個元素，前后狀態(tài)變化不大；同時輸出狀態(tài)僅通過一次交換的操作來更新，易受區(qū)分攻擊。本文針對上述問題提出的基于BBS產(chǎn)生器和橢圓曲線的RC4 改進(jìn)算法的偽隨機(jī)序列生成算法PRGA如下所示：

PRGA（S）

i=0；

j=0；

while（TRUE）

i=(i+1)mod N ；

j=(j+S[i])mod N ；

out=(S[(S[i]+S[j]mod N)+g])mod 256；

S[(S[i]+S[j])mod N]=(g+S[i])mod 256；

改進(jìn)如下：

（1）采用S 盒前一個狀態(tài)j 位置值與后一個狀態(tài)i位置值的和替代當(dāng)前位置的值，更新狀態(tài)表。S盒前后狀態(tài)變化增大，同時確保狀態(tài)表產(chǎn)生的新元素不依賴S盒中的一個值或幾個值。

（2）利用橢圓曲線算法生成秘密整數(shù)g ，采用秘密整數(shù)與狀態(tài)表中j 和i 位置的值相加模256的方法生成輸出密鑰流序列，更新輸出狀態(tài)并確保了輸出序列的隨機(jī)性。

步驟1 獲得KSA 初始化的S 盒和秘密整數(shù)g ，初始化指針i,j。

步驟2 更新索引指針i 和j，輸出兩個指針對應(yīng)的值與g 的和，即(S[S[i]+S[j]mod N]+g)mod 256，其中N=2n。

步驟3 利用g 更新狀態(tài)表中的元素，即S[(S[i]+S[j])mod N]=(g+S[i])mod 256。

橢圓曲線加密算法（Elliptic Curve Cryptography，ECC）[23-24]是一類以橢圓曲線的數(shù)學(xué)理論為核心的單向不可逆公鑰密碼體制，其安全性基于離散對數(shù)問題求解的困難性，橢圓曲線密碼系統(tǒng)單位比特的高強(qiáng)度使得橢圓曲線密碼體制成為目前信息安全領(lǐng)域的核心體制。密碼中普遍采用的是有限域上的橢圓曲線，即所有系數(shù)都是某一有限域GF(m)中的元素（其中m 為一個大素數(shù)）。其中最常用的是由方程y2=x3+ax+b(a,b ∈GF(m),4a3+27b2≠0) 定義的曲線。本文取a=1,b=1 即方程y=x3+x+1 進(jìn)行運(yùn)算，其圖形是連續(xù)曲線，如圖3所示，設(shè)Gm(1,1)表示方程y=x3+x+1 所定義的橢圓曲線上的點(diǎn)集{ }

(x,y)|0 ≤x ＜m,0 ≤y ＜m,且x,y均為整數(shù) 并上無窮遠(yuǎn)點(diǎn)O（O 為加法單元，即對橢圓曲線上任一點(diǎn)G，有G+O=G）。Gm(1,1)由以下方式產(chǎn)生：

步驟1 對每一x（0 ≤x ＜m 且x 為整數(shù)），計算x3+x+1(mod m)。

圖3 橢圓曲線y2=x3+x+1 圖像

步驟2 判斷步驟1中求得的模m 下是否有平方根，如果沒有，則曲線上不存在與該x 相對應(yīng)的點(diǎn)，如果有，則求出兩個平方根（y=0 時只有一個平方根）。

按照上述方式GF(m)上的橢圓曲線y2=x3+x+1在第一象限的整數(shù)點(diǎn)加無窮遠(yuǎn)點(diǎn)O 共有1+m+個。本文從五位大素數(shù)庫中隨機(jī)取一個作為m 進(jìn)行運(yùn)算，從生成的點(diǎn)集Gm(1,1) 中去掉x=0,y=0 和無窮遠(yuǎn)點(diǎn)，在剩下的點(diǎn)集中隨機(jī)取一個坐標(biāo)點(diǎn)，這個坐標(biāo)點(diǎn)的y 坐標(biāo)的值即為所需要的秘密整數(shù)記為g，進(jìn)行接下來的運(yùn)算。

秘密整數(shù)g 是由橢圓曲線基于數(shù)學(xué)上的困難問題——離散對數(shù)分解，在有限域上產(chǎn)生單向不可逆的整數(shù)產(chǎn)生，本文采用隨機(jī)選取一個五位大素數(shù)的方法來劃分橢圓曲線的有限域，增加了秘密整數(shù)g 的隨機(jī)性和破解難度。橢圓曲線選取y=x3+x+1 進(jìn)行運(yùn)算，曲線簡單，運(yùn)算速度較快，五位大素數(shù)能夠滿足橢圓曲線有限域的劃分需求，其安全性優(yōu)于四位大素數(shù)，速度優(yōu)于六位大素數(shù)，因此，二者結(jié)合產(chǎn)生的秘密整數(shù)g 增加了隨機(jī)性和安全性。

3.3 改進(jìn)的RC4算法

基于橢圓曲線的改進(jìn)RC4算法借助BBS產(chǎn)生器生成種子密鑰Key送入S盒，在指針的作用下N 步遍歷后生成S 盒的初始狀態(tài)S0，利用橢圓曲線產(chǎn)生的整數(shù)g更新指針和狀態(tài)表中的元素，生成用于加解密的密鑰流序列。改進(jìn)RC4算法由密鑰編制算法KSA和偽隨機(jī)序列生成算法PRGA 兩部分組成，內(nèi)部狀態(tài)如圖4 所示，步驟如下：

步驟1 隨機(jī)取兩個五位大素數(shù)p,q 送入BBS產(chǎn)生器生成隨機(jī)比特數(shù)列作為種子密鑰Key。

步驟2 初始化S盒，在指針作用下遍歷S盒生成初始狀態(tài)S0。

步驟3 隨機(jī)取五位大素數(shù)m 通過橢圓曲線y2=x3+x+1 生成秘密整數(shù)g。

步驟4 初始化索引指針i,j，通過g 更新指針和狀態(tài)表元素，輸出密鑰流序列。

4 改進(jìn)RC4算法安全性分析

RC4算法密鑰流隨機(jī)性不高，易被敵手猜測賦值，S盒內(nèi)部狀態(tài)被破解等問題使RC4算法安全性降低，遭受多種攻擊。本文改進(jìn)RC4算法針對KSA和PRGA部分進(jìn)行改進(jìn)，提高了RC4 算法密鑰流的隨機(jī)性和安全性，通過理論和實(shí)驗(yàn)驗(yàn)證改進(jìn)RC4 算法可有效抵抗故障引入攻擊、區(qū)分攻擊和“受戒禮”攻擊。

圖4 改進(jìn)RC4算法的內(nèi)部狀態(tài)

4.1 密鑰流序列的隨機(jī)性

密鑰流序列的隨機(jī)性即密鑰流中比特之間的相互獨(dú)立性。隨機(jī)性越高，攻擊者對密文的統(tǒng)計分析難度越大。RC4算法的密鑰流序列的隨機(jī)性有三個影響因素：（1）S 盒中的初始值分布均勻程度；（2）索引指針i,j 分布均勻程度；（3）根據(jù)指針輸出的結(jié)果分布均勻程度。RC4算法的內(nèi)部狀態(tài)由一個包含256個字節(jié)的S盒和指針i,j 組成，輸出的密鑰流序列由S 盒中的初始值和指針i,j 決定，輸出不重復(fù)的值至多Z82個，范圍較小，密鑰流序列的隨機(jī)性較差。

（1）理論驗(yàn)證改進(jìn)RC4算法的密鑰流序列隨機(jī)性

①在KSA過程中，S盒的初始狀態(tài)由種子密鑰Key和指針確定，種子密鑰Key 通過BBS 產(chǎn)生器產(chǎn)生，具有高隨機(jī)性，在指針交換作用下S 盒中256 個元素均勻分布在Z82上。

②在PRGA 過程中，指針i 通過(i+1)mod N 進(jìn)行更新，指針j 通過j=(j+S[i])mod N 進(jìn)行更新，索引指針分布均勻；由于S[i]中的值和指針j 分別均勻分布在上，所以(S[i]+S[j])mod N 均勻分布在Z2n上。秘密整數(shù)g 通過光滑連續(xù)橢圓曲線y2=x3+x+1產(chǎn)生，分布均勻，輸出的密鑰流序列(S[(S[i]+S[j]mod N)+g])mod 256 也是均勻分布的。因此，每個元素的輸出概率是相等的，隨機(jī)性較高。

（2）實(shí)驗(yàn)驗(yàn)證改進(jìn)RC4算法的密鑰流序列隨機(jī)性

本文密鑰流序列的隨機(jī)性測試采用美國國家標(biāo)準(zhǔn)與技術(shù)研究院（National Institute of Standards and Technology，NIST）提供的NIST 統(tǒng)計測試套件[25]完成，Linux是由全球范圍的系統(tǒng)軟件設(shè)計專家在遵守通用公共許可證條款（GPL）的前提下共同開發(fā)的符合POSIX標(biāo)準(zhǔn)的類UNIX操作系統(tǒng)。Linux以其源代碼公開的特性，廣泛用于嵌入式系統(tǒng)中，已經(jīng)成為抗衡Windows 的實(shí)用操作系統(tǒng)[26-27]。本文采用Linux虛擬環(huán)境對RC4算法和改進(jìn)RC4算法的密鑰流序列進(jìn)行測試。測試中，取顯著性水平?=0.01，取256 字節(jié)內(nèi)的密鑰，分別輸出兩種算法的密鑰流序列1 048 576 bit，更換隨機(jī)密鑰，產(chǎn)生100 組序列進(jìn)行測試，密鑰流序列隨機(jī)性測試流程如圖5所示。

圖5 密鑰流序列隨機(jī)性測試流程

步驟如下：

步驟1 產(chǎn)生100 組密鑰流序列。將經(jīng)BBS 產(chǎn)生器產(chǎn)生的種子密鑰Key送入S盒生成初始狀態(tài)，在秘密整數(shù)和指針的作用下生成一組密鑰流序列，共循環(huán)產(chǎn)生100組。

步驟2 生成測試文件。將步驟1中產(chǎn)生的100組密鑰流序列以ASCII或二進(jìn)制形式保存在測試文件中。

步驟3 啟動NIST測試平臺導(dǎo)入測試文件。在Linux環(huán)境下，啟動NIST 測試平臺，配置參數(shù)，并導(dǎo)入步驟2中產(chǎn)生的測試文件。

步驟4 選擇測試項目，輸入?yún)?shù)后開始測試。在NIST平臺中選擇頻率檢驗(yàn)、游程檢驗(yàn)、序列檢驗(yàn)等16項隨機(jī)性測試項目，并輸入相關(guān)參數(shù)開始測試。

步驟5 查看測試結(jié)果進(jìn)行分析。

RC4 算法與改進(jìn)RC4 算法密鑰流序列隨機(jī)性測試結(jié)果如表1所示。

表1 改進(jìn)RC4與RC4隨機(jī)性測試結(jié)果

表1中p-value是利用卡方分布進(jìn)行統(tǒng)計分布均勻性的一種指標(biāo)，測試結(jié)果表明，RC4 算法和改進(jìn)RC4 算法的密鑰流序列雖然都能夠通過測試，但改進(jìn)RC4算法檢測結(jié)果均高于RC4 算法，特別是最重要的3 項測試[28]，頻率檢驗(yàn)、游程檢驗(yàn)和Maurer 的通用統(tǒng)計檢驗(yàn)的結(jié)果比RC4 算法分別高出0.129 18，0.107 39，0.197 64。因此，改進(jìn)后RC4 算法的密鑰流序列隨機(jī)性優(yōu)于RC4算法。這也從密碼學(xué)統(tǒng)計測試的角度驗(yàn)證了本文改進(jìn)的RC4算法的隨機(jī)性和安全性。

4.2 抵抗故障引入攻擊

假設(shè)攻擊者可以獲得足夠多的PRGA輸出序列，然后在RC4的運(yùn)行過程中引入錯誤，使其運(yùn)行進(jìn)入不可能狀態(tài)集內(nèi)，根據(jù)這些輸出序列，通過分析[21，29-30]就可計算出RC4 的初始狀態(tài)，那么RC4 的密文不需要密鑰就可以成功破解。

Finney[1]對RC4的研究提出一種狀態(tài)集：{jt=it+1,S[jt]=1},這個狀態(tài)集有個短的周期((28-1)×28=65 280)，文獻(xiàn)[1]指出在RC4算法的運(yùn)行過程中，由于i0=j0=0，根據(jù)短周期和條件jt=it+1 和S[jt]=1，認(rèn)為這種狀態(tài)是不可能發(fā)生的。Biham 等[29]在RC4 運(yùn)行過程中的某時刻引入錯誤，使該時刻的狀態(tài)進(jìn)入上面所述的不可能狀態(tài)集里，進(jìn)而利用周期性對RC4 的內(nèi)部狀態(tài)進(jìn)行分析，可推測出RC4的初始狀態(tài)。

分析方法如下：

步驟1 正常運(yùn)行RC4 算法一次，記錄足夠多的輸出密鑰字。

步驟2 重新運(yùn)行RC4 算法，在it和jt更新為it+1和jt+1且Swap(St[it+1],St[jt+1])未執(zhí)行前，向S盒的第t個位置引入錯誤，記錄第一個錯誤的輸出時刻T′。

步驟3 重新運(yùn)行RC4算法，在it-1和jt-1更新為it和jt且Swap(St-1[it],St-1[jt])未執(zhí)行前，向S 盒的第t個位置引入錯誤，記錄引入錯誤后得到的第t 個輸出密鑰字為Z′t和正確的第t 個輸出密鑰字為Zt。

步驟4 通過判斷故障引入攻擊后產(chǎn)生的錯誤密鑰字的類型，就可以成功地找出初始狀態(tài)的值。

由上述步驟可知，錯誤引入攻擊是在PRGA階段交換操作之前且S盒中的元素不變的條件下實(shí)施的，由于改進(jìn)RC4算法增加一個秘密整數(shù)g ，在每次輸出之后，利用g 對S盒中的元素重新賦值S[(S[i]+S[j])mod N]=(g+S[i])mod 256，并沒有出現(xiàn)交換操作，且在指針和秘密整數(shù)的作用下S盒中的元素是不斷被更新的，即使在運(yùn)行過程中向S盒的t 位置引入錯誤元素，也不能確定t 位置的值，因此，基于Finney狀態(tài)的故障引入攻擊方法對改進(jìn)RC4 算法無效，即改進(jìn)RC4 算法可以抵抗故障引入攻擊。

4.3 抵抗區(qū)分攻擊

區(qū)分攻擊主要通過檢查由密鑰編制算法KSA引起的偏差或影響密鑰流初始化的其他特點(diǎn)所引起的偏差進(jìn)行攻擊。

（1）抵抗內(nèi)部狀態(tài)分布均勻的區(qū)分攻擊

Mantin 和Shamir 在文獻(xiàn)[31]中提出了對RC4 算法的區(qū)分攻擊，他們假設(shè)算法在經(jīng)過KSA 部分后所得到的內(nèi)部狀態(tài)是獨(dú)立且分布均勻的，通過研究RC4密鑰流的輸出序列發(fā)現(xiàn)以下現(xiàn)象：①RC4 密鑰流的第二個輸出字值是0 的概率為2/N ，如果S0[2]=0 且S0[1]≠2，則第二個輸出值為0 的概率約為1，即P[Z2=0]≈1。②RC4密鑰流第一個輸出字為0的概率為3/N2。由于這些分析，RC4算法遭受區(qū)分攻擊，安全性受到威脅。

然而在改進(jìn)RC4 算法中，輸出值為(S[(S[i]+S[j])mod N]+g)mod 256，由指針和橢圓曲線生成的秘密整數(shù)g 共同確定，無法預(yù)知，即使S0[2]=0 且S0[1]≠2，由于g 分布均勻且是秘密數(shù)，不會出現(xiàn)概率偏差的情況，Mantin's區(qū)分攻擊所依靠的兩個概率對改進(jìn)RC4算法并不適用，無法對改進(jìn)RC4 算法進(jìn)行攻擊，即改進(jìn)RC4算法可以抵抗內(nèi)部狀態(tài)分布均勻的區(qū)分攻擊。

（2）抵抗內(nèi)部狀態(tài)分布不均的區(qū)分攻擊

文獻(xiàn)[12]證明RC4 算法在KSA 部分所得的內(nèi)部狀態(tài)分布不均，Paul和Preneel又在文獻(xiàn)[4]中指出，RC4密鑰流前兩個輸出字節(jié)存在偏差，根據(jù)這個偏差進(jìn)行區(qū)分攻擊只需要226字節(jié)就可以恢復(fù)RC4 算法的初始狀態(tài)S0。而后常亞勤又在文獻(xiàn)[6]中證明了密鑰流的第1 個輸出字節(jié)分布不均勻，將區(qū)分攻擊改進(jìn)為只要224字節(jié)就可恢復(fù)初始狀態(tài)S0。而在本文改進(jìn)RC4 算法中，KSA部分所得的內(nèi)部狀態(tài)分布均勻，不存在這些偏差，因此這些攻擊無效。

RC4算法區(qū)分攻擊的原理如下：

定理1 記P(SN[u]=v)為RC4算法在經(jīng)過KSA 后，數(shù)組SN輸入為u、輸出為v 的概率[5]，為保證數(shù)據(jù)不存在偏差，其計算條件為i=0,j=j+S[i],Swap(S[i],S[j]),則：

①當(dāng)u+1 ≤v ≤N-1 時，有：

其中：

②當(dāng)v ≤u ≤N-1 時，有：

定理2 RC4 算法密鑰流輸出的第1個字節(jié)Z1的概率為：

對于所有的d(0 ≤d ≤255)，根據(jù)定理1 和定理2 可以計算出P(Z1=d)，即理論值Pd。文獻(xiàn)[14]利用232個隨機(jī)密鑰產(chǎn)生RC4密鑰流的第一個字節(jié)進(jìn)行統(tǒng)計，得到了理論值和實(shí)驗(yàn)值結(jié)果相同。可見，對于RC4算法的區(qū)分攻擊只是時間問題，RC4 的初始狀態(tài)S0總是會被恢復(fù)的。

本文改進(jìn)的RC4 算法抵抗Paul's 區(qū)分攻擊分為兩方面：

（1）定理1 中計算P(SN[u]=v)的公式適用條件為：i=0,j=j+S[i],Swap(S[i],S[j])。本文改進(jìn)的RC4 算法中，產(chǎn)生的密鑰流序列由Key、指針S[i]、S[j]和秘密整數(shù)g 共同確定，即使?jié)M足上述條件，由于g 是由橢圓曲線產(chǎn)生的一個秘密生成的隨機(jī)數(shù)且均勻分布，不能得出前兩個輸出字節(jié)存在偏差，因此定理1 中公式對改進(jìn)RC4算法不適用。

（2）改進(jìn)RC4 算法的Key 由BBS 產(chǎn)生器產(chǎn)生，BBS的安全性基于大整數(shù)分階段困難性，產(chǎn)生的比特序列具有秘密隨機(jī)的特性，定理1、2中數(shù)組SN輸入固定值、輸出固定值的概率不能確定，第一個輸出字為一特定值的概率不能計算，定理1、2不適用于改進(jìn)RC4算法。

改進(jìn)RC4 算法的密鑰流序列的隨機(jī)性高于RC4 算法，對改進(jìn)RC4算法的區(qū)分攻擊所需要字節(jié)數(shù)高于RC4算法，耗時長于RC4算法，但密鑰流序列具有時效性，在有效時長內(nèi)區(qū)分攻擊無法對改進(jìn)RC4 算法進(jìn)行有效攻擊，因此區(qū)分攻擊的攻擊方法對改進(jìn)RC4 算法是無效的，即改進(jìn)RC4算法能夠有效抵抗內(nèi)部狀態(tài)分布不均的區(qū)分攻擊。

4.4 抵抗“受戒禮”攻擊

“受戒禮”攻擊是指利用不變性弱密鑰進(jìn)行的攻擊，攻擊者通過嗅探監(jiān)聽大量的SSL鏈接，判斷出第一個加密消息包含SSL 的完成消息和HTTP 請求的可預(yù)測的信息，當(dāng)?shù)鹊揭粋€不變性弱密鑰的鏈接時，一旦明文和這個弱密鑰進(jìn)行異或，攻擊者就可以看到生成的密文模式，異或后可獲得相應(yīng)的明文。

改進(jìn)RC4 算法中，密鑰流序列由Key、指針和秘密整數(shù)g 共同確定，秘密整數(shù)g 由橢圓曲線和五位隨機(jī)大素數(shù)確定，隨機(jī)性很高，攻擊者很難獲得可預(yù)測信息；改進(jìn)PRGA中采用S盒前一個狀態(tài)j 位置值與后一個狀態(tài)i 位置值的和替代當(dāng)前位置的值，使得S 盒前后狀態(tài)變化增大，產(chǎn)生的新元素不依賴S 盒中的一個值或幾個值，密鑰流序列變化性提高，不存在不變性弱密鑰，改進(jìn)RC4算法可有效抵抗“受戒禮”攻擊。

文獻(xiàn)[13]中分析了RC4算法中KSA的輸出值，發(fā)現(xiàn)不變性弱密鑰是一個L型圖案，這部分密鑰可能表現(xiàn)出非隨機(jī)的特性，攻擊者根據(jù)這些特性探測出完整密鑰從而進(jìn)行攻擊。通過統(tǒng)計狀態(tài)表S盒內(nèi)的元素發(fā)現(xiàn)，值X在KSA過程結(jié)束后出現(xiàn)在狀態(tài)S中的位置Y 的概率是：

其中，Y′=N-1-Y,p=1/256,q=1-p。尤其值1出現(xiàn)在0位置的概率比隨機(jī)概率1/N 高37%，值255出現(xiàn)在0位置的概率卻比隨機(jī)概率小26%。攻擊者利用這些分析結(jié)合N 輪之后的PRGA，也可以恢復(fù)密鑰。

在改進(jìn)的RC4 算法中，上述問題很難發(fā)生。滿足P[S0[Y]=X]的條件是：（1）若X=Si[1]且Y=Si[X]則i ＞1,i ≥X,i ≥X+Y ，其中i 時刻S[X]的狀態(tài)用Si[X]表示。（2）攻擊者必須知道S[1],S[X]和S[X+Y]的值。改進(jìn)RC4 算法對KSA 部分進(jìn)行改進(jìn)，利用BBS 產(chǎn)生器和兩個隨機(jī)的五位大素數(shù)生成30位比特序列作為種子密鑰Key，BBS 產(chǎn)生器密碼強(qiáng)度高，已知一個比特序列的前k 個比特，不存在實(shí)際可行的算法能以大于的概率預(yù)測下一個比特是0 還是1，即BBS 產(chǎn)生的比特序列無法預(yù)測，Key 無法被破解，i ≥1 時的下一次迭代后的狀態(tài)和S[1]的值也無法獲知，不滿足上述概率，密鑰無法恢復(fù)。所以“受戒禮”攻擊對改進(jìn)RC4算法無效，即改進(jìn)RC4算法可以抵抗“受戒禮”攻擊。

5 結(jié)束語

本文提出一種基于橢圓曲線的改進(jìn)RC4算法，該算法借助隨機(jī)大素數(shù)和隨機(jī)比特產(chǎn)生器生成種子密鑰Key，在橢圓曲線生成的秘密整數(shù)和指針的作用下進(jìn)行非線性變換最終生成了隨機(jī)性和安全性很高的密鑰流序列。該密鑰流序列由BBS產(chǎn)生器產(chǎn)生的種子Key、大素數(shù)、指針i,j 和橢圓曲線生成的秘密整數(shù)共同確定，由NIST 隨機(jī)性測試的頻率檢驗(yàn)、游程檢驗(yàn)和Maurer 等結(jié)果可知，改進(jìn)RC4 算法比RC4 算法分別高出0.129 18，0.107 39，0.197 64，因此，該算法密鑰流隨機(jī)性高于RC4算法，能夠有效防止不變性弱密鑰的產(chǎn)生，抵抗“受戒禮”攻擊。Key是一個分布均勻的隨機(jī)數(shù)，不存在偏差，能夠有效抵御區(qū)分攻擊。橢圓曲線具有單向不可逆性，秘密整數(shù)g 無法獲知，S 盒內(nèi)部狀態(tài)不斷變化且未知，能夠抵抗故障引入攻擊。安全性理論和隨機(jī)性實(shí)驗(yàn)表明改進(jìn)RC4算法的安全性和隨機(jī)性高于RC4算法。本文在狀態(tài)猜測攻擊和明文恢復(fù)攻擊等方面未進(jìn)行有效測試和驗(yàn)證，這些將是下一步研究工作的方向。