吴悠漾 刘祎飞 林旭

【摘要】 随着随机序列在密码学中的应用日益广泛。很多密码算法和协议中都要用到一些随机序列。对一个密码算法来说，其输出序列的随机性是其安全性的很重要的一个方面，因此随机性测试技术在密码学中占有很重要的作用。我们针对改进的RC4算法进行随机序列检测，其中用到的的方法包括FFT和Walsh变换检测等等，通过检测得出的结果从多个方面对算法产生的随机序列进行分析并得出结论。

【关键词】 RC4算法 傅里叶变换 walsh变换

一、引言

1949年Shannon证明了只有一次一密的密码体制才是理论上不可破译的、绝对安全的，这给流密码技术的研究以极大的支持，由此奠定了流密码的发展基石。流密码的安全与否，则取决于密钥发生器生成伪随机数的安全性。

RC4流密码技术是当前应用最为广泛的一种对称密码技术，以随机置换为基础，是一个可变密钥长度、面向字节操作的流密码。

然而RC4却容易受到攻击，现在已经证明在已知RC4的部分密钥的情况下，可以恢复RC4的完整密钥。为了改进RC4算法，我们改变了RC4循环的轮数，对生成的伪随机序列进行了测量，并对产生的伪随机序列做了Walsh和FFT变换。

二、RC4和序列的生成

RC4算法非常简单，易于描述：用从1到256个字节（8到2048位）的可变长度密钥初始化一个256个字节的状态矢量S，S的元素记为S[0]，S[1]，···，S[255]，从始至终置换后的S的包含从0到255的所有8比特数据。对于加密解密，字节K由S中255个元素按一定方式选出一个元素而生成，每生成一个K的值，S中的元素就被重新置换一次。

我们使用相同的密钥（在这里忽略用户输入密钥对产生伪随机序列的影响），改变循环的次数，在程序中统计生成的伪随机序列中0、1所占的比例。当循环数目设置小于256时，0和1在随机序列中所占比例有一定差距，随着循环数目增大0、1分布逐渐平衡。在循环次数等于256时，0、1所占比例基本相等，之后再次增加循环次数对其频率影响不大。

三、随机序列变换及检测

3.1 Walsh变换

沃尔什变换（Walsh transform）是以沃尔什函数为基本函数的一种非正弦正交变换。Walsh函数是二值正交函数，它仅有可能的取值是+1和-1，与数理逻辑的两个状态相对应，更适合计算机处理。Walsh函数变换可以减少存储空间，提高运算的速度。

对不同循环次数的RC4随机矩阵作walsh变换，统计变换矩阵中各值的出现频次，生成直方图。DNA序列由A，T，C，G四对碱基对组成，我们将随机序列处理为1，2，-1，-2的形式，又分别对四种循环次数生成的伪随机序列作walsh变换，生成频数直方图。

3.2快速傅里叶变换

FFT（Fast Fourier Transformation），即为快速傅里叶变换，是离散傅里叶变换（DFT）的快速算法，它是根据离散傅里叶变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。

在本测试中我们分别使用循环64、128、192、256次生成4个不同的2048 bits的-1，1伪随机序列，通过FFT变换后各序列产生频数分布直方图。同样的我们也生成4个不同的1024 bits的DNA伪随机序列，通过FFT变换后各序列产生频数分布直方图。

四、总结

不同循环次数-1，1伪随机序列通过Walsh变换后，其分布趋向于正态分布，其中最接近正太分布的是循环次数为1024的序列；同样的，DNA形式伪随机序列通过Walsh变换后也有相同的规律。两种序列的128次循环分布都较为不均匀，有较多的离群数据。快速傅里叶变换，在循环次数64-256的情况下，不管是-1，1序列还是DNA序列，其虚部的分布都是标准正太分布，而从64到256，循环次数越大实部越接近正态分布。循环次数较小时，-1，1序列的实部会产生小于0的离群数据，而DNA序列的实部会产生大于0的离群数据。

伪随机序列是人为构成的数字序列，因此它是离散的，只包含高低两种电平，不可能具有真正的正态分布特性。但如果序列的长度逼近无限大时，由中心极限定理可知，它趋于正态分布。

在该伪随机序列变换检测中，经过分析，我们认为，RC4产生的-1，1及DNA序列经FFT（快速傅里叶变换）生成的伪随机序列虚部有较好的正太分布特性，符合伪随机序列特性，能够作为安全的序列密码。

参 考 文 献

[1] 对称布尔函数算术Walsh变换的快速算法. 赵庆兰，郑东.西安邮电大学报，19-5，2014.

[2] 基于Walsh谱变换的S盒算法.孙慧盈，陆继承，魏长征，俞军.计算机工程，40-7，2014.

[3] William Stallings. Cryptography and Network Security Principles and Practice，Sixth Edition[M].北京：电子工业出版社，2015：4.

[4] 葉瑞崧，廖海泳.Walsh變换核矩陣的简單生成及其應用[J].汕头：汕头大学数学系，2005.