周期為素?cái)?shù)平方的二元序列的k-錯(cuò)線性復(fù)雜度*

陳智雄, 牛志華, 吳晨煌,3

1.莆田學(xué)院應(yīng)用數(shù)學(xué)福建省高校重點(diǎn)實(shí)驗(yàn)室, 莆田351100

2.上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院, 上海200444

3.電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院, 成都611731

1 引言

偽隨機(jī)序列在通信、密碼學(xué)等領(lǐng)域具有廣泛的應(yīng)用, 如在序列密碼中, 密文序列是由明文序列與密鑰序列異或得到, 其安全性完全依賴于密鑰序列的隨機(jī)性.因此密鑰序列的設(shè)計(jì)及其密碼學(xué)指標(biāo)是關(guān)鍵的研究方向, 序列的密碼學(xué)指標(biāo)主要包括: 平衡性、相關(guān)性、線性復(fù)雜度及其穩(wěn)定性, 等等[1–3].首先介紹序列的線性復(fù)雜度、k-錯(cuò)線性復(fù)雜度的概念.

設(shè)F2= {0,1} 為二元有限域, 對(duì)于F2上周期為T的二元序列其線性復(fù)雜度(記為定義為滿足F2上的如下線性遞歸關(guān)系的最小階L

S(X)被稱為的生成多項(xiàng)式.那么,在F2上的線性復(fù)雜度可通過(guò)下式計(jì)算

線性復(fù)雜度和k-錯(cuò)線性復(fù)雜度是序列的重要密碼學(xué)性質(zhì), 它們刻畫的是序列的可預(yù)測(cè)性從而衡量該序列是否適用于密碼學(xué)領(lǐng)域.從密碼學(xué)應(yīng)用角度來(lái)說(shuō), 一個(gè)序列的線性復(fù)雜度應(yīng)盡可能的大, 并且序列在改變?nèi)舾身?xiàng)后其線性復(fù)雜度不應(yīng)明顯降低[1,2].

早在 1969 年, Massey 設(shè)計(jì)了一個(gè)算法用于計(jì)算序列的線性復(fù)雜度[5], 往后的文獻(xiàn)中稱之為 BM 算法.1983 年, Games 和Chan[6]給出了周期為2n的二元序列的線性復(fù)雜度的快速算法, 算法的時(shí)間復(fù)雜度遠(yuǎn)低于通用的 BM 算法.1993 年, Stamp 和 Martin[4]對(duì) Games-Chan 算法進(jìn)行了擴(kuò)展, 引入一維代價(jià)數(shù)組, 提出了周期為2n的二元序列的k-錯(cuò)線性復(fù)雜度的快速算法.

本文我們主要討論周期為奇素?cái)?shù)冪pn的二元序列的線性復(fù)雜度與k-錯(cuò)線性復(fù)雜度問(wèn)題.為了綜述的方便, 我們?cè)O(shè)是 F2上周期為pn的二元序列, 并將s的一個(gè)周期表示為矩陣的形式

1999 年, 魏仕民等[7]將Games-Chan 算法進(jìn)行了擴(kuò)展, 提出了周期為pn的二元序列的線性復(fù)雜度的快速計(jì)算算法, 其基本思想是一個(gè)迭代計(jì)算算法, 首先將上述矩陣中的每一行相加得到一個(gè)周期為pn?1新序列那么的線性復(fù)雜度可寫成

其中, 如果上述矩陣的每一行都相同, 則δ=0, 否則δ=1.接著按照這個(gè)思想考慮序列的線性復(fù)雜度.

2001 年, 王磊等[8]基于從 Games-Chan 算法到 Stamp-Martin 算法的思想, 擴(kuò)展了文獻(xiàn) [7]中的算法, 提出了周期為pn的二元序列的k-錯(cuò)線性復(fù)雜度的快速算法, 在計(jì)算中也是考慮序列所對(duì)應(yīng)的矩陣形式的行結(jié)構(gòu).需要說(shuō)明的是, 魏仕民等[7]與王磊等[8]的算法中, 都要求 2 是模p2的一個(gè)本原根, 即2 模p2的乘法階為(p?1)p.

我們將從另一個(gè)角度來(lái)討論序列的線性復(fù)雜度與k-錯(cuò)線性復(fù)雜度, 也就是我們考慮上述矩陣形式(3)的列結(jié)構(gòu), 通過(guò)每一列的重量(即每一列所含1 的個(gè)數(shù)) 分布情況來(lái)確定序列的線性復(fù)雜度與k-錯(cuò)線性復(fù)雜度的取值.為了理解上的方便, 我們只考慮周期為p2的二元序列, 記為S=(s0,s1,··· ,sp2?1), 其一個(gè)周期的矩陣形式為

