序列低頻重乘積關(guān)系計(jì)算算法的研究*

胡建勇，張文政，董新鋒

(保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041)

?

序列低頻重乘積關(guān)系計(jì)算算法的研究*

胡建勇，張文政，董新鋒

(保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041)

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

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

0引言

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

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

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

1預(yù)備知識

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

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

N：等于2n-1，之所以取這樣的N，是因?yàn)榛趎位線性反饋移位寄存器產(chǎn)生的序列，不論是濾波序列，還是組合序列，N一定是其一個(gè)周期，即其最小周期一定能被N整除；

a：周期為N的二進(jìn)制序列；

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

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

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

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

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

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

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

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

則有

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

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

記Na為序列a對應(yīng)頻譜序列A中非零頻譜值構(gòu)成的集合，具體定義為：

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

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

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

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

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

2時(shí)域上低頻重乘積關(guān)系的計(jì)算

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

0l(b)≤l(a)

(1)

由于通常的低頻重乘積關(guān)系計(jì)算算法未涉及序列的傅里葉頻譜值，不妨稱通常的低頻重乘積關(guān)系計(jì)算算法為時(shí)域上的低頻重乘積關(guān)系計(jì)算算法，具體細(xì)節(jié)如算法1所述：

算法1：時(shí)域上的低頻重乘積關(guān)系計(jì)算算法。

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

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

算法過程：

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

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

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

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

3頻域上低頻重乘積關(guān)系的計(jì)算

利用序列的跡表示，可以很快計(jì)算該序列的線性復(fù)雜度。假設(shè)序列a的跡表示式為：

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

(2)

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

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

0(a)

(3)

因此只需在集合Γ2(N)中選擇恰當(dāng)?shù)姆謭A陪集首k滿足關(guān)系式(3)，便可在選取序列b之前，直接過濾掉一部分序列。定義集合

選定好分圓陪集首后，假設(shè)：

Nb={r1,r2,…,rt}

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

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

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

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

算法2：頻域上的低頻重乘積關(guān)系計(jì)算算法

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

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

算法過程：

步驟2：M1=M1/Nb，任意選取Nb∈M1，i=i+1。如果i?|M1|，輸出“不存在這樣的低頻重乘積關(guān)系”；否則，執(zhí)行步驟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；否則執(zhí)行步驟5。

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

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

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

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

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

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

(4)

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

4結(jié)語

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

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

則序列b的線性復(fù)雜度可通過以下方式計(jì)算：

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

參考文獻(xiàn)：

[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ìn) [J].上海交通大學(xué)學(xué)報(bào):自然版，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].上海交通大學(xué)碩士論文，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盒的布爾性質(zhì)[J].通信技術(shù)，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]胡建勇，張文政.一類低頻重零化子的推導(dǎo)及頻譜分析[J].計(jì)算機(jī)應(yīng)用，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

基金項(xiàng)目：保密通信重點(diǎn)實(shí)驗(yàn)室基金項(xiàng)目(No.9140C110203140C11049)

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

中圖分類號：TP309

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

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

作者簡介：

胡建勇(1990—)，男，碩士研究生，主要研究方向?yàn)槊艽a學(xué)；

張文政(1966—)，男，碩士，研究員，主要研究方向?yàn)槊艽a學(xué)；

董新鋒(1985—)，男，碩士，工程師，研究方向?yàn)槊艽a學(xué)。