2n周期優(yōu)秀二元序列生成及其特性分析

牛志華,李 政,李 哲,辛明軍

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院,上海 200444)

2n周期優(yōu)秀二元序列生成及其特性分析

牛志華,李 政,李 哲,辛明軍

(上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院,上海 200444)

定義周期為2n的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度均高的二元序列為優(yōu)秀序列,設(shè)計(jì)了遺傳算法來生成2n周期優(yōu)秀二元序列.對(duì)周期為8、16、32,k值為N/4的情況,匹配各種參數(shù)搜索優(yōu)秀序列,用Lauder-Paterson算法對(duì)得到的結(jié)果序列的線性復(fù)雜度譜進(jìn)行了分析,以說明它們確實(shí)是優(yōu)秀序列.由實(shí)驗(yàn)結(jié)果推測(cè)周期N為2n的二元優(yōu)秀序列當(dāng)k取N/4、N/8時(shí)的k錯(cuò)線性復(fù)雜度滿足規(guī)律LCk(S)≤N-2k+1(對(duì)周期為64、128、256的序列也進(jìn)行了實(shí)驗(yàn)驗(yàn)證),并且優(yōu)秀序列在所有同周期的二元序列中所占的比例為1/4.

流密碼;周期序列;線性復(fù)雜度;k錯(cuò)線性復(fù)雜度

設(shè)(S)=(s0,s1,s2,…)是有限域GF(q)上的序列,若對(duì)于任意的i,有si=si+N,則稱(S)為N周期序列.稱(S)滿足的下列線性遞歸關(guān)系式的最小的階數(shù)為序列的線性復(fù)雜度,記為L(zhǎng)C(S):

密鑰流序列的線性復(fù)雜度必須足夠大,因?yàn)橹灰肋B續(xù)2LC(S)個(gè)比特,就可以通過解線性方程組或借助BM算法[1]將整個(gè)序列完全確定.

密鑰流序列不僅應(yīng)該具有高的線性復(fù)雜度,而且其線性復(fù)雜度必須穩(wěn)定.例如一個(gè)周期為N的二元序列(S)=(0,0,…,0,1)∞,其線性復(fù)雜度LC(S)為N,但只要把其每一周期的最后一位的1變?yōu)?,該序列的線性復(fù)雜度就立刻降為0,這樣的序列是不穩(wěn)定的,顯然,用來作為密鑰流序列是不安全的.針對(duì)這一問題,國(guó)內(nèi)外學(xué)者相繼提出了球體復(fù)雜度、重量復(fù)雜度[2]、k錯(cuò)線性復(fù)雜度[3]的概念.后來,人們更習(xí)慣用k錯(cuò)線性復(fù)雜度的概念來描述線性復(fù)雜度的穩(wěn)定性.

設(shè)(S)是有限域GF(q)上周期為N的序列,當(dāng)改變(S)的周期中至多k(0≤k≤N)位后,得到的所有序列的線性復(fù)雜度中最小的線性復(fù)雜度稱為(S)的k錯(cuò)線性復(fù)雜度,記為L(zhǎng)Ck(S),即LCk(S)=,這里(E)是周期為N的序列,WN(EN)表示(E)的周期中不為零的元素個(gè)數(shù).

筆者研究2n周期二元序列,對(duì)于該周期序列,Games-Chan[4]和Stamp-Martin[3]分別給出了其線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的快速算法,結(jié)合Games-Chan算法和Stamp-Martin算法,Lauder-Paterson[5]提出了線性復(fù)雜度譜算法.該周期序列的理論分析文章見文獻(xiàn)[6-7].

