張愛(ài)雪,年夫生,韓春
(安徽工程大學(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)用的需要。近年來(lái),研究出更具有科學(xué)和社會(huì)價(jià)值的偽隨機(jī)m序列是國(guó)內(nèi)外相關(guān)領(lǐng)域的熱點(diǎn)問(wèn)題。本文主要討論基于m序列構(gòu)造出的第一類m子序列的線性復(fù)雜度和非線性度,從而證明第一類m子序列具有很好的線性復(fù)雜度和良好的非線性度。
假設(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ī)特性。
第一類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)特性都很好。
線性復(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算法來(lái)完成。該算法的核心思想是運(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)系:
成立。我們就說(shuō)<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
為了抵抗各種攻擊,流密碼和分組密碼算法中所用的m序列必須滿足一些密碼學(xué)準(zhǔn)則,比如具有相關(guān)免疫性,有高的非線性度。我們知道,m序列是由線性移位寄存器產(chǎn)生的,LFSR的反饋函數(shù)是線性函數(shù),它的非線性度為零,所以m序列抵抗線性攻擊的能力不強(qiáng)。接下來(lái)我們分析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序列是線性序列,通過(guò)計(jì)算可知任何m序列的非線性度都是零。m子序列是非線性序列,m子序列的|Wf(ω)|的最大值比m序列的要小一些,而且m子序列的Wf(ω)的非零值的個(gè)數(shù)要多一些。根據(jù)圖2可知,相同位數(shù)的不同m子序列,交換序列共軛狀態(tài)的對(duì)數(shù)越多,得到的m子序列的非線性度越大。因此m子序列和m序列相比,非線性度有了很大的提高,m子序列用來(lái)抵抗相關(guān)攻擊的能力要強(qiáng)的多。
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.