王錦玲，鄒慧仙

WANG Jinling，ZOU Huixian

鄭州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，鄭州 450001

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

1 概述

自縮序列是一類重要的偽隨機(jī)序列，而周期和線性復(fù)雜度是序列偽隨機(jī)特性的經(jīng)典度量。GF(3)上如何構(gòu)造自縮序列的新模型使生成序列具有大的周期和高的線性復(fù)雜度，是研究序列密碼安全性的標(biāo)準(zhǔn)。

自縮序列由Meier 和Staffelbach[1]提出，由于自縮序列生成方式結(jié)構(gòu)簡(jiǎn)單，具有良好的偽隨機(jī)性，成為序列密碼研究的熱點(diǎn)；文獻(xiàn)[2-4]給出了比文獻(xiàn)[1]更好的周期和線性復(fù)雜度界值，但“自縮序列”的結(jié)構(gòu)過(guò)于簡(jiǎn)單，密鑰流選擇受到限制；基于此文獻(xiàn)[5-7]將“自縮序列”擴(kuò)展在GF(3)上，得到的自縮序列比文獻(xiàn)[1-4]中有更高的周期和線性復(fù)雜度的界值，但以文獻(xiàn)[7]中“自縮序列”的生成方式為例。

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

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

若a3k=0，則不輸出a3k所在括號(hào)內(nèi)的所有比特；若a3k=1，則輸出a3k+1；若a3k=2，則輸出a3k+1，a3k+2，如此得到的序列記為SS3-序列。在文獻(xiàn)[7]中雖然當(dāng)a3k=2時(shí)，輸出兩個(gè)比特對(duì)原有信息利用率低有所彌補(bǔ)，但當(dāng)a3k=0 時(shí)，a∞收縮過(guò)快過(guò)多。本文在GF(3)上重構(gòu)新型自縮序列模型，首次對(duì)輸出比特進(jìn)行模加改變，根據(jù)模加數(shù)值來(lái)決定輸出比特，這樣得到的自縮序列周期上界為3n，下界為；線性復(fù)雜度上界為3n，下界為。而對(duì)于基于本原三項(xiàng)式和四項(xiàng)式的自縮序列的周期達(dá)到線性復(fù)雜度下界的概率改進(jìn)為8 9 和5 6，比文獻(xiàn)[6]中自縮序列的平衡性強(qiáng)，信息利用率平穩(wěn)，更好地彌補(bǔ)了文獻(xiàn)[7]中自縮序列收縮過(guò)快過(guò)多的不足，使得新型自縮序列保持原有序列大的周期和高的線性復(fù)雜度。

引理1設(shè)a∞=(a0,a1,a2…) 是GF(3) 上一n級(jí)m-序列，對(duì)于0 ＜k≤n，GF(3)上任意k元組(b1,b2,…,bk)在a∞的一個(gè)周期中出現(xiàn)的次數(shù)：

引理2設(shè)a∞=(a0,a1,a2…)是GF(3)上一n級(jí)m-序列，則有：

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

（2）序列a∞是平衡的，即在a∞的一個(gè)周期內(nèi)，1、2各出現(xiàn)3n-1次，0 出現(xiàn)3n-1-1 次。

2 GF(3)上模加實(shí)現(xiàn)的自縮序列

2.1 模加實(shí)現(xiàn)自縮序列模型的構(gòu)造

設(shè)a∞=(a0,a1,a2…)是GF(3)上一n級(jí)m-序列，將a∞的輸出比特依次排列如下：

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

若a3k⊕a3k+1=0，則不輸出a3k所在括號(hào)內(nèi)的所有比特；若a3k⊕a3k+1=1，則輸出a3k+1；若a3k⊕a3k+1=2，則輸出a3k+1，a3k+2，這樣得到的序列z∞稱為擴(kuò)展在GF(3)上a∞的模3-自縮序列，記為SS3(模3)-序列。

