*通信作者：李永珍(1971—)，男，博士，副教授，研究方向?yàn)榫W(wǎng)絡(luò)安全、無線網(wǎng)絡(luò)協(xié)議.

基于哈希鏈的序列密碼算法

姜璇，李永珍*

( 延邊大學(xué)工學(xué)院 計算機(jī)科學(xué)與技術(shù)學(xué)科 網(wǎng)絡(luò)與安全研究室，吉林 延吉 133002 )

摘要：為了設(shè)計出能應(yīng)用于無線移動通信的序列密碼算法，提出了一種將單分組散列函數(shù)應(yīng)用于哈希鏈方法的序列密碼算法(SC-SBH).該算法首先用哈希鏈的方法對單分組散列函數(shù)進(jìn)行循環(huán)運(yùn)算，將運(yùn)算的每一次結(jié)果值輸出后連接成序列密碼的密鑰序列，然后將明文與密鑰序列進(jìn)行按位異或運(yùn)算得到密文.實(shí)現(xiàn)SC-SBH算法后，對其安全性和隨機(jī)性進(jìn)行了測試，并將其運(yùn)行效率與SC-MD5和SC-SHA算法進(jìn)行了比較.實(shí)驗(yàn)結(jié)果表明，SC-SBH算法在加密方面不僅能夠保證安全性，而且其運(yùn)行效率明顯高于SC-MD5和SC-SHA算法.

關(guān)鍵詞：序列密碼； 單分組散列函數(shù)； 哈希鏈； 運(yùn)行效率； 安全性

收稿日期：2015-06-26

文章編號：1004-4353(2015)03-0249-05

中圖分類號：TP309.7

Stream cipher algorithm based on Hash chain

JIANG Xuan,LI Yongzhen*

(NetworkandInformationSecurityLab.,Dept.ofComputerScience&Technology,

CollegeofEngineering,YanbianUniversity,Yanji133002,China)

Abstract：We proposed a new stream cipher in this article to apply in the wireless mobile communications,new stream cipher implemented by Single-Block hash function based on Hash chain method. In this new algorithm,the Single-Block hash function processes loop operation adopted Hash chain method firstly,then links the output of each operation into the Stream Cipher key sequence,finally cipher text is obtained by bit XOR operation of plaintext and key sequence. After the realization of SC-SBH,we have tested its randomness and security,and have made comparison with SC-MD5 and SC-SHA in efficiency. The experimental results showed that the SC-SBH algorithm not only can ensure safety,but also have high efficiency relative to SC-MD5 and SC-SHA.

Key words： stream cipher; Single-Block hash function; Hash chain; running efficiency; security

序列密碼因運(yùn)行速度快，硬件需求低，且具有安全性高、易同步、無錯誤傳輸?shù)葍?yōu)異特性，在無線移動通信中有著廣泛的應(yīng)用，特別是在高速通訊、高噪聲信道傳輸?shù)阮I(lǐng)域中[1].為了能更好地將序列密碼應(yīng)用于無線移動通信領(lǐng)域，在現(xiàn)代Estream計劃中，許多新的序列密碼設(shè)計方法被采用，如移位寄存器與其他裝置的結(jié)合、基于狀態(tài)表驅(qū)動、利用分組密碼的部件或思想；一些單純的基于一種裝置來設(shè)計序列密碼的特殊算法也被提出，如基于神經(jīng)網(wǎng)絡(luò)的算法、基于層疊跳轉(zhuǎn)控制序列的算法、基于偽隨機(jī)數(shù)生成器的算法等.但這些算法目前仍很難做出系統(tǒng)的安全分析，且運(yùn)行速度也有待提高[2].本文通過用哈希鏈方法對單分組散列函數(shù)進(jìn)行迭代運(yùn)算，將中間結(jié)果輸出，連接中間結(jié)果作為序列密碼的密鑰序列，以此實(shí)現(xiàn)新的序列密碼模型，并且通過實(shí)驗(yàn)證明了本文方法的安全性和高效性.

1序列密碼算法的原理與結(jié)構(gòu)

1.1　序列密碼算法的原理及原則

序列密碼的構(gòu)成可用一個6元組來描述，即P，C，K，Z，Ek，Dk，其中P代表明文空間，C代表密文空間，K代表密鑰空間，Z代表密鑰流生成算法，Ek和Dk代表密鑰序列與明文的加密和密文的解密規(guī)則，通常為異或運(yùn)算.對密鑰k∈K，Z確定一個密鑰序列[3].序列密碼算法加解密的原理如圖1所示.

圖1　序列密碼的工作原理

加密過程可表示為Ci=Pi⊕Ki，解密操作可表示為Pi=Ci⊕Ki，i≥1.其中：二進(jìn)制序列P0,P1,…,Pi是明文序列，Pi∈GF(2)，i≥1； K0,K1,…,Ki是密鑰序列，Ki∈GF(2)，i≥1；⊕表示按位異或運(yùn)算，即模2加運(yùn)算.

