基于橢圓曲線的改進RC4算法

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

摘 要：針對流密碼（RC4）算法存在不變性弱密鑰、密鑰流序列隨機性不高和算法初始狀態(tài)可以被破解等問題，提出一種基于橢圓曲線的RC4改進算法。該算法利用橢圓曲線、哈希函數(shù)和偽隨機數(shù)產生器生成初始密鑰 Key ，在S盒和指針的作用下進行非線性變換最終生成具有高隨機性的密鑰流序列。美國國家標準與技術研究院（NIST）隨機性測試結果表明，改進算法的頻率檢驗、游程檢驗和Maurer指標比原RC4算法分別高出0.13893， 0.13081和0.232050，能有效防止不變性弱密鑰的產生，抵抗“受戒禮”攻擊; Key 初始密鑰是一個分布均勻的隨機數(shù)，不存在偏差，能夠有效抵御區(qū)分攻擊;橢圓曲線、哈希函數(shù)具有單向不可逆性，偽隨機數(shù)產生器具有高密碼強度， Key 初始密鑰猜測賦值困難，不易破解，能夠抵抗狀態(tài)猜測攻擊。理論和實驗結果表明改進RC4算法的隨機性和安全性高于原RC4算法。

關鍵詞：流密碼（RC4）算法;密鑰流序列;橢圓曲線;哈希函數(shù);隨機性

中圖分類號：?TP309.7; TP393.08

文獻標志碼：A

Improved RC4 algorithm based on elliptic curve

CHEN Hong， LIU Yumeng*， XIAO Chenglong， GUO Pengfei， XIAO Zhenjiu

School of Software， Liaoning Technical University， Huludao Liaoning 125105， China

Abstract：?For the problem that the Rivest Cipher 4 （RC4） algorithm has invariant weak key， the randomness of the key stream sequence is not high and the initial state of the algorithm can be cracked， an improved RC4 algorithm based on elliptic curve was proposed. In the algorithm， the initial key? Key? was generated by using elliptic curve， Hash function and pseudo-random number generator， and a nonlinear transformation was performed under the action of the S-box and the pointer to finally generate a key stream sequence with high randomness. The randomness test carried out by National Institute of Standards and Technology （NIST） shows that the frequency test， run test and Maurer are 0.13893， 0.13081， and 0.232050 respectively higher than those of the original RC4 algorithm， which can effectively prevent the generation of invariant weak keys and resist the "sentence" attack.? Key The initial key is a uniformly distributed random number without deviation， which can effectively resist the distinguishing attack. The elliptic curve and Hash function have one-way irreversibility， the pseudo-random number generator has high password strength，? Key the initial key guess is difficult to assign and is not easy to crack， which can resist the state guessing attack. Theoretical and experimental results show that the improved RC4 algorithm is more random and safe than the original RC4 algorithm.

Key words：?Rivest Cipher 4 （RC4） algorithm; key stream sequence; elliptic curve; Hash function; randomness

0 引言

流密碼（Rivest Cipher 4， RC4）加密算法是1987年RSA（Rivest-Shamir-Adleman）公司提出的，它用字節(jié)流方式產生的密鑰依次加密明文中的每個字節(jié)，解密時依次對密文中的每個字節(jié)進行解密，是密鑰長度可變的對稱流加密算法。RC4算法廣泛應用于安全套接層（Secure Sockets Layer，SSL）協(xié)議、傳輸層安全（Transport Layer Security，TLS）協(xié)議、有線等效保密（Wired Equivalent Privacy，WEP）協(xié)議和Wi-Fi保護接入（Wi-Fi Protected Access，WPA）協(xié)議等多種網(wǎng)絡和數(shù)據(jù)傳輸協(xié)議。雖然RC4可以加密傳輸數(shù)據(jù)，但密鑰信息存在不變脆弱性，易被敵手猜測攻擊，安全性受到威脅，因此密鑰的健壯性直接影響到RC4算法的安全。

