徐 林， 孫國華

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

0 引 言

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

1 定義及基本事實

定義1 設a=a0 a1 a2…是GF(2)上的n級m序列。設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 設a=a0a1a2…是GF(2)上的n級m序列，其最小周期為2n-1，極小多項式為f(x)=1+c1 x+c2 x2+…+cn-1 xn-1+xn(即序列a滿足線性遞歸關系at=c1at-1+c2at-2+…+cn-1 at-n+1+at-n，t=n+0，n+1，n+2，…)。

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

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

對于一個比特串P，ˉP～ˉP表示P的重復串，重復次數可以等于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]的基礎上，對被控序列Vk=ak+1+ak+2，k=0，1，2…的廣義自縮序列，使用計算機編程驗證，通過適當選擇比特串100、1010、1101、11100、111010和111011，分析其出現次數的奇偶性，證明了該序列的最小周期在1 024種情形下全部達到最大，即2n-1。

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

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

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

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

證明 易知:

(1)b序列中出現比特0，當且僅當序列a中出現比特串100或111。

(2)b序列中出現比特1，當且僅當序列a中出現比特串110或者101。

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

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

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

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

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

表1 b序列中存在比特串101長度大于n的相關串的出現次數

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

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

(1)比特串1011101。

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

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

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

設n＞13，由以上序列的形式，增加系數，選取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內，序列a中形式為且長度小于或等于n的比特串個數為偶數。

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

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

表4 b序列中存在串1101的相關串的出現情形

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

至此，只存在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來分析其出現次數，在所有1 024種情形下最小周期均達到最大，即2n-1。

3 序列b的自相關性

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

定義3 如果2個串的總的相關串個數相等，且具有相同相關長度的相關串的個數相等，則它們具有相同的相關串結構。

由m序列游程分布的性質，有如下結論。

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

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

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

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

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

表5 bjbj+1=rs的相關串

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

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

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

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

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

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

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

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

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

表6 bjbj+1 bj+2=rst的相關串

證明 由定義4知:

由引理10知，比特串“00”與“01”和“10”與“11”分別具有相同的相關串結構及相關串末端。由引理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”收尾的相關串，即考慮“00”與“01”的相關串，由引理12知它們隨著k的每一次增長，都要增加1個串，且k=1，有1個串。那么，為k時有k個串。由引理9的推論即知，它們大于n的相關串的個數的上界為O(nk-1)，也即N2(k，00)與N2(k，11)之和的上界為O(nk-1)，所以2-(n-1)(N2(k，00)+N2(k，

4 結束語

本文通過采用不同的比特串分析其出現次數奇偶性的方法，證明廣義自縮序列b(ak+1+ak+2)最小周期在所有1 024種情形下全部達到最大，同時證明了其具有良好的低階自相關性。通過大量實驗，發(fā)現絕大多數廣義自縮序列都存在若干比特串，能說明在大多數情形下其最小周期達到最大，因而對絕大多數廣義自縮序列，都可以采用選擇適當的多個比特串分析其出現次數奇偶性的方法，證明其最小周期在所有情形下達到最大，即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).關于m序列的自旋轉序列[J].電子科學學刊，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].通信學報，2003，24(6):169-176.

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

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

[7] 董麗華，高軍濤，胡予濮.一類廣義自縮序列的偽隨機性[J].西安電子科技大學學報:自然科學版，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].蘭州大學學報:自然科學版，2007，43(4):86-91.