Ｆｐ上周期序列Ｓ∞與Ｓ∞的線性復雜度分析
2009-01-01 00:00:00王菊香朱士信
計算機應用研究 2009年2期
（合肥工業大學 應用數學系， 合肥230009）
摘 要：研究了有限域Fp上周期序列S∞的極小多項式、生成函數和它的對偶序列S∞的極小多項式及生成函數之間的關系，并建立了明確的關系式。這一結果對研究流密碼密鑰序列線性復雜度有一定的應用價值。
關鍵詞：線性復雜度； 極小多項式； 周期序列； 流密碼
中圖分類號：TN9184 文獻標志碼：A
文章編號：1001-3695(2009)02-0742-02
Complexity of periodic sequences S∞ and S∞ over Fp
WANG Ju-xiang， ZHU Shi-xin
(Dept. of Applied Mathematics， Hefei University of Technology， Hefei 230009， China)
Abstract:This paper presented the relation between fs(x) and fS(x) over field Fp， in which fs(x) and fS(x) are the minimum generate polynomials of periodic sequences S∞ and its bit-wise negative sequences S∞ respectively， and p was prime.The relation presented can be used to analyze the complexity of periodic sequences of stream ciphers over Fp.
Key words：linear complexity; minimum generate polynomials; periodic sequences; stream ciphers
周期序列的線性復雜度是度量流密碼強度的一個重要指標，序列 S∞= (s0，s1，…，sN-1，…) 的線性復雜度定義為生成它的最小線性反饋移位寄存器的長度，記為LC(s∞)。從線性復雜度的定義可知，如果一個序列的線性復雜度為 L ，則只需知道該序列的任意 2L 個連續元素，即可通過解線性方程組或借助B-M 算法[1，2]找到該序列所滿足的齊次線性遞歸關系式，進而可確定整個序列。這說明密鑰流序列的齊次線性復雜度必須足夠大，才能保證流密碼系統的安全性。因而線性復雜度是度量密鑰流序列的密碼強度的一個重要指標，但是線性復雜度高的序列未必是好的密鑰流序列。
例如:sN=1111…10，LC(sN)= N-1， 但只要把序列中的一個字節“0”改為“1”，則序列的線性復雜度就降為1。設fs(x) 是生成SN的極小多項式，則LC(sN)=N-deg(fs(x))[3]。由此可見討論序列的極小多項式有十分重要的意義。由于序列S∞的對偶序列 S∞是一類特殊的序列，且與S∞有著密切的關系，則研究 S∞的極小多項式有一定的應用價值。文獻[4]討論了F2上的序列S∞與其對偶序列 S∞的生成函數及極小多項式之間的關系。本文將討論Fp上序列S∞與其對偶序列 S∞的生成函數及極小多項式之間的關系。
1 基本知識
設SN表示有限域Fp上有限序列(s0，s1，…，sN-1)，S∞表示Fp上無限序列(s0，s1，…，sN-1，…)，設有整數L和Fp上一組數c1，c2，…，cL，使SN（或S∞）滿足
sj+c1sj-1+c2sj-2+…+cLsj-L=0， j≥L（1）
則稱SN（或S∞）是一個L階齊次線性遞歸序列，L是SN（或S∞）所滿足的齊次線性遞歸關系的最小階數，稱為SN（或S∞）的線性復雜度，記為LC(SN)（或LC(S∞)）。
對于序列s∞和sN，它們的生成函數定義為
s(x)=s0+s1(x)+sNxN+…=∞i=0sixi
sN(x)=s0+s1x+…sN-1xN-1
如果S∞是周期為N的序列，sN 是它的第一個周期，則s(x)=sN(x)(1+xN+x2N+…)=SN(x)/(1-xN)。s(x) 可以表示成
s(x)=[sN(x)/gcd(sN(x)，1-xN)]/[(1-xN)/gcd(sN(x)，1-xN)]=rs(x)/fs(x) 。這里
fs(x)=(1-xN)/gcd(sN(x)，1-xN)，rs(x)=sN（x）gcd(sN(x)，1-xN)
顯然rs(x)/fs(x)是既約的，deg(rs(x))＜deg(fs(x)) ， fs(x)為S∞ 的極小多項式，
deg(fs(x)) = LC(S∞)為S∞的線性復雜度[5]。
2 主要結果
定義1 設 S∞是滿足式（1）的p元序列，則
f(x)=c0+c1x+…+cLxL
為 S∞的一個特征多項式或生成多項式。其中：c0=0，ci∈Fp(i=1，2，…，L)，且cL≠0。 S∞的生成多項式中次數最小的多項式稱為 S∞的極小多項式，并記為fs(x)。 S∞所對應的生成函數為s(x)=∞i=0sixi。
定義2 設Fp上p元序列 S∞=(s0，s1，s2，…)，稱S∞= (s0，s1，s2，…) 為 S∞ 的對偶序列。其中：Si=(p-1)-si(i=0，1，2，…)。
引理1[3] 設S∞是周期為N的序列，則其生成函數可表示為
S(x)=∞i=0sixi =[sN(x)/gcd(sN(x)，1-xN)]/[1-xN/gcd(sN(x)，1-xN)]
其中：sN(x)=s0+s1x+…+sN-1xN-1，且 S∞ 的極小多
項式為fs(x)=(1-xN)/gcd(SN(x)，1-xN)。
周期序列生成函數的既約有理表達式惟一，且既約有理性的分母一定是其極小多項式。 對于Fp上的序列 S∞ 與 S∞的生成函數與極小多項式有
定理1 設Fp上周期序列的 S∞極小多項式為f(x)=(1-x)tg(x)。其中t為非負整數，g(1)≠0。 S∞的生成函數s(x)= ∞i=0sixi=rs(x)/fs(x)。其中
gcd(rs(x)，fs(x))=1，則 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)2g(x)]t=1
[(p-1)(1-x)tg(x)-rs(x)(1-x)]/[(1-x)t+1g(x)]t≥2
S∞的極小多項式為
fs(x)=
(1-x)fs(x) t=0
1/(1-x)fs(x)g(1)+rs(1)=p，t=1
fs(x)g(1)+rs(1)≠p，t=1
fs(x)t≥2
證明：
S(x)=∞i=0sixi=∞i=0(p-1-si)xi=∞i=0(p-1)xi- ∞i=0sixi =
(p-1) ∞i=0xi -sN(x)/(1-xN)
∞i=0xi=1+x+x2+…=1/(1-x)
s(x)=(p-1)/(1-x)-rs(x)/fs(x)=
[(p-1)fs(x)-rs(x)(1-x)]/(1-x)fs(x)=
{[(p-1)fs(x)-rs(x)(1-x)]/gcd[(p-1)fs(x)-rs(x)(1-x)，
(1-x)fs(x)]}/(1-x)fs(x)/gcd[(p-1)fs(x)-
rs(x)(1-x)，(1-x)fs(x)]}
由引理1可知S∞的極小多項式為
f s(x)=(1-x)fs(x)/gcd[(p-1)fs(x)-rs(x)(1-x)，(1-x)fs(x)]
接下來只需證明：
gcd[(p-1)fs(x)-rs(x)(1-x)，(1-x)fs(x)]=
1 t=0
(1-x)2g(1)+rs(1)=p，t=1
1-xg(1)+rs(1)≠p，t=1
1-xt≥2
1）當t=0時，fs(x)=g(x)
gcd[(p-1)fs(x)-rs(x)(1-x)，(1-x)fs(x)]=
gcd[(p-1)gs(x)-rs(x)(1-x)，(1-x)g(x)]=
gcd[(1-x)，(p-1)g(x)-rs(x)(1-x)]×
gcd[g(x)，(p-1)g(x)-rs(x)(1-x)]=
gcd[(1-x)，(p-1)g(x)]×gcd[g(x)，
rs(x)(1-x)]=1
f s=(1-x)fs(x)
2）當t≥1時，fs(x)=(1-x)tg(x)，g(1)≠0
gcd[(p-1)fs(x)-rs(x)(1-x)，(1-x)fs(x)]=
gcd[(p-1)(1-x)tg(x)-rs(x)(1-x)，(1-x)t+1g(x)]=
(1-x)gcd[(p-1)(1-x)t-1g(x)-rs(x)，(1-x)tg(x)]=
(1-x)gcd[(1-x)t，(p-1)(1-x)t-1g(x)-rs(x)]×
gcd[g(x)，(p-1)(1-x)t-1g(x)-rs(x)]
(1)當t=1時
gcd[(1-x)t，(p-1)(1-x)t-1g(x)-rs(x)]=
gcd[(1-x)，(p-1)g(x)-rs(x)]=
gcd[(1-x)，g(x)+rs(x)]
a)當g(1)+rs(1)=p時：
gcd[(1-x)，g(x)+rs(x)]=1-x
gcd[g(x)，(p-1)(1-x)t-1g(x)-rs(x)]=
gcd[g(x)，(p-1)g(x)-rs(x)]=1
gcd[(1-x)t，(p-1)(1-x)t-1g(x)-rs(x)]×
gcd[g(x)，(p-1)(1-x)t-1g(x)-rs(x)]=1-x
fs(x)=(1-x)fs(x)/(1-x)2=1/(1-x)fs(x)
b)當g(1)+rs(1)≠p時：
gcd[(1-x)，g(x)+rs(x)]=1
gcd[(1-x)t，(p-1)(1-x)t-1g(x)-rs(x)]×
gcd[g(x)，(p-1)(1-x)t-1g(x)-rs(x)]=1
fs(x)=fs(x)
(2)當t≥2時：
gcd[(1-x)t，(p-1)(1-x)t-1g(x)-rs(x)]×
gcd[g(x)，(p-1)(1-x)t-1g(x)-rs(x)]=1
fs(x)=fs(x)
證畢。
推論1 在上述記號下：
LC(s)=LC(s)+1 t=0
LC(s)-1g(1)+rs(1)=p，t=1
LC(s)g(1)+rs(1)≠p，t=1
LC(s)t≥2
證明 由定理1直接可以證出。
定理2 Fp[x]中的n次不可約多項式 fs(x)
生成的n階偽隨機序列 S∞的對偶序列S∞的極小多
項式為(1-x)fs(x)，且線性復雜度為n+1。
證明 因為fs(x)在域Fp上不可約，
則gcd((1-x)，fs(x))=1 ，即t=0，由定理I得
fs=(1-x)fs(x)，則定理2得證。
定理3 Fp[x]中的n次本原多項式fs(x)生成的n階m序列S∞的對偶序列S∞的極小多項式為(1-x)fs(x)，且線性復雜度為n+1。
證明 Fp[x]中的n次本原多項式fs(x)為不可約多項式，則由定理2直接可以得證。
3 結束語
本文是對F2上二元序列對偶序列的相關性質的推廣，這些關系對分析流密碼的密鑰流序列的線性復雜度有一定參考價值。由于對偶序列是一類特殊序列，本文為研究對偶序列也提供了一定的分析工具。
參考文獻：
［1］RUEPPLE 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 IT， 1987，33(1):121-134.
［3］DING Cun-sheng， XIAO Guo-zhen， SHAN Wei-juan. The stability theory of stream ciphers[M]. New York: Springer-Verlag，1991:85-100.
［4］王尚平，高虎明，王育民.GF（2）上偽隨機序列 S∞與 S∞的復雜性分析[J]. 西安電子科技大學學報，2002，29(1):67-70.
［5］魏仕民，陳愷，肖國鎮.周期序列的極小多項式[J]. 西安電子科技大學學報，2000，27(6):749-751.
