序列低頻重乘積關系計算算法的研究*

胡建勇，張文政，董新鋒

(保密通信重點實驗室，四川 成都 610041)

?

序列低頻重乘積關系計算算法的研究*

胡建勇，張文政，董新鋒

(保密通信重點實驗室，四川 成都 610041)

摘要：針對周期序列實現有效的離散傅里葉頻譜攻擊，前提條件是尋找到序列的一對低頻重乘積關系。基于低頻重乘積關系如何計算的問題，在時域上提出了通常的低頻重乘積關系計算算法。為了減少計算算法的遍歷復雜性，利用序列的頻域特性和跡表示，在頻域上提出了更加有效的低頻重乘積關系計算算法。最后，針對頻域上的低頻重乘積關系計算算法，分別利用跡函數的乘積關系以及滿足乘積關系序列在頻域上的等價條件，給出了關于乘積序列跡表示的兩種適用計算方法。

關鍵詞：頻譜攻擊；低頻重；乘積關系；頻域特性；跡表示

0引言

離散傅里葉頻譜攻擊[1-3]是針對周期序列的一類代數攻擊[4-9]，其在頻域上建立起以參照序列與輸出序列時間間隔為未知量的方程并求解，最后恢復出密鑰或者計算出輸出序列的后續比特。離散傅里葉頻譜攻擊的有效實現嚴重依賴于序列低頻重乘積關系[1,2,10]的計算。當已知的輸出序列比特數小于該序列的線性復雜度時，對周期序列進行離散傅里葉頻譜攻擊的先決條件，是尋找到該周期序列的一組低頻重乘積關系，并且這對低頻重乘積關系的線性復雜度嚴重影響離散傅里葉頻譜攻擊的數據復雜度。事實上，在給定序列a的一組低頻重乘積關系b和u時，離散傅里葉頻譜攻擊的數據復雜度為l(b)+l(u)。因此，一組低頻重乘積關系的線性復雜度之和越小，離散傅里葉頻譜攻擊的數據復雜度就越小。

既然低頻重乘積關系對于離散傅里葉頻譜攻擊具有如此重要的作用，那么就有必要對低頻重乘積關系作進一步研究，比如研究低頻重乘積關系的計算。但是目前為止，尚未有文獻給出具體的低頻重乘積關系的計算算法。

本文的目的就是研究如何快速計算序列的低頻重乘積關系，分別從時域上和頻域上提出低頻重乘積關系的計算算法，從而完善離散傅里葉頻譜攻擊的相關理論研究，彌補就低頻重乘積關系如何計算這一問題的短缺。

1預備知識

為了便于理解，這里先將本文用到的記號以及數學知識作簡要說明。

n：正整數，通常取為線性反饋移位寄存器的位數；

N：等于2n-1，之所以取這樣的N，是因為基于n位線性反饋移位寄存器產生的序列，不論是濾波序列，還是組合序列，N一定是其一個周期，即其最小周期一定能被N整除；

a：周期為N的二進制序列；

l(a)：序列a的線性復雜度；

α：域F2n上階為N的元素，通常選本原元；

ns：使得等式s≡s2t(mod N)成立的最小t值；

Cs：代表元為s的分圓陪集，定義為Cs={s2imod N|i=0,1,…,ns-1}，Cs中的最小元素稱為分圓陪集首。不失一般性，就定義s為Cs的分圓陪集首。

Γ2(N)：在模N的意義下，所有分圓陪集首構成的集合。

周期序列a的離散傅里葉頻譜變換定義為：

離散傅里葉頻譜逆變換定義為：

序列A稱為a的離散傅里葉頻譜序列，簡稱頻譜序列。頻譜序列中非零頻譜值的個數，定義為序列的頻譜重量。事實上，一個序列的頻譜重量就等于該序列的線性復雜度。令：

則有

at=A(αt)更進一步A(x)可以寫成序列跡表示[10]的形式：

從而得到序列a的跡表示：

記Na為序列a對應頻譜序列A中非零頻譜值構成的集合，具體定義為：

Na={k∈Γ2(N)|Ak≠0}

于是，序列的跡表示可以簡化為：

給定序列a，當序列b和u滿足下列兩個關系時：(1)乘積關系u=a°b；(2)線性復雜度關系l(u)+l(b)≤l(a)時，就稱(b，u)是序列a的一組低頻重乘積關系。

