徐 林， 孫國華

(1.馬鋼車輪公司信息中心，安徽馬鞍山 243000;2.安徽工業(yè)大學(xué)計算機學(xué)院，安徽馬鞍山 243002)

0 引 言

偽隨機序列在序列密碼、擴頻通信等領(lǐng)域有著極為廣泛的應(yīng)用。周期與相關(guān)性是衡量序列偽隨機性質(zhì)的一個重要而方便易行的指標(biāo)。序列密碼的設(shè)計準(zhǔn)則總是高度安全性和簡單結(jié)構(gòu)的統(tǒng)一。文獻[1]提出的自縮序列因結(jié)構(gòu)簡單而引人入勝，頗受關(guān)注[2-7]，但同時因結(jié)構(gòu)過于簡單而使密鑰的選擇大受限制，并易受攻擊;文獻[2]給出了廣義自縮序列族的概念，它們同樣具有簡潔的結(jié)構(gòu);并指出該序列族中每個序列的最小周期都是2n-1的因子，給出該序列族的許多密碼學(xué)優(yōu)點，如0～1分布的均衡性等。

1 定義及基本事實

定義1 設(shè)a=a0 a1 a2…是GF(2)上的n級m序列。設(shè)GF(2)上的n維向量G=(g0，g1，g2，，定義序列v=v0v1v2…，使vk=g0ak+對于k=0，1，2，…，如果ak=1，則輸出vk，否則放棄輸出。這樣得到的序列b=b0 b1 b2…記為b(v)或b(G)，稱其為基于m序列a的廣義自縮序列，稱序列族B(a)={b(G)，G∈GF(2)n}為基于m序列a的廣義自縮序列族。

定義2 設(shè)a=a0a1a2…是GF(2)上的n級m序列，其最小周期為2n-1，極小多項式為f(x)=1+c1 x+c2 x2+…+cn-1 xn-1+xn(即序列a滿足線性遞歸關(guān)系at=c1at-1+c2at-2+…+cn-1 at-n+1+at-n，t=n+0，n+1，n+2，…)。

以下的引理是平凡事實，參見文獻[6]。

引理2 設(shè)k1，k2，…，km均為非負(fù)整數(shù)，則bi=ak1+i+ak2+i+…+akm+i，i=0，1，2，…，仍然是序列a的一個平移等價序列。

對于一個比特串P，ˉP～ˉP表示P的重復(fù)串，重復(fù)次數(shù)可以等于1，2，3，…，但長度必須大于0;*表示一個不定比特。

由ak-1、ak+1和ak-1+ak+1得到的廣義自縮序列最小周期都是2n-1，參見文獻[5，6]。文獻[4]在許多情形下證明了由平移等價序列ak-2+ak-1得到的廣義自縮序列最小周期是2n-1;文獻[7]證明了在64種情形中有56種由平移等價序列ak-2+ak+1得到的廣義自縮序列最小周期是2n-1。

本文在文獻[4-9]的基礎(chǔ)上，對被控序列Vk=ak+1+ak+2，k=0，1，2…的廣義自縮序列，使用計算機編程驗證，通過適當(dāng)選擇比特串100、1010、1101、11100、111010和111011，分析其出現(xiàn)次數(shù)的奇偶性，證明了該序列的最小周期在1 024種情形下全部達到最大，即2n-1。

2 序列b(ak+1+ak+2)最小周期的證明

對于周期為2的冪次的序列(如2k)，如果有某個串出現(xiàn)奇數(shù)次，該序列的最小周期達到最大[7]，即2k。從上述結(jié)論可以得知，只要證明在廣義自縮序列b的2n-1長的比特串中有某個串出現(xiàn)奇數(shù)次，就可以得出廣義自縮序列b的最小周期達到最大，即2n-1。

由引理2，ak+1+ak+2仍然是序列a的一個平移等價序列，故有廣義自縮序列b(ak+1+ak+2)。

引理3 設(shè)b=b(ak+1+ak+2)，則b序列中出現(xiàn)比特串101，當(dāng)且僅當(dāng)序列a中出現(xiàn)以下5種互不重合的情形之一:比特串101110;比特串比特串比特串比特串

證明 易知:

(1)b序列中出現(xiàn)比特0，當(dāng)且僅當(dāng)序列a中出現(xiàn)比特串100或111。

(2)b序列中出現(xiàn)比特1，當(dāng)且僅當(dāng)序列a中出現(xiàn)比特串110或者101。

綜合以上事實，引理得證。

引理4 在一個周期2n-1內(nèi)，序列a中形式為或且長度小于或等于n的比特串個數(shù)為偶數(shù)。

綜合以上事實，引理得證。

應(yīng)用與引理3或引理4的方法，可以分別得到后面的引理，故略去其證明。

由引理4得知，若當(dāng)序列a的長度大于n的比特串個數(shù)為奇數(shù)時，即可以證明該序列最小周期達到最大。本文分析序列a長度大于n的比特串個數(shù)，由序列的形式可以選取cn-1、cn-2、c4、c3、c2、c1的不同值來判定序列是否滿足定義2中的要求，從而推算出不同情形下滿足長度大于n的比特串個數(shù)，可得到表1所列的數(shù)據(jù)。

表1 b序列中存在比特串101長度大于n的相關(guān)串的出現(xiàn)次數(shù)

由表1可以看出，在b序列的2n-1長的比特串中，串“101”有48種情形其長度大于n的相關(guān)串出現(xiàn)了奇數(shù)次，但還有16種情形其長度大于n的相關(guān)串出現(xiàn)了偶數(shù)次，本文借助串“1011”對剩余的16種出現(xiàn)偶數(shù)次的情形進行討論。

引理5 設(shè)b=b(ak+1+ak+2)，則b序列中出現(xiàn)比特串1011，當(dāng)且僅當(dāng)序列a中出現(xiàn)以下7種互不重合的情形之一:

(1)比特串1011101。

引理6 在1個周期2n-1內(nèi)，序列a中形式為或且長度小于或等于n的比特串個數(shù)為偶數(shù)。

同上，采用相同的方法分析序列a長度大于n的比特串個數(shù)，可以得到表2所列的數(shù)據(jù)。

由表2可以看出，存在36種情形其長度大于n的相關(guān)串出現(xiàn)了奇數(shù)次，并且在這36種情形中，有12種是在表1中不能證明周期最大情形的。也就是說，僅僅又證明了b序列最小周期達到最大時的另外12種情形，但是還有4種情形不能加以證明。

設(shè)n＞13，由以上序列的形式，增加系數(shù)，選取cn-1、cn-2、cn-3、cn-4、c4、c3、c2和c1的不同值來

判定序列是否滿足定義2中的要求。易得b序列中串“101”和“1011”在256種情形下未能使其周期達到最大的情形，見表3所列。

表3 b序列中未能使其周期達到最大情形

本文借助串“1101”對這16種未能說明周期達到最大的情形進行討論。

(1)比特串1101110。

(2)比特串10101110。

引理8 在一個周期2n-1內(nèi)，序列a中形式為且長度小于或等于n的比特串個數(shù)為偶數(shù)。

一是水資源供需矛盾突出。我國水資源總量位居世界第六，但人均水資源量僅為世界平均水平的1/4。經(jīng)濟的持續(xù)高速或較高增長，人口增長及人均消費水平的持續(xù)提高，使得供需矛盾突出，給水安全帶來了日益沉重的壓力，且這種壓力在相當(dāng)長時間內(nèi)是不可逆轉(zhuǎn)的。

b序列中存在比特串1101長度大于n的相關(guān)串的出現(xiàn)情形，見表4所列。

表4 b序列中存在串1101的相關(guān)串的出現(xiàn)情形

由表4可知，存在12種情形其長度大于n的相關(guān)串出現(xiàn)了奇數(shù)次，但還有4種情形其長度大于n的相關(guān)串出現(xiàn)了偶數(shù)次。

至此，只存在256種情形中的4種還不能加以證明，即cn-1 cn-2 cn-3 cn-4 c4 c3 c2 c1為00100101、00101001、11000111和11001011時。

采用同樣的方法，相繼采用比特串11100、111010和111011對序列進行分析，可以證明序列b(ak+1+ak+2)的1 024種情形在此都被證明了最小周期達到最大，此時可以得到如下定理。

定理1 廣義自縮序列b(ak+1+ak+2)通過用不同的比特串101、1011、1101、11100、111010和111011來分析其出現(xiàn)次數(shù)，在所有1 024種情形下最小周期均達到最大，即2n-1。

3 序列b的自相關(guān)性

以下給出2個定義、1個引理及1個推論，均來自文獻[7]。

定義3 如果2個串的總的相關(guān)串個數(shù)相等，且具有相同相關(guān)長度的相關(guān)串的個數(shù)相等，則它們具有相同的相關(guān)串結(jié)構(gòu)。

由m序列游程分布的性質(zhì)，有如下結(jié)論。

引理9 對于bjbj+k=rs，其中j的出現(xiàn)次數(shù)N(k，rs)分2種情形討論，即其相關(guān)串的長度不超過n的出現(xiàn)次數(shù)(記為N1(k，rs)和長度大于n的出現(xiàn)次數(shù)(記為N2(k，rs))。

(1)相關(guān)串長度不超過n的出現(xiàn)次數(shù)N1(k，rs)，滿足:若一相關(guān)串長度為t且不含串，則它出現(xiàn)2n-t次;若一相關(guān)串中含有1個串并且除串外的長度為t，則它出現(xiàn)次;若一相關(guān)串中有b(b≥2)個串并且其除串外的長度為t，則它出現(xiàn)次。

(2)長度大于n的相關(guān)串的出現(xiàn)次數(shù)N 2(k，rs)，滿足:若一相關(guān)串中沒有串，則它出現(xiàn)0次;若一相關(guān)串中有1個串并且串后邊的元素數(shù)為t，則它出現(xiàn)t次;若一相關(guān)串中有b(b≥2)個串，除串外的長度為t，且最后一個串后的元素數(shù)為s，則它出現(xiàn)次。

推論 設(shè)bj bj+1…bj+k的所有相關(guān)串中，串q1 q2…ql(含有b個串)是含有串最多的一個串，則bjbj+1…bj+k的長度大于n的相關(guān)串的出現(xiàn)次數(shù)的上界為O(nb-1)。

引理10 序列bjbj+1=rs(其中，r和s均可以取0，1)的相關(guān)串，見表5所列。

表5 bjbj+1=rs的相關(guān)串

證明 與引理3的證明完全相同。

定理2 設(shè)n≥9，則|A(1)|≤2-(n-2)。

證明 由表5可以看出，“00”與“01”和“10”與“11”具有相同的相關(guān)串結(jié)構(gòu)。故由引理9，它們長度不超過n的相關(guān)串的出現(xiàn)次數(shù)分別相同;而它們大于n的相關(guān)串的出現(xiàn)次數(shù)的下界為0。設(shè)“00”與“11”的大于n的相關(guān)串的出現(xiàn)次數(shù)的上界分別為M1和M2，則由一階自相關(guān)系數(shù)公式有:|A(1)|≤2-(n-1)(M1+M2)，又由引理9及引理10知:M1=2，M2=0，所以|A(1)|≤2-(n-2)。

引理11 設(shè)已知bjbj+1…bj+k-1的相關(guān)串，要得到bjbj+1…bj+k的相關(guān)串:如果bj+k=0，則bjbj+1…bj+k-1的相關(guān)串末端為“11”時加“1”，末端為“01”時加“00”或“11”，末端為“10”時加“0”，末端為“00”時加“100”或“111”或或如果bj+k=1，則bjbj+1…bj+k-1的相關(guān)串末端為“11”時加“0”，末端為“01”時加“10”或“01”，末端為“10”時加“1”，末端為“00”時加“101”或“110”或“

證明 由表5可以看出，bjbj+1=rs的相關(guān)串末端有“11”、“01”、“10”和“00”這4種可能，那么由線性組合器Vk=ak+1+ak+2的結(jié)構(gòu)易知結(jié)論成立。

引理12 序列bjbj+1bj+2=rst(其中，r、s和t均可以取0，1)的相關(guān)串，見表6所列。

證明 與引理3的證明完全相同。

定理3 設(shè)n≥9，則|A(2)|≤(n-1)×2-(n-2)。

證明 由表6可以看出，串“000”與“001”、“010”與“011”、“100”與“101”和“110”與“111”分別具有相同的相關(guān)串結(jié)構(gòu)，所以由引理10可知，長度不超過n的相關(guān)串的個數(shù)分別相等，且長度大于n的相關(guān)串的個數(shù)的下界為0。若設(shè)比特串“000”、“011”、“100”和“110”的長度大于n的相關(guān)串的個數(shù)之和的上界為M，則|A(2)|≤2-(n-1)M，由引理9和引理12知:

表6 bjbj+1 bj+2=rst的相關(guān)串

證明 由定義4知:

由引理10知，比特串“00”與“01”和“10”與“11”分別具有相同的相關(guān)串結(jié)構(gòu)及相關(guān)串末端。由引理11知，它們分別具有相同的發(fā)展趨勢;由引理9得N1(k，00)=N1(k，01)和N1(k，10)=N1(k，11)，同時得到N2(k，10)與N2(k，01)的下界為0。

下面分析N2(k，00)和N2(k，11)。由引理9的推論及引理11知，只需考慮含比特串最多的且以“01”收尾的相關(guān)串，即考慮“00”與“01”的相關(guān)串，由引理12知它們隨著k的每一次增長，都要增加1個串，且k=1，有1個串。那么，為k時有k個串。由引理9的推論即知，它們大于n的相關(guān)串的個數(shù)的上界為O(nk-1)，也即N2(k，00)與N2(k，11)之和的上界為O(nk-1)，所以2-(n-1)(N2(k，00)+N2(k，

4 結(jié)束語

本文通過采用不同的比特串分析其出現(xiàn)次數(shù)奇偶性的方法，證明廣義自縮序列b(ak+1+ak+2)最小周期在所有1 024種情形下全部達到最大，同時證明了其具有良好的低階自相關(guān)性。通過大量實驗，發(fā)現(xiàn)絕大多數(shù)廣義自縮序列都存在若干比特串，能說明在大多數(shù)情形下其最小周期達到最大，因而對絕大多數(shù)廣義自縮序列，都可以采用選擇適當(dāng)?shù)亩鄠€比特串分析其出現(xiàn)次數(shù)奇偶性的方法，證明其最小周期在所有情形下達到最大，即2n-1。一般廣義自縮序列可以采用哪些比特串來完全證明其最小周期達到最大，還有待進一步研究。

[1] M eierW，Stafflebach O.The self-shrinking generator[C]//Advances in C ryp tology-Eurocry pt'94.Berlin:Springer-Verlag，1995:205-214.

[2] 胡予濮，肖國鎮(zhèn).關(guān)于m序列的自旋轉(zhuǎn)序列[J].電子科學(xué)學(xué)刊，1997，19(6):847-851.

[3] Simon R B.The linear com plexity of the self-sh rinking generator[J].IEEE Trans on Inform Theory，1999，45(6):2073-2077.

[4] 胡予濮，張玉清.新一類廣義自縮序列的最小周期[J].通信學(xué)報，2003，24(6):169-176.

[5] 胡予濮，肖國鎮(zhèn).第四類廣義自縮序列的偽隨機性[J].中國科學(xué):E輯，2003，33(10):89-905.

[6] 胡予濮，張玉清，肖國鎮(zhèn).對稱密碼學(xué)[M].北京:機械工業(yè)出版社，2002:67-159.

[7] 董麗華，高軍濤，胡予濮.一類廣義自縮序列的偽隨機性[J].西安電子科技大學(xué)學(xué)報:自然科學(xué)版，2004，31(3):394-398.

[8] Hu Yupu，XiaoGuozhen.Generalized self-sh rinking generator[J].IEEE T rans on Inform Theory，2004，50(4):714-719.

[9] 戚君賢，周建欽.一類廣義自縮序列的偽隨機性[J].蘭州大學(xué)學(xué)報:自然科學(xué)版，2007，43(4):86-91.