綜上,密鑰流序列不僅應(yīng)該具有高的線性復(fù)雜度,而且應(yīng)該具有高的k錯(cuò)線性復(fù)雜度(對(duì)于不太大的k),傳統(tǒng)的序列生成方法(例如割圓序列、交錯(cuò)序列等)能夠生成線性復(fù)雜度較高的序列,但是無法同時(shí)兼顧到線性復(fù)雜度的穩(wěn)定性.遺傳算法是基于自然界中不必明確地描述問題的全部特征,只需要根據(jù)自然法則來產(chǎn)生新的更好解的這種思想而發(fā)展起來的一種通用的問題求解方法,具有極強(qiáng)的魯棒性.筆者首先設(shè)計(jì)遺傳算法來生成線性復(fù)雜度和k錯(cuò)線性復(fù)雜度都高的優(yōu)秀序列,然后分析優(yōu)秀序列的特性.

1 生成二元優(yōu)秀序列的遺傳算法設(shè)計(jì)

首先給出文中用到的定義和引理如下:

定義1 同時(shí)具有高的線性復(fù)雜度和高的k錯(cuò)線性復(fù)雜度的序列稱為優(yōu)秀序列,如果線性復(fù)雜度和k錯(cuò)線性復(fù)雜度都達(dá)到了可能的最大值,則稱該序列為最優(yōu)序列.

給出優(yōu)秀序列的定義是為了文中敘述方便,這里的優(yōu)秀僅指線性復(fù)雜度及其穩(wěn)定性意義上的優(yōu)秀,不考慮序列評(píng)價(jià)的其他指標(biāo).

定義2 設(shè)(S)是GF(q)上的周期序列,定義minerror(S)為滿足LCk(S)＜LC(S)的最小的k值,即minerror(S)是滿足LC(S+E)＜LC(S)的錯(cuò)誤向量EN的最小漢明重量[6].

引理1 對(duì)于2n周期二元序列,如果LC(S)≥3,則LCminerror(S)≤LC(S)-3[7].

下面設(shè)計(jì)生成二元優(yōu)秀序列的遺傳算法.

筆者所設(shè)計(jì)的遺傳算法的主要思想為首先按照種群規(guī)模隨機(jī)生成一定數(shù)量的序列組成初始種群,然后利用設(shè)計(jì)的算法計(jì)算其適應(yīng)度,通過遺傳算子的操作迭代選擇出最優(yōu)個(gè)體.具體設(shè)計(jì)如下:

算法的輸入是一定數(shù)目的序列,輸出是得到的優(yōu)秀序列.由于遺傳算法依賴于它的一些參數(shù),這里參數(shù)說明如下:PS表示種群規(guī)模,整數(shù);GEN表示進(jìn)化代數(shù),整數(shù);p X表示交叉概率,[0,1]區(qū)間的一個(gè)值;p M表示變異概率,[0,1]區(qū)間的一個(gè)值.

(1)編碼方式 在標(biāo)準(zhǔn)遺傳算法中,通常采用二進(jìn)制編碼方法.二進(jìn)制編碼方法與生物染色體的組成較類似,便于從遺傳學(xué)的角度來解釋,并且遺傳操作如交叉、變異比較容易實(shí)現(xiàn),算法處理的模式最多.二進(jìn)制編碼方法產(chǎn)生新個(gè)體的可能情況多,且產(chǎn)生的新個(gè)體不受父代個(gè)體所構(gòu)成的種群的限制,因此二進(jìn)制編碼方法搜索能力比其它的編碼方法強(qiáng).由于處理的序列本身為二元序列,故直接采用序列本身作為染色體進(jìn)行遺傳操作.

(2)初始種群 對(duì)于給定的N,隨機(jī)生成PS個(gè)長(zhǎng)為N的二元序列作為遺傳算法的初始種群.

(3)適應(yīng)度函數(shù)的設(shè)計(jì) 根據(jù)優(yōu)秀序列的定義,最終得到的個(gè)體為種群中線性復(fù)雜度和k錯(cuò)線性復(fù)雜度較高的個(gè)體,故需計(jì)算序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度值的和.序列的線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的和越高,在種群生成中個(gè)體的適應(yīng)度也越高,此序列被選擇復(fù)制的概率也越大,搜索得到優(yōu)秀序列的幾率亦越大.筆者采用Games-Chan算法[4]來計(jì)算周期為2n的二元序列的線性復(fù)雜度,采用Stamp-Martin算法[3]來計(jì)算周期為2n的二元序列的k錯(cuò)線性復(fù)雜度,將兩者的和作為適應(yīng)度函數(shù).

