Fp上周期序列S∞與S*∞的線性復雜度分析

摘 要:周期序列的線性復雜度是衡量密鑰序列偽隨機性的重要指標，周期序列的線性復雜度可以通過周期序列的極小多項式的次數求出。研究了有限域Fp上周期序列S∞的極小多項式的次數和由S∞及其對偶序列定義的一類新序列S*∞的極小多項式的次數之間的關系，建立了明確的關系式。這些結果對研究流密碼密鑰序列有一定的應用價值。

關鍵詞:線性復雜度; 極小多項式; 周期序列; 流密碼

中圖分類號:TN918.1文獻標志碼:A

文章編號:1001-3695(2010)06-2297-02

doi:10.3969/j.issn.10013695.2010.06.086

Complexity of periodic sequences S∞ and S*∞over Fp

WANG Jun， ZHU Shixin

(School of Mathematics， Hefei University of Technology， Hefei 230009， China)

Abstract:Linear complexity is the most important standards to scale the randomness properties of sequences. It can be achieved by using the minimum polynomials .This paper presentedthe relation between minimumpolynomials of periodic sequences S∞and S*∞over field Fp，respectively. The relationpresented can be used to analyze the complexity of periodic sequences of stream ciphers over Fp.

Key words:linear complexity; minimum polynomial; periodic sequence; stream cipher

0 引言

周期序列的線性復雜度是度量流密碼強度的一個重要指標 ，序列S∞=(s0，s1，…，sN-1…)的線性復雜度定義為生成它的最小線性反饋移位寄存器的長度， 記LC(S)。從線性復雜度的定義可知，如果一個序列的線性復雜度為L，則只需知道該序列的任意2L個連續元素，即可通過解線性方程組或借助BM算法[1，2]，找到該序列所滿足的齊次線性遞歸關系式，進而可確定整個序列。這說明密鑰流序列的齊次線性復雜度必須足夠大，才能保證流密碼系統的安全性。因而線性復雜度是度量密鑰流序列的密碼強度的一個重要指標，但是線性復雜度高的序列未必是好的密鑰流序列。例如，SN=(0，0，0，…，0，1)，LC(SN)=N，但只要把序列中的一個字節“1”改為“0”，序列的線性復雜度序列的線性復雜度就降為0。 由文獻[3]知fs(x)是生成SN的極小多項式則序列的線性復雜度為LC(SN)=deg(fs(x))， 由此可見討論序列的極小多項式具有十分重要的意義。 由于序列S*∞是一類特殊的序列，且與S∞有著密切的關系，則研究S∞的極小多項式有一定的應用價值。 文獻 [4] 討論了F2上的序列S∞與其對偶序列S∞的生成函數及極小多項式之間的關系。 文獻 [5] 討論了Fp上的序列S∞與其對偶序列S∞的生成函數及極小多項式之間的關系。 本文將討論Fp上序列S∞與序列S∞的生成函數及極小多項式之間的關系，以期獲得這類新序列的線性復雜度。

1 預備知識

設sN表示有限域Fp上有限序列(s0，s1，…，sN-1)，s∞表示有限域Fp上無限序列(s0，s1，…，sN-1…)，設有整數L和Fp上一組數c1，c2，…，cL，使sN( 或s∞)滿足

sj+c1sj-1+c2sj-2+…+cLsj-L=0，j≥L(1)

則稱sN( 或s∞)是一個L階齊次線性遞歸序列，L是sN( 或s∞)所滿足的齊次線性遞歸關系的最小階數，成為sN( 或s∞)的線性復雜度，記為LC(sN)( 或LC(s∞))。

對于序列s∞和sN，它們的生成函數定義為

s(x)=s0+s1x+…+sN-1xN-1+…=∑∞i=osixisN(x)=s0+s1x+…+sN-1xN-1=∑Ni=0sixi

如果s∞是周期為N的序列，sN是它的第一個周期， 則s(x)=sN(x)(1+xN+x2N+…)=sN(x)/(1-xN)，則s(x)可以表示成

s(x)=[sN(x)/gcd(sN(x)，1-xN)]/

[(1-xN)/gcd(sN(x)，1-xN)]=r(x)/fs(x)

其中:fs(x)=(1-xN)/gcd(sN(x)，1-xN)，rs(x)=sN(x)/gcd(sN(x)，1-xN)。顯然rs(x)/fs(x)是既約的，deg(rs(x))

