*通信作者：李永珍(1971—)，男，博士，副教授，研究方向為網絡安全、無線網絡協(xié)議.

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

姜璇，李永珍*

( 延邊大學工學院 計算機科學與技術學科 網絡與安全研究室，吉林 延吉 133002 )

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

關鍵詞：序列密碼； 單分組散列函數； 哈希鏈； 運行效率； 安全性

收稿日期：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ōu)異特性，在無線移動通信中有著廣泛的應用，特別是在高速通訊、高噪聲信道傳輸等領域中[1].為了能更好地將序列密碼應用于無線移動通信領域，在現代Estream計劃中，許多新的序列密碼設計方法被采用，如移位寄存器與其他裝置的結合、基于狀態(tài)表驅動、利用分組密碼的部件或思想；一些單純的基于一種裝置來設計序列密碼的特殊算法也被提出，如基于神經網絡的算法、基于層疊跳轉控制序列的算法、基于偽隨機數生成器的算法等.但這些算法目前仍很難做出系統(tǒng)的安全分析，且運行速度也有待提高[2].本文通過用哈希鏈方法對單分組散列函數進行迭代運算，將中間結果輸出，連接中間結果作為序列密碼的密鑰序列，以此實現新的序列密碼模型，并且通過實驗證明了本文方法的安全性和高效性.

1序列密碼算法的原理與結構

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

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

圖1　序列密碼的工作原理

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

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

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

1.2　序列密碼中幾種構造密鑰生成器的方法

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

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

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

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

2.1　單分組散列函數

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

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

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

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

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

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

圖3　SC-SBH密鑰生成器設計邏輯圖

SC-SBH密鑰生成器的設計步驟為：

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

2) 運算次數.在設計密鑰生成器時，當明文長度是128×n位時，哈希鏈進行n次哈希運算，其結果直接與明文進行按位異或運算即可；當明文長度不是128×n位時，需要將明文長度與128進行求模運算，得到模m后，哈希鏈再進行m+1次運算.這是因為序列密碼加密要求明文和密鑰要有相同的長度，所以，明文與密鑰按位異或運算，密鑰多出來的位自動舍棄.

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

4) 生成密文.將明文與得到的密鑰序列進行位異或運算得到密文.

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

3實驗及結果分析

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

3.1　“0/1”平衡隨機性測試

Golomb提出的“序列應滿足的隨機性假設”中第1條要求為：在序列的一個周期內，0和1的個數相差至多為1，即要求0和1出現的概率基本相同.

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

表1　SC-SBH的平衡性測試結果

3.2　游程隨機性測試

Golomb提出的“序列應滿足的隨機性假設”中第2條要求為：長度為T的周期內，任意長度的0的游程個數與1的游程個數相同.

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

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

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

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

表2　SC-SBH的游程測試

3.3　效率性能分析

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

表3　3種算法對明文加密運行的平均時間

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

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

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

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

4結論

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

參考文獻：

[1]William Stallings.密碼編碼學與網絡安全-原理與實踐[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]王相生.序列密碼設計與實現的研究[D].上海：中國科學院上海冶金研究所,2001.

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

[5]張海納.eSTREAM序列密碼候選算法的安全性分析[D].山東：山東大學,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和流密碼分析現狀[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函數在流密碼中的應用[J].通信學報,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]王靜雅.單分組散列函數的設計與應用[D].延吉：延邊大學,2014.

[12]尤加勇.現代序列密碼的設計與分析[D].北京：國防科學技術大學,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.