关于m-序列模加实现的自缩序列

王锦玲，邹慧仙

WANG Jinling，ZOU Huixian

郑州大学 数学与统计学院，郑州 450001

School of Mathematics and Statistics,Zhengzhou University,Zhengzhou 450001,China

1 概述

自缩序列是一类重要的伪随机序列，而周期和线性复杂度是序列伪随机特性的经典度量。GF(3)上如何构造自缩序列的新模型使生成序列具有大的周期和高的线性复杂度，是研究序列密码安全性的标准。

自缩序列由Meier 和Staffelbach[1]提出，由于自缩序列生成方式结构简单，具有良好的伪随机性，成为序列密码研究的热点；文献[2-4]给出了比文献[1]更好的周期和线性复杂度界值，但“自缩序列”的结构过于简单，密钥流选择受到限制；基于此文献[5-7]将“自缩序列”扩展在GF(3)上，得到的自缩序列比文献[1-4]中有更高的周期和线性复杂度的界值，但以文献[7]中“自缩序列”的生成方式为例。

若a∞=(a0,a1,a2…)是GF(3)上一n级m-序列，将a∞的输出比特依次排列如下：

a∞=(a0,a1,a2)(a3,a4,a5)…(a3k,a3k+1,a3k+2)…

若a3k=0，则不输出a3k所在括号内的所有比特；若a3k=1，则输出a3k+1；若a3k=2，则输出a3k+1，a3k+2，如此得到的序列记为SS3-序列。在文献[7]中虽然当a3k=2时，输出两个比特对原有信息利用率低有所弥补，但当a3k=0 时，a∞收缩过快过多。本文在GF(3)上重构新型自缩序列模型，首次对输出比特进行模加改变，根据模加数值来决定输出比特，这样得到的自缩序列周期上界为3n，下界为；线性复杂度上界为3n，下界为。而对于基于本原三项式和四项式的自缩序列的周期达到线性复杂度下界的概率改进为8 9 和5 6，比文献[6]中自缩序列的平衡性强，信息利用率平稳，更好地弥补了文献[7]中自缩序列收缩过快过多的不足，使得新型自缩序列保持原有序列大的周期和高的线性复杂度。

引理1设a∞=(a0,a1,a2…) 是GF(3) 上一n级m-序列，对于0 ＜k≤n，GF(3)上任意k元组(b1,b2,…,bk)在a∞的一个周期中出现的次数：

引理2设a∞=(a0,a1,a2…)是GF(3)上一n级m-序列，则有：

（1）序列a∞的最小周期是3n-1。

（2）序列a∞是平衡的，即在a∞的一个周期内，1、2各出现3n-1次，0 出现3n-1-1 次。

2 GF(3)上模加实现的自缩序列

2.1 模加实现自缩序列模型的构造

设a∞=(a0,a1,a2…)是GF(3)上一n级m-序列，将a∞的输出比特依次排列如下：

a∞=(a0,a1,a2)(a3,a4,a5)…(a3k,a3k+1,a3k+2)…

若a3k⊕a3k+1=0，则不输出a3k所在括号内的所有比特；若a3k⊕a3k+1=1，则输出a3k+1；若a3k⊕a3k+1=2，则输出a3k+1，a3k+2，这样得到的序列z∞称为扩展在GF(3)上a∞的模3-自缩序列，记为SS3(模3)-序列。

2.2 SS3(模3)-序列z∞的周期和线性复杂度

设a∞=(a0,a1,a2…)是GF(3)上一n级m-序列，将a∞的输出比特依次分组如下：

(a0,a1,a2)…(a3n-3,a3n-2,a3n-1)(a1,a2,a3)…(a3n-5,a3n-4,a3n-3)(a3n-2,a0,a1)…(a3n-4,a3n-3,a3n-2)(a0,a1,a2)…

由此看到，把序列a∞的三个周期内输出比特依次分组排列后，(a0,a1,a2)重复出现，因此SS3(模3)-序列z∞是周期的。由三元组组合的知识可得以下结论。

定理1设a∞=(a0,a1,a2…)是GF(3)上一n级m-序列，z∞为a∞导出的SS3(模3)-序列，则p(z∞)/3n。

定理2SS3(模3)-序列的最小周期。

由以上结果可以看出：SS3(模3)-序列z∞的周期和线性复杂度的界以3 的指数倍增加，保持了文献[6]中SS3-序列的周期和线性复杂度。文献[6]中自缩序列模型是根据a3k的取值来决定该括号内的输出比特个数，而SS3(模3)-序列模型是根据a3k⊕a3k+1（模3）的取值决定该括号内的输出比特个数，更好地弥补了a3k=0 时a∞收缩过快过多的不足，提高了原有的信息利用率，所得到的自缩序列整体上的平衡性更优。

3 GF(3)上本原三项式和本原四项式SS3(模3)-序列的周期和线性复杂度

3.1 基于本原三项式SS3(模3)-序列的周期和线性复杂度

下面考虑GF(3) 基于n次本原三项式f(x)=xn+c1xk+c0的LFSR序列，由此导出的SS3(模3)-序列的周期和线性复杂度。

定理3基于GF(3)上的n次本原三项式f(x)=xn+c1xk+c0，a∞是由f(x)生成的m-序列，又若在a∞导出的序列z∞中，至少出现长为的1-游程（或2-游程，或0-游程），则。

证明设，由定理2 知，即z∞中长为m的所有状态都出现。又若在z∞中出现连续m+1 个1（或0 或2），在序列a∞的一个周期内至少出现了两次，所以p(z∞)≥3m+1。

由定理1 知，p(z∞)/3n，因此。

证明以下设。

n=3r：

（1）c0,c1都是1

（2）c0=c1=2,k=3s或c0=1,c1=2,k=3s或k=3s+1

