葉　婷,陳克非,3,沈忠華,孟　倩,張文政

(1. 杭州師范大學(xué)理學(xué)院, 浙江 杭州 310036； 2. 保密通信重點(diǎn)實(shí)驗(yàn)室, 四川 成都 610041；3. 杭州市密碼與網(wǎng)絡(luò)安全重點(diǎn)實(shí)驗(yàn)室, 浙江 杭州 310036)

擴(kuò)展的WG序列線性復(fù)雜度的研究

葉婷1,2,陳克非1,2,3,沈忠華1,3,孟倩1,3,張文政2

(1. 杭州師范大學(xué)理學(xué)院, 浙江 杭州 310036； 2. 保密通信重點(diǎn)實(shí)驗(yàn)室, 四川 成都 610041；3. 杭州市密碼與網(wǎng)絡(luò)安全重點(diǎn)實(shí)驗(yàn)室, 浙江 杭州 310036)

摘要：Welch-Gong(WG)序列是一類具有良好隨機(jī)性的二元序列，由特定的五項(xiàng)式通過(guò)WG變換產(chǎn)生.文章將WG變換中特定的五項(xiàng)式推廣成一般的三項(xiàng)式，對(duì)基于三項(xiàng)式的WG序列的線性復(fù)雜度展開研究, 找到了幾類指數(shù)的一般形式，能使序列的線性復(fù)雜度為指數(shù)級(jí)增長(zhǎng), 為三項(xiàng)式在WG變換中的應(yīng)用提供了多種選擇.

關(guān)鍵詞：WG序列;三項(xiàng)式;隨機(jī)性;線性復(fù)雜度

0引言

偽隨機(jī)序列是流密碼系統(tǒng)的核心, 作為密鑰流、隨機(jī)數(shù)生成的重要手段, 有著廣泛的應(yīng)用. 多年來(lái), 如何生成好的偽隨機(jī)序列一直是密碼學(xué)研究的重點(diǎn), 也是密碼學(xué)中許多理論和應(yīng)用的基礎(chǔ)與前提.

對(duì)m序列的研究始于20世紀(jì)50年代, 對(duì)于n級(jí)LFSR, 它具有最大長(zhǎng)度周期2n-1, 除了線性復(fù)雜度外, 其他隨機(jī)特性都好. 正是因?yàn)閙序列的線性復(fù)雜度太小, 所以不能直接用于流密碼系統(tǒng)的密鑰流序列. 根據(jù)Berlekamp-Massey(簡(jiǎn)稱B-M算法): 如果序列的線性復(fù)雜度為n, 則只需要2n個(gè)連續(xù)比特就可以恢復(fù)出全部的序列[1]. 線性復(fù)雜度較高的序列能夠抵抗應(yīng)用B-M算法產(chǎn)生的攻擊.

由Golomb, Gong和Gaal在1998年研究的Welch-Gong(WG)序列是一類具有良好隨機(jī)性的序列，包括長(zhǎng)周期、0, 1分布均勻、理想的2元分布、二值自相關(guān)、與m序列三值互相關(guān)、指數(shù)級(jí)增長(zhǎng)的線性復(fù)雜度等. 2005年, Nawaz和Gong首次提出了WG序列密碼, 并且作為歐洲eSTREAM計(jì)劃候選對(duì)象之一[2]. 之后2個(gè)輕量級(jí)的WG序列密碼相繼提出, 分別是WG-7[3]和WG-8[4]. 最近, Fan等[5]提出使用WG-16密碼體制來(lái)保證4G網(wǎng)絡(luò)的安全性與完整性. 基于WG變換產(chǎn)生的同步流密碼不僅具有很好的隨機(jī)性, 也能抵抗一些攻擊來(lái)保證安全性, 這類密鑰流一般可通過(guò)硬件實(shí)施產(chǎn)生. 由于WG序列良好的密碼學(xué)性質(zhì), 至今被用在各個(gè)領(lǐng)域且引起很多國(guó)內(nèi)外學(xué)者的進(jìn)一步研究.

