盧櫟羽, 柯品惠

(福建省網(wǎng)絡(luò)安全與密碼技術(shù)重點實驗室; 福建師范大學數(shù)學與信息學院, 福建福州 350117)

1 引言

線性反饋移位寄存器(LFSRs) 和帶進位的反饋移位寄存器(FCSRs) 是兩種偽隨機序列發(fā)生器.它們所產(chǎn)生的序列具有良好的偽隨機性質(zhì), 如低相關(guān)性、長周期等.這些偽隨機序列在密碼學和通信系統(tǒng)中有著廣泛的應(yīng)用.理論上, 任何二元周期序列都可以由LFSR或FCSR 生成.人們通常把能產(chǎn)生序列s的最短LFSRs (或FCSRs) 的長度稱為序列s的線性復(fù)雜度(或2-adic 復(fù)雜度), 用符號LC(s)(或φ2(s)) 表示.而Berlekamp-Massey 算法(BMA)[1]和FCSRs 的有理逼近算法(RAA)[2]分別是針對序列的LFSRs 和FCSRs 的有效算法.如果序列的線性復(fù)雜度或2-adic 復(fù)雜度偏低, 則該序列在密碼學意義下就是不安全的.因此, 線性復(fù)雜度和2-adic 復(fù)雜度被認為是序列的兩個重要的安全準則.而對于流密碼中的密鑰流生成器產(chǎn)生的周期序列, 為了抵抗RAA 其2-adic 復(fù)雜度應(yīng)不小于其周期的一半.

交織技術(shù)是分析和設(shè)計序列的重要技術(shù)之一.許多最優(yōu)自相關(guān)序列[3,4]、低相關(guān)序列集[5,7]、或低相關(guān)區(qū)序列集[8]都是采用交織技術(shù)設(shè)計的或者被證明具有特殊的交織結(jié)構(gòu).例如, 利用交織結(jié)構(gòu), Tang 和Gong 在文獻[3]中構(gòu)造了三類具有優(yōu)自相關(guān)性質(zhì)的序列, 進一步地, Li 和Tang 在文獻[9]證明了這些序列具有大的線性復(fù)雜度.Arasu 等在文獻[10]中構(gòu)造了一類具有最優(yōu)自相關(guān)性質(zhì)的序列, 進一步地, Wang 和Du 等在文獻[11]中證明其具有大的線性復(fù)雜度.后來, Tang 和Ding 在文獻[4]中給出了比文獻[3]和[10]更一般的構(gòu)造.上述所提到的交織序列基本都由兩類不同的序列構(gòu)成, 且它們的形式為或但是這類序列的2-adic 復(fù)雜度一直沒人計算, 直到Xiong 等在文獻[12]中提出一種利用循環(huán)矩陣去計算二元序列的2-adic 復(fù)雜度的方法, 以及Hu 在文獻[13]中提出運用自相關(guān)值的精確分布去計算二元序列的2-adic 復(fù)雜度的方法.此外, 利用循環(huán)矩陣, Xiong 等在文獻[12]中證明了所有具有理想自相關(guān)值的序列的2-adic 復(fù)雜度可達到其最大值.Xiong 等在文獻[14]中證明了兩類基于交織結(jié)構(gòu)構(gòu)造的序列也具有最大2-adic 復(fù)雜度.這兩類序列中的一類是由Tang 和Ding 構(gòu)造的[4], 該序列具有最佳自相關(guān)性質(zhì); 另一類由Zhou 等構(gòu)造[15], 該序列的相關(guān)值可達到最優(yōu)的Tang-Fan-Matsufuji 界.此外, 利用文獻[13]提出的方法和精確自相關(guān)值分布, Sun 等在文獻[16]和文獻[17]中分別給出了兩類序列的2-adic 復(fù)雜度的下界.

Tang 等[4]給出了一類具有優(yōu)相關(guān)性質(zhì)的二元序列的構(gòu)造.最近, Yan 等[18]推廣了文獻[4]的構(gòu)造, 并給出了該序列的自相關(guān)值的具體分布.本文將研究該序列的2-adic 復(fù)雜度.具體地, 本文將在Tang 和Yan 等構(gòu)造的二元序列的基礎(chǔ)上, 利用Hu 的方法, 給出這些序列的2-adic 復(fù)雜度的一個下界.全文安排如下: 第2 節(jié)給出了交織結(jié)構(gòu)和勒讓德序列的定義, 并回顧了Tang 和Yan 等給出的一類具有優(yōu)相關(guān)性質(zhì)的二元序列的構(gòu)造及其性質(zhì); 第3 節(jié), 給出了該二元序列的2-adic 復(fù)雜度的一個下界; 第4 節(jié)對本文工作做了小結(jié).

2 預(yù)備知識

2.1 交織結(jié)構(gòu)

設(shè)v是一個正整數(shù),si=(si(0),si(1),···,si(v ?1)),0≤i ≤u ?1 為u個周期為v的二元序列.構(gòu)造一個v×u矩陣I=(Ii,j) 如下

按行連接上述矩陣可得到一條長為uv的周期序列s, 稱序列s為si, 0≤i ≤u ?1 的交織序列, 記為s=I(s0,s1,···su?1), 其中I表示交織算子.

2.2 勒讓德序列

設(shè)p是一個奇素數(shù), 勒讓德符號定義如下

其中QRp和NQRp分別為模p的二次剩余和非二次剩余.