在序列密碼系統(tǒng)中，加密原則為：1)明文序列與密鑰序列逐位進(jìn)行加密，所以密鑰序列一定要與明文的長度相同；2)序列密碼的密鑰序列隨時間變換，加密算法“一次一密”，所以在序列密碼中相同明文對應(yīng)的密文也不同.

根據(jù)加密原理及原則可知，密鑰序列的偽隨機(jī)性決定了序列密碼的安全強(qiáng)度.研究[4]表明，將無記憶的、離散的二進(jìn)制均勻分布信源產(chǎn)生的隨機(jī)序列作為密鑰序列，在理論上雖然被證實(shí)是安全可靠的，但在實(shí)際中是不可能的.文獻(xiàn)[4]還表明，僅當(dāng)密鑰個數(shù)與明文個數(shù)至少一樣多時，“一次一密”才是完全保密的，即密鑰長度至少和明文長度一樣長且不重復(fù)使用時才是安全的.但由于過長的密鑰序列在實(shí)際中不便于存儲和分配，所以設(shè)計序列密碼的主要目標(biāo)就是研究如何用一個短的密鑰生成一個周期長且安全性高的密鑰序列.

1.2　序列密碼中幾種構(gòu)造密鑰生成器的方法

1) 線性反饋移位寄存器構(gòu)造密鑰序列生成器.該密鑰生成器的典型算法是RC4算法[5-6],它是一個密鑰長度可變、面向字節(jié)操作的序列密碼，以隨機(jī)置換作為基礎(chǔ).由于該算法易于軟件實(shí)現(xiàn)，而且安全性高，因而得到非常廣泛的應(yīng)用.

2) 基于分組密碼構(gòu)造密鑰序列生成器.該密鑰序列生成器的典型算法是LEX算法[7-8]，其密鑰序列生成器借鑒了分組密碼的成熟設(shè)計理念，易于理解和實(shí)現(xiàn).

3) 基于布爾函數(shù)構(gòu)造密鑰序列生成器.將Bent函數(shù)使用在非線性組合序列生成器中，非線性組合函數(shù)f(x)的選取能夠保證非線性組合序列具有較好的隨機(jī)特性、較高的線性復(fù)雜度和較強(qiáng)的抗破譯性，但是使用Bent函數(shù)具有不平衡、無相關(guān)免疫性等缺陷[9-10].

2基于哈希鏈的序列密碼算法設(shè)計

2.1　單分組散列函數(shù)

本文提出的基于哈希鏈方法的序列密碼算法，其密鑰序列是利用單分組散列函數(shù)設(shè)計的.單分組散列函數(shù)SBH是以哈希函數(shù)的設(shè)計原理和準(zhǔn)則為理論依據(jù)來進(jìn)行設(shè)計的，它是一種針對短消息進(jìn)行處理的散列函數(shù).由于單分組散列函數(shù)優(yōu)化了MD5的運(yùn)算，減少了不必要的計算，即縮短了運(yùn)算周期，因此在能夠保證安全的同時，還能夠提高消息的處理效率.SBH算法的輸入和輸出均為128位，因此也被稱為SBH-128[11].該算法使用4個寄存器，主循環(huán)有4輪，每輪4步.

運(yùn)算時，首先將128位的初始值分成4個組(每組32位)，分別與A、B、C、D4個寄存器常量進(jìn)行運(yùn)算，一共運(yùn)算16步.在每步運(yùn)算結(jié)束時，將當(dāng)前獲得的運(yùn)算結(jié)果替換緩存器保存的前一輪的值，以此來更新緩存內(nèi)容.算法的輸出值是由4個32位緩存寄存器經(jīng)過16步運(yùn)算后得到的結(jié)果構(gòu)成的一組128位哈希碼.圖2為SBH算法主循環(huán)部分的邏輯圖.在圖2中：F,G,H,I是4輪運(yùn)算中應(yīng)用的非線性函數(shù);ρ2,ρ3,ρ4是128bits分組X[i]在第2、3、4輪中的使用順序;K1,K2,K3,K4是常量.

圖2　SBH-128算法整體邏輯圖

2.2　基于哈希鏈的序列密碼算法結(jié)構(gòu)

基于哈希鏈的序列密碼算法的設(shè)計思想主要是：將SBH-128用哈希鏈方法進(jìn)行迭代運(yùn)算，然后把每次運(yùn)算得到的中間結(jié)果連接成為密鑰序列，最后將密鑰序列與明文進(jìn)行按位異或運(yùn)算得到密文.