原WG序列是由特定的五項(xiàng)式通過(guò)WG變換產(chǎn)生的. 針對(duì)WG變換, 一般研究的是奇數(shù)項(xiàng)式, 若能把特定的五項(xiàng)式推廣到一般的三項(xiàng)式、五項(xiàng)式、七項(xiàng)式乃至任意的奇數(shù)項(xiàng)式并且產(chǎn)生的序列仍具有良好的隨機(jī)性, 便能得到一系列更多的偽隨機(jī)序列, 也為偽隨機(jī)序列的應(yīng)用提供更多的選擇. 考慮到多項(xiàng)式通過(guò)WG變換的復(fù)雜程度, 本文將WG變換中特定的五項(xiàng)式推廣成一般的三項(xiàng)式, 產(chǎn)生的序列依然能保持較好的隨機(jī)性. 但序列的線性復(fù)雜度的增長(zhǎng)與三項(xiàng)式中各項(xiàng)的指數(shù)有關(guān), 選取好的指數(shù)能使線性復(fù)雜度呈現(xiàn)指數(shù)級(jí)增長(zhǎng). 因此，本文對(duì)基于三項(xiàng)式的WG序列的線性復(fù)雜度展開全面研究, 找到了幾類指數(shù)的一般形式，能使序列的線性復(fù)雜度為指數(shù)級(jí)增長(zhǎng), 為三項(xiàng)式在WG變換中的應(yīng)用提供了多種選擇.

1預(yù)備知識(shí)

設(shè)F(q)=GF(q), 則a={ai}, ai∈F2表示F2上的二元序列.序列a={ai}的線性復(fù)雜度是指產(chǎn)生此序列的LFSR的最小階數(shù), 記為L(zhǎng)S(a).

定義1[1]F=GF(qn), K=GF(q), 跡函數(shù)TrF/K(x)定義如下:TrF/K(x)=x+xq+…+xqn-1, x∈F.TrF/K(x)是一個(gè)從F到K的映射函數(shù). 當(dāng)q=2時(shí), TrF/K(x)可簡(jiǎn)寫成Tr(x): Tr(x)=x+x2+…+x2n-1,x∈GF(2n). Tr(x)的取值為0或1.

定義2[6]令h(x)=x+xt1+xt2+xt3+xt4, x∈F2n.

其中n, k均為正整數(shù), Tr(h(x))的WG變換為:f(x)=Tr(h(x+1)+1), x∈F2n.

2序列的線性復(fù)雜度

2.1原WG序列的線性復(fù)雜度

定理1[7]f(x)=Tr(h(x+1)+1)=∑i∈ITr(xi), 則

由推論1, 以下對(duì)基于三項(xiàng)式的WG序列的線性復(fù)雜度展開研究.

2.2基于三項(xiàng)式的WG序列的線性復(fù)雜度

令g(x)=x+xq1+xq2, f(x)為Tr(g(x))的WG變換, 即

f(x)=Tr(g(x+1)+1), x∈F2n(n=2k-1或2k).

2.2.1指數(shù)個(gè)+非指數(shù)個(gè)

即(x+1)q1的展開式為指數(shù)個(gè)，(x+1)q2的展開式為非指數(shù)個(gè).