RC4算法易受的攻擊主要包括區(qū)分攻擊、弱密鑰攻擊和狀態(tài)猜測攻擊等。1994年，文獻[1]提出了對RC4算法的“故障引入攻擊”;1998年，文獻[2]提出狀態(tài)猜測攻擊，即假設攻擊者能夠獲得一段足夠多的偽隨機序列生成算法（Pseudo Random Generation Algorithm，PRGA）輸出值并計算出初始狀態(tài)，則不需要密鑰序列即可繼續(xù)產生輸出值，從而破解RC4算法;文獻[3-6]證明了RC4算法密鑰流的任意連續(xù)兩個輸出字可以不獨立或存在偏差，根據(jù)這個偏差進行區(qū)分攻擊，可以恢復RC4算法的初始狀態(tài)，導致加密信息泄露等嚴重后果;文獻[7]提出了對RC4算法的錯誤引入攻擊;文獻[8-11]利用RC4算法存在的不變性弱密鑰問題，讓RC4算法陷入了“受戒禮”攻擊[11];文獻[12]通過對經(jīng)不同種子密鑰長度的RC4算法加密的明文的前256Byte進行恢復，提出了對RC4算法的明文恢復攻擊。RC4算法存在的不安全問題引起了人們重視，針對以上對RC4算法的攻擊已經(jīng)提出了不少的改進算法，但改進算法仍存在一定的缺陷。如文獻[13]中，為了抵御狀態(tài)猜測攻擊和錯誤引入攻擊，在PRGA部分增加了自我檢錯步驟，但密鑰字節(jié)序列的輸出變得復雜，效率有所降低;文獻[14]對RC4算法中PRGA階段S表的元素交換進行改進;文獻[15]提出的可變可修改的置換組合（Variably Modified Permutation Composition， VMPC）算法是RC4的典型改進算法，它對RC4的密鑰編制算法（Key Sehedule Algorithm， KSA）部分進行了改進，可以靈活選擇算法步驟，但其狀態(tài)表S盒取值范圍很?。?～28-1），隨機性不夠高導致安全性降低;文獻[16]對文獻[15]的VMPC算法進行了破解，利用輸出值將密鑰流序列與隨機序列區(qū)分開，獲得了初始狀態(tài)，破解了VMPC算法。

本文針對RC4算法易受區(qū)分攻擊、“受戒禮”攻擊和狀態(tài)猜測攻擊等導致安全性降低的問題，提出了一種基于橢圓曲線的RC4改進算法。該改進算法基于橢圓曲線算法產生隨機整數(shù)，借助哈希函數(shù)擴展位數(shù)輸入到偽隨機數(shù)產生器中生成偽隨機數(shù)，并在狀態(tài)表中進行非線性變換，從而產生用于加解密的流密鑰序列。該改進算法具有不可逆性、高安全性和隨機性，能有效抵抗區(qū)分攻擊、“受戒禮”攻擊和狀態(tài)猜測攻擊。

1 RC4算法

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

從運算過程上可分為密鑰編制算法KSA和偽隨機序列生成算法PRGA。

1）密鑰編制算法KSA：設置S盒的初始排列，用可變長度的密鑰生成密鑰流生成器的初始狀態(tài)。

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

1.1 密鑰編制算法KSA

RC4的密鑰編制算法KSA用于產生密鑰流生成器的初始狀態(tài)[17-18]，步驟如下：

步驟1? 隨機選取一個字長為l的密鑰Key，初始化S盒;

步驟2? 用指針 i t搜索S盒中的每一個位置， i t每更新一次， j t由St-1[ i t]和Key共同計算生成下一個值;

步驟3? 將St中的 j t和 i t交換。

RC4初始狀態(tài)表S0由上面KSA經(jīng)過N步迭代后生成。RC4的KSA偽代碼如下：

作者說明：算法內部運行過程中，將指針所指位置的值互換，所以指針除了代表該位置，還包括該位置所表示的值，可以看作有大小有方向的量。

程序前

KSA：S0[i]=i（i=0，1，…，2n-1），? i 0=0，? j 0=0;

i t= i t-1+1;

j t= j t-1+St-1[ i t-1]+K[ i t-1 mod l];

St[ i t]=St-1[ j t]， S[ j t]=St-1[ i t]， t=1，2，…，N-1

程序后

其中：n表示算法中使用的一個字節(jié)長度;N表示長度為n的一個字節(jié)能顯示值的總量，即N=2n; i t和 j t表示兩個參數(shù);K表示種子密鑰，l為其長度，l=K的比特數(shù)/n。

1.2 偽隨機序列生成算法PRGA

PRGA生成的偽隨機序列構成加解密運算的密鑰流序列。偽隨機序列生成原理如圖2所示。

PRGA[17-18]的步驟如下：

步驟1? 初始化。指針 i t和 j t的初始值在KSA產生的S0中選取。

步驟2? 變換S盒。改變該算法中的j值，并將St中的 i t和 j t進行交換。

步驟3? 生成偽隨機序列Z。連續(xù)改變S盒中各個字節(jié)的位置，并輸出變換后的St[ i t]+St[ j t]位置的值，該輸出字節(jié)序列是偽隨機序列，也是密鑰流序列，記為Z={Zt}∞t=0，加密時，用Zt與明文進行異或運算，解密時同樣用Zt與密文進行異或運算。

RC4的PRGA偽代碼如下：

程序前

PRGA： i 0=0，? j 0=0; i t= i t-1+1;

St-1[ j t]= j t-1+St-1[ i t];

St[ i t]=St-1[ j t]， St[ j t]=St-1[ i t];

Zt=St[St[ i t]+St[ j t]]， t=1，2，…，N-1

程序后

其中： i t，? j t表示兩個位置參數(shù)，Zt表示t時刻的輸出值。加密時，將Zt與明文異或;解密時，將Zt與密文異或。

