徐玉春，王錦玲

(1.鄭州鐵路職業(yè)技術學院，河南 鄭州 450052；2.鄭州大學，數(shù)學系，河南 鄭州 450001)

GF(3)上一類廣義自縮序列的偽隨機性*

徐玉春1，王錦玲2

(1.鄭州鐵路職業(yè)技術學院，河南 鄭州 450052；2.鄭州大學，數(shù)學系，河南 鄭州 450001)

在GF(3)上構(gòu)造了一類廣義自縮序列的新模型，經(jīng)過分析和計算，證明了新型廣義自縮序列的最小周期為:2×3n-1，并對新序列的1長1-游程的個數(shù)進行精確的統(tǒng)計，計算出0-游程，1-游程，2-游程的分布非常均衡。研究得出此類新序列不但保持了GF(2)上第四類廣義自縮序列良好的偽隨機性，而且在此基礎上得出一些新的密碼學指標，相比之下各項指標都有很大的提高，并與GF(3)上其它廣義自縮序列相比具有更好的密碼學特性。

廣義自縮序列；m-序列；游程；周期

0 引 言

序列密碼的設計準則是高度安全和簡單結(jié)構(gòu)的統(tǒng)一,首先是Willi Meier[1]提出了自縮序列，因結(jié)構(gòu)簡單而引人入勝,頗受關注,隨后胡予璞等人又在此基礎上給出了廣義自縮序列[2-6]的定義,先是在GF(2)上研究了廣義自縮序列的很多性質(zhì)，作為對廣義自縮思想的推廣，又在GF(q)上研究了此定義下廣義自縮序列的許多密碼學性質(zhì),如0-1分布的均衡性等。而本文則在GF(3)上又討論一類廣義自縮序列的偽隨機性質(zhì),其優(yōu)點在于：改變了以往在GF(3)上所討論的雙向輸出模型，使輸出模型由雙向輸出到雙向組合輸出，而且是三項組合，比前人構(gòu)造的廣義自縮序列更加完善，這一突破使得此序列的密碼學性質(zhì)比前人的更具優(yōu)勢[8-11]，如0,1,2游程分布均衡，且最小周期都達到最大2·3n-1。

1 序列b的定義

定義1:設a=a0a1a2…∈GF(3)，a=a0a1a2…為n級m-序列，且周期為3n-1?，F(xiàn)有序列b=b0b1b2…，且與序列a=a0a1a2…的關系如下：

如果ak=1,則輸出ak-1;如果ak=2,則輸出ak-1+ak+1+ak+2;否則不輸出;(k=1,2,…)，這樣得到的輸出序列記為b=b0b1b2… ，稱序列b為GF(3)上新一類廣義自縮序列。

標記0m是長度為m的0串，其中長度m可以取0；“*” 表示GF(3)上任意值，有上述定義知，2×3n-1為序列b的一個周期。

2 序列b的游程分布

首先考慮序列b的長度為1的1-游程：

引理2.1：設t為以固定整數(shù)，滿足at=at-1=1，此時對應序列b的一個輸出比特bs=at-1=1，若得到序列b的長度為1的1-游程。

當且僅當，在以下7種情形下得到010：

(1)011220(2)011201(3)011211(4)01100m221(5)01100m212 (6)01100m200 (7)01100m1 。

當且僅當，在以下7種情形下得到210：

(1)211220(2)211201(3)211211(4)21100m221(5)21100m212(6)21100m200 (7)21100m1。

當且僅當，在以下6種情形下得到012：

(1)011222(2)011210(3)011201(4)01100m211(5)01100m220 (6)01100m202。

當且僅當，在以下6種情形下得到212：

(1)211222(2)211210(3)211201(4)21100m211(5)21100m220 (6)21100m202。

引理2.2：設t為以固定整數(shù)，滿足at=2，ak-1+ak+1+ak+2=1，此時對應序列b的一個輸出比特bs=ak-1+ak+1+ak+2=1，若得到序列b的長度為1的1-游程。

當且僅當，在以下15種情形下得到010：

(1)222201(2)1220221(3)120201(4)1220212(5)1220200 (6)1202222(7)012210(8)01200m0221(9)01200m0212(10)01200m0200(11)01200m01(12)010m02222(13)0200m02222(14)010m0201(15)0200m0201。

