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

1.莆田學院應用數(shù)學福建省高校重點實驗室, 莆田351100

2.上海大學計算機工程與科學學院, 上海200444

3.電子科技大學計算機科學與工程學院, 成都611731

1 引言

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

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

S(X)被稱為的生成多項式.那么,在F2上的線性復雜度可通過下式計算

線性復雜度和k-錯線性復雜度是序列的重要密碼學性質(zhì), 它們刻畫的是序列的可預測性從而衡量該序列是否適用于密碼學領域.從密碼學應用角度來說, 一個序列的線性復雜度應盡可能的大, 并且序列在改變?nèi)舾身椇笃渚€性復雜度不應明顯降低[1,2].

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

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

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

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

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

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

我們將通過考察MS的結構, 更準確地說, 我們應用MS的列重量即可確定二元序列S的線性復雜度及k-錯線性復雜度.第2 節(jié)給出一般性結果, 第3 節(jié)討論兩類特殊的序列, 第4 節(jié)總結并提出進一步研究的問題.

2 k-錯線性復雜度: 一般性結論

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

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

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

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

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

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

而當k?κ3時, LCk(S)p.

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

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

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

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

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

那么我們得到

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

而當κ0+κ2>κ1時, 情況更為簡單.當k<κ1時, 對任何的Ek(X) 都不能保證 (Xp?1)|Sk(X);當k<κ3時, 對任何的Ek(X) 都不能保證Φ2(X)|Sk(X), 我們就證明了第二個結論.

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

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

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

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

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

我們在附錄中, 列舉了2 個例子, 并借助文獻[8]中的算法通過計算機程序運行, 驗證結果與上述定理一致.

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

3 k-錯線性復雜度: 兩類特殊序列

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

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

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

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

引理 2設v∈ {1,2,··· ,p? 1}.

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

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

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

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

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

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

3.2 周期為p2的交織序列

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

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

MU(r)的列形如

對于交織序列的一般構造, 有興趣的讀者可參見文獻[2,14,18].文獻[15,16]研究了均為Legendre序列時的交織序列的平衡性、相關性等問題.

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

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

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

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

當w為奇數(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) 知, 只需增加一項Xp?1, 即可保證 (1+X+···+Xp?2+Xp?1)|(U(p)(X)+Ek(X)), 那么只需在MU(p)的最后一列增加k= 1 比特即可實現(xiàn), 故LC1(U(p)) =p2?p+1.再根據(jù)式 (8), 在MU(p)的前p?1 列每列增加或減少 1 個比特即可即可保證(Xp?1)|(U(p)(X)+Ek(X)), 這時k=p?1, 故 LCp?1(U(p))=p2?p.其它情況與上面的討論類似.

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

與定理4 結論一致.

4 結束語

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

本文的結果也是在 2 模p2是本原根的條件下成立, 但對于 2 模p2不是本原根時, 也是值得研究的問題.

附錄

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

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

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

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

驗證結果符合定理1.我們也進一步選擇不同的p對定理1 與定理2 所有可能的情況加以驗證, 結論都是一致的.

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

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