(4)選擇操作 采用輪盤選擇算法做選擇操作.選擇的過程為在N次輪盤旋轉(zhuǎn)的過程中,每一次旋轉(zhuǎn)選擇一個(gè)染色體,然后將選出的染色體組成新的種群.

(5)交叉操作 采用單點(diǎn)交叉方法(SPX).產(chǎn)生一個(gè)隨機(jī)的自然數(shù)r,滿足0≤r＜N.按如下方式交叉兩個(gè)選中的序列.

交叉前的初始序列為

交叉后的序列為

(6)變異操作 遺傳算法中,變異操作是必要的.變異亦稱為突變,就是改變?nèi)旧w某個(gè)(些)位上的基因.通過遺傳操作,可以引入新的基因,從而容易得到良好的個(gè)體.

2 二元優(yōu)秀序列的特性分析

本節(jié)的實(shí)驗(yàn)分為3部分:第1部分為基于上節(jié)設(shè)計(jì)的遺傳算法得到周期為N的二元優(yōu)秀序列,第2部分為基于遺傳算法來得出2n周期二元優(yōu)秀序列的k錯(cuò)線性復(fù)雜度規(guī)律,第3部分為通過窮舉法得到優(yōu)秀序列在所有同樣周期的二元序列中所占的比例.

2.1 基于遺傳算法得到周期為N的二元優(yōu)秀序列

用上節(jié)設(shè)計(jì)的遺傳算法進(jìn)行試驗(yàn),實(shí)驗(yàn)首先考慮周期N為8、16、32,k值為N/4,使用種群規(guī)模、迭代代數(shù)、交叉率、變異率等參數(shù)的常用范圍進(jìn)行各種組合的匹配,從而使遺傳算法的搜索結(jié)果更加全面,將搜索得到的結(jié)果序列用Lauder-Paterson算法[5]計(jì)算其線性復(fù)雜度譜,由譜線分布的均勻程度來判斷搜索的序列是否為線性復(fù)雜度和k錯(cuò)線性復(fù)雜度均較高的優(yōu)秀序列.實(shí)驗(yàn)結(jié)果如表1～3所示.

表1 各參數(shù)組合得到的周期為8的二元優(yōu)秀序列及Lauder-Paterson算法結(jié)果

表2 各參數(shù)組合得到的周期為16的二元優(yōu)秀序列及Lauder-Paterson算法結(jié)果

顯然,當(dāng)周期為N時(shí),線性復(fù)雜度LC(S)的最大值為N.由引理1,當(dāng)N=8時(shí),LCminerror(S)的最大可能值為5;當(dāng)N=16時(shí),LCminerror(S)的最大可能值為13;當(dāng)N=32時(shí),LCminerror(S)的最大可能值為29.根據(jù)表1～3的實(shí)驗(yàn)結(jié)果,通過遺傳算法搜索得到的序列大部分達(dá)到了線性復(fù)雜度和最小錯(cuò)線性復(fù)雜度可能的最大值,并且由Lauder-Paterson算法計(jì)算得到的結(jié)果序列的線性復(fù)雜度譜線分布平穩(wěn),而且在不同的參數(shù)組合下得到的這些序列的譜線非常接近,所以說筆者設(shè)計(jì)的遺傳算法能夠得到優(yōu)秀序列,并且得到最優(yōu)序列的概率超過了50%.

表3 各參數(shù)組合得到的周期為32的二元優(yōu)秀序列及Lauder-Paterson算法結(jié)果

2.2 2n周期二元優(yōu)秀序列的k錯(cuò)線性復(fù)雜度規(guī)律