我們將通過(guò)考察MS的結(jié)構(gòu), 更準(zhǔn)確地說(shuō), 我們應(yīng)用MS的列重量即可確定二元序列S的線性復(fù)雜度及k-錯(cuò)線性復(fù)雜度.第2 節(jié)給出一般性結(jié)果, 第3 節(jié)討論兩類特殊的序列, 第4 節(jié)總結(jié)并提出進(jìn)一步研究的問(wèn)題.

2 k-錯(cuò)線性復(fù)雜度: 一般性結(jié)論

我們先定義幾個(gè)參數(shù).設(shè)wj=wt(Mj) 表示上節(jié)式 (4) 矩陣MS的列Mj的重量 (即向量Mj中 1的個(gè)數(shù)).記二元序列S=(s0,s1,··· ,sp2?1) 的生成多項(xiàng)式為S(X) 及

引理 1設(shè)S= (s0,s1,··· ,sp2?1) 是 F2上周期為p2的二元序列, 其矩陣表示形式為MS=[M0,M1,··· ,Mp?1],S(X) 為S的生成多項(xiàng)式, 則有

證明:(i) 顯然; (ii) 從Mj(X)≡wjXj(modXp? 1) 即得.

我們需要事先做一個(gè)說(shuō)明, 如果序列S的矩陣形式MS= [M0,M1,··· ,Mp?1]中, 所有列或?yàn)槿?0列 (0,0,··· ,0)T或?yàn)槿?1 列 (1,1,··· ,1)T, 那么 (1+Xp+X2p+ ···+X(p?1)p)|S(X), 從而S的線性復(fù)雜度LC(S)p.因此下文中我們總假設(shè)MS至少有一列不是全0 列或全1 列.

定理 1設(shè)S= (s0,s1,··· ,sp2?1) 是 F2上周期為p2的二元序列, 其矩陣表示形式為MS=[M0,M1,··· ,Mp?1],S(X) 為S的生成多項(xiàng)式.對(duì)于wj= wt(Mj),0j

如果 2 模p2為本原元, 那么當(dāng)S(1)≡0 (mod 2) 時(shí), 我們有

而當(dāng)k?κ3時(shí), LCk(S)p.

證明:由于2 模p2為本原元, 我們得到

是既約分解, 令 Φ1(X)=1+X+X2+ ···+Xp?1, Φ2(X)=1+Xp+X2p+ ···+X(p?1)p.

其中Ek是周期為p2的二元錯(cuò)誤序列且在一個(gè)周期內(nèi)僅含有k個(gè) 1.設(shè)新序列Sk與錯(cuò)誤序列Ek的生成多項(xiàng)式分別記為Sk(X) 與Ek(X), 那么Sk(X)=S(X)+Ek(X).下面我們討論使得Φ1(X)|Sk(X) 或Φ2(X)|Sk(X) 成立的最小k.

首先考察當(dāng)k滿足什么條件時(shí)可以保證Φ1(X)|Sk(X).由引理1 知

其次考察當(dāng)k滿足什么條件時(shí)可以保證 Φ2(X)|Sk(X).如果存在h(X) =h0+h1X+ ··· +hp?1Xp?1(次數(shù)

那么我們得到

從上面討論, 并注意到κ1κ3, 那么當(dāng)κ0+κ2<κ1時(shí), 當(dāng)k<κ0+κ2時(shí), 對(duì)任何的Ek(X) 都不能保證 Φ1(X)|Sk(X); 當(dāng)k<κ1時(shí), 對(duì)任何的Ek(X) 都不能保證 (Xp? 1)|Sk(X); 當(dāng)k<κ3時(shí), 對(duì)任何的Ek(X) 都不能保證Φ2(X)|Sk(X), 故我們證明了第一個(gè)結(jié)論.

而當(dāng)κ0+κ2>κ1時(shí), 情況更為簡(jiǎn)單.當(dāng)k<κ1時(shí), 對(duì)任何的Ek(X) 都不能保證 (Xp?1)|Sk(X);當(dāng)k<κ3時(shí), 對(duì)任何的Ek(X) 都不能保證Φ2(X)|Sk(X), 我們就證明了第二個(gè)結(jié)論.

而當(dāng)kκ3時(shí), 我們能找到合適的Ek(X) 使得 Φ2(X)|Sk(X), 從而 LCk(S)p.

在定理1 的條件下, 如果S(1)≡1 (mod 2), 情況可以類似討論, 結(jié)果如下.

定理 2設(shè)S= (s0,s1,··· ,sp2?1) 是 F2上周期為p2的二元序列, 其矩陣表示形式為MS=[M0,M1,··· ,Mp?1],S(X) 為S的生成多項(xiàng)式.對(duì)于存在某個(gè)j0使得0

如果 2 模p2為本原元, 那么當(dāng)S(1)≡1 (mod 2) 時(shí), 我們有

(i) 若κ0+κ2=0 (也即κ1=p), 則有

我們?cè)诟戒浿? 列舉了2 個(gè)例子, 并借助文獻(xiàn)[8]中的算法通過(guò)計(jì)算機(jī)程序運(yùn)行, 驗(yàn)證結(jié)果與上述定理一致.

