基于循环替换原理的高性能伪随机序列

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于循环替换原理的高性能伪随机序列范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：在介绍了现有随机序列的优缺点以及分析随机序列主要产生方法的基础上，提出了一种基于循环替换原理的伪随机序列产生方法，并用FPGA加以实现。该方法产生的伪随机序列完全符合FIPS140-2标准，并具有周期长、线性复杂度高、相关性好以及产生时间短的特性,能广泛应用于信息安全等系统中。

关键词：循环；替换；相关性；线性复杂度

中图分类号：TN929-1 文献标识码：B

文章编号：1004373X(2008)0511003

High Performance Pseudorandom Sequence Based on Substitution and Recurrence Structure

CHEN Ruisen1,2

(1.Xiamen Ocean College,Xiamen,361012,China;2.EDA Lab,Department of Physics,Xiamen University,Xiamen,361005,China)

Abstract：Based on the introduction of the merit and shortcoming and the analysis of the generate methods of the main random sequences,we propose a new method which is based on the substitution and recurrence structure,and the method is implemented by FPGA.The generated sequences by this method not only can pass the test of the FIPS 140-2 standard,but also have high performance:long period,high linear complexity,good correlation function value and high generation speed,it can be used widely in information security system and so on.

Keywords：recurrence;substitution;correlation;linear complexity

随机序列在流密码、信道编码、扩频通信等领域有着广泛的应用，特别是在信息安全领域，他是以现代密码学为基础的信息安全系统的基石。几乎所有已知的信息安全体系中的协议和方法都离不开随机序列[1]，因此研制高性能的随机序列显得尤为重要。评价一个伪随机序列优劣的基本准则是伪随机性，现在有许多指标来描述一个周期序列的伪随机性,比如周期、线性复杂度、均衡性、相关性、稳定性等。虽然现在已经研制出一些较高性能的伪随机序列，如m序列、GMW序列以及广义GMW序列等，但他们都还存在一些不足。周期为2n-1的m序列虽具有良好的多维分布和游程分布，但其线性复杂度只有n；GMW序列以及广义GMW序列，虽具有良好自相关特性，也具有良好的多维分布和游程分布,但其线性复杂度也仅仅为n的幂[2]。本文的目标研制出一个高性能的伪随机序列，本序列具有周期长、线性复杂度高、相关性好以及产生时间短、产生方法简单的特性。

1 循环替换的伪随机序列

本文的伪随机序列产生方法是在分析现在主要的3种随机序列产生方法的优缺点的基础上提出来的。现在主要的三种随机序列产生方法[3]是：

基于纯计算机算法的随机序列产生方法 该方法是目前最常用随机序列产生方法，他基于事先确定的序列生成方法，依赖“种子”来产生随机序列，该方法对于给定的输入，具有确定的输出，因此从理论上讲这样的随机序列都是可以预测的，因此被称为“伪随机序列产生方法”；

基于人工的方法 这类方法通过掷硬币、扔股子等随机方式获得随机序列，是目前人工的最安全的随机序列产生方法之一，但这种方法效率极低，不实用，不能适应现代信息安全系统对随机序列产生量的需求；

基于随机噪声发生检测方法 这类随机序列产生方法通过产生、测量自然界的具有高度随机性的噪声信号，但这种产生方法需要信号发生装置，而这些装置结构复杂、操作繁琐、价格高，产生的随机序列效率低、速度慢，不方便也不实用。

考虑到现在存在的一些高性能随机序列生成方法速度慢、效率低，无法满足信息安全系统需求等问题，以及上面分析的后两种方法中存在的局限，所以不再采用后两种方法，采用第一种方法，同时加入一些改进方法，使他产生的序列具备周期足够长，复杂度高、相关性好以及产生时间短的特性，以符合现代信息安全系统的要求。我们采用不可分解多相式式(1)来构造二进制伪随机序列，同时在输出过程中，对固定的输出元素进行替换，采用替换在硬件上实现比较简单：

上面的替换原理其实在以前已经有人做了研究，文献[4]中就对序列中有k个符号替换、插入或删除的情况进行过分析，也有人对单符号替换、插入和删除的情况进行研究，研究表明线性复杂度会有变化(增加或减少)，这就提供了一种提高线性复杂度的可能方法。但如果只对一个周期为N的序列进行替换、插入或删除等变换，线性复杂度的提高是很有限的，并且不能保证线性复杂度一定会提高，还需要加入循环的原理，才可能极大地提高序列的周期和线性复杂度。因为00,01,10,11总共有4×3×2=24种组合方法，所以如果每个周期N的序列用一种组合来替代其中相应的位，那同一个“种子”通过替换原理就可以产生24个不同的序列，把24个序列进行组合，那同一个种子产生序列的周期就可能扩大到24N，线性复杂度也可能大大的提高，仿真实验证明这种方法是可行的，周期扩大到原来的24倍，线性复杂度也大大提高，同时序列还有良好的随机性和相关特性。

2 性能分析

下面将具体分析构造出来的序列的周期、相关特性、随机特性和线性复杂度。

2.1 周期和相关特性

一个序列如果对于所有的i都满足Si=Si+N ,则他的周期为N，经过仿真可以确定，序列的最小周期为24N，达到749 952。同时他具有很好的相关特性，他具有尖锐的自相关特性和几乎处处为零的互相关特性。自相关特性S,S(Γ)检查的是序列和他本身移动Γ位后两序列的一致性情况;互相关特性 S,T(Γ) 检查的是序列S和T序列移动Γ位后的序列的一致性情况。公式S,S(Γ) 定义如下:

表1列出了3个实际仿真值，从这个表中，就可以知道本文构造的序列具有尖锐的自相关特性和几乎处处为零的互相关特性。

