散列函数在序列密码中的应用

薛 明 ，许迎秋 ，张 妍 ，邱伟星

（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.