引理2[12]：若時序上周期為T的序列a,c,d，滿足：d=a°c，其充要條件是在頻域上滿足：

其中m=0,1,…,T。

2時域上低頻重乘積關系的計算

取定一個序列b，u便可以根據u=a°b計算得出，因此最直接的方法是遍歷所有的b，再驗證b和u是否滿足線性復雜度關系。然而考慮到遍歷復雜度的問題，通常先利用線性復雜度關系過濾掉一些序列b。當序列b和u滿足線性復雜度關系，即l(u)+l(b)≤l(a)時，則序列b必須滿足：

0l(b)≤l(a)

(1)

由于通常的低頻重乘積關系計算算法未涉及序列的傅里葉頻譜值，不妨稱通常的低頻重乘積關系計算算法為時域上的低頻重乘積關系計算算法，具體細節如算法1所述：

算法1：時域上的低頻重乘積關系計算算法。

已知條件：給定N比特序列a。

目的：求解序列b和u，使得u=a°b，且滿足l(u)+l(b)≤l(a)。

算法過程：

(1)初始化：t=0，b=0，V為所有N比特序列構成的集合。

(2)V=V/b，任意選取b∈V,t=t+1。如果t?2N-1，輸出“不存在這樣的低頻重乘積關系”，程序結束；否則，執行步驟(3)。

(4)計算u=a°b，得到u的線性復雜度l(u)。如果l(u)+l(b)≤l(a)，則輸出b和u；否則，轉回步驟(2)。

時域上的低頻重乘積關系計算算法雖然利用了序列b的線性復雜度性質過濾掉一些序列b，在一定程度上降低了算法的復雜度。但是由于序列b無論如何仍要遍歷整個集合V，并且對于每個序列b，都要計算其復雜度。相對地，序列u則是通過序列b的過濾而直接避免被計算，從這個層面上來說，真正過濾的是序列u。并且b確定時，序列u也跟著確定。因此如何利用序列b的線性復雜度性質，使得不滿足要求的序列b直接不被選取，減少序列b的遍歷復雜度，真正意義上過濾掉一部分序列b，是進一步優化算法，減少算法復雜度的關鍵。

3頻域上低頻重乘積關系的計算

利用序列的跡表示，可以很快計算該序列的線性復雜度。假設序列a的跡表示式為：

其中,t=0,1,…,N-1，那么序列a的線性復雜度可由公式：

(2)

快速計算得出。由此可以看出，一個序列的線性復雜度只與對應頻譜序列的非零項的個數有關，并且頻譜序列中非零項對應的分圓陪集首一旦確定，頻譜序列的非零項個數就確定了，換句話說，該序列的線性復雜度就確定了。因此，確定序列a的線性復雜度，關鍵在于集合Na的確定，根本無需知道序列a的任何比特。

對于任意N比特長度序列a，集合Na?Γ2(N)。欲求序列a的一組低頻重乘積關系(b，u)，首先計算序列a的離散傅里葉頻譜序列，得到其跡表示，然后猜測序列b的跡表示。雖然不知道具體的Nb，但同樣有Nb?Γ2(N)。由關系式(1)和線性復雜度的計算式(2)知：

0(a)

(3)

因此只需在集合Γ2(N)中選擇恰當的分圓陪集首k滿足關系式(3)，便可在選取序列b之前，直接過濾掉一部分序列。定義集合

選定好分圓陪集首后，假設：

Nb={r1,r2,…,rt}

其中t為集合Nb的大小，對于每一個k∈Nb，Bk的可選值有2nk-1個，定義集合

M2={(Br1,Br2,…,Brt)|Bri∈F2nk/0}

其中ri∈Nb,i=1,2,…,t，從而具有相同線性復雜度的序列b的總個數為：

然后根據乘積關系u=a°b，得到u的跡表示，計算u的線性復雜度。最后驗證b和u是否滿足線性復雜度關系。于是得到新的低頻重乘積關系計算算法，由于新的低頻重乘積關系計算算法用到了序列的離散傅里葉頻譜值，稱這樣的算法為頻域上的低頻重乘積關系計算算法，具體細節如算法2所述：

算法2：頻域上的低頻重乘積關系計算算法

