散列函數(shù)在序列密碼中的應(yīng)用

薛 明 ，許迎秋 ，張 妍 ，邱偉星

（1.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210003；2.南京郵電大學(xué) 計(jì)算機(jī)學(xué)院，江蘇 南京 210046）

散列函數(shù)和序列密碼在實(shí)際生活中有很多應(yīng)用，為了使其性能得到更好的實(shí)現(xiàn)，將二者通過一定的算法聯(lián)系起來。本文利用散列函數(shù)MD5通過密碼反饋模式產(chǎn)生序列密碼的密鑰，使生成的密鑰序列具有盡可能高的不可預(yù)測性。序列密碼則通過簡單的異或運(yùn)算生成。為確定這樣的運(yùn)算過后得到的序列能達(dá)到隨機(jī)性要求，對產(chǎn)生的序列進(jìn)行了頻率測試及游程測試。

1 理論支持

1.1 序列密碼

序列密碼的安全強(qiáng)度主要依賴密鑰序列的隨機(jī)性，因此，如何設(shè)計(jì)一個好的密鑰序列產(chǎn)生器，使其產(chǎn)生隨機(jī)的密鑰序列是序列密碼體制的關(guān)鍵所在。

密鑰序列產(chǎn)生器的主要要求：[10]

(1)種子密鑰K長度足夠大，一般應(yīng)在128位以上；

(2)密鑰序列ki具有極大周期；

(3)ki具有均勻的n元分布，即在一個周期環(huán)上，某特定形式的n長比特串與其求反比特串，兩者出現(xiàn)的頻率大抵相當(dāng)（如均勻的游程分布）；

(4)利用統(tǒng)計(jì)方法由ki提取關(guān)于KG結(jié)構(gòu)或K的信息在計(jì)算上不可行；

(5)混亂性：即ki的每一比特均與K的大多數(shù)比特有關(guān)；

(6)擴(kuò)散性：即K任一比特的改變要引起ki在全貌上的變化；

(7)密鑰序列ki不可預(yù)測，密文及相應(yīng)的明文的部分信息，不能確定整個ki.

1.2 MD5

MD5算法的輸入是最大長度小于264bit的消息，輸出為128bit的消息摘要。輸入消息以512bit的分組為單位處理。MD5通過直接構(gòu)造復(fù)雜的非線性關(guān)系實(shí)現(xiàn)單向性。

MD5的主要性質(zhì)：[6]

(1)對“任意”給定的消息x,計(jì)算H(x)比較容易，用硬件和軟件均可實(shí)現(xiàn)；

(2)單向性：又稱抗原像性，對任意給定的散列值h，找到滿足H(x)=h的消息x在計(jì)算上是不可行的；

(3)抗弱碰撞性：又稱為抗第二原像性，對任何給定的消息x,找到滿足y≠x且H(x)=H(y)的消息y在計(jì)算上是不可行的；

(4)抗強(qiáng)碰撞性：找到任何滿足H(x)=H(y)的偶對（x,y）在計(jì)算上是不可行的；

(5)雪崩效應(yīng)：即消息的散列值的每一比特應(yīng)與消息的每一比特有關(guān)聯(lián)。MD5在MD4的基礎(chǔ)上增加了計(jì)算輪數(shù)，增加了一種邏輯運(yùn)算，對步函數(shù)及每輪的循環(huán)左移位移量做了優(yōu)化，實(shí)現(xiàn)了更快的“雪崩效應(yīng)”，雖然速度較MD4降低了近30%，但在抗安全性分析方面表現(xiàn)的更好。

由于MD5的輸出只有128比特，而它的輸入為512比特，為了保證產(chǎn)生的序列密鑰的抗碰撞性及大周期，還需要增加一些比特與上一輪MD5的輸出一起送到下一輪MD5的輸入,確保每次的輸入都不相同，從而保證序列密鑰具有大周期。

2 算法描述

2.1 序列密鑰流的產(chǎn)生