由2.1節(jié)中實(shí)驗(yàn)數(shù)據(jù)分析可得周期為N=2n的二元優(yōu)秀序列的N/4錯(cuò)線性復(fù)雜度滿足:

當(dāng)N=8,k=N/4時(shí),LS2(S)=5=8-2k+1;

當(dāng)N=16,k=N/4時(shí),LS4(S)=9=16-2k+1;當(dāng)N=16,k=N/8時(shí),LS2(S)=13=16-2k+1;

當(dāng)N=32,k=N/4時(shí),LS8(S)=17=32-2k+1;當(dāng)N=32,k=N/8時(shí),LS4(S)=25=32-2k+1;

因此,有下面的推測(cè):

推測(cè)1 對(duì)于周期為N=2n的二元序列,當(dāng)k=N/4、N/8時(shí),其k錯(cuò)線性復(fù)雜度滿足LCk(S)≤N-2k+1,并且該上界是可以達(dá)到的.

接下來對(duì)N=64,128,256的周期序列再用第二節(jié)設(shè)計(jì)的遺傳算法進(jìn)行實(shí)驗(yàn)驗(yàn)證,生成的優(yōu)秀序列的N/4和N/8的錯(cuò)線性復(fù)雜度都不超過推測(cè)1給出的最大值,并且很多情況下能夠達(dá)到該最大值,統(tǒng)計(jì)數(shù)據(jù)如表4所示.

表4 周期為N的二元周期序列的N/4和N/8的錯(cuò)線性復(fù)雜度最大值

2.3 二元優(yōu)秀序列在同樣周期的二元序列中所占的比例

由2.1節(jié)遺傳算法搜索3個(gè)周期的序列所得到的數(shù)據(jù)可知,一部分的參數(shù)組合,均能得到線性復(fù)雜度和N/4錯(cuò)線性復(fù)雜度較高的優(yōu)秀序列.由于遺傳算法的搜索是由各種參數(shù)引導(dǎo)搜索的,對(duì)參數(shù)的設(shè)定依賴性較強(qiáng).如果優(yōu)秀序列在所有序列中所占比例很小,則不可能出現(xiàn)較多的參數(shù)組合均能搜索到良好的個(gè)體,故可知,優(yōu)秀序列在所有同樣周期的二元序列中會(huì)占一定的比例.所以有下面的大膽推測(cè),并在N=8,16,32的情況下驗(yàn)證了該推測(cè)的正確性.

表5 周期為N的二元優(yōu)秀序列在序列總數(shù)中的比例

推測(cè)2 對(duì)于周期為N=2n的二元序列,當(dāng)k=2i時(shí),使得線性復(fù)雜度和k錯(cuò)線性復(fù)雜度都達(dá)到可能的最大值的優(yōu)秀序列所占的比例為1/4.

以達(dá)到LS(S)=N,LSk(S)=N-2k+1的序列為優(yōu)秀序列,對(duì)周期為N=8、16、32的所有序列進(jìn)行了窮舉驗(yàn)證,得到的數(shù)據(jù)如表5所示.

表5不僅說明了推測(cè)2的可能性,而且在這個(gè)過程中沒有發(fā)現(xiàn)不滿足推測(cè)1的序列,也說明了推測(cè)1的合理性.當(dāng)N=64時(shí),要通過窮舉來驗(yàn)證推測(cè)2由于計(jì)算規(guī)模過大而不可行.

3 結(jié)束語(yǔ)

