單圈T函數(shù)輸出序列k-錯(cuò)線(xiàn)性復(fù)雜度研究

羅小建 胡 斌

(解放軍信息工程大學(xué)電子技術(shù)學(xué)院 鄭州 450004)

1 引言

2002年，文獻(xiàn)[1]提出了T函數(shù)的概念，并對(duì)其進(jìn)行了系列研究。T函數(shù)是非線(xiàn)性的甚至是非代數(shù)的，并能在軟件上快速實(shí)現(xiàn)，T函數(shù)先后用于分組密碼，Hash函數(shù)和流密碼的構(gòu)造。

如果可逆T函數(shù)所決定的狀態(tài)轉(zhuǎn)移圖的周期為2n，則稱(chēng)該T函數(shù)為單圈T函數(shù)。文獻(xiàn)[1]提出用單圈T函數(shù)代替線(xiàn)性移位寄存器作為密鑰發(fā)生器的驅(qū)動(dòng)源的思想，因此，單圈T函數(shù)輸出序列的穩(wěn)定性成為研究的重點(diǎn)。安全強(qiáng)度高的序列不但具有高的線(xiàn)性復(fù)雜度，而且必須具有很好的穩(wěn)定性，而序列的穩(wěn)定性一般采用k-錯(cuò)線(xiàn)性復(fù)雜度表征。

國(guó)內(nèi)外對(duì)單圈T函數(shù)輸出序列線(xiàn)性復(fù)雜度的研究較少，2006年，文獻(xiàn)[2]給出了單圈T函數(shù)輸出序列的線(xiàn)性復(fù)雜度和k-錯(cuò)線(xiàn)性復(fù)雜度；2008年，文獻(xiàn)[3]得到了單圈T函數(shù)按位輸出的序列的線(xiàn)性復(fù)雜度以及k-錯(cuò)線(xiàn)性復(fù)雜度。本文對(duì)單圈T函數(shù)輸出序列的k-錯(cuò)線(xiàn)性復(fù)雜度進(jìn)行了深入研究，利用多項(xiàng)式理論和Chan Games算法，在輸入規(guī)模2tn=時(shí)，分析得到了單圈T函數(shù)輸出序列的線(xiàn)性復(fù)雜度的所有下降點(diǎn)，及其相應(yīng)位置的k-錯(cuò)線(xiàn)性復(fù)雜度取值，并進(jìn)一步給出該序列k-錯(cuò)線(xiàn)性復(fù)雜度的分布情況及k-錯(cuò)線(xiàn)性復(fù)雜度曲線(xiàn)。

2 準(zhǔn)備知識(shí)

線(xiàn)性復(fù)雜度：設(shè)S=s0s1s2…是Z2上周期為N的序列，定義其形式化多項(xiàng)式s(x)為

序列S的線(xiàn)性復(fù)雜度指產(chǎn)生此序列的線(xiàn)性反饋移位寄存器的最小階數(shù)，記為L(zhǎng)C(S)。文獻(xiàn)[4]給出了周期序列S的線(xiàn)性復(fù)雜度的一個(gè)代數(shù)化描述，即

2.1 基本定義

定義1[1]設(shè)f(x)是Z/(2n)→Z/(2n)上的多輸出函數(shù)，記f(x)=([f(x)]n?1,…,[f(x)]1,[f(x)]0)，如果其輸出的第i位[f(x)]i僅與輸入的第0至第i位，即([x]i,…,[x]0)有關(guān)，則稱(chēng)f(x)為T(mén)函數(shù)。其中[x]i,[f(x)]i表示x和f(x)的第i路分量，i=0,1,…,n ?1。

顯然，根據(jù)T函數(shù)的定義，可將T函數(shù)表示為如下形式：

其中fi(x)=fi([x]i,[x]i?1,…,[x ]0)為布爾函數(shù)。

定義2[1]若可逆T函數(shù)的狀態(tài)轉(zhuǎn)移圖是單圈的，則稱(chēng)該函數(shù)為單圈T函數(shù)。

定義3[5]對(duì)一個(gè)周期序列S，每個(gè)周期改變小于或等于k比特后得到的新序列的最小線(xiàn)性復(fù)雜度，稱(chēng)為k-錯(cuò)線(xiàn)性復(fù)雜度，記為L(zhǎng)Ck(S)。

從定義可以看出，計(jì)算LCk(S)的一般方法為構(gòu)造一個(gè)周期與S相同的序列e，一般稱(chēng)為錯(cuò)誤序列，則LCk(S)=min{LC(S⊕e)|W(e)≤k }。