定義1 設s∞是滿足式(1)的p元序列，則f(x)=c0+c1x+…+cLxL為s∞的一個特征多項式或生成多項式。其中c0=0，ci∈Fp，i=1，2，…，L，且cL≠0。s∞的生成多項式中次數最小的多項式稱為s∞的極小多項式，并記為fs(x)。s∞所對應的生成函數為S(x)=∑∞i=0sixi。

定義2[5] 設Fp上p 元序列s∞=(s0，s1，s2，…)，稱s∞=(s0，s1，s2，…)為s∞對偶序列。其中si=(p-1)-si，i=0，1，2，…。

引理1 設s∞是周期為N的序列，則其生成函數可表示為s(x)=∑∞i=0sixi=rs(x)/fs(x)。(rs(x)=sN(x)/gcd(sN(x)，1-xN)，fs(x)=(1-xN)/gcd(sN(x)，1-xN)，sN(x)=s0+s1x+…+sN-1xN-1，且S∞的極小多項式為fs(x)=(1-xN)/gcd(SN(x)，1-xN))

周期序列生成函數的既約有理表達式是惟一的，而既約有理表達式的分母一定是其序列的極小多項式，對于Fp上的序列s∞與其對偶序列s∞的生成函數、極小多項式有如下關系:

定理1[5] 設Fp上周期序列s∞的極小多項式為fs(x)=(1-x)tg(x)。其中t為非負整數，且g(1)≠0，s∞的生成函數s(x)=∑∞i=0sixi=rs(x)/fs(x)，(gcd(rs(x)，fs(x))=1)則s∞的對偶序列s∞的生成函數為

S(x)=[(p-1)fs(x)-rs(x)(1-x)]/[(1-x)fs(x)]=

(p-1)g(x)-rs(x)(1-x)(1-x)g(x)，t=0

(p-1)(1-x)g(x)-rs(x)(1-x)(1-x)2g(x)，t=1

(p-1)(1-x)tg(x)-rs(x)(1-x)(1-x)t+1g(x)，t≥2

S∞的極小多項式為

fS(x)=(1-x)fS(x)，t=0[1/(1-x)]#8226;fS(x)，g(1)+rS(1)=p，t=1

fS(x)，g(1)+rS(1)≠p，t=1

fS(x)，t≥2

2 主要結論

設在Fp上 ，周期為N的p元序列s∞=(s0，s1，…)和s∞=(s0，s1，…)，合并為S*∞(x)=(s0，s1，…，sN-1，s0，s1，…，sN-1，…)， 則S*∞為一類新序列，其周期為2N。

定理2 設在F2上， 周期為N的二元序列s∞和s∞，由它們合并為一類新序列S*∞，則這類新序列s*∞的極小多項式為(1-x)(1+xN)。

證明 s*2N(x)=sN(x)+xN#8226;(sN(x)+∑2N-1i=Nxi)=

sN(x)#8226;(1+xN)+xN#8226;[(1-xN)/(1-x)]s*∞(x)=

s*2N(x)(1+x2N+x4N+x6N+…)=s*2N(x)/(1-x2N)=