勒讓德序列定義如下

當l(0) = 1 時, 稱l(t) 為第一類勒讓德序列, 記作l(t); 當l(0) = 0 時, 稱l(t) 為第二類勒讓德序列, 記作l0(t).

設(shè)p是一個奇素數(shù),a和b是周期為p的第一類或第二類勒讓德序列, 定義二元序列s如下

其中Lη(a) 表示序列a左循環(huán)移η位,表示a的補序列.

引理1[18]設(shè)序列s定義如上, 則

(i) 當p ≡1 (mod 4), 且a=l(t),b=l0(t) 時, 序列s的自相關(guān)值分布如下

(ii) 當p ≡1 (mod 4), 且a=l0(t),b=l(t) 時, 序列s的自相關(guān)值分布如下

(iii) 當p ≡3 (mod 4), 且a=l(t),b=l0(t) 時, 序列s的自相關(guān)值分布如下

(iv) 當p ≡3 (mod 4), 且a=l0(t),b=l(t) 時, 序列s的自相關(guān)值分布如下

3 主要結(jié)論

設(shè)N是一個正整數(shù), ZN為模N的剩余類環(huán).設(shè)s= (s(0),s(1),···,s(N ?1)) 為周期為N的二元序列, 定義其序列多項式為由文獻 [19]可知, 若

其中 0≤e ≤f,gcd(e,f)=1.則序列s的 2-adic 復(fù)雜度φ2(s)為其中z為小于或等于z的最大正整數(shù).

引理 2[13]設(shè)s=(s(0),s(1),···,s(N ?1)) 是一條周期為N的二元序列,S(x) 為s的序列多項式, 記則

引理3設(shè)p為奇素數(shù)且p ≡1 (mod 4),s為式(2.1)定義的二元序列,其中a=l,b=l0,則有g(shù)cd(S(2),5)=1.

證由

進而gcd(S(2),5)=1.

引理 4設(shè)p為奇素數(shù), 則有

證(1) 由 22p ≡1 (mod 3) 及 22p ≡?1 (mod 5) 易知.

定理1設(shè)p為奇素數(shù)且p ≡1 (mod 4),s為式(2.1)定義的二元序列,其中a=l,b=l0,且則序列s的 2-adic 復(fù)雜度φ2(s) 滿足φ2(s)≥2p, 即序列s的 2-adic 復(fù)雜度大于其周期的一半.

證設(shè)τ=4τ1+τ2, 其中 0≤τ1

由引理2, 有

由引理 3 及引理 4, 有 gcd(S(2),24p ?1)≤22p ?1.因此有由φ2(s) 的定義知結(jié)論成立.

推論1設(shè)p為奇素數(shù)且p ≡1 (mod 4),s為式(2.1)定義的二元序列,其中a=l0,b=l,且則序列s的 2-adic 復(fù)雜度φ2(s) 滿足:φ2(s)≥2p, 即序列s的 2-adic 復(fù)雜度大于其周期的一半.

證注意到, 該序列和定理1 中序列很相似, 差別在于交織構(gòu)造中的基序列略有差異.進而它們的2-adic 復(fù)雜度的分析類似, 但是具體的計算細節(jié)也略有差異.設(shè)τ=4τ1+τ2, 其中0≤τ1

由引理2, 有

類似定理 1 的證明, 由引理 3 及引理 4, 有 gcd(S(2),24p ?1)≤22p ?1.再由φ2(s) 的定義知結(jié)論成立.

引理5設(shè)p為奇素數(shù)且p ≡3 (mod 4),s為式(2.1)定義的二元序列,其中a=l,b=l0,其序列多項式為S(x), 則有g(shù)cd(S(2),3)=1.

證由

進而gcd(S(2),3)=1.

定理2設(shè)p為奇素數(shù)且p ≡3 (mod 4),s為式(2.1)定義的二元序列,其中a=l,b=l0,且則序列s的 2-adic 復(fù)雜度φ2(s) 滿足φ2(s)≥2p, 即序列s的 2-adic 復(fù)雜度大于其周期的一半.

證設(shè)τ=4τ1+τ2, 其中 0≤τ1

由引理2, 有

再由φ2(s) 的定義, 有

因此結(jié)論成立.

推論2設(shè)p為奇素數(shù)且p ≡3 (mod 4),s為式(2.1)定義的二元序列,其中a=l0,b=l,且則序列s的 2-adic 復(fù)雜度φ2(s) 滿足φ2(s)≥2p, 即序列s的 2-adic 復(fù)雜度大于其周期的一半.

證注意到, 該序列和定理2 中序列很相似, 差別在于交織構(gòu)造中的基序列略有差異.進而它們的2-adic 復(fù)雜度的分析類似, 但是具體的計算細節(jié)也略有差異.設(shè)τ=4τ1+τ2, 其中0≤τ1

由引理2, 有

由引理4 及引理5, gcd(S(2),24p ?1)≤22p+1.再由φ2(s) 的定義可知

4 總結(jié)

本文研究了一類具有優(yōu)自相關(guān)性質(zhì)的二元序列的2-adic 復(fù)雜度, 給出了該類序列的2-adic 復(fù)雜度的一個下界.本文的結(jié)果表明這類序列的2-adic 復(fù)雜度不小于其周期的一半,這意味著這些序列可以抵抗針對帶進位的反饋移位寄存器的有理逼近算法的攻擊.