定義4[5]對(duì)周期序列S，定義minerror(S)為使得LCk(S)＜LC(S)的k的最小值。

定義5[5]設(shè)S是Z2上周期為N的序列，S的k-錯(cuò)復(fù)雜度曲線(xiàn)定義為S的k-錯(cuò)復(fù)雜度序列，即LC0(S)=LC(S),LC1(S),…,LCW(S)(S)。

2.2 單圈T函數(shù)輸出序列

單圈T函數(shù)周期達(dá)到最大，即為2n，設(shè)si=(ai,0,ai,1,…,ai,n?1)為單圈T函數(shù)輸出的第i個(gè)狀態(tài)，1≤i≤n ?1，稱(chēng)S(T)=(s0|s1|…|s2n?1……)為單圈T函數(shù)輸出序列，其中si|si+1表示狀態(tài)si和si+1的級(jí)聯(lián)，即si|si+1=(ai,0,…,ai,n?1,ai+1,0,…,ai+1,n?1)。

引理1[1]設(shè)f(x)是單圈T函數(shù)，s0, s1,…,s2n?1表示f(x)在一個(gè)周期內(nèi)的所有輸出狀態(tài)，設(shè)ai=(a0,i,a1,i,…,a2n?1,i,…)表示f(x)的第i分位序列，則(1)ai的周期為2i+1; (2)aj,i⊕aj+2i,i=1對(duì)j≥0都成立。

3 單圈T函數(shù)輸出序列k-錯(cuò)線(xiàn)性復(fù)雜度研究

下面研究當(dāng)n=2t時(shí)，單圈T函數(shù)輸出序列的k-錯(cuò)線(xiàn)性復(fù)雜度的分布情況及k-錯(cuò)線(xiàn)性復(fù)雜度曲線(xiàn)。首先給出幾個(gè)引理。

引理2[6]設(shè)S是周期為N的二元序列，若N=2t，則minerror(S)=2W(N?LC(S))。

引理3[7]令sm=(s0, s1,…,s2m?1)∈Z /(22m)，則S=(sm,sm,sm,…)是周期為2m的序列。記sm=(L(sm),R(sm))，其中L(sm)=(s0,…,s2m?1?1), R(sm)=(s2m?1,…,s2m?1)分別表示sm的左半部分和右半部分。令d=L(sm)⊕R(sm)，則當(dāng)d為全零向量時(shí)，LC(S)=LC(L(sm))，當(dāng)d不為全零向量時(shí)，LC(S)=2m?1+LC(d)。

由引理3可知，序列的周期越小，線(xiàn)性復(fù)雜度越小。

引理4[8]設(shè)k, t∈Z,k＜2t，則(1+x)k?1的項(xiàng)數(shù)為2W(k?1)。

引理5 設(shè)S是單圈T函數(shù)輸出序列，記單圈T函數(shù)的第i分位序列為ai,ai改變?nèi)舾杀忍睾蟮男蛄杏洖閎i，其周期為p(bi)，則對(duì)任意整數(shù)j,0≤j≤i，可在S的每個(gè)周期內(nèi)通過(guò)改變a的2n?1i個(gè)比特得到bi，使得p(bi)=2j成立，其中0≤i≤n ?1。

證明 設(shè)單圈T函數(shù)輸出序列為S=(a0,0,a0,1,…,a0,n?1,a1,0,a1,1,…,a1,n?1,…,a2n?1,0,a2n?1,1,…,a2n?1,n ?1,…)，顯然S的周期p(S)=n×2n。設(shè)單圈T函數(shù)輸出序列的第i分位序列ai=(a0,i,a1,i,…,a2i+1,i,…)，顯然S的一個(gè)周期內(nèi)第i分位序列的長(zhǎng)度為2n，記為，由引理1知，

設(shè)bi=(b0,i,b1,i,…,b2j?1,i,…)是周期為2j的任一序列，0≤j≤i，并記表示bi的前t個(gè)比特，下面證明將變成需要改變2n?1個(gè)比特。

由于p(b)=2j|2i，顯然，=(,)。i 變成需要改變x個(gè)不妨設(shè)將比特，0≤x ≤2i，即(a,a,…,)和有x個(gè)0,i1,i比特不同，2i?x個(gè)比特相同。再由引理1知，⊕=1，因此和有x個(gè)比特相同，2i?x個(gè)比特不同，進(jìn)而要將(a2i,i,a2i+1,i,…,a2i+1?1,i)變成需要改變2i?x個(gè)比特。因此，要將(a,a,…,a)變成一共需要改變x+(2i?x)=2i個(gè)比特。又因?yàn)?2i+1|2n,由2n?1?i個(gè)(a,a,…,a)組成，故0,i1,i2i+1,i將變成需要改變2n?1?i×2i=2n?1個(gè)比特。