{sN(x)#8226;(1+xN)+xN#8226;[(1-xN)/(1-x)]}/(1-x2N)=

[sN(x)#8226;(1-x)+xN]/[(1-x)(1+xN)]

設h(x)=sN(x)#8226;(1-x)+xN，因為h(1)=1，

所以[sN(x)#8226;(1-x)+xN]/[(1-x)(1+xN)]為既約分式， 所以新序列s*∞的極小多項式為(1-x)(1+xN)。

定理3 設在F2上，周期為2N的二元新序列s*∞，則這類新序列s*∞的線性復雜度為N+1。

證明 由定理1可知這種新序列s*∞的極小多項式為(1-x)(1+xN)，所以

LC(s*∞)=2N-deg((1-x2N)，S*2N(x))=deg((1-x)(1+xN))=N+1

定理4 設在Fp上，周期為N的序列S∞和s∞，由它們合并為一類新序列S*∞，則這類新序列s*∞的極小多項式為

(1-x)(1+xN)

證明 s*2N(x)=sN(x)+xN#8226;sN(x)

s*∞(x)=s*2N(x)(1+x2N+x4N+x6N+…)=s*2N(x)/(1-x2N)=[sN(x)+xN#8226;sN(x)]/(1-x2N)=

[1/(1+xN)]#8226;[sN(x)/(1-xN)+sN(x)#8226;xN/(1-xN)]

由定理1可知，當t=0時，

[1/(1+xN)]#8226;[sN(x)/(1-xN)+(sN(x)#8226;xN)/(1-xN)]=[1/(1+xN)]#8226;{rs(x)/g(x)+[(p-1)g(x)-rs(x)(1-x)]/

(1-x)g(x)}=(p-1)/[(1-x)(1+xN)]

當t=1時，

[1/(1+xN)]#8226;[sN(x)/(1-xN)+(s-N(x)#8226;xN)/(1-xN)]=[1/(1+xN)]#8226;{rs(x)/[(1-x)g(x)]+[(p-1)(1-x)g(x)-rs(x)(1-x)]/(1-x)2g(x)}=(p-1)/[(1-x)(1+xN)]

當t≥2時，[1/(1+xN)]#8226;[sN(x)/(1-xN)+(sN(x)#8226;xN)/(1-xN)]=[1/(1+xN)]#8226;{rs(x)/[(1-x)tg(x)]+[(p-1)(1-x)tg(x)-rs(x)(1-x)]/(1-x)t+1g(x)}=(p-1)/[(1-x)(1+xN)]

綜上所述，這種新序列s*∞的極小多項式為

(1-x)(1+xN)

定理5 設在Fp上，周期為2N的p元序列S*∞，則這類新序列S*∞的線性復雜度為N+1。

證明 由定理2可知，這種新序列S*∞的極小多項式為

(1-x)(1+xN)

LC(S′)=2N-deg((1-x2N)，S′2N(x))=deg((1-x)(1+xN))=N+1

例1 設在F2上，周期為4的二元序列s4=(1，0，0，0)，其對偶序列為s4=(0，1，1，1)。則周期為8的這種新序列s*8=(1，0，0，0，0，1，1，1…)，求LC(S*∞)。

解

S*∞(x)=s*8(x)/(1-x8)=(1+x5+x6+x7)/(1-x8)=[(1+x)#8226;(1+x+x2+x3+x4)+x6(1+x)]/(1-x8)=(1+x+x2+x3+x4+x6)/(1-x)7=[(1+x)+x2(1+x)+x4(1+x)2]/(1-x)7

=[1+x2+x4(1+x)]/(1-x)6=(1+x+x4)/(1-x)5

所以LC(s′)=deg((1-x)5)=N+1=5

例2 設在F2上，周期為8的二元序列s8=(1，1，1，0，0，0，0，0)，s8=(0，0，0，1，1，1，1，1)，則周期為16的這種新序列S*16=(1，1，1，0，0，0，0，0，0，0，0，1，1，1，1，1)，求LC(S*∞)。

解

S*(x)=s*16(x)/(1-x16)=(1+x+x2+x11+x12+x13+x14+x15)/(1-x16)=[(1+x)+x2(1+x9)+x12(1+x)+x14(1+x)]/(1-x16)=[(1+x)+x3(1+x)2+x7(1+x)2+x12(1+x)]/(1-x)14=[(1+x3)4+x3(1+x)+x7(1+x)]/(1-x)13=

[(1+x)3(1+x+x2)4+x3(1+x)]4/(1-x)13=[(1+x+x2)4+x3(1+x)]/(1-x)9

所以LC(S*∞)=deg((1-x)9)=N+1=9

3 結束語

本文主要討論了新序列的極小多項式，從而求出了這種新序列的線性復雜度，在此基礎上還可以進一步討論這類新序列的穩定性。

參考文獻:

[1]RUEPPEL R A . Analysis and design of stream cipher[M]. Berlin: SpringerVerlag， 1986.

[2]RUEPPEL R A， STAFFELBACH O J.Product of linear recurring sequences with maximum complexity[J]. IEEE Trans on Information， 1987， 33(1):121-134.

[3]DING Cunsheng，XIAO Guozhen ，SHAN Weijuan . The stability theory of StreamCiphers [M]. Berlin:SpringerVerlag，1991:133-257.

[4]王尚平，高虎明，王育民.GF(2)上偽隨機序列S∞與∞的復雜性分析[J].西安電子科技大學學報，2002，29(1):67-70.

[5]王菊香，朱士信. Fp上周期序列s∞與s∞的線性復雜度分析[J].計算機應用研究，2009，26(2):21-22.

[6]魏仕民，陳愷，肖國鎮.周期序列的極小多項式[J]. 西安電子科技大學學報，2000，27(6):749-751.