2 改進的RC4算法

針對原有RC4算法密鑰流序列隨機性不高、易受區(qū)分攻擊、“受戒禮”攻擊和狀態(tài)猜測攻擊等問題，提出了基于橢圓曲線的改進RC4算法。該改進算法利用橢圓曲線、MD5哈希算法和偽隨機數(shù)產生器，在隨機性、安全性等方面有較大的提升。橢圓曲線固有的數(shù)學困難問題、不易破解，MD5哈希算法存在單向安全性以及偽隨機數(shù)產生器的隨機性，增加了RC4算法密鑰流序列的隨機性，增強了改進算法的安全性，可以有效抵抗區(qū)分攻擊、“受戒禮”攻擊和狀態(tài)猜測攻擊。

基于橢圓曲線的改進RC4算法利用橢圓曲線產生單向不可逆的整數(shù)，經(jīng)MD5哈希算法生成消息摘要后送入偽隨機數(shù)產生器生成偽隨機數(shù)，在S盒中進行非線性變換最后生成用于加解密的密鑰流序列。

改進RC4算法由密鑰編制算法KSA和偽隨機序列生成算法PRGA兩部分組成，流程如圖3所示，步驟如下：

步驟1? 產生隨機整數(shù)e。隨機取五位大素數(shù)p通過橢圓曲線y2=x3+x+1產生隨機整數(shù)e。

步驟2? 變換隨機整數(shù)e。借助MD5哈希算法將隨機整數(shù)e以128bit輸出。

步驟3? 產生密鑰Key。 從產生的128bit數(shù)據(jù)中選取一個64bit的隨機數(shù)送入偽隨機數(shù)產生器，輸出新的64bit的偽隨機數(shù)Ri作為密鑰Key。

步驟4? 初始化S盒。N步遍歷后產生RC4的初始狀態(tài)S0。根據(jù)初始狀態(tài)表，初始化指針 i t和 j t。

步驟5? 產生密鑰流序列。更新指針 i t和 j t進行非線性變換，不斷改變S盒中元素的位置，每次改變后將St[ i t]+St[ j t]位置的值Z輸出，即偽隨機序列，也稱密鑰流序列。

算法的時間復雜度為O（n2）。

3 改進RC4的密鑰編制算法KSA

橢圓曲線加密（Elliptic Curve Cryptography， ECC）算法[19-20]是一類以橢圓曲線的數(shù)學理論為核心的單向不可逆公鑰密碼體制，優(yōu)點是密鑰短、安全性高且存儲空間小，其安全性主要依據(jù)由其定義的某類橢圓曲線點群上的離散對數(shù)問題求解的困難性，橢圓曲線密碼系統(tǒng)單位比特的高強度使得橢圓曲線密碼體制成為目前信息安全領域的核心體制。本文提出的基于橢圓曲線的RC4改進算法的密鑰編制算法KSA分為以下3個部分。

3.1 利用橢圓曲線生成隨機整數(shù)

密碼學中普遍采用的是有限域上的橢圓曲線，即所有系數(shù)都是某一有限域GF（p）中的元素（其中p為一個大素數(shù)）。其中最常用的是由方程

y2=x3+ax+b （a，b∈GF（p），4a3+27b2≠0）