證畢

由引理5及其證明過(guò)程可知，對(duì)任意滿(mǎn)足j＜i+1的非負(fù)整數(shù)j，在單圈T函數(shù)輸出序列的一個(gè)周期內(nèi)，改變分位序列ai的2n?1個(gè)比特，可使得改變后的序列bi為周期整除2i的任意序列。

定理1 設(shè)S是單圈T函數(shù)輸出序列，當(dāng)n=2t時(shí)，對(duì)任意的整數(shù)u,1≤u≤n ?1，令k=u×2n?1,S的k-錯(cuò)線(xiàn)性復(fù)雜度為L(zhǎng)Ck(S)=n?u+n×2n?u?1。

設(shè)ai=(a0,i,a1,i,…,a2n?1,i,…)為輸出序列的第i分位序列，0≤i≤n ?1。由引理3可知，要將序列S的線(xiàn)性復(fù)雜度降低，在S的一個(gè)周期內(nèi)改變相同比特?cái)?shù)的前提下，改變后序列的周期越小，其線(xiàn)性復(fù)雜度越小。進(jìn)一步地，根據(jù)序列S的特性和引理5可知，當(dāng)S在每個(gè)周期內(nèi)改變u×2n?1個(gè)比特時(shí)，其周期最小可以達(dá)到n×2n?u，即將an?u,…,an?1這u個(gè)分位序列分別改變2n?1個(gè)比特，使得改變后的分位序列周期整除2n?u。

設(shè)(1+x)u=1+c1x+…+cuxu，其中c1,…,cu∈Z2。對(duì)任意整數(shù)i(1≤i≤u)，若ci=0，將分位序列an?1?(u?i)在每周期內(nèi)改變2n?1個(gè)比特使其變成全零序列；若ci=1，將an?1?(u?i)在每周期內(nèi)改變2n?1個(gè)比特使其變成an?u?1。