當且僅當，在以下15種情形下得到210：

(1)122201(2)0220221(3)0220212(4)0220200(5)212210(6)21200m0221(7)21200m0212(8)21200m01(9)21200m0200(10)0202222(11)210m02222(12)2200m02222(13)020201(14)210m0201 (15)2200m0201。

當且僅當，在以下16種情形下得到012：

(1)02211(2)222200(3)1220220(4)1220211 (5)1220202(6)012212(7)01212(8)01200m0220(9)01200m0211(10)01200m0202(11)1202221(12)010m02221(13)0200m02221(14)120210(15)010m0210 (16)0200m0210。

當且僅當，在以下16種情形下得到212：

(1)22211(2)122200(3)0220220(4)0220211 (5)0220202(6)212212(7)21212(8)21200m0220(9)21200m0211(10)21200m0202(11)0202221(12)210m02221(13)2200m02221(14)020210(15)210m0210 (16)2200m0210。

定理2.1：設序列b1的長度為1的1-游程的個數(shù)為u，則：

72×3n-6-22≤u≤72×3n-6+23

以同樣的分析方法可得：

定理2.2：設序列b的長度為1的0-游程的個數(shù)為u，則:

72×3n-6-24n+124≤u≤72×3n-6+58n-164

定理2.3：設序列b的長度為1的2-游程的個數(shù)為u，則:

72×3n-6-30≤u≤72×3n-6+22

3 序列b的最小周期

引理3.1：設b為輸出序列，在b的一個周期P內(nèi)，若有一s長1-游程出現(xiàn)的次數(shù)為N，且滿足gcd(N,P)=1，則稱P是序列b的最小周期。

證明：參見文獻[7]。

為了得到序列b的最小周期，由序列b游程分布可得：

引理3.2：當k≥1；m≥1時，若輸出序列b中出現(xiàn)n+3k長的1-游程時，m-序列a中有以下幾種情況出現(xiàn)：(其中n-3m-2≥0)

定理3.1：序列a為m-序列，由a控制輸出的序列b有最小周期:2×3n-1。

證明：根據(jù)輸出序列的形式，知2×3n-1是輸出序列b的一個周期，又因m-序列a中沒有大于n長的1-游程，故考慮以下幾種情況：若序列b在一個周期2×3n-1中，出現(xiàn)了n+3k長的1-游程，則一定是在引理3.2中m-序列a控制輸出的所有比特串中出現(xiàn)，因m-序列a中n長1-游程僅出現(xiàn)一次，故比特串200

4 結(jié)束語

先列出GF(3)上幾類廣義自縮序列的輸出序列與本文的一類廣義自縮序列在最小周期都達到2×3n-1內(nèi)的游程分布情況表。

表1

從表上可以看到本文構(gòu)造的一類廣義自縮序列長游程少，0，1，2游程分布均勻，研究表明：由驅(qū)動序列a生成的廣義自縮序列b其優(yōu)點在于，序列b對序列a的保護強度高，而且暴露的驅(qū)動信息少，適合在通信和計算機編碼系統(tǒng)的應用。

[1] W Meier,Stafflebach O.The Self-Shrinking Generator[A]. Advanced in Cryptology-Eurocrypt,94,1994:205-214.

[2] HU Y P，XIAO G Z. Generalized Self-Shrinking Generator[J]. IEEE, Trans on Inform Theory, 2004, 150(4):714-719.

[3] 董麗華,高軍濤,胡予璞.一類廣義自縮序列的偽隨機性[J].西安電子科技大學學報(自然科學報),2004,31(3):394-398. DONG Li-hua,GAO Jun-tao,HU Yu-pu. Pseudo-Random ness of the First Generalized Self-Shrinking Sequences[J]. Xi'an University of Electronic Science and Technology Journal (Natural Science),2004,31(3):394-398.

[4] 胡予璞,張玉清.新一類廣義自縮序列的最小周期[J].通信學報,2003,24(6):169-176. HU Yu-pu, ZHANG Yu-qing. A New Class of Generalized Self Shrinking Sequences of the Minimum Period [J].Journal of Communications,2003,24(6):169-176.