定義的曲線。本文取a=1，b=1，即方程y2=x3+x+1進行運算，其圖形是連續(xù)曲線，如圖4所示，設EP（1，1）表示方程y2=x3+x+1所定義的橢圓曲線上的點集{（x，y） | 0≤x

步驟1? 對每一x（0≤x

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

按照上述方式，GF（p）上的橢圓曲線y2=x3+x+1在第一象限的整數(shù)點加無窮遠點O共有1+p+∑ x∈GF（p）?? x3+x+1 p? 個。本文取p為五位隨機大素數(shù)進行運算，從生成的點集EP（1，1）中去掉x=0，y=0和無窮遠點，在剩下的點集中隨機取一個坐標點，這個坐標點的y坐標的值即為所需要的整數(shù)，記為e，進行接下來的運算。

3.2 利用哈希函數(shù)生成消息摘要

哈希函數(shù)是密碼學的重要內容，將任意長的消息M映射為較短的、固定長度的一個值H（M），即消息摘要（又稱為哈希碼）。哈希函數(shù)滿足單向性的特點，即它只可從明文得到密文而不可從密文獲得明文，只有加密過程，不能解密[21]。

本文采用MD5哈希算法對數(shù)據(jù)進行處理，MD5采用迭代型哈希函數(shù)結構，算法框圖如圖5所示，算法的輸入為任意長消息（圖中為Kbit），實際運行時將輸入3.1節(jié)中生成的整數(shù)e分成512bit長的分組，輸出為128bit的消息摘要。

由圖5可知，MD5算法對輸入數(shù)據(jù)的處理過程如下：

步驟1? 對輸入的Kbit消息進行填充，使得e的比特長在模512下為448，留出的64bit給步驟2使用。

小端方式：指將數(shù)據(jù)的低位放在內存的低地址上，而數(shù)據(jù)的高位放在內存的高地址上。

步驟2? 附加消息的長度，用步驟1留出的64bit以小端方式表示消息被填充前的長度，如果消息長大于264，則以264為模數(shù)取模。

步驟3? 對MD5緩沖區(qū)初始化。

步驟4? 以分組為單位對消息進行處理。

步驟5? 輸出。消息的L個分組都被處理完后，最后一個HMD5的輸出即為需要的128bit的消息摘要。

3.3 利用偽隨機數(shù)產生器產生偽隨機數(shù)

從3.2節(jié)產生的128bit的消息摘要中選取64bit的隨機數(shù)n送入偽隨機數(shù)產生器，輸出新的64bit的偽隨機數(shù)Ri送入S盒，經(jīng)過N步遍歷生成RC4的初始狀態(tài)S0。由圖6產生器的框圖可知，產生器的運行分為3個部分：

步驟1? 輸入兩個64bit的偽隨機數(shù)，其中DTi表示當前的日期和時間，每產生一個數(shù)Ri后，DTi都更新一次;Vi是產生第i個隨機數(shù)時的種子，初值可以任意設定，這里設為隨機數(shù)n，以后每次自動更新。

步驟2? 密鑰。產生器用了3次三重DES加密，3次加密使用相同的兩個56bit的密鑰K1和K2，這兩個密鑰必須保密且不能用作他用。

步驟3 ?輸出。輸出為一個64bit的偽隨機數(shù)Ri和一個64bit的新種子Vi+1，其中：

Ri=EDEK1，K2[Vi⊕EDEK1，K2[DTi]]

Vi+1=EDEK1，K2[Ri⊕EDEK1，K2[DTi]]

EDE表示兩個密鑰的三重DES。

4 改進RC4算法安全性分析

密鑰流序列的隨機性是指密鑰流中各比特之間具有的獨立程度。提高密鑰流的獨立性，將會增大密文的統(tǒng)計分析的難度，攻擊者難以破解。因此，提高密鑰流的獨立性（即隨機性）是衡量流密碼安全性的重要指標之一。RC4算法近年頻遭攻擊，其中最典型的包括區(qū)分攻擊、“受戒禮”攻擊和狀態(tài)猜測攻擊，本文針對這三類攻擊對改進RC4算法進行安全性分析。

索引指針只表示位置，不作為向量，it即表示位置又表示值時才視為向量

4.1 密鑰流序列的隨機性

影響RC4算法的密鑰流序列隨機性的三個因素包括：1）S盒中的初始值分布均勻程度;2）索引指針i， j分布均勻程度;3）根據(jù)指針輸出的結果分布均勻程度。RC4算法的內部狀態(tài)由一個包含256Byte的S盒和指針i， j組成，輸出的密鑰流序列由S盒中的初始值和指針i， j共同確定，因此輸出不重復的值至多Z82個，范圍較小，密鑰流序列的隨機性較差。

1）理論驗證改進RC4算法的密鑰流序列隨機性。

RC4算法的S盒中的初始值由初始密鑰Key和指針確定，改進RC4算法中，密鑰Key的產生由以下三部分確定：

①橢圓曲線y2=x3+x+1。由圖4可知該曲線平滑連續(xù)，函數(shù)值分布均勻。

②MD5哈希算法。該算法采用迭代型哈希函數(shù)結構，將輸入的消息填充后劃分為一系列512bit長的分組Y0，Y1，…，YL-1對消息進行處理，每一分組Yq（q=0，1，…，L-1）都經(jīng)壓縮函數(shù)HMD5處理，算法采用128bit長的緩沖區(qū)存儲中間結果和最終哈希值，使得消息具有安全性且分布均勻。

③偽隨機數(shù)產生器。哈希函數(shù)生成的均勻分布的128bit數(shù)據(jù)隨機取64bit送入偽隨機數(shù)生成器，產生器采用112bit長的密鑰和3次三重DES加密，生成的隨機數(shù)Ri隨機性很高，送入S盒后進行非線性變換，使得S盒初始值分布均勻。而在偽隨機序列生成過程中，由于S盒中256個元素是均勻分布的，S[i]中的值和指針i， j分布均勻，所以算法的輸出密鑰流序列（S[i]+S[j]） mod 256也分布均勻。

內部狀態(tài)分布均勻，產生的值均為隨機數(shù)，改進算法的密鑰流序列隨機性高于RC4算法。

2）實驗驗證改進RC4算法的密鑰流序列隨機性。

本文密鑰流序列的隨機性測試采用美國國家標準與技術研究院（National Institute of Standards and Technology，NIST）提供的NIST統(tǒng)計測試套件[22]完成，Linux操作系統(tǒng)因其完備的功能、強大的性能、良好的兼容性以及開源免費等優(yōu)點，本文采用Linux虛擬環(huán)境對RC4算法和改進RC4算法的密鑰流序列進行測試[23]。測試中，取顯著性水平α=0.01，取256Byte內的密鑰，分別輸出兩種算法的密鑰流序列1048576bit，更換隨機密鑰，產生100 組序列進行測試，密鑰流序列隨機性測試流程如圖7所示。步驟如下：

步驟1? 產生100組密鑰流序列。將橢圓曲線、MD5算法和偽隨機數(shù)產生器產生的隨機數(shù)經(jīng)過S盒變換生成一組密鑰流序列，共循環(huán)產生100組。

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

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

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

步驟5? 查看測試結果進行分析。

RC4算法與改進RC4算法密鑰流序列隨機性測試結果如表1所示。

表1中p-value是利用卡方分布進行統(tǒng)計分布均勻性的一種指標，測試結果表明，RC4算法和改進RC4算法的密鑰流序列雖然都能夠通過測試，但改進RC4算法檢測結果均高于RC4算法，特別是最重要的三項測試[24]：頻率檢驗、游程檢驗和Maurer的通用統(tǒng)計檢驗的結果比RC4算法分別高出0.13893，0.13081，0.232050。因此，本文改進的RC4算法產生的密鑰流序列比原RC4算法的獨立性高，隨機性和安全性均優(yōu)于RC4算法。

4.2 抵抗區(qū)分攻擊

由于KSA生成的密鑰流序列可能存在偏差，區(qū)分攻擊就是指對該偏差進行的攻擊。

文獻[8]證明了RC4算法在KSA部分所得的內部狀態(tài)分布不均，文獻[4]證明了根據(jù)RC4密鑰流前兩個輸出字節(jié)存在的偏差進行區(qū)分攻擊只需要226Byte即可恢復RC4算法的初始狀態(tài)S0。文獻[6]證明了密鑰流的第1個輸出字節(jié)分布不均勻，區(qū)分攻擊只要224Byte即可恢復初始狀態(tài)S0。而在本文的改進RC4算法中，KSA部分所得的內部狀態(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]）：

1）當u+1≤v≤N-1時，有：

P（SN[u]=v）=pu，vv+1· ?N-1 N? N-1-v+

（1-pu，vv+1）· 1 N ·?? N-1 N? v-? N-1 N? N-1

其中：

pu，vv+1=

2（N-1） N2 ，?????? u=0，v=1

1 N ·? N-1 N? v-u+ 1 N ·? N-1 N? v- 1 N2 ·? N-1 N? 2v-u-1， 其他

2）當v≤u≤N-1時，有：

P（SN[u]=v）= 1 N · ?N-1 N? N-1-u+??? 1 N ·?? N-1 N? v+1- ?N-1 N? N+v+u

設P（SN[0]=x）為數(shù)組SN輸入為0輸出為x的概率，P（SN[x]=y）為數(shù)組SN輸入為x、輸出為y的概率，P（SN[z]=m）為數(shù)組SN輸入為z、輸出為m的概率，其中，z=（x+y） mod 256，則可得密鑰流輸出的第1 個密鑰字為一特定值的概率。

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

P（Z1=m）=∑ x ∑ y P（SN[0]=x）·? P（SN[x]=y）·P（SN[（x+y） mod 256]=m）

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

本文改進的RC4算法抵抗區(qū)分攻擊分為兩方面：

1）本文改進的RC4算法中，產生的密鑰流序列由Key、指針S[i]、S[j]共同確定，由于Key是一個秘密生成的隨機數(shù)且分布均勻，前兩個輸出字節(jié)不存在偏差問題，因此不存在定理1中計算條件問題;另外，改進RC4算法的Key具有秘密隨機的特性，定理1、2中數(shù)組SN輸入固定值、輸出固定值的概率不能確定，第一個輸出字為一特定值的概率不能計算，定理1、2不適用于改進RC4算法。

2）改進RC4算法的密鑰流序列的隨機性高于RC4算法，對改進RC4算法的區(qū)分攻擊所需要字節(jié)數(shù)高于RC4算法，耗時長于RC4算法，但密鑰流序列具有時效性，在有效時長內區(qū)分攻擊無法對改進RC4算法進行有效攻擊，因此區(qū)分攻擊的攻擊方法對改進RC4算法是無效的，即改進RC4算法能夠有效抵抗區(qū)分攻擊。

4.3 抵抗“受戒禮”攻擊

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

改進RC4算法中，密鑰流序列由Key和指針共同確定。其中，Key由橢圓曲線、哈希函數(shù)和偽隨機數(shù)產生器共同確定。橢圓曲線根據(jù)隨機素數(shù)生成的隨機整數(shù)送入MD5哈希算法后隨機取64bit作為產生器的第一個種子，產生器的兩個輸入為當前的日期、時間和算法上次產生的新種子，密鑰流序列不斷變化，信息隨機性變換，攻擊者很難獲得可預測信息，不存在不變性弱密鑰，改進RC4算法可有效抵抗“受戒禮”攻擊。

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

P[S0[Y]=X]= p（qX+qY′-qX+Y′），? X≤Yp（pX+qY′）， X>Y

其中：Y′=N-1-Y，p=1/256，q=1-p。尤其是值1和值255出現(xiàn)在0位置的概率分別比隨機概率1/N高37%、低26%。攻擊者對獲得的統(tǒng)計值進行分析，并結合N輪計算后的PRGA，也可以恢復密鑰。

在改進的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]的值。改進RC4算法對KSA部分進行改進，橢圓曲線的離散對數(shù)問題使得橢圓曲線單向不可逆，經(jīng)過MD5和偽隨機數(shù)產生器進一步處理，Key無法被破解，S盒的初始值無法被獲取。即使獲得了初始值，初始S盒的元素每一次都是隨機產生，跟初始值無關且不同，i≥1時的下一次迭代后的狀態(tài)和S[1]的值也無法獲知，因此不滿足上述概率，密鑰無法恢復。所以“受戒禮”攻擊對改進RC4算法無效，即改進RC4算法可以抵抗“受戒禮”攻擊。

