RC4隨機序列變換檢測

吳悠漾 劉祎飛 林旭

【摘要】 隨著隨機序列在密碼學中的應用日益廣泛。很多密碼算法和協議中都要用到一些隨機序列。對一個密碼算法來說，其輸出序列的隨機性是其安全性的很重要的一個方面，因此隨機性測試技術在密碼學中占有很重要的作用。我們針對改進的RC4算法進行隨機序列檢測，其中用到的的方法包括FFT和Walsh變換檢測等等，通過檢測得出的結果從多個方面對算法產生的隨機序列進行分析并得出結論。

【關鍵詞】 RC4算法 傅里葉變換 walsh變換

一、引言

1949年Shannon證明了只有一次一密的密碼體制才是理論上不可破譯的、絕對安全的，這給流密碼技術的研究以極大的支持，由此奠定了流密碼的發展基石。流密碼的安全與否，則取決于密鑰發生器生成偽隨機數的安全性。

RC4流密碼技術是當前應用最為廣泛的一種對稱密碼技術，以隨機置換為基礎，是一個可變密鑰長度、面向字節操作的流密碼。

然而RC4卻容易受到攻擊，現在已經證明在已知RC4的部分密鑰的情況下，可以恢復RC4的完整密鑰。為了改進RC4算法，我們改變了RC4循環的輪數，對生成的偽隨機序列進行了測量，并對產生的偽隨機序列做了Walsh和FFT變換。

二、RC4和序列的生成

RC4算法非常簡單，易于描述：用從1到256個字節（8到2048位）的可變長度密鑰初始化一個256個字節的狀態矢量S，S的元素記為S[0]，S[1]，···，S[255]，從始至終置換后的S的包含從0到255的所有8比特數據。對于加密解密，字節K由S中255個元素按一定方式選出一個元素而生成，每生成一個K的值，S中的元素就被重新置換一次。

我們使用相同的密鑰（在這里忽略用戶輸入密鑰對產生偽隨機序列的影響），改變循環的次數，在程序中統計生成的偽隨機序列中0、1所占的比例。當循環數目設置小于256時，0和1在隨機序列中所占比例有一定差距，隨著循環數目增大0、1分布逐漸平衡。在循環次數等于256時，0、1所占比例基本相等，之后再次增加循環次數對其頻率影響不大。

三、隨機序列變換及檢測

3.1 Walsh變換

沃爾什變換（Walsh transform）是以沃爾什函數為基本函數的一種非正弦正交變換。Walsh函數是二值正交函數，它僅有可能的取值是+1和-1，與數理邏輯的兩個狀態相對應，更適合計算機處理。Walsh函數變換可以減少存儲空間，提高運算的速度。

對不同循環次數的RC4隨機矩陣作walsh變換，統計變換矩陣中各值的出現頻次，生成直方圖。DNA序列由A，T，C，G四對堿基對組成，我們將隨機序列處理為1，2，-1，-2的形式，又分別對四種循環次數生成的偽隨機序列作walsh變換，生成頻數直方圖。

3.2快速傅里葉變換

FFT（Fast Fourier Transformation），即為快速傅里葉變換，是離散傅里葉變換（DFT）的快速算法，它是根據離散傅里葉變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。

在本測試中我們分別使用循環64、128、192、256次生成4個不同的2048 bits的-1，1偽隨機序列，通過FFT變換后各序列產生頻數分布直方圖。同樣的我們也生成4個不同的1024 bits的DNA偽隨機序列，通過FFT變換后各序列產生頻數分布直方圖。

四、總結

不同循環次數-1，1偽隨機序列通過Walsh變換后，其分布趨向于正態分布，其中最接近正太分布的是循環次數為1024的序列；同樣的，DNA形式偽隨機序列通過Walsh變換后也有相同的規律。兩種序列的128次循環分布都較為不均勻，有較多的離群數據。快速傅里葉變換，在循環次數64-256的情況下，不管是-1，1序列還是DNA序列，其虛部的分布都是標準正太分布，而從64到256，循環次數越大實部越接近正態分布。循環次數較小時，-1，1序列的實部會產生小于0的離群數據，而DNA序列的實部會產生大于0的離群數據。

偽隨機序列是人為構成的數字序列，因此它是離散的，只包含高低兩種電平，不可能具有真正的正態分布特性。但如果序列的長度逼近無限大時，由中心極限定理可知，它趨于正態分布。

在該偽隨機序列變換檢測中，經過分析，我們認為，RC4產生的-1，1及DNA序列經FFT（快速傅里葉變換）生成的偽隨機序列虛部有較好的正太分布特性，符合偽隨機序列特性，能夠作為安全的序列密碼。

參 考 文 獻

[1] 對稱布爾函數算術Walsh變換的快速算法. 趙慶蘭，鄭東.西安郵電大學報，19-5，2014.

[2] 基于Walsh譜變換的S盒算法.孫慧盈，陸繼承，魏長征，俞軍.計算機工程，40-7，2014.

[3] William Stallings. Cryptography and Network Security Principles and Practice，Sixth Edition[M].北京：電子工業出版社，2015：4.

[4] 葉瑞崧，廖海泳.Walsh變換核矩陣的簡單生成及其應用[J].汕頭：汕頭大學數學系，2005.