線性復雜度為2n2m的2n周期序列的k錯線性復雜度
2010-01-01 00:00:00楊名慧朱士信
計算機應用研究 2010年6期
摘 要:線性復雜度和k錯線性復雜度是衡量密鑰序列隨機性的兩個重要標準，運用ChanGames算法，得到線性復雜度為2n2m的2n周期二元序列的k錯線性復雜度的所有可能的值，LCk(s)=0或2n-2m-2r+1+c，2n-2r+1+c。這一結果對于進一步探討流密碼密鑰序列的安全性有重要的應用價值。
關鍵詞:密鑰序列; 線性復雜度;k錯線性復雜度;ChanGames算法;二元周期序列
中圖分類號:TN918.4文獻標志碼:A
文章編號:1001-3695(2010)06-2299-02
doi:10.3969/j.issn.10013695.2010.06.087
kerror linear complexity of 2nperiodic sequences with linear complexity 2n2m
YANG Minghui， ZHU Shixin
(School of Mathematics， Hefei University of Technology， Hefei 230009， China)
Abstract:Linear complexity and kerror linear complexity are two important standards to scale the randomicity of key sequences. For a 2nperiodic binary sequence with linear complexity 2n2m. This paper obtained all the possible values of the kerror linear complexity using ChanGames algorithm， LCk(s)=0 or 2n-2m-2r+1+c，2n-2r+1+c. The result presented of stream cipher is so important that it can be used to analyze the safety of periodic key sequences more deeply.
Key words:key sequence; linear complexity; kerror linear complexity; ChanGames algorithm; periodic binary sequences
對于有限域F2上2n周期二元序列，文獻[1，2]分別給出了快速計算2n周期序列的線性復雜度和k錯線性復雜度的算法。文獻[3]中給出了線性復雜度等于l(0≤l≤2n，l是整數)的序列的個數，且計算了這類序列的線性復雜度的期望。文獻[4]討論了任意2n周期序列的k錯線性復雜度小于線性復雜度的最小的k的表達式。Meidl在文獻[5]中對于線性復雜度為2n的序列給出了1錯線性復雜度的具體形式及期望，并討論了k錯(k≥2)線性復雜度的期望的界，而文獻[6]對線性復雜度為2n-1的序列給出了2錯線性復雜度的具體形式及期望。對于線性復雜度為2n-2m的序列，文獻[7]研究了其2錯線性復雜度的具體形式及2錯誤序列個數可能的值。本文通過應用ChanGames算法，給出了線性復雜度為2n-2m的2n周期二元序列k錯(k為正整數)線性復雜度的具體形式。
1 預備知識
設s=(s0，s1，…，sN-1)∞是有限域F2上N周期序列，定義s的Hamming重量為s的一個周期中非零元素個數，記為W(s)。類似地，定義向量sN的Hamming重量為sN中非零元素的個數，記為W(sN)。顯然，對于周期序列s，若sN是其一個周期，則W(s)=W(sN)。定義F2上周期序列s=(s0，s1，…，sN-1)∞所對應的多項式sN(x)=s0+s1x+…+sN-1xN-1。另外，若N=2n，簡記s(n)=s2n。
定義s的線性復雜度LC(s)為能生成該序列的最短線性反饋移位寄存器的長度。特別地，當s為0序列時，令LC(s)=0。為敘述方便，設向量sN=(s0，s1，…，sN-1)的線性復雜度是以sN為一個周期的序列s=(s0，s1，…，sN-1)∞的線性復雜度，即LC(s)=LC(sN)。s的k錯線性復雜度[1]是指s(N)中改變至多k個si，所得到的新周期序列的最小的線性復雜度，記為LCk(s)，即LCk(s)=minw(e)≤kLC(s+e)。其中:e=(e0，e1，…，eN-1)∞，W(e)表示序列e的一個周期中“1”的個數。
給定F2上2n周期二元序列，其線性復雜度可以由ChanGames算法[2]計算出來，該算法是本文的重要工具。下面簡要介紹ChanGames算法:
ChanGames算法是一個遞歸過程，每一步將向量s(m)，1≤m≤n，分成左右兩個部分:
L(sm)=(s0，s1，…，s2m-1-1)
R(s(m))=(s2m-1，s2m-1+1，…，s2m-1)
如果L(s(m))=R(s(m))，LC(s)=LC(L(s(m)));否則，LC(s)=2m-1+LC(d)。其中d=L(s(m))+R(s(m))。要注意的是僅當L(s(m))≠R(s(m))時，線性復雜度才能增加。
由ChanGames算法的思想，可以定義一個F22m到F22m-1的映射φm
φm(s0，s1，…，s2m-1)=(s0+s2m-1，s1+s2m-1+1，…，s2m-1-1+s2m-1)
該映射有下面三個性質:
a)W(φm(s(m)))≤W(s(m));
b)當m≥2時，W(φm(s(m)))和W(s(m))同奇偶;
c)s(m)的原像集合
φ-1m+1(s(m))={v∈F22m+1 φm+1(v)=s(m)}
中元素的個數為22m。
2 主要結果
引理1[8] 設s是2n周期二元序列，則LC(s)=2n當且僅當W(s)是奇數。
引理2[5] 設s是2n周期二元序列，則當W(s(n))>k時，序列s的k錯線性復雜度為LCk(s)=2n-2r+1+c。其中1≤r≤n-1，1≤c≤2r-1。
引理3 設s是2n周期二元序列，若W(s(n))為偶數，則LC2g(s)=LC2g+1(s)，g為任意非負整數。
證明因為W(s(n))為偶數，若每個周期相同位置改變恰好2g+1個比特，W(s(n))變成了奇數，由引理1，序列s的線性復雜度變成了2n，故LC2g(s)=LC2g+1(s)，g為任意非負整數。
設s是2n周期二元序列，LC(s)=2n-2m，0≤m≤n-1，則由引理1，W(s(n))為偶數，由引理3，W(s(n))為偶數時，LC2g(s)=LC2g+1(s)，g為任意非負整數，故下文只考慮k=2h(h≥1)時序列s的k錯線性復雜度。
定理1設s是線性復雜度為2n-2m的2n周期二元序列。其中0≤m≤n-1，則LCk(s)=0或為如下兩種形式:
LCk(s)=2n-2m-2r+1+c1≤r≤m-1，1≤c≤2r-12n-2r+1+cm+1≤r≤n-1，1≤c≤2r-1
證明設s(n)=(s0，s1，…，s2n-1)是序列s的一個2n-周期所對應的向量，s(t)=φt+1…φn(s(n))=(s(t)0，s(t)1，…，s(t)2t-1)。其中m≤t≤n-1，根據ChanGames算法，序列s必滿足
L(s(t))≠R(s(t))，m+2≤t≤nL(s(m+1))=R(s(m+1))(1)
且LC(L(s(m+1)))=2m。而s(m)=φm+1(s(m+1))，由式(1)，s(m)=0。由引理1，W(s(n))為偶數，由映射φn的性質a)和b)，W(s(t))為偶數且W(s(t))≤W(s(n))，m≤t≤n。下面根據s(n)和s(m+1)的Hamming重量來分情況討論:
情形1 W(s)=W(s(n))≤k。
根據k錯線性復雜度的定義，則LCk(s)=0。
情形2 W(s)=W(s(n))>k，W(s(m+1))>k。
當j>m時，W(s(j))>k而且L(s(m+1))=R(s(m+1))，對s(m+1)改變的k比特即:對L(s(m+1))與R(s(m+1))作相同的h比特改變，則LCk(s)=2n-1+…+2m+1+f。其中f=LCh(L(s(m+1)))。因為L(s(m+1))=R(s(m+1))，W(s(m+1))>k，所以W(L(s(m+1)))>h，又因為L(s(m+1))為周期為2m的二元序列，由引理2知f=LCh(L(s(m+1)))=2m-2r+1+c，1≤r≤m-1，1≤c≤2r-1。根據ChanGames算法的遞歸過程知，W(s)=W(s(n))>k且W(s(m+1))>k時s(n)的k錯線性復雜度為
2n-1+…+2m+1+2m-2r+1+c=2n-2m-2r+1+c
1≤r≤m-1，1≤c≤2r-1
情形3 W(s)=W(s(n))>k，W(s(m+1))≤k。設r是使得W(s(r))，m+1≤r≤n-1至多為k的最大整數，由W(s(m+1))≤k知這樣的r是存在的。令b=W(s(r))，設a(n)是由s(n)改變b比特得到的向量，類似s(t)，定義a(t)=(a(t)0，a(t)1，…，a(t)2t-1)，m+1≤t≤n，則向量a(t)和s(t)至多相差b比特并且對于整數j，r
Lr，c=2n-1+2n-2+…+2r+1+c=2n-2r+1+c，0≤c≤2r
其中c=LC(L(a(r+1)))。
如果L(a(r+1))≠R(a(r+1))，即a(r)是非零向量，此時a(n)的線性復雜度LC滿足
LC>2n-1+2n-2+…+2r+1+2r≥Lr，c
而LCk(s)是由s(n)改變b比特所得到的最小的線性復雜度，因此LCk(s)=Lr，c。其中c是s(r+1)變化后所能得到的最小的線性復雜度。不妨設a(n)就是由s(n)改變b比特得到的線性復雜度達到最小值的向量。下面證明c≠0，c≠2r。
設s(r)=(0，…，0，…，1↑u1，…1↑u2，…1↑ub，…，0)，即
s(r)u1=s(r)u2=…=s(r)ub=1，0≤u1<… 且s(r)j=0，0≤j≤2r-1，j≠u1，u2，…，ub。則由s(r)=φr+1(s(r+1))，有 s(r+1)u1+s(r+1)u1+2r=1s(r+1)ub+s(r+1)ub+2r=1 (2) 且s(r+1)j=s(r+1)j+2r，0≤j≤2r-1，j≠u1，…，ub，可以適當改變s(r+1)u1，s(r+1)u1+2r，…，s(r+1)ub和s(r+1)ub+2r中b比特來保證W(L(s(r+1)))變成偶數，同時使式(2)中b個等式變成0，從而使s(r)變成0，由引理1，c≠2r。另外，c=0與r是使得W(s(r))至多為k的最大整數相矛盾，故1≤c≤2r-1。因此當W(s)=W(s(n))>k且W(s(m+1))≤k時，LCk(s)=2n-2r+1+c，1≤c≤2r-1。 下面通過一個具體例子來說明一下本文的主要結果。 例1 設n=3，m=1，求線性復雜度為2n-2m=6的2n周期二元序列s=(11101011)的4錯線性復雜度的范圍。 由于W(s)=W(s(3))=6>4且W(s(2))=2<4，利用情形2的結論知1≤LC4(s)≤3。計算得LC4(s)=1，與情形2的結論相符合。 3 結束語 本文運用ChanGames算法，計算出F2上線性復雜度為2n2m的序列s的k錯線性復雜度，對序列s的k錯線性復雜度的計數及期望仍是尚待研究的問題。 參考文獻: [1]STAMP M， MARTIN C F. An algorithm for the kerror linear complexity of binary sequences with period 2n[J]. IEEE Trans on Information Theory， 1993，39(4):1398-1401. [2]GAMES R A，CHAN A H. A fast algorithm for determining the linear complexity of a pseudorandom sequence with period 2n [J]. IEEE Trans on Information Theory，1983， IT29(1):144-146. [3]RUEPPEL R A. Analysis and design of stream ciphers[M]. Berlin:SpringerVerlag，1986. [4]KUROSAA K， SATO F， SAKATA T， et al. A relationship between linear complexity and kerror linear complexity[J]. IEEE Trans on Information Theory， 2000， 46(2):694-698. [5]MEIDL W. On the stability of 2nperiodic binary sequences[J]. IEEE Trans on Information Theory， 2005， 51(3):1151-1155. [6]ZHU Fengxiang，QI Wenfeng. The 2error linear complexity of 2nperiodic binary sequences with linear complexity 2n-1[J]. Journal of Electronics， 2007， 24(3):390-395. [7]譚林，戚文峰.F2上2n周期的k錯誤序列[J]. 電子與信息學報，2008，30(11):2592-2595. [8]FU Fangwei，NIEDERREITER H， SU Ming. The characterization of 2nperiodic binary sequences with fixed 1error linear complexity[C]//Proc of SETA. Heidelberg:Springer， 2006:88-103.