4.4 抵抗狀態(tài)猜測攻擊

文獻[7]中針對RC4算法中的PRGA部分進行狀態(tài)猜測攻擊，假設攻擊者獲得了一段足夠多的PRGA 輸出值對內部狀態(tài)賦值，根據(jù)已知的輸出值和其他信息進行判斷，如果矛盾，重新賦值;如果整個賦值過程中沒有矛盾，攻擊者即得到一個正確的內部狀態(tài)。若攻擊者能夠根據(jù)這些輸出值計算出PRGA 的初始狀態(tài)，那么無需密鑰即可以繼續(xù)產生任何輸出值，RC4 算法即被破解。

在改進RC4算法中，KSA部分借助偽隨機產生器使得初始Key不斷改變，S盒的初值即PRGA的初始狀態(tài)也隨之改變，攻擊者對PRGA狀態(tài)賦值成功后得到的內部狀態(tài)也已失效，無法繼續(xù)產生輸出值。同時改進RC4算法的KSA部分使得Key隨機性很高，很難賦值成功，且密鑰生存期很短，攻擊者獲知初始狀態(tài)進行猜測花費的時間高于密鑰生存期，賦值成功得到的信息失去時效性，攻擊失敗。因此，改進RC4算法可以抵抗狀態(tài)猜測攻擊。