（3）c0=c1=2,k=3s+1或c0=2,c1=1,k=3s+1

（4）c0=c1=2,k=3s+2

（5）c0=2,c1=1,且k=3s

（6）c0=2,c1=1,且k=3s+2

在以下情形下：

（1）n=3r+1，c0,c1全部为1 或全部为2。

（2）n=3r+1，k=3s，c0,c1中有一个为1。

（3）n=3r+2，k是小于n的任意正整数。

均可适当选取a∞的n元初态，使得。

因此对于任意的n次本原三项式生成的LFSR 序列a∞所导出的对应自缩序列z∞，易得的概率约为8 9，且易得时，。

3.2 基于本原四项式的SS3(模3)-序列的周期和线性复杂度

下面考虑的GF(3) 上基于n次本原四项式f(x)=xn+c2xm+c1xl+c0(n＞m＞l)生成的LFSR 序列a∞所导出的SS3(模3)-序列z∞的周期和线性复杂度，虽然分析和计算上更加困难和复杂，但通过分析计算仍然可以得到z∞的周期和线性复杂度的下界，由于篇幅较长，这里只给出结论，不予证明。

定理5设f(x)=xn+c2xm+c1xl+c0(n＞m＞l)是GF(3)上的本原四项式，r是正整数，a∞是由f(x)生成的m-序列，z∞是由a∞导出的SS3(模3)-序列，在下列情形下，则p(z∞)≥3d+1，其中。

在下列情形下：

（1）n=3r，c0,c1,c2全部为2，m=3s或m=3s+2 且l=3h+2。

（2）n=3r，c0,c1,c2全部为1，m=3s+1，l=3h+2或m=3s+2，l=3h+1。

（3）n=3r,c0,c1，c2全部为1 或全部为2，m=3s，l=3h+1。

（4）n=3r,c0,c1，c2全部为1或全部为2，m=3s+1，l=3h或l=3h+1。

（5）n=3r，c0,c1,c2中有一个为2，m=3s，l=3h。

（6）n=3r，m=3s，l=3h+1，c0=2 或c1=2。

（7）n=3r，c1=2，l=3h+2，m=3s或m=3s+1。

（8）n=3r，c0,c1,c2中有一个为2，m=3s+1，l=3h+1。

（9）n=3r，c2=2，m=3s+2。

（10）n=3r，c0,c1,c2中有一个为1。

（11）n=3r+1,c0,c1，c2全部为1 或全部为2。

（12）n=3r+1,c0,c1，c2中有一个为2。

（13）n=3r+1,c0,c1，c2中有一个为1。

（14）n=3r+2，m，l是小于n的任意正整数。均可适当选取a∞的初态，得到p(z∞)≥3d+1。

从以上分析可以得出：当n=3r和n=3r+1 时，由任意的n次本原四项式生成的LFSR 序列a∞所导出的对应自缩序列z∞的周期的概率约为3 4，而当n=3r+2 时，的概率为1，因此对于任意的n次本原四项式生成的LFSR 序列a∞所导出的对应自缩序列z∞的周期的概率约为，易得当时，。

4 结束语

周期和线性复杂度是度量序列安全性的两个重要指标，由以上结论可以看出：SS3(模3)-序列与文献[7]中SS3-序列保持了相同的周期和线性复杂度下界，且均比文献[5]中多位自缩MSS3-序列的周期和线性复杂度更优。GF( 3) 上基于本原三项式和四项式的LFSR 序列a∞导出的SS3-序列z∞的周期和线性复杂度的3 倍的概率分别为8 9 和5 6。由此模加实现生成的SS3(模3)-序列在模型构造上克服了多位自缩生成器生成序列在a3k=0时，收缩过快、过多的不足，序列平衡性更优。所以GF(3)上的模加实现的新型自缩序列是更适合流密码应用的伪随机序列。表1 将SS3(模3)-序列的周期、线性复杂度和收缩率与SS3-序列及MSS3-序列进行详细比较。

表1 MSS3-序列、SS3-序列、SS3（模3）-序列对比表

由表1 可以看出新型自缩序列生成方式的改变，利用模加快速实现的方式使新型SS3(模3)-序列周期、线性复杂度和收缩率比文献[6]更优，在保持文献[7]SS3-序列的周期、线性复杂度界值和收缩率比例的情况下，对达到更优的周期、线性复杂度界值概率有进一步的改善；基于一般本原多项式的周期和线性复杂度更精确的界值，有待于寻求新的方法解决。

[1] Meier W，Staffelbach O.The self-shrinking generator[C]//LNCS 950：Advances in Cryptology Eurocrypt’94.Berlin：Springer-Verlag，1995：205-214.

[2] Blackburn S R.The linear complexity of the self-shrinking generator[J].IEEE Transactions on Information Theory，1999，45（6）：2073-2077.

[3] 张楠，戚文峰.基于三项和五项本原多项式的Self-Shrinking序列[J].信息工程大学学报，2004，5（2）：4-8.

[4] Kanso A.Modified self-shrinking generator[J].Computers and Engineering，2010，36（9）：993-1001.

[5] 王锦玲.多位Self-Shrinking 序列模型与研究[J].郑州大学学报，1998，19（2）：119-122.

[6] 王锦玲，王娟，陈忠宝.GF(3)上多位自收缩序列的模型与研究[C]//密码学进展-ChinaCrypt 2007.成都：西南交通大学出版社，2007：299-300.

[7] 王锦玲，陈亚华，兰娟丽.扩展在GF(3)上新型自缩序列模型及研究[J].计算机工程与应用，2009，45（35）：114-119.

[8] 王锦玲，陈亚华，孙海峰.GF(q)上新型自收缩序列模型及研究[J].通信技术，2009，42（9）：74-76.