已知條件：給定N比特序列a；

目的：求解序列b和u，使得u=a°b，且滿足l(u)+l(b)≤l(a)。

算法過程：

步驟2：M1=M1/Nb，任意選取Nb∈M1，i=i+1。如果i?|M1|，輸出“不存在這樣的低頻重乘積關系”；否則，執行步驟3。

步驟3：M2={(Br1,Br2,…,Brt)|Bri∈F2nk/0}，j=0，(Br1,Br2,…,Brt)=(0,0,…,0)。

步驟4：M2=M2/{(Br1,Br2,…,Brt)}，任意選取(Br1,Br2,…,Brt)∈M2，j=j+1。如果j?|M2|，返回步驟2；否則執行步驟5。

步驟5：計算u=a°b，得到u的線性復雜度l(u)。如果l(u)+l(b)≤l(a)，則輸出b和u；否則，轉回步驟4。

算法2——頻域上的低頻重乘積關系計算算法中，步驟4選擇序列b的非零離散傅里葉頻譜值，相當于選擇具體的序列b，而在此之前，利用序列b應該滿足的線性復雜度關系，使得滿足條件的Nb構成集合M1，遍歷時直接在集合M1中選取適當的Nb，從而達到選取序列b之前，預先過濾掉一部分序列的效果。

與算法1相比，算法2利用低頻重乘積關系的線性復雜度關系，在遍歷序列b之前，率先過濾掉一部分不滿足條件的序列，減少了遍歷的復雜度，這是算法1不能達到的，因此算法2的算法復雜性要小于算法1的算法復雜性。另外，算法2充分利用序列的頻域性質，實現在頻域上計算低頻重乘積關系，這也為低頻重乘積關系的計算提供一種新的方式。

值得一提的是，算法2中步驟5計算序列u，與算法1中的計算也有區別。算法1中由于知道序列b的每一位，直接對應位相乘，便可得到序列u的每一位。而算法2直接將序列a的跡表示與序列b的跡表示相乘，得到序列u的跡表示，從而快速計算u的線性復雜度，避免了序列u的比特位計算，減少了算法的計算復雜性。

利用序列的跡表示相乘是計算序列u的跡表示的方法之一，這里還有另外一種方法。序列u的跡表示的形式如下：

因此只需確定Uk的值即可。根據引理2，可以得到:

(4)

注意這里并不需要對所有的k，計算出Uk，而僅僅對于k∈Γ2(N)，計算Uk即可。計算式(4)中，頻譜序列A可由序列a通過離散傅里葉變換得到，頻譜序列B則滿足：當k∈Nb時，步驟(4)已經取定了Bk；當k∈Γ2(N)/Nb時，Bk=0；而對于k?Γ2(N)，均可根據引理1計算得出。因此計算Uk是可行的，最后求解出序列u的跡表示。與直接利用序列的跡表示相乘相比，跡表示相乘的計算方法主要的計算復雜性在于跡函數的相乘，而這種計算方法需要計算序列b的所有頻譜值，盡管可根據引理1快速計算得出，但還是無法避免增加整個算法的計算復雜度和數據復雜度。

4結語

鑒于低頻重乘積關系對于離散傅里葉頻譜攻擊的重要性，本文對序列的低頻重乘積關系計算算法進行了研究，分別提出了時域上的低頻重乘積關系計算算法和頻域上的低頻重乘積關系的計算算法，對有效實現序列的離散傅里葉頻譜攻擊具有重要的作用。

另外，引入指示器隨機變量Ik，Ik的具體定義為：

則序列b的線性復雜度可通過以下方式計算：

假如我們能夠根據乘積關系u=a°b得到序列u的線性復雜度和指示器隨機變量Ik的關系，那么就可以將低頻重乘積關系的計算問題轉化為0-1整數規劃問題。因此，下一步的計劃主要是研究如何將序列u的線性復雜度的變量轉化為關于指示器隨機變量Ik的函數。

參考文獻：

[1]GONG G,R?njom S,Helleseth T.Fast Discrete Fourier Spectra Attacks on Stream Ciphers[J].IEEE Transactions on Information Theory.2011,57: 5555-5565.

[2]王晶晶,陳克非.序列快速傅里葉攻擊的改進 [J].上海交通大學學報:自然版，2012,46(02): 285-288.