2.2 SS3(模3)-序列z∞的周期和線性復(fù)雜度

設(shè)a∞=(a0,a1,a2…)是GF(3)上一n級(jí)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∞的三個(gè)周期內(nèi)輸出比特依次分組排列后，(a0,a1,a2)重復(fù)出現(xiàn)，因此SS3(模3)-序列z∞是周期的。由三元組組合的知識(shí)可得以下結(jié)論。

定理1設(shè)a∞=(a0,a1,a2…)是GF(3)上一n級(jí)m-序列，z∞為a∞導(dǎo)出的SS3(模3)-序列，則p(z∞)/3n。

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

由以上結(jié)果可以看出：SS3(模3)-序列z∞的周期和線性復(fù)雜度的界以3 的指數(shù)倍增加，保持了文獻(xiàn)[6]中SS3-序列的周期和線性復(fù)雜度。文獻(xiàn)[6]中自縮序列模型是根據(jù)a3k的取值來(lái)決定該括號(hào)內(nèi)的輸出比特個(gè)數(shù)，而SS3(模3)-序列模型是根據(jù)a3k⊕a3k+1（模3）的取值決定該括號(hào)內(nèi)的輸出比特個(gè)數(shù)，更好地彌補(bǔ)了a3k=0 時(shí)a∞收縮過(guò)快過(guò)多的不足，提高了原有的信息利用率，所得到的自縮序列整體上的平衡性更優(yōu)。

3 GF(3)上本原三項(xiàng)式和本原四項(xiàng)式SS3(模3)-序列的周期和線性復(fù)雜度

3.1 基于本原三項(xiàng)式SS3(模3)-序列的周期和線性復(fù)雜度

下面考慮GF(3) 基于n次本原三項(xiàng)式f(x)=xn+c1xk+c0的LFSR序列，由此導(dǎo)出的SS3(模3)-序列的周期和線性復(fù)雜度。

定理3基于GF(3)上的n次本原三項(xiàng)式f(x)=xn+c1xk+c0，a∞是由f(x)生成的m-序列，又若在a∞導(dǎo)出的序列z∞中，至少出現(xiàn)長(zhǎng)為的1-游程（或2-游程，或0-游程），則。

證明設(shè)，由定理2 知，即z∞中長(zhǎng)為m的所有狀態(tài)都出現(xiàn)。又若在z∞中出現(xiàn)連續(xù)m+1 個(gè)1（或0 或2），在序列a∞的一個(gè)周期內(nèi)至少出現(xiàn)了兩次，所以p(z∞)≥3m+1。

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

證明以下設(shè)。

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中有一個(gè)為1。

（3）n=3r+2，k是小于n的任意正整數(shù)。

均可適當(dāng)選取a∞的n元初態(tài)，使得。

因此對(duì)于任意的n次本原三項(xiàng)式生成的LFSR 序列a∞所導(dǎo)出的對(duì)應(yīng)自縮序列z∞，易得的概率約為8 9，且易得時(shí)，。

3.2 基于本原四項(xiàng)式的SS3(模3)-序列的周期和線性復(fù)雜度

下面考慮的GF(3) 上基于n次本原四項(xiàng)式f(x)=xn+c2xm+c1xl+c0(n＞m＞l)生成的LFSR 序列a∞所導(dǎo)出的SS3(模3)-序列z∞的周期和線性復(fù)雜度，雖然分析和計(jì)算上更加困難和復(fù)雜，但通過(guò)分析計(jì)算仍然可以得到z∞的周期和線性復(fù)雜度的下界，由于篇幅較長(zhǎng)，這里只給出結(jié)論，不予證明。

定理5設(shè)f(x)=xn+c2xm+c1xl+c0(n＞m＞l)是GF(3)上的本原四項(xiàng)式，r是正整數(shù)，a∞是由f(x)生成的m-序列，z∞是由a∞導(dǎo)出的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中有一個(gè)為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中有一個(gè)為2，m=3s+1，l=3h+1。

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