下一節(jié)討論文獻(xiàn)中研究較多的兩類序列: 廣義割圓序列與交織序列.在一些特殊條件下, 它們的k-錯(cuò)線性復(fù)雜度取值更為直觀.

3 k-錯(cuò)線性復(fù)雜度: 兩類特殊序列

3.1 周期為p2的廣義割圓序列

Kim 與 Song[9]利用模pn剩余類環(huán)構(gòu)造廣義割圓序列, 根據(jù)我們的需要, 這里限定n= 2.設(shè)e=(p?1)/2 及g模p2為本原元.定義廣義割圓類

其中j=0,1.注意到模p2剩余類環(huán) Zp2滿足

即可定義周期為p2的二元平衡的廣義割圓序列C=(c0,c1,··· ,cp2?1) 如下:

引理 2設(shè)v∈ {1,2,··· ,p? 1}.

(i) 有 (p? 1)/2 個(gè)v使得另外 (p? 1)/2 個(gè)v使得

(ii) 對(duì)于j=0,1, 如果則對(duì)任意的 0i

證明:(i) 從即得.(ii) 設(shè)v+ip≡g2m+jmodp2,那么v≡v+ip≡g2m+jmodp, 故結(jié)論成立.

將序列C寫成矩陣的形式MC, 從引理2 可以看出, 該矩陣的第 1 列含有 (p+1)/2 個(gè) 1, 第 2 列至第p列中有 (p?1)/2 列是全 0 的列, 剩下的 (p?1)/2 列是全 1 的列.于是我們得到下面的結(jié)論.

定理 3設(shè)C=(c0,c1,··· ,cp2?1) 是如式 (5) 所定義的周期為p2的二元廣義割圓序列, 如果 2 模p2為本原元, 我們有

從定理3看, 只需改變(p?1)/2 項(xiàng), 其線性復(fù)雜度就會(huì)引起急劇降低, 而且從該序列的矩陣形式看, 有p?1 列是全0 列或全1 列, 這種分布也是很糟糕的, 因此該序列不是好的偽隨機(jī)序列.事實(shí)上, 從MC的結(jié)構(gòu)即可看出, 對(duì)任何的素?cái)?shù)p(2 模p2未必是本原元), 恒有 LC(p?1)/2(C)p.但最近幾年研究的另一類序列, 它的構(gòu)造與費(fèi)馬商有關(guān), 具有很好的密碼學(xué)性質(zhì), 見(jiàn)文獻(xiàn)[10–13].

3.2 周期為p2的交織序列

先介紹交織序列的構(gòu)造.周期為p的二元序列對(duì)于整數(shù)i, 左移操作Li定義為并記如果第 1 節(jié)中式 (4) 所列的序列S的矩陣MS, 其每一列Mj都可以寫成如下形式:

其中對(duì)每一個(gè)j:0,1,··· ,p? 2,ej∈ {0,1,··· ,p? 1} 且ep?1= ∞.于是就稱序列S為一個(gè)周期為p2的交織序列 (interleaved sequence), 而序列是構(gòu)造S的基序列 (base sequence).如果選取另一個(gè)周期為p的二元序列在S的基礎(chǔ)上, 可以構(gòu)造交織序列簇如下,它總共含有p+1 個(gè)序列

MU(r)的列形如

對(duì)于交織序列的一般構(gòu)造, 有興趣的讀者可參見(jiàn)文獻(xiàn)[2,14,18].文獻(xiàn)[15,16]研究了均為L(zhǎng)egendre序列時(shí)的交織序列的平衡性、相關(guān)性等問(wèn)題.

為簡(jiǎn)便起見(jiàn), 我們僅討論序列U(p)的k-錯(cuò)線性復(fù)雜度問(wèn)題, 而其它序列U(0),U(1),··· ,U(p?1)的k-錯(cuò)線性復(fù)雜度問(wèn)題在討論方法上是類似的.

定理 4設(shè)是 F2上周期為p2的二元交織序列, 其矩陣表示形式為其中是周期為p的二元序列且在一個(gè)周期內(nèi)含有 1的個(gè)數(shù)記為w, 對(duì) 0jp? 2,ej∈ {0,1,··· ,p? 1}.不妨假設(shè) 1w(p? 1)/2, 那么在 2 模p2為本原元時(shí), 我們有

證明:記U(p)的生成多項(xiàng)式為U(p)(X), 我們發(fā)現(xiàn)

