盧櫟羽, 柯品惠

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

1 引言

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

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

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

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

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

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

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

2.2 勒讓德序列

設(shè)p是一個(gè)奇素?cái)?shù), 勒讓德符號(hào)定義如下

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

勒讓德序列定義如下

當(dāng)l(0) = 1 時(shí), 稱(chēng)l(t) 為第一類(lèi)勒讓德序列, 記作l(t); 當(dāng)l(0) = 0 時(shí), 稱(chēng)l(t) 為第二類(lèi)勒讓德序列, 記作l0(t).

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

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

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

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

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

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

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

3 主要結(jié)論

設(shè)N是一個(gè)正整數(shù), ZN為模N的剩余類(lèi)環(huán).設(shè)s= (s(0),s(1),···,s(N ?1)) 為周期為N的二元序列, 定義其序列多項(xiàng)式為由文獻(xià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的序列多項(xiàng)式, 記則

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

證由

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

引理 4設(shè)p為奇素?cái)?shù), 則有

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

定理1設(shè)p為奇素?cái)?shù)且p ≡1 (mod 4),s為式(2.1)定義的二元序列,其中a=l,b=l0,且則序列s的 2-adic 復(fù)雜度φ2(s) 滿(mǎn)足φ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為奇素?cái)?shù)且p ≡1 (mod 4),s為式(2.1)定義的二元序列,其中a=l0,b=l,且則序列s的 2-adic 復(fù)雜度φ2(s) 滿(mǎn)足:φ2(s)≥2p, 即序列s的 2-adic 復(fù)雜度大于其周期的一半.

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

由引理2, 有

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

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

證由

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

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

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

由引理2, 有

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

因此結(jié)論成立.

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

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

由引理2, 有

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

4 總結(jié)

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