一個單分組散列函數(shù)輸出的是128位的散列碼.運(yùn)算時，首先用哈希鏈的方法對SBH-128的128位散列碼進(jìn)行處理，即把當(dāng)前一次的SBH-128輸出值作為下一次的SBH-128輸入值，然后把每一次SBH-128的運(yùn)算結(jié)果記錄并輸出，以此形成128×n位的序列作為算法的最終密鑰序列.圖3為序列密碼SC-SBH密鑰生成器設(shè)計邏輯圖.

圖3　SC-SBH密鑰生成器設(shè)計邏輯圖

SC-SBH密鑰生成器的設(shè)計步驟為：

1) 設(shè)計密鑰生成器的初始值.由于序列密碼要求加密時“一次一密”，所以本文用currentTimeMillis方法生成初始值.

2) 運(yùn)算次數(shù).在設(shè)計密鑰生成器時，當(dāng)明文長度是128×n位時，哈希鏈進(jìn)行n次哈希運(yùn)算，其結(jié)果直接與明文進(jìn)行按位異或運(yùn)算即可；當(dāng)明文長度不是128×n位時，需要將明文長度與128進(jìn)行求模運(yùn)算，得到模m后，哈希鏈再進(jìn)行m+1次運(yùn)算.這是因?yàn)樾蛄忻艽a加密要求明文和密鑰要有相同的長度，所以，明文與密鑰按位異或運(yùn)算，密鑰多出來的位自動舍棄.

3) 組成密鑰序列.把單分組散列函數(shù)每一次循環(huán)運(yùn)算的中間結(jié)果值輸出，連接成128×n位的密鑰序列.

4) 生成密文.將明文與得到的密鑰序列進(jìn)行位異或運(yùn)算得到密文.

由于SC-SBH的密鑰生成器部件的設(shè)計是以單分組散列函數(shù)為基礎(chǔ)，繼承了其針對短消息處理的功能，因此該方法實(shí)現(xiàn)了具有非線性特性的新型序列密碼算法.

3實(shí)驗(yàn)及結(jié)果分析

本實(shí)驗(yàn)采用的編程語言是Java語言，編譯工具是Eclipse(JUNO版本)，實(shí)驗(yàn)運(yùn)行環(huán)境是PC機(jī)(配置為Intel Core 3.20GHZ,4.00GB ROM).根據(jù)Golomb提出的隨機(jī)性假設(shè)要求，本文從“0/1”平衡和“0/1”游程個數(shù)[12-13]的角度分析SC-SBH的安全性，并將SC-SBH同SC-MD5(基于MD5的哈希鏈方法序列密碼算法)和SC-SHA(基于SHA的哈希鏈方法序列密碼算法)進(jìn)行效率對比.

3.1　“0/1”平衡隨機(jī)性測試

Golomb提出的“序列應(yīng)滿足的隨機(jī)性假設(shè)”中第1條要求為：在序列的一個周期內(nèi)，0和1的個數(shù)相差至多為1，即要求0和1出現(xiàn)的概率基本相同.

用SC-SBH加密算法分別對50KB、500KB、1MB、5MB、10MB不同大小的明文進(jìn)行了加密，并記錄密文中“1”的個數(shù)所占2進(jìn)制密鑰序列長度的比例.從表1的實(shí)驗(yàn)結(jié)果中可以看出，“1”所占的比例約為53%，因此本文設(shè)計的序列密碼算法SC-SBH生成的密鑰序列的“0”和“1”個數(shù)較為平衡，基本符合Golomb提出的“序列隨機(jī)性假設(shè)”中的第1條要求.

表1　SC-SBH的平衡性測試結(jié)果

3.2　游程隨機(jī)性測試

Golomb提出的“序列應(yīng)滿足的隨機(jī)性假設(shè)”中第2條要求為：長度為T的周期內(nèi)，任意長度的0的游程個數(shù)與1的游程個數(shù)相同.

游程定義：一個二元序列中，形如100…001的片段稱為該序列的一個0游程，形如0111…110的片段為該序列的一個1游程，并稱0游程中0的個數(shù)為該游程的長度，1游程中1的個數(shù)為該游程的長度.

約定：0開頭的信號片段00…01為一個0游程，1開頭的信號片段11…10為一個1游程，以0結(jié)束的信號片段100…0為一個0游程，以1結(jié)束的信號片段011…1為一個1游程.

本測試實(shí)驗(yàn)中利用單分組散列函數(shù)進(jìn)行1000次迭代，累加生成12.8萬個長度的密鑰序列作為一個周期，然后對這個周期內(nèi)密鑰序列中長度為2、3、4、5的0的游程和1的游程的個數(shù)進(jìn)行統(tǒng)計和對比.

