m子序列的特性研究

張愛雪，年夫生，韓春

(安徽工程大學電氣工程學院安徽省電氣傳動與控制重點實驗室，安徽蕪湖241000)

基于線性移位寄存器(LFSR)構造產生的偽隨機m序列是成熟的理論，m序列具有周期性、游程性、平衡性和相關性良好的偽隨機性。但m序列的數目有限，線性復雜度低，非線性度為零，往往不能滿足實際應用的需要。近年來，研究出更具有科學和社會價值的偽隨機m序列是國內外相關領域的熱點問題。本文主要討論基于m序列構造出的第一類m子序列的線性復雜度和非線性度，從而證明第一類m子序列具有很好的線性復雜度和良好的非線性度。

1 m序列和m子序列

1.1 m序列及其特性

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

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

1.2 m子序列

第一類m子序列是在m序列線性反饋函數所確定狀態轉移圖上，修改一定的狀態后繼，將會在保留原狀態轉移圖主構架基礎上，形成一個新的狀態轉移圖，這個新的狀態轉移圖對應一個新的移位寄存器，這個新的移位寄存器所產生的序列就是m子序列，其總的狀態數目也是2n－1。

m序列移位寄存器反饋函數式如式(1)，若改變狀態轉換，其反饋函數也隨之改變。

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

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

2 m子序列的線性復雜度

線性復雜度及其穩定性的研究是評價序列不可預測性的重要指標，序列的線性復雜度不僅要足夠大，而且必須有很好的穩定性。由線性復雜度的定義可知［2］:對于非線性序列，其等效線性移位寄存器的長度為該序列的線性復雜度，在已知N長二元序列a0，a1，a2，…，aN－1的情形下，求取這樣一個等效線性移位寄存器的長度，采用Berrekamp－Messey算法來完成。該算法的核心思想是運用數學歸納法求出一系列線性移位寄存器。

對于一個GF(2)上的多項式:

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

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

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

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

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

3 m子序列的非線性度

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

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

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

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

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

布爾函數的非線性度與Walsh譜之間存在如下的關系:

因此要求出一個布爾函數的非線性度，只要求出其絕對值最大的Walsh譜值即可。

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

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

4 結論

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

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

［2］肖國鎮，梁傳甲，王育民.偽隨機序列及其應用［M］.北京:國防工業出版社，1985.

［3］楊義先，林須端.編譯密碼學［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］程郁凡，洪福明.跳頻碼序列復雜度與隨機性分析［J］.電子科技大學學報，1996，25(9):351－357.

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

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

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