狀態(tài)猜測攻擊過程如圖8所示，其步驟如下：

步驟1? 根據(jù)Have_val值（TRUE或FALSE）判斷St-1[ i t]是否被賦值。

①已賦值，則轉步驟2。

②若未賦值，則從2n-a選出一個未使用值對St[ i t]賦值，更新at，得到 j t= j t-1+St-1[ i t]，轉步驟2。

步驟2? 判斷Zt是否與at中某值相等。

①若相等，計算St-1[ j t]=S-St[Zt]-St-1[ j t]，判斷St-1[ j t]是否已被賦值過;若是，判斷是否與計算值相等，相等則t=TRUE，轉步驟1;不相等則返回步驟1的②，重新對St-1[ j t]賦值。若Have_val=FALSE，判斷剛計算的St-1[ j t]是否在at中：若不存在，用剛計算出的St-1[ j t]賦值，更新at，返回步驟1;若存在，返回步驟1的②，對St-1[ i t]賦值。

②若不相等，則轉步驟3。

步驟3? 根據(jù)Have_val值（TRUE或FALSE）判斷St-1[ j t]是否被賦值。

①若未賦值，則從2n-a選出一個未使用值對St-1[ j t]賦值，更新at，計算 i t=St-1[ i t]+St-1[ j t]，判斷St[ i t]是否被賦值：若被賦值，判斷是否等于Zt，相等則t=TRUE，轉步驟1;不相等則重新對St-1[ j t]賦值。

若未被賦值，判斷Zt是否出現(xiàn)在at中：若存在則重新賦值St-1[ j t];若不存在則用Zt值更新St[ i t]，更新at值，令t=t+1，返回步驟1。

若Zt對St[ i t]中所有值的賦值均出現(xiàn)矛盾，則返回步驟1的①，重新對St-1[ i t]賦值。

②若已賦值，則計算 i t=St-1[ i t]+St-1[ j t]，判斷是否被賦值：若未被賦值，則把Zt賦值給St[ i t]，更新at，令t=t+1，返回步驟1;若已被賦值，則出現(xiàn)矛盾返回步驟1的②，再次對St-1[ i t]賦值。