程序運(yùn)行時輸入一個字符串，該字符串作為MD5的初始輸入，每次從MD5的輸出中取出第45位保存到數(shù)組中組成序列密鑰。（由于MD5是以十六進(jìn)制形式輸出的，在進(jìn)行此項(xiàng)操作前應(yīng)先進(jìn)行十六進(jìn)制到二進(jìn)制的轉(zhuǎn)換。）循環(huán)時將本次的循環(huán)數(shù)i轉(zhuǎn)換成二進(jìn)制與MD5的128比特輸出連接起來，作為下一次循環(huán)時MD5的輸入，以確保產(chǎn)生的序列密鑰具有大周期。

2.2 序列密碼的生成

隨機(jī)產(chǎn)生20000個0,1數(shù)字作為初始密鑰，將初始密鑰與序列密鑰進(jìn)行按位異或得到序列密碼；解密時將加密得到的序列密碼與序列密鑰按位異或，得到初始密鑰。

2.3 隨機(jī)性測試

均勻性測試：統(tǒng)計(jì)序列密鑰中0和1的個數(shù)，檢測0和1的個數(shù)是否大致相等。統(tǒng)計(jì)量X=(k0k1)2/n2.當(dāng)n大于等于10時，該統(tǒng)計(jì)量近似服從自由度為1的χ2分布。對于顯著性水平α=0.05，統(tǒng)計(jì)量X的閾值為3.8415.

游程測試：在真正的隨機(jī)位序列中，游程的長度應(yīng)是隨機(jī)分布的。測試20000個二進(jìn)制位，先計(jì)算各種長度的游程個數(shù)，如果每個游程的數(shù)量位都位于區(qū)間內(nèi)，那么該序列位（0序列位或1序列位）就通過了此測試。

3 對隨機(jī)性測試的理論分析

由于每次輸入都不相同，在理想狀況下（即無碰撞），輸出應(yīng)有2128種情況。

n=1時，增值表如下：

?

n=2時，增值表如下：

?

n=3時，增值表如下：

?

以此類推，每一列取0和1的個數(shù)應(yīng)該是相同的。由數(shù)學(xué)歸納法可以得知，若一列中0和1的個數(shù)不同，則必然存在重復(fù)的現(xiàn)象。由此可以證明密鑰流是隨機(jī)的。

下圖為程序測試結(jié)果（測試時統(tǒng)計(jì)的游程長度為0游程及1游程的總長度，故而區(qū)間應(yīng)乘以2）

4.結(jié)論

本文提出利用MD5作為密鑰產(chǎn)生器來產(chǎn)生一個序列密鑰流，并對產(chǎn)生的密鑰流進(jìn)行隨機(jī)性檢測。事實(shí)表明，MD5作為序列密鑰發(fā)生器產(chǎn)生的序列密鑰滿足大周期及隨機(jī)性，且計(jì)算速度很快（整個程序運(yùn)行的時間約是兩秒），具備了實(shí)際應(yīng)用價值。

〔1〕National Bureau of Standards.Data Encryption Standard,U.S.Department of Commerce,FIPS pub.46,January 1977.

〔2〕W.Diffie,M.Hellman.Exhaustive Cryptanalysisofthe NBS DataEncryption Standard[J].IEEE Computer,1977.

〔3〕Mitsuru Matsui.Linear Cryptanalysis Method for DES Cipher[J].Lecture Notes in Computer Science,1994.

〔4〕Chaum D.Blind Signatures for untraceable payments.Advances in Cryptology Crypto，82，LNCS[C],1982:199-203.

〔5〕ElGamal T.A public key cryptosystem and a signature scheme based on discrete logarithms.IEEE Trans.Information Theory,1985,IT-314:469-472.

〔6〕范九倫.密碼學(xué)基礎(chǔ).西安電子科技大學(xué)出版社,2008.

〔7〕盧開澄.計(jì)算機(jī)密碼學(xué)——計(jì)算機(jī)網(wǎng)絡(luò)中的數(shù)據(jù)保密與安全(第3版)[M].北京:清華大學(xué)出版社,2003.

〔8〕胡予濮.對稱密碼學(xué)[M].北京:機(jī)械工業(yè)出版社,2002.

〔9〕胡向東.應(yīng)用密碼學(xué)教程.電子工業(yè)出版社，2005.

〔10〕谷利澤.現(xiàn)代密碼學(xué)教程.北京郵電大學(xué)出版社,2009.