用SC-SBH加密算法分別對50KB、500KB、1MB、5MB、10MB不同大小的明文對應(yīng)生成的密鑰序列進(jìn)行了游程測試，并記錄了不同長度密鑰序列的不同長度的0的游程和1的游程的個數(shù)，結(jié)果如表2所示.從表2中可以看出，0的游程個數(shù)和1的游程個數(shù)基本相同，因此，本文設(shè)計的SC-SBH算法生成的密鑰序列的游程測試基本符合Golomb提出的“序列隨機(jī)性假設(shè)”中的第2條要求.

表2　SC-SBH的游程測試

3.3　效率性能分析

為驗(yàn)證SC-SBH算法的效率性能，將SC-SBH算法的效率分別與SC-MD5和SC-SHA算法的效率進(jìn)行了對比.實(shí)驗(yàn)中，3種算法均對50KB、500KB、1MB、5MB、10MB不同大小的明文進(jìn)行100次加密處理，實(shí)驗(yàn)記錄數(shù)據(jù)如表3所示.3種算法的效率示意圖如圖4所示.

表3　3種算法對明文加密運(yùn)行的平均時間

圖4　3種算法的效率示意圖

由表3和圖4可以看出，在相同大小的明文和運(yùn)行環(huán)境下，SC-SBH算法的運(yùn)行效率優(yōu)于SC-MD5和SC-SHA算法.為了更準(zhǔn)確地顯示出SC-SBH算法效率的提高率，實(shí)驗(yàn)又對SC-SBH、SC-MD5、SC-SHA算法的效率進(jìn)行了再計算，結(jié)果如表4所示.

表4SC-SBH算法相對于SC-MD5和SC-SHA算法的運(yùn)行效率的提高率%

不同大小明文效率提高率50KB500KB1MB5MB10MBSC-SBH相對于SC-MD516.1310.3911.689.055.26SC-SBH相對于SC-SHA6.3811.0314.6913.6111.42

4結(jié)論

本文提出的SC-SBH算法的創(chuàng)新之處在于它將單分組散列函數(shù)應(yīng)用于哈希鏈方法的序列密碼算法.經(jīng)實(shí)驗(yàn)分析表明，本文提出的方法與MD5和SHA算法相比，具有安全性好、效率高、硬件消耗資源小、軟件易實(shí)現(xiàn)等優(yōu)點(diǎn)，可應(yīng)用于“保證常規(guī)安全性前提下快速加密”的數(shù)據(jù)保護(hù)，尤其是無線移動通信的數(shù)據(jù)保護(hù).本文對算法的安全性和效率進(jìn)行了分析和驗(yàn)證，今后還需對其抗攻擊性做進(jìn)一步驗(yàn)證分析，以期得到更加完善的算法.

參考文獻(xiàn)：

[1]William Stallings.密碼編碼學(xué)與網(wǎng)絡(luò)安全-原理與實(shí)踐[M].王張宜，楊敏，杜瑞穎譯.5版.北京：電子工業(yè)出版社,2012.

[2]Halevi S,Coppersmith D,Jutla C. Scream: a software-efficient stream cipher[C]//Fast Software Encryption (FSE) 2002. Lecture Notes in Computer Science，2002:195-209.

[3]王相生.序列密碼設(shè)計與實(shí)現(xiàn)的研究[D].上海：中國科學(xué)院上海冶金研究所,2001.

[4]宮大力.流密碼算法的研究與設(shè)計[D].南京：南京航空航天大學(xué),2011.

[5]張海納.eSTREAM序列密碼候選算法的安全性分析[D].山東：山東大學(xué),2009.

[6]Singhal N,Raina J P S. Comparative analysis of AES and RC4 algorithms for better utilization[J]. International Journal of Computer Trends and Technology,2011,2(6):177-181.

[7]劉依依.eSTREAM和流密碼分析現(xiàn)狀[J].信息安全與通信保密,2009(12)：47-49.

[8]Luo Y,Chai Q,Gong G,et al. A lightweight stream cipher WG-7 for RFID encryption and authentication[C]//Global Telecommunications Conference (GLOBECOM 2010),IEEE,2010:1-6.

[9]武傳坤,王新梅.Bent函數(shù)在流密碼中的應(yīng)用[J].通信學(xué)報,1993,4:23-27.

[10]Gupta S S,Chattopadhyay A,Sinha K,et al. High-performance hardware implementation for RC4 stream cipher[J]. IEEE Transactions on Computers,2013,62(4):730-743.

[11]王靜雅.單分組散列函數(shù)的設(shè)計與應(yīng)用[D].延吉：延邊大學(xué),2014.

[12]尤加勇.現(xiàn)代序列密碼的設(shè)計與分析[D].北京：國防科學(xué)技術(shù)大學(xué),2007.

[13]Sharif S O,Mansoor S P. Performance analysis of Stream and Block cipheralgorithms[C]//Advanced Computer Theory and Engineering (ICACTE),2010 3rd International Conference on. IEEE,2010,1:522-525.