其中：S-1t[Zt]表示輸出值Zt在內部狀態(tài)S中的對應位置; j t，St[ i t]，St[ j t]分別為t時刻j，S[i]，S[j]的值;at為已猜測出的字節(jié)。從狀態(tài)猜測攻擊的攻擊過程看出，猜測過程中主要是猜測 j t，St[ i t]，St[ j t]和S-1t[Zt]直到t=0時S0中的所有算法。已獲知的初始狀態(tài)越少，復雜度越高，需要進行的猜測越多，攻擊越困難，算法越安全。

對于初始狀態(tài)表S0猜測成功一般應該存在以下兩個條件：

1）已獲得四個未知數(shù)中的三個，猜測第四個，如若已知 j t，St[ i t]，St[ j t]和S-1t[Zt]且Zt已在狀態(tài)表S中被賦值，則St[ j t]=S-1t[Zt]-St[ i t]。

2）S盒中的元素取值是固定范圍，且St-1[ i t]或St-1[ j t]每一次都必須與S中已經(jīng)賦過的值不同。

而在改進RC4算法中，橢圓曲線、MD5哈希函數(shù)和偽隨機數(shù)產生器無法被破解，攻擊者無法獲知t時刻的內部狀態(tài)，即無法獲知四個未知數(shù)中的任意三個，條件1）無法滿足;S盒中元素取值范圍影響因素包括：①隨機大素數(shù)p，②橢圓曲線y2=x3+x+1，③MD5哈希函數(shù)，④偽隨機數(shù)產生器，四個因素，高隨機性使得S盒中元素取值不會是固定范圍，條件2）失效。因此狀態(tài)猜測攻擊無法攻擊改進RC4算法，即改進的RC4算法可以有效抵抗狀態(tài)猜測攻擊。

5? 結語

本文提出了一種基于橢圓曲線的改進RC4算法，該算法通過橢圓曲線、哈希函數(shù)和偽隨機數(shù)產生器生成初始密鑰Key，在S盒和指針的作用下進行非線性變換最終生成了隨機性和安全性很高的密鑰流序列。該密鑰流序列由隨機產生的初始Key、大素數(shù)和指針i、? j共同確定，利用NIST隨機性測試工具對密鑰流序列在頻率檢驗、游程檢驗和Maurer等16個指標進行檢測，結果表明，該3項指標改進的RC4算法比原RC4算法分別高出0.13893，0.13081，0.232050，因此，該算法密鑰流隨機性高于RC4算法，能夠有效防止不變性弱密鑰的產生，能夠抵抗“受戒禮”攻擊。Key是一個分布均勻的隨機數(shù)，不存在偏差，能夠有效抵御區(qū)分攻擊。橢圓曲線、哈希函數(shù)具有單向不可逆性，偽隨機數(shù)產生器具有高密碼強度，Key猜測賦值困難，能夠抵抗狀態(tài)猜測攻擊。安全性理論分析和隨機性實驗結果表明，改進RC4算法的安全性和隨機性高于RC4算法。本文在錯誤引入攻擊和明文恢復攻擊等方面未進行有效測試和驗證，這些將是下一步的研究方向。

參考文獻

[1]???FINNEY H. An RC4 cycle that cant happen [J]. Post. in Sci. ?Crypt.，1994： 246.

[2]?KNUDSEN L R， MEIER W， PRENEEL B， et al. Analysis methods for （alleged） RC4 [C]// Proceedings of the 1998 International Conference on the Theory and Application of Cryptology and Information Security， LNCS 1514. Berlin： Springer， 1998： 327-341.

[3]?FLUHRER S R， McGREW D A. Statistical analysis of the alleged RC4 keystream generator [C]// Proceedings of the 2000 International Workshop on Fast Software Encryption， LNCS 1978. Berlin： Springer， 2000： 19-30.

[4]?PAUL S， PRENEEL B. A new weakness in the RC4 key stream generator and an approach to improve the security of the cipher [C]// Proceedings of the 2004 International Workshop on Fast Software Encryption， LNCS 3017. Berlin： Springer， 2004： 245-259.

[5]?MIYAJI A， SUKEGAWA M. New analysis based on correlations of RC4 PRGA with nonzero-bit differences [J]. IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences， 2010， E93-A（6）： 1066-1077.

[6]?常亞琴.對流密碼RC4的區(qū)分攻擊[J].計算機工程，2011，37（3）：119-120，123. （CHANG Y Q. Distinguishing attack on stream cipher RC4 [J]. Computer Engineering， 2011， 37（3）： 119-120， 123.）

[7]?HOCH J J， SHAMIR A. Fault analysis of stream ciphers [C]// Proceedings of the 2004 International Workshop on Cryptographic Hardware and Embedded Systems， LNCS 3156. Berlin： Springer， 2004： 240-253.