1)q1=2w1k+v1-1,q2=2w2k+v2+1(w1

(x+1)q2=x2w2k+v2+1+x2w2k+v2+x+1.

LS=2w1k+v1+1.

2)q1=2w1k+v1-1,q2=2w2k+v2+2m2k+n2+1(w1

(x+1)q2=x2w2k+v2+2m2k+n2+1+x2w2k+v2+2m2k+n2+x2w2k+v2+1+x2m2k+n2+1+x2w2k+v2+x2m2k+n2+x+1.

Tr(g(x+1)+1)=Tr(x2w2k+v2+2m2k+n2+1+x2w2k+v2+2m2k+n2+x2w2k+v2+1+x2m2k+n2+1+

LS=2w1k+v1+5.

(x+1)q2=x2w2k+v2+1+x2w2k+v2+x+1.

LS≈2(w1-m1)k+v1-n1+1.

4)q1=2w1k+v1-2m1k+n1+1,q2=2w2k+v2+2m2k+n2+1(w1

(x+1)q2=x2w2k+v2+2m2k+n2+1+x2w2k+v2+2m2k+n2+x2w2k+v2+1+x2m2k+n2+1+x2w2k+v2+x2m2k+n2+x+1.

Tr(g(x+1)+1)=Tr(x2w2k+v2+2m2k+n2+1+x2w2k+v2+2m2k+n2+x2w2k+v2+1+x2m2k+n2+1+x2w2k+v2+

LS≈2(w1-m1)k+v1-n1+1+5.

2.2.2指數(shù)個(gè)+指數(shù)個(gè)

即(x+1)q1與(x+1)q2的展開式都為指數(shù)個(gè).

1)q1=2w1k+v1-1,q2=2w2k+v2-1(w1

LS=2w2k+v2-2w1k+v1+1.

2)q1=2w1k+v1-1,q2=2w2k+v2-2m2k+n2+1(w1

LS=2w1k+v1+2(w2-m2)k+v2-n2+1-3.

3)q1=2w1k+v1-2m1k+n1+1,q2=2w2k+v2-2m2k+n2+1(w1

LS=2(w1-m1)k+v1-n1+1+2(w2-m2)k+v2-n2+1-3.

例1和例2是研究三項(xiàng)式的過(guò)程中找到的兩個(gè)具體的例子,其中例1為指數(shù)級(jí)增長(zhǎng),例2為線性級(jí)增長(zhǎng).

例1g(x)=x+xq1+xq2,x∈F2n,n=2k-1或2k,q1=2k+1+2k+1，q2=2k-1.

(x+1)2k+1+2k+1=x2k+1+2k+1+x2k+1+2k+x2k+1+1+x2k+1+x2k+1+x2k+x+1.

例2g(x)=x+xq1+xq2,x∈F2n,n=2k-1或2k,q1=2k+1，q2=2k-1+1.則

(x+1)2k+1=x2k+1+x2k+x+1.

(x+1)2k-1+1=x2k-1+1+x2k-1+x+1.

f(x)=Tr(g(x+1)+1)=Tr(x+x2k-1+x2k-1+1+x2k+x2k+1).

所以序列b的線性復(fù)雜度為L(zhǎng)S(b)=LS(f(x))=5n.

3總結(jié)

參考文獻(xiàn):

[1] 郭鑫.偽隨機(jī)序列構(gòu)造及其隨機(jī)性分析研究[D]. 上海：上海交通大學(xué),2008.

[2] eSTREAM. The ECRYPT stream cipher project[EB/OL]. [2015-06-02]. http://www.ecrypt.eu.org/stream/.

[3] LUO Y, CHAI Q, GONG G, et al. WG-7: a lightweight stream cipher with good cryptographic properties[C]//IEEE.IEEE Global Communications Conference-GLOBECOM. Florida：[s.n.]，2010:1-6.

[4] FAN X X, MANDAL K, GONG G. WG-8: A lightweight stream cipher for resource-constrained smart devices[M]. Quality, Reliability, Security and Robustness in Heterogeneous Networks. Heidelbergs: Springer,2013:617-632.

[5] FAN X X, WU T, GONG G. An efficient stream cipher WG-16 and its application for securing 4G-LTE networks[J]. Applied Mechanics & Materials,2014(490/491):1436-1450.

[6] GONG G, YOUSSEF A M. Cryptographic properties of the Welch-Gong transformation sequence generators[J]. IEEE Transactions on Information Theory,2002,48(11):2837-2846.

[7] NO J S, GOLOMB S W, GONG G, et al. Binary pseudorandom sequences of period 2n-1 with ideal autocorrelation[J]. IEEE Transactions on Information Theory,1998,44(2):814-817.

On the Linear Span of the Extended WG Sequences

YE Ting1,2, CHEN Kefei1,2,3, SHEN Zhonghua1,3, MENG Qian1,3, ZHANG Wenzheng2

(1. School of Science, Hangzhou Normal University, Hangzhou 310036, China；2. Science and Technology on Communication Security Laboratory, Chengdu 610041, China；3. Hangzhou Key Laboratory of Cryptography and Network Security, Hangzhou 310036, China.)

Abstract:Welch-Gong(WG) sequences have good randomness. The original WG sequences are generated by a specific five-term function through WG transformation. This paper extends the specific five-term function to general three-term function in WG transformation, and studies the linear span of WG sequences based on three-term function. Some general forms of the indexes, which can make linear span increase exponentially are found. This provides a variety of options for the applications of three-term function in the WG transformation.

Key words:WG sequences; three-term function; randomness; linear span

收稿日期：2015-08-22

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61472114); 保密通信重點(diǎn)實(shí)驗(yàn)室基金項(xiàng)目(9140C110203140C11049).

通信作者：陳克非(1959—),男,教授,博士，主要從事密碼學(xué)與信息安全研究.E-mail:kfchen@hznu.edu.cn

doi:10.3969/j.issn.1674-232X.2016.03.010

中圖分類號(hào):TP309MSC2010: 94A60

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1674-232X(2016)03-0277-05