周建欽,王傳銀
(杭州電子科技大學通信工程學院,浙江杭州310018)
線性復雜度是衡量密鑰流序列隨機性的一個重要指標,但高線性復雜度并不能保證序列是安全的。如果改變序列的一個周期段中一個或幾個元素,其線性復雜度發(fā)生很大的變化,則該序列仍然是密碼學意義上的弱序列。為了解決這個問題,文獻1引入了線性復雜度穩(wěn)定性度量指標:k-錯線性復雜度。文獻2給出了2n-周期二元序列s的k-錯線性復雜度嚴格小于線性復雜度L(s)的最小值:kmin=2WH(2n-L(s)),其中WH(b)表示整數(shù)b在二進制表示下的Hamming重量。文獻3給出了線性復雜度為L的2n-周期二元序列的具體個數(shù)。文獻4給出了當k=1,2時,線性復雜度為2n的2n周期二元序列的k-錯線性復雜度分布情況。文獻5給出了2n周期二元序列的3錯線性復雜度分布的完整計數(shù)公式。本文通過將5錯線性復雜度的計算轉化為求Hamming重量最小的錯誤序列,討論了線性復雜度為2n,周期為2n二元序列的5錯線性復雜度分布情況,給出了5錯線性復雜度為2n-3,2n-3+1和2n-3+2n-4的二元序列計數(shù)公式。
定義1 設s(n)={s0,s1,s2,…,s2n-1}是二元序列s的第一周期,n≥1,根據(jù)Games-Chan算法,定義映射φn從到
引理1 定義1的映射φn滿足下面的性質(zhì)[4]:
(1)W(φn(s(n)))≤W(s(n));
(2)W(φn(s(n))),W(s(n))奇偶性相同;
引理 2 設 N(L)表示周期為 2n,線性復雜度為 L的二元序列個數(shù)[3],則 N(L)
引理3 設s(n),t(n)是2個不同的二元序列但線性復雜度均為c,1≤c〈2n-3,n〉3,u(n),v(n)是2個不同的二元序列但線性復雜度均為2n,且u(n),v(n)的非零元素個數(shù)分別為1,3或5,則u(n)+s(n)與t(n)+v(n)不同。
證明 欲證明u(n)+s(n)與t(n)+v(n)不同,即證明s(n)+u(n)+v(n)與t(n)不同,即證明u(n)+v(n)與s(n)+t(n)不同。
因為s(n),t(n)是2個不同的二元序列但線性復雜度均為c,1≤c〈2n-3,n〉3,所以s(n)+t(n)的線性復雜度小于2n-3,且s(n)+t(n)的2n個元素可以分成8個相同的部分。
假設u(n)+v(n)和s(n)+t(n)相同,則u(n)+v(n)的2n個元素可以分成8個相同的部分,故u(n)+v(n)的非零元素個數(shù)只能為8,u(n)+v(n)的線性復雜度為2n-3,與s(n)+t(n)的線性復雜度小于2n-3矛盾。
給出具有給定5錯線性復雜度的2n周期二元序列個數(shù)的具體表達式:
定理1 設N5(2n-3)表示周期為2n,線性復雜度為L(s)=2n,5錯線性復雜度為2n-3的二元序列s的個數(shù),n〉3,則 N5(2n-3
證明 設序列s(n)是線性復雜度為2n-3的二元序列,則由引理2知s(n)的個數(shù)為n=5。
設二元序列u(n)的線性復雜度為2n且W(u(n))=1,可知u(n)+v(n)的5錯線性復雜度為2n-3。
設序列u(n)的線性復雜度為2n且W(u(n))=3,且u(n)中任意兩個非零元素距離為2n-3的倍數(shù),易知恰好存在一個序列v(n)且W(v(n))=5,使得u(n)+v(n)的線性復雜度為2n-3,即u(n)+s(n)的5錯線性復雜度小于2n-3。
設序列u(n)的線性復雜度為2n且W(u(n))=5,且u(n)中至少4個非零元素距離為2n-3的倍數(shù),易知恰好存在一個序列 v(n),使得 u(n)+v(n)的線性復雜度為2n-3,即u(n)+s(n)的5錯線性復雜度小于2n-3。
設序列u(n)的線性復雜度為2n且W(u(n))=3,則u(n)的個數(shù)為
設序列u(n)的線性復雜度為2n,W(u(n))=3,且u(n)中任意兩個非零元素距離為2n-3的倍數(shù),則u(n)的個數(shù)為
設序列u(n)的線性復雜度為2n且W(u(n))=5,則u(n)的個數(shù)為
設序列u(n)的線性復雜度為2n,W(u(n))=5,且u(n)中恰好4個非零元素距離為2n-3的倍數(shù),則u(n)的個數(shù)為
設序列u(n)的線性復雜度為2n,W(u(n))=5,且u(n)中任意5個非零元素距離為2n-3的倍數(shù),則u(n)的個數(shù)為
故5錯線性復雜度為2n-3的二元序列s的個數(shù)為
例如,當n=4時,N5(24-3)=7 200,即線性復雜度L(s)=24,5錯線性復雜度為2的二元序列s的個數(shù)為7 200,通過計算機驗證可得同樣的結果。
定理2 設N5(2 +1)表示周期為2,線性復雜度為L(s)=2,5錯線性復雜度為2 +1的二元序列s的個數(shù),n〉4,則
與定理1證明方法類似,只需考慮更復雜的重復情況即可。
定理3 設N5(2n-2-2n-4)表示周期為2n,線性復雜度為L(s)=2n,5錯線性復雜度為2n-2-2n-4的二元序列s的個數(shù),n〉3,則
與定理1、2證明方法類似,只需考慮更復雜的重復情況即可。
通過研究周期為2n的二元序列線性復雜度,將具體5錯線性復雜度值所對應的原序列的計數(shù)轉化為求Hamming重量最小的錯誤序列的個數(shù)。基于Games-Chan算法,本文討論了線性復雜度為2n的2n周期二元序列的5錯線性復雜度分布情況,給出了若干具體5錯線性復雜度對應原序列個數(shù)的計算公式?;谏厦娴挠懻摚瑢﹄S機周期序列的線性復雜度和k錯線性復雜度的統(tǒng)計性質(zhì)[6],也可研究線性復雜度為2n的2n周期二元序列的5錯線性復雜度對應原序列個數(shù)的期望值。
[1] Stamp M,Martin C F.An algorithm for the k-error linear complexity of binary sequences with period 2n[J].IEEE Transactions on Information Theory,1993,39(4):1 398-1 401.
[2] Kurosawa K,Sato F,Sakata T,et al.A relationship between linear complexity and k-error linear complexity[J].IEEE Transactions on Information Theory,2000,46(2):694-698.
[3] Rueppel R A.Analysis and Design of Stream Ciphers[M].Berlin:Springer-Verlag,1986:20-152.
[4] MeidlW.On the stablity of 2n-periodic binary sequences[J].IEEE Transactions on Information Theory,2005,51(3):1 151-1 155.
[5] Zhou J.A counterexample concerning the 3-error linear complexity of 2n-periodic binary sequences[EB/OL].http://www.springerlink.com/content/7 562p69 561 624 154/,2011-05-02.
[6] 蘇明.周期序列復雜度的分布[D].天津:南開大學,2004.