[8]?FLUHRER S， MANTIN I， SHAMIR A. Weakness in the key scheduling algorithm of RC4 [C]// Proceedings of the 2001 International Workshop on Selected Areas in Cryptography， LNCS 2259. Berlin： Springer， 2001： 1-24.

[9]?MANTIN I. Analysis of the stream cipher RC4 [D/OL]. Weizmann Institute of Science， 2001 [2018-10-23]. http： //www.wisdom.weizmann.ac.il/itsik/RC4/Papers/Mantin1.zip.

[10]?AKGN M， KAVAK P， DEMIRCI H. New results on the key scheduling algorithm of RC4 [C]// Proceedings of the 2008 International Conference on Cryptology in India， LNCS 5365. Berlin： Springer， 2008： 40-52.

[11]??MANTIN I. Bar-Minzva attack： breaking SSL with 13-year old? RC4 weakness [N]. Blackhat， 2015-03-22.

[12]?苑超，徐蜜雪，斯雪明.對不同種子密鑰長度的RC4算法的明文恢復攻擊[J].計算機應用，2018，38（2）：370-373. （YUAN C， XU M X， SI X M. Plaintext recovery attack on RC4 with different length of seed key [J]. Journal of Computer Applications， 2018， 38（2）： 370-373.）

[13]?胡亮，遲令，袁巍，等.RC4算法的密碼分析與改進[J].吉林大學學報（理學版），2012，50（3）：511-516. （HU L， CHI L， YUAN W， et al. Cryptanalysis and improvements of RC4 algorithm [J]. Journal of Jilin University （Science Edition）， 2012， 50（3）： 511-516.）

[14]?陳立，鄧成良，肖慧娟.基于RC4的混沌改進算法及其性能分析[J].科學技術與工程，2010，10（26）：6449-6452，6458. （CHEN L， DENG C L， XIAO H J. An algorithm improved by chaos based on RC4 and its performance analysis [J]. Science Technology and Engineering， 2010， 10（26）： 6449-6452， 6458.）

[15]?ZOLTAK B. VMPC oneway function and stream cipher [C]// Proceedings of the 2004 International Workshop on Fast Software Encryption， LNCS 3017. Berlin： Springer， 2004： 210-225.

[16]?TSUNOO Y， SAITO T， KUBO H， et al. The most efficient distinguishing attack on VMPC and RC4A [J]. Estream Project， 2005： 1-12. 沒找到

[17]?侯整風，孟毛廣，朱曉玲，等. RC4流密碼算法的分析與改進[J].計算機工程與應用，2015，51（24）：97-101. （HOU Z F， MENG M G， ZHU X L， et al. Analysis and improvement of RC4 stream cipher algorithm [J]. Computer Engineering and Applications， 2015， 51（24）： 97-101.）

[18]?孟毛廣.RC4流密碼算法的研究與改進[D].合肥：合肥工業(yè)大學，2014：9-12. （MENG M G. Research and improvement of RC4 stream cipher algorithm [D]. Hefei： Hefei University of Technology， 2014： 9-12.）

[19]?田松，李寶，王鯤鵬.橢圓曲線離散對數(shù)問題的研究進展[J].密碼學報，2015，2（2）：177-188. （TIAN S， LI B， WANG K P. On the progress of elliptic curve discrete logarithm problem [J]. Journal of Cryptologic Research， 2015， 2（2）：177-188.）

[20]?張小紅，郭焰輝.基于橢圓曲線密碼的RFID系統(tǒng)安全認證協(xié)議研究[J].信息網(wǎng)絡安全，2018，18（10）：51-61. （ZHANG X H， GUO Y H. Research on RFID system security authentication protocol based on elliptic curve cryptography [J]. Netinfo Security， 2018， 18（10）： 51-61.）

[21]?巫光福，曾憲文，劉娟，等.基于糾錯碼的Hash函數(shù)的設計與分析[J].信息網(wǎng)絡安全，2018，18（1）：67-72. （WU G F， ZENG X W， LIU J， et al. Design and analysis of hash function based on error correcting code [J]. Netinfo Security， 2018， 18（1）： 67-72.）

[22]?BARKER E， BARKER W， BURR W， et al. Recommendation for Key Management — Part 1： General， SP 800-57 [R]. Gaithersburg， MD： National Institute of Standards & Technology， 2007： 1-142.

[23]?翟高壽，劉晨，向勇.基于內核函數(shù)監(jiān)控的Linux系統(tǒng)防護方法的研究與實現(xiàn)[J].信息網(wǎng)絡安全，2018，18（3）：26-38. （ZHAI G S， LIU C， XIANG Y. Study and implementation of systematic protection by monitoring abnormal invocation of Linux kernel functions [J]. Netinfo Security， 2018， 18（3）： 26-38.）

[24]?KIM S， UMENO K， HASEGAWA A. Corrections of the NIST statistical test suite for randomness [EB/OL]. [2018-10-10]. http： //www.docin.com/p-1036631337.html.