一類廣義自縮序列的偽隨機(jī)性

徐 林， 孫國(guó)華

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

0 引 言

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

1 定義及基本事實(shí)

定義1 設(shè)a=a0 a1 a2…是GF(2)上的n級(jí)m序列。設(shè)GF(2)上的n維向量G=(g0，g1，g2，，定義序列v=v0v1v2…，使vk=g0ak+對(duì)于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級(jí)m序列，其最小周期為2n-1，極小多項(xiàng)式為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，…)。

以下的引理是平凡事實(shí)，參見(jiàn)文獻(xiàn)[6]。

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

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

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

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

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

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

由引理2，ak+1+ak+2仍然是序列a的一個(gè)平移等價(jià)序列，故有廣義自縮序列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。

綜合以上事實(shí)，引理得證。

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

綜合以上事實(shí)，引理得證。

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

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

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

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

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

(1)比特串1011101。

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

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

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

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

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

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

本文借助串“1101”對(duì)這16種未能說(shuō)明周期達(dá)到最大的情形進(jìn)行討論。

(1)比特串1101110。

(2)比特串10101110。

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

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

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

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

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

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

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

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

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

以下給出2個(gè)定義、1個(gè)引理及1個(gè)推論，均來(lái)自文獻(xiàn)[7]。

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

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

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

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

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

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

引理10 序列bjbj+1=rs(其中，r和s均可以取0，1)的相關(guān)串，見(jià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，它們長(zhǎng)度不超過(guò)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”時(shí)加“1”，末端為“01”時(shí)加“00”或“11”，末端為“10”時(shí)加“0”，末端為“00”時(shí)加“100”或“111”或或如果bj+k=1，則bjbj+1…bj+k-1的相關(guān)串末端為“11”時(shí)加“0”，末端為“01”時(shí)加“10”或“01”，末端為“10”時(shí)加“1”，末端為“00”時(shí)加“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)串，見(jià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可知，長(zhǎng)度不超過(guò)n的相關(guān)串的個(gè)數(shù)分別相等，且長(zhǎng)度大于n的相關(guān)串的個(gè)數(shù)的下界為0。若設(shè)比特串“000”、“011”、“100”和“110”的長(zhǎng)度大于n的相關(guān)串的個(gè)數(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ā)展趨勢(shì);由引理9得N1(k，00)=N1(k，01)和N1(k，10)=N1(k，11)，同時(shí)得到N2(k，10)與N2(k，01)的下界為0。

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

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

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

[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] 胡予濮，肖國(guó)鎮(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é)報(bào)，2003，24(6):169-176.

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

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

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