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

摘 要:周期序列的線性復(fù)雜度是衡量密鑰序列偽隨機(jī)性的重要指標(biāo)，周期序列的線性復(fù)雜度可以通過(guò)周期序列的極小多項(xiàng)式的次數(shù)求出。研究了有限域Fp上周期序列S∞的極小多項(xiàng)式的次數(shù)和由S∞及其對(duì)偶序列定義的一類新序列S*∞的極小多項(xiàng)式的次數(shù)之間的關(guān)系，建立了明確的關(guān)系式。這些結(jié)果對(duì)研究流密碼密鑰序列有一定的應(yīng)用價(jià)值。

關(guān)鍵詞:線性復(fù)雜度; 極小多項(xiàng)式; 周期序列; 流密碼

中圖分類號(hào):TN918.1文獻(xiàn)標(biāo)志碼:A

文章編號(hào):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 引言

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

1 預(yù)備知識(shí)

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

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

則稱sN( 或s∞)是一個(gè)L階齊次線性遞歸序列，L是sN( 或s∞)所滿足的齊次線性遞歸關(guān)系的最小階數(shù)，成為sN( 或s∞)的線性復(fù)雜度，記為L(zhǎng)C(sN)( 或LC(s∞))。

對(duì)于序列s∞和sN，它們的生成函數(shù)定義為

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是它的第一個(gè)周期， 則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 設(shè)s∞是滿足式(1)的p元序列，則f(x)=c0+c1x+…+cLxL為s∞的一個(gè)特征多項(xiàng)式或生成多項(xiàng)式。其中c0=0，ci∈Fp，i=1，2，…，L，且cL≠0。s∞的生成多項(xiàng)式中次數(shù)最小的多項(xiàng)式稱為s∞的極小多項(xiàng)式，并記為fs(x)。s∞所對(duì)應(yīng)的生成函數(shù)為S(x)=∑∞i=0sixi。

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

引理1 設(shè)s∞是周期為N的序列，則其生成函數(shù)可表示為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∞的極小多項(xiàng)式為fs(x)=(1-xN)/gcd(SN(x)，1-xN))

周期序列生成函數(shù)的既約有理表達(dá)式是惟一的，而既約有理表達(dá)式的分母一定是其序列的極小多項(xiàng)式，對(duì)于Fp上的序列s∞與其對(duì)偶序列s∞的生成函數(shù)、極小多項(xiàng)式有如下關(guān)系:

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

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∞的極小多項(xiàng)式為

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 主要結(jié)論

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

定理2 設(shè)在F2上， 周期為N的二元序列s∞和s∞，由它們合并為一類新序列S*∞，則這類新序列s*∞的極小多項(xiàng)式為(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)]

設(shè)h(x)=sN(x)#8226;(1-x)+xN，因?yàn)閔(1)=1，

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

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

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

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

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

(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可知，當(dāng)t=0時(shí)，

[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)]

當(dāng)t=1時(shí)，

[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)]

當(dāng)t≥2時(shí)，[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*∞的極小多項(xiàng)式為

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

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

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

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

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

例1 設(shè)在F2上，周期為4的二元序列s4=(1，0，0，0)，其對(duì)偶序列為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 設(shè)在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 結(jié)束語(yǔ)

本文主要討論了新序列的極小多項(xiàng)式，從而求出了這種新序列的線性復(fù)雜度，在此基礎(chǔ)上還可以進(jìn)一步討論這類新序列的穩(wěn)定性。

參考文獻(xiàn):

[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)上偽隨機(jī)序列S∞與∞的復(fù)雜性分析[J].西安電子科技大學(xué)學(xué)報(bào)，2002，29(1):67-70.

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

[6]魏仕民，陳愷，肖國(guó)鎮(zhèn).周期序列的極小多項(xiàng)式[J]. 西安電子科技大學(xué)學(xué)報(bào)，2000，27(6):749-751.