国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

m子序列的特性研究

2015-03-18 05:21:36張愛(ài)雪年夫生韓春
關(guān)鍵詞:游程布爾寄存器

張愛(à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ù)雜度和良好的非線性度。

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算法來(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

3 m子序列的非線性度

為了抵抗各種攻擊,流密碼和分組密碼算法中所用的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)的多。

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.

猜你喜歡
游程布爾寄存器
基于劃分組參考數(shù)的差值編碼壓縮方法
中國(guó)羽毛球組合鄭思維/黃雅瓊連續(xù)得失分規(guī)律研究
Lite寄存器模型的設(shè)計(jì)與實(shí)現(xiàn)
改進(jìn)型相對(duì)游程長(zhǎng)度編碼方法
布爾和比利
幽默大師(2019年4期)2019-04-17 05:04:56
布爾和比利
幽默大師(2019年3期)2019-03-15 08:01:06
布爾和比利
幽默大師(2018年11期)2018-10-27 06:03:04
布爾和比利
幽默大師(2018年3期)2018-10-27 05:50:48
分簇結(jié)構(gòu)向量寄存器分配策略研究*
基于游程數(shù)的非參數(shù)隨機(jī)性檢驗(yàn)
逊克县| 大姚县| 上饶县| 会宁县| 徐水县| 沐川县| 黑河市| 庆城县| 固镇县| 扶风县| 衡阳市| 英吉沙县| 富民县| 沧州市| 兴城市| 上高县| 北海市| 古丈县| 正安县| 蒲江县| 黑水县| 邮箱| 津南区| 体育| 巫山县| 日照市| 上虞市| 延边| 都江堰市| 定安县| 临朐县| 潢川县| 达尔| 武平县| 焉耆| 龙江县| 吉木萨尔县| 昌乐县| 奉节县| 高陵县| 麻江县|