m子序列的特性研究

張愛雪，年夫生，韓春

(安徽工程大學(xué)電氣工程學(xué)院安徽省電氣傳動(dòng)與控制重點(diǎn)實(shí)驗(yàn)室，安徽蕪湖241000)

基于線性移位寄存器(LFSR)構(gòu)造產(chǎn)生的偽隨機(jī)m序列是成熟的理論，m序列具有周期性、游程性、平衡性和相關(guān)性良好的偽隨機(jī)性。但m序列的數(shù)目有限，線性復(fù)雜度低，非線性度為零，往往不能滿足實(shí)際應(yīng)用的需要。近年來，研究出更具有科學(xué)和社會(huì)價(jià)值的偽隨機(jī)m序列是國(guó)內(nèi)外相關(guān)領(lǐng)域的熱點(diǎn)問題。本文主要討論基于m序列構(gòu)造出的第一類m子序列的線性復(fù)雜度和非線性度，從而證明第一類m子序列具有很好的線性復(fù)雜度和良好的非線性度。

1 m序列和m子序列

1.1 m序列及其特性

假設(shè)以F2上n次多項(xiàng)式f(x)=c0+c1x+…+cnxn為聯(lián)接多項(xiàng)式的n級(jí)線性移位寄存器所產(chǎn)生的非零序列a的周期為2n－1，便稱序列a是n級(jí)最大周期線性移位寄存器序列，簡(jiǎn)稱m序列。

m序列具有良好的平衡性、游程特性，它的自相關(guān)函數(shù)具有很好的δ(t)函數(shù)特征，所以，m序列具有很好的偽隨機(jī)特性。

1.2 m子序列

第一類m子序列是在m序列線性反饋函數(shù)所確定狀態(tài)轉(zhuǎn)移圖上，修改一定的狀態(tài)后繼，將會(huì)在保留原狀態(tài)轉(zhuǎn)移圖主構(gòu)架基礎(chǔ)上，形成一個(gè)新的狀態(tài)轉(zhuǎn)移圖，這個(gè)新的狀態(tài)轉(zhuǎn)移圖對(duì)應(yīng)一個(gè)新的移位寄存器，這個(gè)新的移位寄存器所產(chǎn)生的序列就是m子序列，其總的狀態(tài)數(shù)目也是2n－1。

m序列移位寄存器反饋函數(shù)式如式(1)，若改變狀態(tài)轉(zhuǎn)換，其反饋函數(shù)也隨之改變。

根據(jù)參考文獻(xiàn)［1］，m序列反饋函數(shù)在四點(diǎn)處完成模2加1就能形成m子序列。所以m子序列的反饋函數(shù)f'(x)的形式如下:

m子序列移位寄存器是基于m序列移位寄存器，且進(jìn)行了一定的狀態(tài)重組，其循環(huán)狀態(tài)也是2n－1個(gè)非零狀態(tài)，所以m子序列的平衡性、游程特性和自相關(guān)特性都很好。

2 m子序列的線性復(fù)雜度

線性復(fù)雜度及其穩(wěn)定性的研究是評(píng)價(jià)序列不可預(yù)測(cè)性的重要指標(biāo)，序列的線性復(fù)雜度不僅要足夠大，而且必須有很好的穩(wěn)定性。由線性復(fù)雜度的定義可知［2］:對(duì)于非線性序列，其等效線性移位寄存器的長(zhǎng)度為該序列的線性復(fù)雜度，在已知N長(zhǎng)二元序列a0，a1，a2，…，aN－1的情形下，求取這樣一個(gè)等效線性移位寄存器的長(zhǎng)度，采用Berrekamp－Messey算法來完成。該算法的核心思想是運(yùn)用數(shù)學(xué)歸納法求出一系列線性移位寄存器。

對(duì)于一個(gè)GF(2)上的多項(xiàng)式:

其中c0=1，但并不限定c1=1。我們把以f(x)為聯(lián)接多項(xiàng)式的l級(jí)線性移位寄存器簡(jiǎn)記為＜f(x)，l＞。如果遞歸關(guān)系:

成立。我們就說＜f(x)，l＞產(chǎn)生二元序列a0，a1，a2，…，aN－1。B－M算法的流程圖如圖1所示:

根據(jù)線性復(fù)雜度定義，設(shè)a=a0a1a2…a1－1是一n級(jí)m序列，則n級(jí)m序列線性復(fù)雜度是n。同一周期(p=2n－1)的m子序列的線性復(fù)雜度較m序列的線性復(fù)雜度大的多，應(yīng)用B－M算法可以計(jì)算出第一類m子序列的線性復(fù)雜度。對(duì)最高次數(shù)n取7～10的各m序列本原多項(xiàng)式(文獻(xiàn)［2］中的附表三)所確定的式(1－2)的m子序列進(jìn)行了線性復(fù)雜度的統(tǒng)計(jì)，部分結(jié)果如表1所示。

