RC4隨機(jī)序列變換檢測(cè)

吳悠漾 劉祎飛 林旭

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

【關(guān)鍵詞】 RC4算法 傅里葉變換 walsh變換

一、引言

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

RC4流密碼技術(shù)是當(dāng)前應(yīng)用最為廣泛的一種對(duì)稱密碼技術(shù)，以隨機(jī)置換為基礎(chǔ)，是一個(gè)可變密鑰長(zhǎng)度、面向字節(jié)操作的流密碼。

然而RC4卻容易受到攻擊，現(xiàn)在已經(jīng)證明在已知RC4的部分密鑰的情況下，可以恢復(fù)RC4的完整密鑰。為了改進(jìn)RC4算法，我們改變了RC4循環(huán)的輪數(shù)，對(duì)生成的偽隨機(jī)序列進(jìn)行了測(cè)量，并對(duì)產(chǎn)生的偽隨機(jī)序列做了Walsh和FFT變換。

二、RC4和序列的生成

RC4算法非常簡(jiǎn)單，易于描述：用從1到256個(gè)字節(jié)（8到2048位）的可變長(zhǎng)度密鑰初始化一個(gè)256個(gè)字節(jié)的狀態(tài)矢量S，S的元素記為S[0]，S[1]，···，S[255]，從始至終置換后的S的包含從0到255的所有8比特?cái)?shù)據(jù)。對(duì)于加密解密，字節(jié)K由S中255個(gè)元素按一定方式選出一個(gè)元素而生成，每生成一個(gè)K的值，S中的元素就被重新置換一次。

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

三、隨機(jī)序列變換及檢測(cè)

3.1 Walsh變換

沃爾什變換（Walsh transform）是以沃爾什函數(shù)為基本函數(shù)的一種非正弦正交變換。Walsh函數(shù)是二值正交函數(shù)，它僅有可能的取值是+1和-1，與數(shù)理邏輯的兩個(gè)狀態(tài)相對(duì)應(yīng)，更適合計(jì)算機(jī)處理。Walsh函數(shù)變換可以減少存儲(chǔ)空間，提高運(yùn)算的速度。

對(duì)不同循環(huán)次數(shù)的RC4隨機(jī)矩陣作walsh變換，統(tǒng)計(jì)變換矩陣中各值的出現(xiàn)頻次，生成直方圖。DNA序列由A，T，C，G四對(duì)堿基對(duì)組成，我們將隨機(jī)序列處理為1，2，-1，-2的形式，又分別對(duì)四種循環(huán)次數(shù)生成的偽隨機(jī)序列作walsh變換，生成頻數(shù)直方圖。

3.2快速傅里葉變換

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

在本測(cè)試中我們分別使用循環(huán)64、128、192、256次生成4個(gè)不同的2048 bits的-1，1偽隨機(jī)序列，通過FFT變換后各序列產(chǎn)生頻數(shù)分布直方圖。同樣的我們也生成4個(gè)不同的1024 bits的DNA偽隨機(jī)序列，通過FFT變換后各序列產(chǎn)生頻數(shù)分布直方圖。

四、總結(jié)

不同循環(huán)次數(shù)-1，1偽隨機(jī)序列通過Walsh變換后，其分布趨向于正態(tài)分布，其中最接近正太分布的是循環(huán)次數(shù)為1024的序列；同樣的，DNA形式偽隨機(jī)序列通過Walsh變換后也有相同的規(guī)律。兩種序列的128次循環(huán)分布都較為不均勻，有較多的離群數(shù)據(jù)?？焖俑道锶~變換，在循環(huán)次數(shù)64-256的情況下，不管是-1，1序列還是DNA序列，其虛部的分布都是標(biāo)準(zhǔn)正太分布，而從64到256，循環(huán)次數(shù)越大實(shí)部越接近正態(tài)分布。循環(huán)次數(shù)較小時(shí)，-1，1序列的實(shí)部會(huì)產(chǎn)生小于0的離群數(shù)據(jù)，而DNA序列的實(shí)部會(huì)產(chǎn)生大于0的離群數(shù)據(jù)。

偽隨機(jī)序列是人為構(gòu)成的數(shù)字序列，因此它是離散的，只包含高低兩種電平，不可能具有真正的正態(tài)分布特性。但如果序列的長(zhǎng)度逼近無限大時(shí)，由中心極限定理可知，它趨于正態(tài)分布。

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

參 考 文 獻(xiàn)

[1] 對(duì)稱布爾函數(shù)算術(shù)Walsh變換的快速算法. 趙慶蘭，鄭東.西安郵電大學(xué)報(bào)，19-5，2014.

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

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

[4] 葉瑞崧，廖海泳.Walsh變換核矩陣的簡(jiǎn)單生成及其應(yīng)用[J].汕頭：汕頭大學(xué)數(shù)學(xué)系，2005.