2.2 随机性测试

在所有随机序列质量检测方法中，以美国国际技术标准局NIST于2001年5月的关于密码系统的信息安全标准FIPS 140-2[5](Federal Information Processing Publication,FIPS)最为出名。在FIPS 140-2中指定了4种测试方式对随机序列的质量指标进行测试：单比特测试(the monobit test)、扑克测试(the poker test)、游程测试(the runs test)、长游程测试(long runs test)。我们采用FIPS 140-2标准对本文产生的序列进行测试，测试结果全部通过，表2列出了其中的3组测试结果。

2.3 线性复杂度

序列线性复杂度是衡量序列随机性的重要指标，著名的Berlekamp-Massey[6]算法指出，当我们得到一个序列中连续2C(s)个位时(C(s)表示这个序列的复杂度)，就可以知道整个序列。由此可见，一个随机性强的序列必须拥有大的线性复杂度，当然线性复杂度高并不代表着就安全，这还与其他性质有关，如相关性等，在上面已经分析过。现在计算线性复杂度的主要有Chan-Games算法[7]和文献[8]算法等，不同的算法得到的线性复杂度可以差别很大，但从不同的算法得到的线性复杂度的大小可以反映出序列的随机指标。其中Chan-Games算法对周期为2n的序列更加有效，主要应用Chan-Games 算法和文献[8]对我们的序列进行线性复杂度测试。

Chan-Games 算法的基本原理是：如果一个序列具有周期2n，那么可以把这个序列分成两部分S1和S2,S1代表序列的前2n-1位，S2代表序列的后2n -1位，把S1和S2相应位进行相加并对2取余，结果得到一个2n-1位的序列B，如果B为全0的序列，则C(S)=C(S1)=C(S2)，否则C(S)=2n-1+C(B)，依次类推，可得到最后的复杂度。Chan-Games的算法原理决定了他只能具体计算周期2n的序列的线性复杂度，本文序列的周期为749 912，并不符合Chan-Games算法的要求，因此只应用Chan-Games算法对序列的前524 288位(219)的线性复杂度进行计算，前524 288位的线性复杂度就可以反映出本文序列的线性复杂度情况。

文献[8]算法的基本原理是：他对序列的周期没有限制，他先看序列的第一位，第一位前面肯定找不到已经出现和他相同的位，把他看成子序列，然后看第2位，如果前面(第2位的前面)不能找到和他相同的位，则第2位也形成子序列，否则继续看第2位和第3位合起来的两位序列，看前面(第3位以前)的序列中有没有和他们相同的，如果没有则第2位和第3位也形成子序列，如果有的话，则看第2,3,4位合起来的序列的情况，依次类推。例如一个序列为0001101001000101,那么他可以分成以下几个子序列0,001,10,100,1000,101，那么他的线性复杂度可以看成6。表3是采用Chan-Games 算法和文献[8]算法对本文序列的线性复杂度进行计算的结果，从表中可以看出本文的序列具有高的线性复杂度。

以上从3个大的方面对构造出来的序列的性能进行了仿真测试，从上面的结果可以看出，我们构造的序列具有良好的特性。

3 FPGA实现

随机产生器是否容易用硬件来实现也是一个重要的方面，如在信息安全领域，需要加密的数字量是很大的，增长也很快，如果随机序列产生过程以及加密过程能在同一硬件模块中实现，将能更好地节省芯片面积、存储面积、芯片接口以及设计时间等。因此用硬件描述语言对本随机序列产生方法进行描述，进行前仿真，然后综合进行后仿真，最后下载到Xilinx公司的xc2v1000 FPGA上加以验证。现场可编程阵列(FPGA)在电子领域的应用越来越广泛，在很多高速设计和高速测试的场合下，在FPGA中直接构造伪随机序列发生器是一种很好的选择。下面为截取的部分FPGA输出序列。

4 结 语

本文具体提出了一种伪随机序列产生方法，并对由此方法产生的序列进行性能测试，结果显示本文提出的方法是一种高效的伪随机序列产生方法，能满足信息安全等系统的要求。同时本文的结构是一种可扩展的结构，通过不同的代替以及循环机制，还可以产生更大线性复杂度以及周期的序列，具有较好的工程使用价值。

参考文献

［1］Bruce Schneier.Applied Cryptography:Protocols,Algorithms,and Source Code in C [M].Second Edition.New York:John Wiley & Sons,Inc,1996.

［2］胡予濮.一类理想自相关序列的伪随机性[J].电子学报,2003,31(2):245-247.

［3］肖攸安,周祖德.高效真随机序列生成方法的研究[J].计算机工程与应用,2006(16):1-3.

［4］Jiang S,Dai Z,Imamura K.Liner Complexities of a Sequence Obtained from a Periodic Sequence by Either Substituting,Inserting or Deleting k Symbols Within One Period[J].IEEE Transactions on Information Theory,2000,46(3):1 174-1 177.

［5］National Institute of Standards and Technology[S].Federal Information Processing Standards Publication FIPS 140-2:Security Requirements for Cryptographic Modules,2001.

［6］May J L.Shift-Register Synthesis and BCH Decoding[J].IEEE Trans.Inform.Theory,1969,15(1):122-127.

［7］Games R,Chan A.A Fast Algorithm for Determining the Complexity of a Binary Sequence with Period 2n[J].IEEE Trans Inform Theory,1983,29(1):144-146.

［8］[JP2]Abraham Lempel,Jacob ZIV.On the Complexity of Finite Sequences[J].IEEE Trans.Inform.Theory,1976,22(1):75-81.

作者简介

陈瑞森 男， 1981年出生，助教，博士生。主要研究方向为集成电路设计，无线电。

注：“本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。”