几类伪随机序列和序列簇的设计与分析
Research on the Design and Analysis of Several Classes of Pseudorandom Sequence and Sequence Families

伪随机序列和序列簇在密码学、扩频通信和纠错码等领域都有广泛的应用,它的设计和分析一直是国际上的研究热点.本文主要研究在密码学和扩频通信领域广泛使用的几类伪随机序列和序列簇的设计与分析.序列密码通常使用一条伪随机序列作为密钥流序列与明文序列逐位异或生成密文,其安全强度取决于相应的密钥流序列的质量,因而产生好的密钥流序列是序列密码的关键.传统的序列密码通常使用LFSR作为密钥源发生器,再通过前馈、钟控或组合等方式获取非线性序列.但由于LFSR产生的序列具有较多的线性性质,因此按照上述方式生成的序列易受到相关攻击和代数攻击的威胁.此外,此类序列密码的软件实现速度慢,不能满足快速加密大量数据的需求.近年来随着计算机技术的迅猛发展,出现了许多基于字运算的序列密码,这些序列密码的软件实现速度快,能够适用于快速加密大量数据的场合.许多这样的序列密码,如在欧洲序列密码方案中提交的ABC、TSC和Mir,均采用单圈T-函数作为密钥源发生器.由于单圈T-函数生成的序列具有可证的长周期性质和良好的分布性质,同时不具有明显的线性结构,从而能够有效地抵制相关攻击和代数攻击,因此单圈T-函数有望代替LFSR成为新型序列密码的密钥源发生器.本文第一部分研究了单字单圈T-函数生成序列的代数结构,具体结果如下:1.证明了Molland关于Klimov-Shamir T-函数f(x)=x+x2∨5 mod 2n生成序列(x0,x1,…)代数结构的四个猜想,这里x表示一个n比特字,v为或运算.从而说明了由此T-函数生成的序列仍然具有简单的代数结构:即第j权位序列相差1/8(或1/16)周期的两个元素[xi]j,[xi+2j-2]j(或[xi]j,[xi+2j-3]j)的异或与[xi]j-1,[xi]j-2(或[xi]j-1,[xi]j-2, [xi]j-3)和[xi]0,[xi]1(或[xi]0,[xi]1,[xi]2)有关,其中[x]j表示字x的第J比特.因此在生成的序列中已知足够长的一段,可以由第j权位序列部分还原较低权位序列的信息,于是截尾的Klimov-Shamir T-函数是不安全的.2.给出了多项式函数为单圈T-函数充要条件的又一证明,接着分析了多项式单圈T-函数生成序列(x0.x1,…)的代数结构,得到此类T-函数生成序列中第j权位序列相差1/4周期的两个元素[xi]j,[xi+2j-1]j的异或等于[xi]j-1与(?)([xi]1,[xi]0)的和(这里ψ是某个逻辑函数).3.综合1和2的研究结果,进一步分析了单字单圈T-函数f(x)=x+γ(x) mod 2n生成序列(x0,x1,…)的代数结构,说明了其复杂程度主要由r(x)决定,这里r(x)是一个偶参数.接着给出了第J权位序列相差1/4周期(或1/8周期)的两个元素[xi]j,[xi+2j-1]j(或[xi]j,[xi+2j-2]j)的异或与元素[xi]j-1,[xi]j-2,…,[xi]0的关系式,该式有助于进一步研究含有单字单圈T-函数序列密码体制的安全性.本文第二部分综合运用有限域、组合数学等理论研究了在异步CDMA通信系统中广泛使用的低相关序列簇的设计和分析,具体结果如下:4.研究了Bent函数的构造,给出了Gold-like项的线性组合构成Bent函数的充要条件,进一步得到了三类可快速生成的Bent函数;分析了Bent序列簇的表达式,由此给出了Bent序列簇的迹表示,并在前面得到的Bent函数基础上构造了可快速生成的Bent序列簇.5.选用Gold-like项的组合构造了四类二次型低相关序列簇S1、S2、S3和S4,其中S1是6-值相关的,对于S2、S3和S4,根据参数的不同选取,S2和S3或是6-值或是8-值相关的,S4或是8-值或是10-值相关的.与Klim和No构造的序列簇相比,这四类序列簇具有更加优良的相关性,同时具有更大的参数选取范围.6.研究了交织低相关序列簇的构造,由两条周期为p和p+2的Legendre序列构造了一类(p(p+2),p+3,3p+4)低相关序列簇,其中p和p+2是一对孪生素数且p≡3 mod 4.该类序列簇在目前已知的序列簇中线性复杂度达到最大.本文第三部分主要研究了在准同步CDMA通信系统中广泛使用的ZCZ序列簇的设计,我们综合了Torii等人和Hayashi构造的ZCZ序列簇的研究结果,着重考虑由初始ZCZ序列簇和正交序列簇通过交织方式生成长周期ZCZ序列簇的构造方式,具体结果如下:7.给出了ZCZ序列簇周期扩展的两种基本方式,即:1.保持序列数目不变,零相关区长度扩展倍数等于周期扩展倍数;2.保持零相关区长度不变或稍稍减少,序列数目扩展倍数等于周期扩展倍数.接着对于这两种周期扩展方式,分别给出了交织ZCZ序列簇的两个构造算法.我们通过D-矩阵控制生成的交织ZCZ序列簇的零相关区长度,并给出了这两种构造算法对应的D-矩阵.8.考虑了在第2种周期扩展方式中选用二元或四元ZCZ序列簇作为初始ZCZ序列簇、周期扩展2e倍的情形,它可以通过两种方式实现:(1)周期扩展2倍递归e次,(2)周期直接扩展2e倍.我们研究了这两种生成方式的区别与联系,证明了方式(1)生成的ZCZ序列簇均可通过方式(2)得到,并给出了两类可由方式(2)生成但不能通过方式(1)得到的ZCZ序列簇.