由表1可知:m子序列的線性復(fù)雜度比m序列的線性復(fù)雜度大的多，逼近于序列周期的一半，正好符合文獻(xiàn)［3］中對(duì)于密鑰序列的要求。

表1 具有同一周期的m序列和m子序列線性復(fù)雜度Tab.1 The linear complexity of m sequence and m subsequence which have the same period length

3 m子序列的非線性度

為了抵抗各種攻擊，流密碼和分組密碼算法中所用的m序列必須滿足一些密碼學(xué)準(zhǔn)則，比如具有相關(guān)免疫性，有高的非線性度。我們知道，m序列是由線性移位寄存器產(chǎn)生的，LFSR的反饋函數(shù)是線性函數(shù)，它的非線性度為零，所以m序列抵抗線性攻擊的能力不強(qiáng)。接下來我們分析m子序列的非線性度。

布爾函數(shù)f(x)的Walsh變換，也稱Walsh譜，是研究布爾函數(shù)非線性度的有力工具。

設(shè)f(x)是上的布爾函數(shù)，稱

為f(x)在ω處的Walsh譜，其中ω·x代表ω與x的內(nèi)積，即:

設(shè)f(x)是上的布爾函數(shù)，f(x)的非線性度(Nonlinearity)，記為Nf，等于它與所有線性函數(shù)的漢明距離的最小值，即:

布爾函數(shù)的非線性度與Walsh譜之間存在如下的關(guān)系:

因此要求出一個(gè)布爾函數(shù)的非線性度，只要求出其絕對(duì)值最大的Walsh譜值即可。

根據(jù)參考文獻(xiàn)［1］在m序列狀態(tài)轉(zhuǎn)移圖的基礎(chǔ)上修改一定的狀態(tài)后繼得到m子序列的反饋函數(shù)f'(x)，根據(jù)公式(5)和(8)可以計(jì)算出反饋函數(shù)f'(x)產(chǎn)生的m子序列的Walsh譜值和非線性度的值。圖2是9位的m序列交換不同對(duì)數(shù)的共軛狀態(tài)得到的不同的m子序列的非線性度Nf的值。

m序列是線性序列，通過計(jì)算可知任何m序列的非線性度都是零。m子序列是非線性序列，m子序列的|Wf(ω)|的最大值比m序列的要小一些，而且m子序列的Wf(ω)的非零值的個(gè)數(shù)要多一些。根據(jù)圖2可知，相同位數(shù)的不同m子序列，交換序列共軛狀態(tài)的對(duì)數(shù)越多，得到的m子序列的非線性度越大。因此m子序列和m序列相比，非線性度有了很大的提高，m子序列用來抵抗相關(guān)攻擊的能力要強(qiáng)的多。

4 結(jié)論

m子序列和m序列一樣具有周期長(zhǎng)、游程性、平衡性和良好的相關(guān)性，研究結(jié)果表明m子序列的線性復(fù)雜度比m序列的線性復(fù)雜度大的多，其非線性度和m序列相比也有了很大的提高，因此m子序列是好序列，可以廣泛用于密碼序列系統(tǒng)中。

［1］呂虹，段穎妮，管必聰，等.第一類 m子序列的構(gòu)造［J］.電子學(xué)報(bào)，2007，35(10):2029 －2032.

［2］肖國(guó)鎮(zhèn)，梁傳甲，王育民.偽隨機(jī)序列及其應(yīng)用［M］.北京:國(guó)防工業(yè)出版社，1985.

［3］楊義先，林須端.編譯密碼學(xué)［M］.北京:人民郵電出版社，1992.

［4］CUANG LONG.Crypftographic properties of the welchgong transformation sequence generators［J］.IEEE Transactions on Inforrnation Theory，2002，48(11):2837－2846.

［5］NO J S，CHUNG H，YUN M S.Binary pseudorandom sequences of period 2n －1 with ideal auto correlalation［J］.IEEE Trans IT，1998，44(2):814 － 817.

［6］程郁凡，洪福明.跳頻碼序列復(fù)雜度與隨機(jī)性分析［J］.電子科技大學(xué)學(xué)報(bào)，1996，25(9):351－357.

［7］武傳坤.布爾函數(shù)非線性度的譜分析［J］.電子科學(xué)學(xué)刊，1996，18(5):487 －494.

［8］胡斌，金晨輝，邵增玉.密碼學(xué)中3類具有特殊Walsh譜值布爾函數(shù)的關(guān)系［J］.通信學(xué)報(bào)，2010，31(7):104－109.

［9］朱華安，謝端強(qiáng).基于m序列統(tǒng)計(jì)特性的序列密碼攻擊［J］.通信技術(shù)，2003，8(140):96－98.