散列函數在序列密碼中的應用

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

（1.南京郵電大學 計算機學院，江蘇 南京 210003；2.南京郵電大學 計算機學院，江蘇 南京 210046）

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

1 理論支持

1.1 序列密碼

序列密碼的安全強度主要依賴密鑰序列的隨機性，因此，如何設計一個好的密鑰序列產生器，使其產生隨機的密鑰序列是序列密碼體制的關鍵所在。

密鑰序列產生器的主要要求：[10]

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

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

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

(4)利用統計方法由ki提取關于KG結構或K的信息在計算上不可行；

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

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

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

1.2 MD5

MD5算法的輸入是最大長度小于264bit的消息，輸出為128bit的消息摘要。輸入消息以512bit的分組為單位處理。MD5通過直接構造復雜的非線性關系實現單向性。

MD5的主要性質：[6]

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

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

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

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

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

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

2 算法描述

2.1 序列密鑰流的產生

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

2.2 序列密碼的生成

隨機產生20000個0,1數字作為初始密鑰，將初始密鑰與序列密鑰進行按位異或得到序列密碼；解密時將加密得到的序列密碼與序列密鑰按位異或，得到初始密鑰。

2.3 隨機性測試

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

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

3 對隨機性測試的理論分析

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

n=1時，增值表如下：

?

n=2時，增值表如下：

?

n=3時，增值表如下：

?

以此類推，每一列取0和1的個數應該是相同的。由數學歸納法可以得知，若一列中0和1的個數不同，則必然存在重復的現象。由此可以證明密鑰流是隨機的。

下圖為程序測試結果（測試時統計的游程長度為0游程及1游程的總長度，故而區間應乘以2）

4.結論

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

〔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〕范九倫.密碼學基礎.西安電子科技大學出版社,2008.

〔7〕盧開澄.計算機密碼學——計算機網絡中的數據保密與安全(第3版)[M].北京:清華大學出版社,2003.

〔8〕胡予濮.對稱密碼學[M].北京:機械工業出版社,2002.

〔9〕胡向東.應用密碼學教程.電子工業出版社，2005.

〔10〕谷利澤.現代密碼學教程.北京郵電大學出版社,2009.