（10）n=3r，c0,c1,c2中有一個(gè)為1。

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

（12）n=3r+1,c0,c1，c2中有一個(gè)為2。

（13）n=3r+1,c0,c1，c2中有一個(gè)為1。

（14）n=3r+2，m，l是小于n的任意正整數(shù)。均可適當(dāng)選取a∞的初態(tài)，得到p(z∞)≥3d+1。

從以上分析可以得出：當(dāng)n=3r和n=3r+1 時(shí)，由任意的n次本原四項(xiàng)式生成的LFSR 序列a∞所導(dǎo)出的對(duì)應(yīng)自縮序列z∞的周期的概率約為3 4，而當(dāng)n=3r+2 時(shí)，的概率為1，因此對(duì)于任意的n次本原四項(xiàng)式生成的LFSR 序列a∞所導(dǎo)出的對(duì)應(yīng)自縮序列z∞的周期的概率約為，易得當(dāng)時(shí)，。

4 結(jié)束語(yǔ)

周期和線性復(fù)雜度是度量序列安全性的兩個(gè)重要指標(biāo)，由以上結(jié)論可以看出：SS3(模3)-序列與文獻(xiàn)[7]中SS3-序列保持了相同的周期和線性復(fù)雜度下界，且均比文獻(xiàn)[5]中多位自縮MSS3-序列的周期和線性復(fù)雜度更優(yōu)。GF( 3) 上基于本原三項(xiàng)式和四項(xiàng)式的LFSR 序列a∞導(dǎo)出的SS3-序列z∞的周期和線性復(fù)雜度的3 倍的概率分別為8 9 和5 6。由此模加實(shí)現(xiàn)生成的SS3(模3)-序列在模型構(gòu)造上克服了多位自縮生成器生成序列在a3k=0時(shí)，收縮過(guò)快、過(guò)多的不足，序列平衡性更優(yōu)。所以GF(3)上的模加實(shí)現(xiàn)的新型自縮序列是更適合流密碼應(yīng)用的偽隨機(jī)序列。表1 將SS3(模3)-序列的周期、線性復(fù)雜度和收縮率與SS3-序列及MSS3-序列進(jìn)行詳細(xì)比較。

表1 MSS3-序列、SS3-序列、SS3（模3）-序列對(duì)比表

由表1 可以看出新型自縮序列生成方式的改變，利用模加快速實(shí)現(xiàn)的方式使新型SS3(模3)-序列周期、線性復(fù)雜度和收縮率比文獻(xiàn)[6]更優(yōu)，在保持文獻(xiàn)[7]SS3-序列的周期、線性復(fù)雜度界值和收縮率比例的情況下，對(duì)達(dá)到更優(yōu)的周期、線性復(fù)雜度界值概率有進(jìn)一步的改善；基于一般本原多項(xiàng)式的周期和線性復(fù)雜度更精確的界值，有待于尋求新的方法解決。

[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] 張楠，戚文峰.基于三項(xiàng)和五項(xiàng)本原多項(xiàng)式的Self-Shrinking序列[J].信息工程大學(xué)學(xué)報(bào)，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].鄭州大學(xué)學(xué)報(bào)，1998，19（2）：119-122.

[6] 王錦玲，王娟，陳忠寶.GF(3)上多位自收縮序列的模型與研究[C]//密碼學(xué)進(jìn)展-ChinaCrypt 2007.成都：西南交通大學(xué)出版社，2007：299-300.

[7] 王錦玲，陳亞華，蘭娟麗.擴(kuò)展在GF(3)上新型自縮序列模型及研究[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（35）：114-119.

[8] 王錦玲，陳亞華，孫海峰.GF(q)上新型自收縮序列模型及研究[J].通信技術(shù)，2009，42（9）：74-76.