因此，根據(jù)ci的取值，存在序列bn?1?(u?i)，滿(mǎn)足周期為2n且W(bn?1?(u?i))=2n?1，使得an?1?(u?i)⊕bn?1?(u?i)=cian?u?1,i=1,2,…,u 。令錯(cuò)誤序列為=(0…0b0,n?u… b0,n?1,0…0b1,n?u…b1,n?1, …,0…0其中(0…0bi,n?u…bi,n?1)中含有n個(gè)比特，i=0,1,…,2n?1，則W()=u×2(n?1),S⊕的周期為n×2n?u。設(shè)S⊕的形式化多項(xiàng)式為s'(x)，即

其中

則

設(shè)S是二元周期序列，記err1(S)為使得LCk(S)＜LC(S)成立最小的k，稱(chēng)err1(S)為序列S線(xiàn)性復(fù)雜度的第1下降點(diǎn)，顯然err1(S)=minerror(S)；記err2(S)為使得LCt(S)＜LCk1(S)成立最小的t，其中k1=err1(S)，稱(chēng)err2(S)為序列S線(xiàn)性復(fù)雜度的第2下降點(diǎn)。同樣可得到第3,…，第k下降點(diǎn)的定義。顯然1≤err1(S)＜…＜errk(S)＜…且LC(S)＞LCerr1(S)(S)＞…＞LCerrk(S)(S)＞…。

下面給出當(dāng)n=2t時(shí)，單圈T函數(shù)輸出序列線(xiàn)性復(fù)雜度的第u下降點(diǎn)erru(S)及當(dāng)k=erru時(shí)，LCk(S)取值。

定理2 設(shè)S是單圈T函數(shù)輸出序列，當(dāng)n=2t時(shí)，對(duì)任意整數(shù)u,1≤u≤n ?1,S的線(xiàn)性復(fù)雜度的第u下降點(diǎn)erru(S)=u×2n?1，且LCk(S)=n?u+n×2n?u?1，其中k=err(S)。

證明 當(dāng)u=1時(shí)，err1(S)=minerror(S)=2W(n×2n?1?n×2n?1?n)=2n?1，由引理5可知，LCk(S)=n?1+n×2n?2，其中k=err1(S)，故此時(shí)結(jié)論成立；

假設(shè)當(dāng)u=h時(shí)，err(S)=2h×(n?1)且LCk(S)=n?h+n×2n?h?1，其中k=errh(S)，由定義可知，存在錯(cuò)誤序列滿(mǎn)足周期為n×2n且W()=h×2n?1，使得LC(S⊕)=n?h+n×2n?h?1。

定理3的證明可直接由LCk(S)的定義、定理2及其推論得到，在此不再進(jìn)行證明。

基于上述討論，可以得到當(dāng)n=2t時(shí)，單圈T函數(shù)輸出序列的k-錯(cuò)線(xiàn)性復(fù)雜曲線(xiàn)，如圖1所示：

圖1 單圈T函數(shù)輸出序列k-錯(cuò)線(xiàn)性復(fù)雜度曲線(xiàn)

圖1形象地描述了當(dāng)n=2t時(shí)，單圈T函數(shù)輸出序列的k-錯(cuò)線(xiàn)性復(fù)雜的變化情況，圖中橫坐標(biāo)k表示序列S在一個(gè)周期內(nèi)改變了k個(gè)比特，縱坐標(biāo)LCk(S)表示序列S的k-錯(cuò)線(xiàn)性復(fù)雜度取值。

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

本文分析了當(dāng)n=2t時(shí)，單圈T函數(shù)輸出序列的k-錯(cuò)線(xiàn)性復(fù)雜度分布情況及k-錯(cuò)線(xiàn)性復(fù)雜度曲線(xiàn)。對(duì)于單圈T函數(shù)輸出序列來(lái)說(shuō)，在輸入規(guī)模為任意取值時(shí)，單圈T函數(shù)輸出序列的k-錯(cuò)線(xiàn)性復(fù)雜度的分布和k-錯(cuò)線(xiàn)性復(fù)雜度曲線(xiàn)都是非常有意義的問(wèn)題，值得進(jìn)一步研究。

[1] Klimov A and Shamir A. A new class of invertible mappings.Workshop of CHES 2002, Springer Verlag, 2003, LNCS 2523:470-483.

[2] Zhang W Y and Wu C K. The algebraic normal form, linear complexity and k-error linear complexity of single-cycle T-function. Proceedings of SETA 2006, LNCS 4086, Springer Heidelberg, 2006: 391-401.

[3] 趙璐, 溫巧燕. 單圈T函數(shù)輸出序列的線(xiàn)性復(fù)雜度及穩(wěn)定性.北京郵電大學(xué)學(xué)報(bào), 2008, 31(4): 62-65.Zhao Lu and Wen Qiao-yan. Linear complexity and stability of output sequences of single cycle T-function. Journal of Beijing University of Posts and Telecommunications, 2008,31(4): 62-65.

[4] Cusick T, Ding C, and Renvall A. Stream ciphers and number theory. North-Holland, Elsevier, 1998.

[5] Ding C, Xiao G, and Shan W. The stability theoery of stream ciphers. Springer-Verlag, Heidelberg, LNCS 561, 1991: 1.

[6] Kurosawa K and Sato F. A relationship between linear complexity and k-error linear complexity. IEEE Transactions on Information Theory, 2000, 46(2): 694-698.

[7] Games R A and Chan A H. A fast algorithm for determining the complexity of a binary sequence with period 2n. IEEE Transactions on Information Theory, 1983, 29(4): 144-146.

[8] Massey J, Costeuo D, and Juotesen J. Polynomial weights and code constructions. IEEE Transactions on Information Theory, 1973, IT-19(1): 101-110.

[9] 周旋, 瞿成勤, 李斌. 單圈T函數(shù)輸出序列性質(zhì)研究. 電子技術(shù)學(xué)院學(xué)報(bào), 2009, 21(6): 13-16.Zhou Xuan, Qu Cheng-qin, and Li Bin. Research on properties of output sequences of single cycle T-function.Journal of Institure of Electronic Technology, 2009, 21(6):13-16.

[10] 王菊香. 周期序列的k-錯(cuò)線(xiàn)性復(fù)雜度分析和研究.[碩士論文],合肥工業(yè)大學(xué), 2009.Wang Ju-xiang. Analyse and research of the k-error linear complexity of periodic sequences. [Master dissertation],Hefei University of Technology, 2009.

[11] 郝年朋, 岳勤. 二元周期序列線(xiàn)性復(fù)雜度的2位置錯(cuò)誤譜. 計(jì)算機(jī)工程, 2010, 36(2): 158-160.Hao Nian-peng and Yue Qin. 2-position error spectrum of linear complexity for binary periodic sequence. Computer Engineering, 2010, 36(2): 158-160.

[12] Xu Li-qing. On GF(P)-linear complexities of binary sequences. The Journal of China Universities of Posts and Telecommunications, 2009, 16(4): 112-115.