WANG Jing-jing,CHEN Ke-fei.Improvement of Discrete Fourier Transform Attack[J].Journal of Shanghai Jiaotong University.2012,46(02): 285-288.

[3]王晶晶.序列密碼的快速離散傅里葉頻譜攻擊[D].上海交通大學碩士論文，2013: 13-34.

WANG Jing-jing.Fast Discrete Fourier Spectra Attacks of Stream Ciphers[D].Shanghai Jiaotong University.2013: 13-34.

[4]Courtois N.Fast Algebraic Attacks on Stream Ciphers with Linear Feedback[C].Advances in Cryptology-CRYPTO 2003.Springer-Verlag.2003,2729:176-194.

[5]董軍武.DES的S盒的布爾性質[J].通信技術，2012,45(12): 66-70.DONG Jun-wu.Boolean Properties of DES′s S-Boxes[J].Communications Technology.2012,45(12):66-70.

[6]Armknecht F.Improving Fast Algebraic Attacks[C].FSE 2004.Springer-Verlag.2004,3017: 65-82.

[7]Courtois N,Meier W.Algebraic Attacks on Stream Ciphers with Linear Feedback[C].Advances in Cryptology - Eurocrypt’2003.Springer-Verlag.2003,2656:345-359.

[8]Armknecht F,Krause M.Algebraic Attacks on Combiners with Memory[C].Advances in Cryptology - CRYPTO 2003.Springer-Verlag.2003,2729:162-176.

[9]Helleseth T,R?njom S.Simplifying Algebraic Attacks with Univariate Analysis[C].Information Theory and Applications Workshop (ITA),2011.[S.l.]: IEEE,2011: 1-7.

[10]WANG Jing-jing,CHEN Ke-fei,ZHU Shi-xiong.Annihilators of Fast Discrete Fourier Spectra Attacks[C].Advances in Information and Computer Security.Heidelberg: Springer,2012:182-196.

[11]R?njom S,Gong G,Helleseth T.On Attacks on Filtering Generators Using Linear Subspace Structures[C].Sequences,Subsequences,and Consequences.Berlin Heidelberg: Springer,2007,4893: 204-217.

[12]胡建勇，張文政.一類低頻重零化子的推導及頻譜分析[J].計算機應用，2015,35(12):3447-3449,3445.

HU Jian-yong,ZHANG Wen-zheng.Derivation and Spectrum Analysis of A Kind of Low Weight[J].Journal of Computer Applications.2015,35(12):3447-3449,3455.

Computational Algorithms of Product Relations with Low Spectral Weight

HU Jian-yong,ZHANG Wen-zheng,DONG Xin-feng

(Science and Technology on Communication Security Laboratory,Chengdu Sichuan 610041,China)

Abstract：For implementing effective discrete fourier spectral attack on periodic sequence,the premise condition is to find a pair of product relations with low spectral weight.Based on the problem of how to calculate the product relations,a general computational algorithm for product relations with low spectral weight is proposed in time domain.In order to reduce the traversing complexity in calculating product relations with low spectral weight,by using the spectral properties and the trace representations of sequences,a more effective computational algorithm is proposed in frequency domain.Finally,based on computational algorithm for product relations with low spectral weight in frequency domain,and by using the product relation of trace representations and meeting the equivalent condition of product-relation sequence in frequency domain,two applicable methods for calculating trace representation of product sequences are presented.

Key words：spectral attack; low spectral weight; product relations; spectral property; trace representation

doi:10.3969/j.issn.1002-0802.2016.02.018

* 收稿日期：2015-09-11；修回日期：2015-12-19Received date:2015-09-11；Revised date：2015-12-19

基金項目：保密通信重點實驗室基金項目(No.9140C110203140C11049)

Foundation Item:Foundation of Science and Technology on Communication Security Laboratory (No.9140C110203140C11049)

中圖分類號：TP309

文獻標志碼：A

文章編號：1002-0802(2016)02-0217-04

作者簡介：

胡建勇(1990—)，男，碩士研究生，主要研究方向為密碼學；

張文政(1966—)，男，碩士，研究員，主要研究方向為密碼學；

董新鋒(1985—)，男，碩士，工程師，研究方向為密碼學。