單圈T函數(shù)輸出序列k-錯線性復雜度研究

羅小建 胡 斌

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

1 引言

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

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

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

2 準備知識

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

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

2.1 基本定義

定義1[1]設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)有關，則稱f(x)為T函數(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)轉移圖是單圈的，則稱該函數(shù)為單圈T函數(shù)。

定義3[5]對一個周期序列S，每個周期改變小于或等于k比特后得到的新序列的最小線性復雜度，稱為k-錯線性復雜度，記為LCk(S)。

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

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

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

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

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

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

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

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

引理2[6]設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為全零向量時，LC(S)=LC(L(sm))，當d不為全零向量時，LC(S)=2m?1+LC(d)。

由引理3可知，序列的周期越小，線性復雜度越小。

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

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

證明 設單圈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。設單圈T函數(shù)輸出序列的第i分位序列ai=(a0,i,a1,i,…,a2i+1,i,…)，顯然S的一個周期內(nèi)第i分位序列的長度為2n，記為，由引理1知，

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

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

證畢

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

定理1 設S是單圈T函數(shù)輸出序列，當n=2t時，對任意的整數(shù)u,1≤u≤n ?1，令k=u×2n?1,S的k-錯線性復雜度為LCk(S)=n?u+n×2n?u?1。

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

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

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

其中

則

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

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

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

證明 當u=1時，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)，故此時結論成立；

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

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

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

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

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

4 結束語

本文分析了當n=2t時，單圈T函數(shù)輸出序列的k-錯線性復雜度分布情況及k-錯線性復雜度曲線。對于單圈T函數(shù)輸出序列來說，在輸入規(guī)模為任意取值時，單圈T函數(shù)輸出序列的k-錯線性復雜度的分布和k-錯線性復雜度曲線都是非常有意義的問題，值得進一步研究。

[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ù)輸出序列的線性復雜度及穩(wěn)定性.北京郵電大學學報, 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ù)輸出序列性質研究. 電子技術學院學報, 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-錯線性復雜度分析和研究.[碩士論文],合肥工業(yè)大學, 2009.Wang Ju-xiang. Analyse and research of the k-error linear complexity of periodic sequences. [Master dissertation],Hefei University of Technology, 2009.

[11] 郝年朋, 岳勤. 二元周期序列線性復雜度的2位置錯誤譜. 計算機工程, 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.