密碼學(xué)上強(qiáng)的序列不僅應(yīng)該具有高的線性復(fù)雜度,而且應(yīng)該具有高的k錯(cuò)線性復(fù)雜度,傳統(tǒng)的序列生成方法(例如割圓序列,交錯(cuò)序列等)以生成線性復(fù)雜度高的序列為目標(biāo),然后再分析所生成的序列的k錯(cuò)線性復(fù)雜度,往往k錯(cuò)線性復(fù)雜度的分析非常困難.筆者基于遺傳算法的魯棒性和它在多目標(biāo)優(yōu)化中的優(yōu)勢(shì),以線性復(fù)雜度和k錯(cuò)線性復(fù)雜度的和為適應(yīng)度函數(shù)引導(dǎo)搜索找到線性復(fù)雜度和k錯(cuò)線性復(fù)雜度都高的優(yōu)秀序列;在搜索過程中發(fā)現(xiàn)了2n周期序列的k錯(cuò)線性復(fù)雜度的一些規(guī)律和最優(yōu)序列的分布情況,并對(duì)此進(jìn)行了大膽的推測(cè);然后通過大量的實(shí)驗(yàn)對(duì)推測(cè)進(jìn)行了驗(yàn)證,當(dāng)周期為32時(shí),驗(yàn)證工作就需要大量的時(shí)間,對(duì)更長(zhǎng)的周期進(jìn)行實(shí)驗(yàn)驗(yàn)證基本不可行.所以尋求理論上的證明將是下一步努力的方向.

[1]Berlekamp E R.Algebraic Coding Theory[M].New York:McGraw-Hill,1968.

[2]Ding C,Xiao G,Shan W.The Stability of Stream Cipher[M].Lecture Notes in Computer Science:561.Berlin: Springer,1991.

[3]Stamp M,Martin C F.An Algorithm for the k-error Linear Complexity of Binary Sequences with Period 2n[J].IEEE Transactions on Information Theory,1993,39(4):1398-1401.

[4]Games R A,Chan A H.A Fast Algorithm for Determining the Complexity of a Binary Sequence with Period 2n[J].IEEE Transactions on Information Theory,1983,29(1):144-146.

[5]Lauder A G B,Paterson K G.Computing the Error Linear Complexity Spectrum of a Binary Sequence of Period 2n[J]. IEEE Transactions on Information Theory,2003,49(1):273-280.

[6]Kurosawa K,Sato F,Sakata T,et al.A Relationship Between Linear Complexity and k-Error Linear Complexity[J]. IEEE Transactions on Information Theory,2000,46(2):694-698.

[7]Chang Z,Wen Q,Chang Z,et al.On Cryptographic Properties of Binary 2n-periodic Sequences[J].Chinese Journal of Electronics,2011,2(2):307-311.

(編輯:李恩科)

Generation and analysis of the excellent 2n-periodic binary sequences

NIU Zhihua,LI Zheng,LI Zhe,XIN Mingjun
(School of Computer Engineering and Science,Shanghai Univ.,Shanghai 200444,China)

The 2n-periodic binary sequence with high linear complexity and high k-error linear complexity is defined as an excellent sequence.We design a genetic algorithm for generating excellent sequences and studying their features.Choosing the N-periodic binary sequences,where N=8,16,32,k=N/4,we search the resulted sequences by the genetic algorithm with various parameters,and compute the linear complexity profiles of results sequences by using the Lauder-Paterson algorithm,to confirm that the obtained sequences are the real excellent sequences.By numerous experiments,we speculate that the kerror linear complexity of the N-periodic binary excellent sequence meets the formula LCk(S)≤N-2k+1,when k=N/4、N/8(we also do experiments on sequences with periods 64,128 and 256).By the brute-force method we obtain that the proportion of the excellent sequence in all binary sequences of the same period is 1/4.

stream cipher;periodic sequence;linear complexity;k-error linear complexity

TN918.4

A

1001-2400(2014)01-0130-05

10.3969/j.issn.1001-2400.2014.01.023

2012-11-07 < class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2013-09-16

國(guó)家自然科學(xué)基金資助項(xiàng)目(60903187,61074135,61272096,61202395);上海市自然科學(xué)基金資助項(xiàng)目(13ZR141610);教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃資助項(xiàng)目(ncet-12-0620)

牛志華(1976-),女,副教授,博士,E-mail:zhihua_niu@163.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20130916.0926.201401.162_019.html