那么當(dāng)w為偶數(shù)時(shí), 有(Xp?1)|U(p)(X), 所以LC0(U(p))=p2?p.另一方面, 我們考慮U(p)在一個(gè)周期內(nèi)改變k比特后, 使得 (1+Xp+X2p+···+X(p?1)p)|(U(p)(X)+Ek(X)), 其中Ek(X) 是一個(gè)含有k項(xiàng)且次數(shù)小于p2的多項(xiàng)式.為此, 只有把U(p)的矩陣形式的每一列都變?yōu)槿?0 列或全 1 列, 才能實(shí)現(xiàn).注意到w(p?1)/2, 易知最小的k= (p?1)w, 且此時(shí)可以把U(p)變?yōu)橐粋€(gè)全 0 序列, 故有 LC(p?1)w(U(p))=0.

當(dāng)w為奇數(shù)時(shí),U(p)(1)=0 但 (1+X+ ···+Xp?2+Xp?1) ?U(p)(X) 且 (1+Xp+X2p+ ···+X(p?1)p) ?U(p)(X), 故 LC0(U(p)) =p2? 1.從式 (8) 知, 只需增加一項(xiàng)Xp?1, 即可保證 (1+X+···+Xp?2+Xp?1)|(U(p)(X)+Ek(X)), 那么只需在MU(p)的最后一列增加k= 1 比特即可實(shí)現(xiàn), 故LC1(U(p)) =p2?p+1.再根據(jù)式 (8), 在MU(p)的前p?1 列每列增加或減少 1 個(gè)比特即可即可保證(Xp?1)|(U(p)(X)+Ek(X)), 這時(shí)k=p?1, 故 LCp?1(U(p))=p2?p.其它情況與上面的討論類似.

從應(yīng)用的角度, 當(dāng)然選擇w= (p?1)/2, 可以保證序列的 0,1 分布基本達(dá)到均衡.如取p= 11, 當(dāng)是周期為 11 的 Legendre 序列 (01011100010) 時(shí), 我們隨機(jī)選取移位值e0,e1,··· ,ep?2得到周期為 121的交織序列U(11), 于是我們可以得到并運(yùn)用算法驗(yàn)證下面結(jié)果:

與定理4 結(jié)論一致.

4 結(jié)束語(yǔ)

我們分析了周期為素?cái)?shù)平方p2的二元序列的線性復(fù)雜度與k-錯(cuò)線性復(fù)雜度, 通過(guò)序列的矩陣表示的列重量即可得出相關(guān)的結(jié)論, 無(wú)需通過(guò)設(shè)計(jì)算法進(jìn)行計(jì)算.本文的方法可以推廣到周期為pn(n> 2)的二元序列事實(shí)上只需按照文獻(xiàn) [7,8]中算法的思想, 將序列的矩陣 (3) 的每一行相加得到周期為pn?1的新序列, 考慮新序列的k-錯(cuò)線性復(fù)雜度問(wèn)題, 由此進(jìn)行迭代計(jì)算.簡(jiǎn)言之, 記序列的矩陣(3) 的第j(0j

本文的結(jié)果也是在 2 模p2是本原根的條件下成立, 但對(duì)于 2 模p2不是本原根時(shí), 也是值得研究的問(wèn)題.

附錄

例 1.設(shè)p=5, 如果取周期為 25 的二元序列S的矩陣形式為

那么定理1 中的參數(shù)κ0=0,κ1=4,κ2=1,κ3=8, 滿足κ0+κ2<κ1, 應(yīng)用算法 [7]通過(guò)運(yùn)行程序得到

如果取周期為25 的二元序列S的矩陣形式為

那么參數(shù)κ0=1,κ1=2,κ2=2,κ3=7, 滿足κ0+κ2>κ1, 應(yīng)用算法 [7]通過(guò)運(yùn)行程序得到

驗(yàn)證結(jié)果符合定理1.我們也進(jìn)一步選擇不同的p對(duì)定理1 與定理2 所有可能的情況加以驗(yàn)證, 結(jié)論都是一致的.

例 2.設(shè)p=3, 取周期為27 的二元序列S的矩陣形式為

從MS的列可以看出, 第 0, 3, 8 列的 0 改為 1, 第 1, 4, 5, 6 列的 1 改為 0, 共需改變 7 個(gè)比特, 可得 LC7(S)9(=p2), 而 LC6(S) ? 18(=p3?p2).當(dāng)矩陣的第 1, 4, 5, 6, 7 列各改變一個(gè)比特(即共改變 5 個(gè)比特) 使得每一列的重量為偶數(shù)時(shí), 改變后的序列的生成多項(xiàng)式≡0 (modXp2?1), 故LC5(S)=18=LC6(S).