[5] 胡予璞,白國強,肖國鎮(zhèn).GF(q)上的廣義自收縮序列[J]. 西安電子科技大學學報(自然科學報),2001,28(1):5-7. HU Yu-pu, BAI Guo-qiang, XIAO Guo-zhen. Generalized Self Shrinking Sequence of GF (q) [J]. Journal of Xi'an Electronic and Science University (Natural Science), 2001, 28 (1): 5-7.

[6] 胡予璞,肖國鎮(zhèn).第四類廣義自縮序列的偽隨機性.中國科學(E輯),2003,33(10):896-905. HU Yu-pu, XIAO Guo-zhen.The Pseudo Randomness of the Fourth Class Generalized Self-Shrinking Sequences.Chinese Science (E), 2003, 33 (10): 896-905.

[7] 萬哲先.代數(shù)與編碼.北京:機械工業(yè)出版社.2002. WAN Zhe-xian. Algebra and Coding. Beijing: China Machine Press.2002.

[8] 王錦玲,徐玉春.GF(3)上若干類廣義自收縮序列的偽隨機性[J].通信技術,2011,44(5):54-56. WANG Jin-ling, XU Yu-chun. Pseudo-Randomness of Some Generalized Self-Shrinking Sequences on GF(3)[J]. Communications Technology, 2011,44(5):54-56.

[9] 董樂,王錦鈴,陳鐵生.廣義自收縮序列特例的擴展[J].信息安全與通信保密,2006,152(8):78-82.

DONG Le, WANG Jin-ling, CHEN Tie-sheng. Extension of Generalized Self-Shrinking Sequences[J].Information Security and Communications Privacy,2006,152(8):78-82.

[10] 龔呂樂.GF(3)上新一類廣義自縮序列及其擴展[D].鄭州大學碩士學位論文,2010：5. GONG Lv-le. A Special Generalized Self-Shrinking Sequence on GF (3) and Its Extension[D].Zhengzhou University Degree Thesis,2010：5.

[11] 王慧娟,王錦鈴,龔呂樂. GF(3)上第四類廣義自縮序列[A].密碼學進展-中國密碼學會2009年論文集,Science Press USA Inc,2009:58-63. WANG Hui-juan, WANG Jin-ling, GONG Lv-le. Generalized Self-Shrinking Sequences of Fourth Classes of GF(3)[A].Advances in Cryptography-the 2009 Paper Collection of the China Cipher Society,Science Press USA Inc,2009:58-63.

Pseudo-Randomness of New Generalized Self-shrinking Sequence on GF(3)

XU Yu-chun1, WANG Jin-ling2

(1.Zhengzhou Railway Vocational and Technical College, Zhengzhou Henan 450052,China; 2.Department of Mathematics, Zhengzhou University, Zhengzhou Henan 450001,China)

New model of a generalized self-shrinking sequence is constructed, based on this new model, the analysis and calculation indicates that the minimum cycle of this new-type generalized self-shrinking sequence is 2×3n-1.Accurate statistics is also done on the number of new sequences 1 long 1-pattern, and calculation shows that the 0-pattern, 1-pattern, 2-pattern are in very balanced distribution. Research indicates that such new sequences over GF (2) on the fourth class of generalized self shrinking sequences have fairly good pseudo-randomness, some new indicators of cryptography are drawn, and all are relatively improved. The new self-shrinking sequence on GF(3) keeps very good pseudo-randomness, and as compared with other self-shrinking sequences,has much better crypto properties.

generalized self-shrinking sequence; m-sequence; run distribution; cycle

2015-04-01；

2015-07-28 Received date:2015-04-01；Revised date：2015-07-28

河南省教育廳自然科學指導性計劃項目(No.200510459003)

Foundation Item:Natural Science Guiding Program of Education Office of Henan Province(No.200510459003)

TN918.4

A

1002-0802(2015)09-1078-04

10.3969/j.issn.1002-0802.2015.09.019

徐玉春(1986—)女，碩士，助教，主要研究方向為代數(shù)與密碼學;

王錦玲(1963—)女，碩士，副教授，主要研究方向為代數(shù)與密碼學。