擴展的WG序列線性復雜度的研究

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

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

擴展的WG序列線性復雜度的研究

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

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

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

關鍵詞：WG序列;三項式;隨機性;線性復雜度

0引言

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

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

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

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

1預備知識

設F(q)=GF(q), 則a={ai}, ai∈F2表示F2上的二元序列.序列a={ai}的線性復雜度是指產(chǎn)生此序列的LFSR的最小階數(shù), 記為LS(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)是一個從F到K的映射函數(shù). 當q=2時, TrF/K(x)可簡寫成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序列的線性復雜度

2.1原WG序列的線性復雜度

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

由推論1, 以下對基于三項式的WG序列的線性復雜度展開研究.

2.2基于三項式的WG序列的線性復雜度

令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ù)個+非指數(shù)個

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

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ù)個+指數(shù)個

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

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是研究三項式的過程中找到的兩個具體的例子,其中例1為指數(shù)級增長,例2為線性級增長.

例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的線性復雜度為LS(b)=LS(f(x))=5n.

3總結

參考文獻:

[1] 郭鑫.偽隨機序列構造及其隨機性分析研究[D]. 上海：上海交通大學,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

基金項目：國家自然科學基金項目(61472114); 保密通信重點實驗室基金項目(9140C110203140C11049).

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

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

中圖分類號:TP309MSC2010: 94A60

文獻標志碼:A

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