潘臻，唐小虎

（西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，四川 成都 610031）

1 引言

在1994年，Klapper和Goresky提出了帶進(jìn)位的反饋移位寄存器（FCSR）[1]，給出的分析結(jié)果表明，F(xiàn)CSR易于實(shí)現(xiàn)，生成速度快，其極大周期序列（l-序列）有良好的統(tǒng)計(jì)特性，在帶進(jìn)位加的作用下，l-序列線性復(fù)雜度極高[1～4]，避免了使用LFSR的m-序列所受的B-M算法攻擊，使得近十多年利用 FCSR構(gòu)造密鑰流生成器的方案被研究者所關(guān)注。但是由于FCSR基于2-adic理論，其生成序列的2-adic復(fù)雜度，利用有理數(shù)逼近算法[4]僅需要很短的序列段就可以將FCSR結(jié)構(gòu)還原，因此要使用FCSR構(gòu)造密鑰流生成器，需要提高其2-adic復(fù)雜度，而線性濾波是一個(gè)可行的辦法。在 2005年，Berger和Arnault利用FCSR主寄存器濾波的方法來產(chǎn)生密鑰流，得到了好的效果，從而提出了F-FCSR濾波密鑰流生成器族，且該生成器族序列生成速度快，生成序列統(tǒng)計(jì)特性好，線性復(fù)雜度高。同年在eSTREAM項(xiàng)目上他們提交了其設(shè)計(jì)的密鑰流生成器，其硬件密鑰流生成器F-FCSR-Hv2[5]最后通過了eSTREAM的評(píng)選，成為4個(gè)硬件方案之一。只是2008年Hell和Johansson在文獻(xiàn)[6]中以很小的代價(jià)攻破了 F-FCSR-Hv2，攻擊的關(guān)鍵是利用Galois表示的FCSR在運(yùn)行中主寄存器會(huì)以一定的概率出現(xiàn)短暫的線性平移，而F-FCSR-Hv2濾波函數(shù)為線性函數(shù)，從而攻擊者可以列出足夠多的線性方程，以解線性方程的方法還原F-FCSR-Hv2生成器的狀態(tài)。

極高的生成速度，簡單的實(shí)現(xiàn)方式，良好的統(tǒng)計(jì)特性對(duì)于密鑰流生成器來說，是至關(guān)重要的，由于當(dāng)前對(duì)F-FCSR流密碼族有效攻擊手段只有Hell-Johnson攻擊[6]，因此，如果某種改進(jìn)方案能夠在保證其他良好性質(zhì)的同時(shí)避免Hell-Johnson攻擊，將是對(duì)該密鑰流生成器族的成功改進(jìn)，具有很好的意義。最近，Berger和Arnault提出了用環(huán)（ring）表示的FCSR進(jìn)行濾波的方案[7]，并聲稱能抵抗文獻(xiàn)[6]的攻擊。而本文提出基于FCSR的全動(dòng)態(tài)濾波密鑰流生成器DF-FCSR-8，利用一個(gè)FCSR來組成動(dòng)態(tài)濾波函數(shù)，避免了文獻(xiàn)[6]中的攻擊和其他的攻擊。本文安排如下：第2節(jié)介紹FCSR自動(dòng)機(jī)；第3節(jié)介紹F-FCSR和Hell-Johansson攻擊；第4節(jié)介紹DF-FCSR-8密鑰流生成器；第5節(jié)和第6節(jié)介紹DF-FCSR-8密鑰流生成器的性質(zhì)和抵抗攻擊的能力；最后為結(jié)束語。

2 FCSR自動(dòng)機(jī)

Galois表示下的FCSR自動(dòng)機(jī)如圖1所示。其中，“田”表示帶進(jìn)位加法，qn,qn-1,…,q1∈GF2將與反饋值進(jìn)行乘法運(yùn)算，運(yùn)算結(jié)果作為對(duì)應(yīng)位置帶進(jìn)位加的一個(gè)輸入，由此得到的整數(shù)（且=1），滿足2n＜q＜2n+1，稱為FCSR的連接數(shù)。具體的FCSR由2個(gè)寄存器構(gòu)成：

1) 主寄存器M=(mn-1,mn-2,…,m0)，由n個(gè)比特構(gòu)成；

2) 進(jìn)位寄存器C=(cn, cn-1,…,c1)，為方便起見，將其看做由n個(gè)比特構(gòu)成且cn=0。

在單元級(jí)上，寄存器在時(shí)間t時(shí)的轉(zhuǎn)移函數(shù)表示如下：

其中，“⊕”表示異或，為方便表示，令mn( t)=m0( t)。但是需要注意的是，當(dāng)qi=0時(shí)有ci最終會(huì)恒等于0，不會(huì)對(duì)FCSR的運(yùn)行產(chǎn)生影響，只有在qi=1時(shí)ci才會(huì)起作用。因此實(shí)際中FCSR進(jìn)位寄存器的數(shù)量為l=wt( q-1)-1，wt( x)表示數(shù)x的二進(jìn)制展開中1的個(gè)數(shù)，也就是x的漢明重量。為了表示方便，也可以認(rèn)為進(jìn)位寄存器C包含n個(gè)單元ci(0≤i≤n-1)。為了便于理解，舉例如下：

例1：如果q=-347，那么有d=174=0xAE，n=8和l=4。則對(duì)應(yīng)FCSR表示如圖2所示。

定理1[1]有理數(shù)α=p/ q和二元終歸周期序列=(a0, a1, a2,…)之間存在一一對(duì)應(yīng)關(guān)系，對(duì)應(yīng)規(guī)則為序列為有理數(shù)α的2-adic展開的系數(shù)序列，即。而其中奇整數(shù)為生成該序列的FCSR連接數(shù)。

定理2[1]如果p和q互素，-q＜p≤0，q為奇數(shù)，則α=p/ q 的2-adic展開序列周期為T=ordq(2)。

圖1 帶進(jìn)位的反饋移位寄存器的Galois結(jié)構(gòu)

圖2 FCSR舉例

定義2[1]如果FCSR自動(dòng)機(jī)的連接數(shù)q滿足ordq(2)=|q|-1，稱該FCSR自動(dòng)機(jī)為最優(yōu)的，其生成序列為l-序列。

定義3[8]存在素?cái)?shù)q，若2模q的階為q-1（i.e.2q-1≡1(modq)），則稱q為2-素?cái)?shù)，當(dāng)q=2r+1且r也為2-素?cái)?shù)時(shí)，則稱q為強(qiáng)2-素?cái)?shù)。

當(dāng)FCSR的連接數(shù)q為2-素?cái)?shù)，則生成的序列為極大周期序列，l-序列，其周期為q-1。下面的定理3為l-序列的線性復(fù)雜度的一些結(jié)論。

定理3[8]當(dāng)FCSR的連接數(shù)為q=2p+1，其中，為2-素?cái)?shù)，那么其FCSR生成序列的線性復(fù)雜度至少為m+2，其中，m為2模p的階。當(dāng)q為強(qiáng)2-素?cái)?shù)時(shí)，線性復(fù)雜度為p+1。

FCSR的主寄存器中寄存器單元所生成的序列稱為主寄存器序列，主寄存器第i個(gè)單元在時(shí)刻后的值構(gòu)成的序列表示為Mi( t)=(mi( t+τ))τ≥0，其中，0≤i≤n-1。當(dāng)序列從t=0時(shí)刻開始時(shí)，記為Mi=Mi(0)，而FCSR的生成序列M即為M0。

定理4[9]若有連接數(shù)為q=1-2d的最優(yōu)FCSR自動(dòng)機(jī)，令n為d的比特長度，那么對(duì)于所有的i,0≤i≤n-1，存在一個(gè)整數(shù)pi，使得主寄存器生成序列Mi為piq的2-adic展開。整數(shù)pi由如下公式給出：

其中，pn=p0。那么由定理2可知，F(xiàn)CSR主寄存器生成序列與FCSR序列具有相同的連接數(shù)和周期。

3 F-FCSR與Hell-Johansson攻擊

F-FCSR密鑰流生成器族[9]由FCSR自動(dòng)機(jī)與濾波函數(shù)組成， FCSR自動(dòng)機(jī)的主寄存器值通過濾波函數(shù)產(chǎn)生出密鑰流比特。

下面以F-FCSR-Hv2[5]為例，介紹F-FCSR密鑰流生成器族的具體實(shí)現(xiàn)。根據(jù)式(1)可知，當(dāng)di=0時(shí)，有mi( t+1)=mi+1(t )，即主寄存器序列Mi( t+1)=Mi+1(t )，那么這2個(gè)序列將不適合同時(shí)參與濾波的異或運(yùn)算，所以在文獻(xiàn)[5]中采用了固定的濾波器F（為二進(jìn)制向量）等于d的二進(jìn)制展開，這樣進(jìn)位寄存器單元后的主寄存器單元都將參與濾波運(yùn)算。該結(jié)構(gòu)使用k=8個(gè)不同的子濾波器來增加吞吐量。F-FCSR-Hv2中的FCSR長度（主寄存器數(shù)目）為n=160，進(jìn)位寄存器包含l=82個(gè)單元，F(xiàn)CSR的連接數(shù)為

F-FCSR-Hv2使用固定的濾波器

對(duì)應(yīng)k=8個(gè)子濾波器為F7, F6,…,F0。令F對(duì)應(yīng)比特串為(fn-1,fn-2,…,f1,f0)，F(xiàn)i對(duì)應(yīng)比特串為(fi,n/k-1,fi,n/k-2,…,fi,1,fi,0),0≤i＜k ，則存在如下對(duì)應(yīng)關(guān)系(t≥0)：

對(duì)應(yīng)8個(gè)子濾波器確定如下：

F7=(1101 0011 1011 1011 0100)2,

F6=(0011 0101 0010 0110 0101)2,

F5=(1001 1100 0100 1000 1010)2,

F4=(0111 0010 0010 0011 1100)2,

F3=(1111 0010 0011 1000 1001)2,

F2=(1011 1011 1010 1110 1111)2,

F1=(1001 1010 1101 1100 0001)2,

F0=(0011 0111 0100 1010 1010)2

令主寄存器向量(m152(t), m144(t),…,m8( t), m0( t ))用(t)表示，而( t),1≤i≤7表示主寄存器值(m152+i(t), m144+i(t),…,m8+i(t), mi( t ))。z( t)為F-FCSRHv2在時(shí)刻t的一個(gè)字節(jié)輸出，最高比特為z7( t)，最小比特為z0( t)，輸出字節(jié)z( t)則可表示為

其中，F(xiàn)i,j(t)表示向量Fi( t)中的第j個(gè)元素，i,j(t)表示( t)中的第j個(gè)元素。圖3為F-FCSRHv2結(jié)構(gòu)。

2008年，Hell和Johansson以很小的代價(jià)攻破了F-FCSR-Hv2[6]。他們認(rèn)為F-FCSR流密碼族中，進(jìn)位寄存器C變化并不是很隨機(jī)是其主要弱點(diǎn)。原因在于它們都有一個(gè)共同的輸入變量——反饋比特，當(dāng)反饋比特為0時(shí)，C中為0的單元仍為0，為1的單元以50%的概率變?yōu)?。所以當(dāng)反饋比特連續(xù)出現(xiàn)多個(gè)0時(shí)，會(huì)將進(jìn)位寄存器變?yōu)槌?shù)0x2。設(shè)正整數(shù)20r＜ ，定義如下事件：

圖3 F-FCSR-Hv2結(jié)構(gòu)

Et( r):C( t)=C( t+1)=…=C( t+r)=(0,0,…,0,1,0)

當(dāng)Et( r)發(fā)生時(shí)，主寄存器出現(xiàn)線性平移的情況具體如下：

結(jié)合式(4)與式(5)可發(fā)現(xiàn)：zi( t+τ),0≤τ≤r ，僅與(τ+i)mod8(t )相關(guān)。那么令

其中，τ+τi≡i(mod8)對(duì)于任意的0≤τ≤r，0≤i≤7。則有

在這里Ri是由濾波器F決定的一個(gè)20×(r+1)的矩陣，=( t)為含有20個(gè)未知數(shù)的行向量。當(dāng)分別求解這8個(gè)方程組時(shí)，每個(gè)方程組有20個(gè)未知數(shù)和r+1個(gè)方程。令矩陣Ri的秩為d(Ri)，若為20則可直接計(jì)算出主寄存器值，否則需要猜測(cè)20-d (Ri)個(gè)比特。所以正確解出這160個(gè)未知數(shù)的概率為

而Et( r)的出現(xiàn)條件為：需要lbl2≈6個(gè)反饋0使得C在時(shí)刻t變?yōu)闈h明重量為1的常數(shù)，同時(shí)需要r個(gè)反饋0使C再保持為常數(shù)r次。Et( r)的發(fā)生概率為p=2-(r+lbl2)，因此一次實(shí)驗(yàn)就能解出FCSR主寄存器值的概率為

由此，成功攻擊F-FCSR-Hv2的概率上限為2-25。同時(shí)由于反饋比特的作用，在求解方程前是可以事先確定r+2個(gè)比特，其值如下：

此時(shí)，成功的概率提高到2-23。真實(shí)情況的成功概率會(huì)比理想狀態(tài)稍低，文獻(xiàn)[6]給出的成功概率為2-24.7。

4 基于FCSR的全動(dòng)態(tài)濾波密鑰流生成器DF-FCSR-8

由于FCSR本身具有很好的性質(zhì)，F(xiàn)-FCSR密鑰流族的輸出密鑰流序列具有很好的統(tǒng)計(jì)特性，且吞吐量大，僅有Hell-Johansson攻擊，因此對(duì)其進(jìn)行改進(jìn)是很有利的。

由前面的敘述可知，F(xiàn)-FCSR密鑰流族被成功攻擊的原因如下：

1) Galois表示下的FCSR在反饋比特出現(xiàn)多個(gè)0的時(shí)候，其主寄存器會(huì)出現(xiàn)線性平移的情況；

2) 對(duì)FCSR主寄存器的濾波器為線性濾波器，且以字節(jié)為單位輸出。

情況1使得多次的濾波輸出有相同的主寄存器值，可以列出具有相同變量的多個(gè)方程；情況2使得列出的方程為線性方程，且每次可以列出的方程數(shù)量為8。這2種情況就會(huì)使得FCSR的主寄存器很容易被恢復(fù)。那么可以根據(jù)這2種情況來對(duì)F-FCSR密鑰流生成器進(jìn)行改進(jìn)。由于使用Galois表示的FCSR，主寄存器可能的線性平移是FCSR的固有性質(zhì)，因此只能針對(duì)情況2進(jìn)行改進(jìn)。改進(jìn)的可能方法如下：

1) 改變線性濾波的情況，使用非線性的濾波器；

2) 減少每次濾波的輸出比特?cái)?shù)，如只輸出1bit[10]；

3) 隱藏濾波器，使攻擊者無法獲知濾波器的具體信息，從而使攻擊者無法列出對(duì)應(yīng)的線性方程。

由于FCSR本身為非線性結(jié)構(gòu)，若再使用非線性濾波器將會(huì)使得分析困難，無法保證生成序列的性質(zhì)。而減少每次的濾波輸出，如F-FCSR流密碼族中最早提出的F-FCSR-SF1[10]，就是只輸出1bit，雖然會(huì)使得列出的線性方程組大大減少，無法還原FCSR主寄存器，但是高的吞吐率對(duì)于流密碼來說非常重要，減少輸出會(huì)使得密鑰流生成器性能大幅下降，喪失效率優(yōu)勢(shì)而無法滿足要求。所以最好的改進(jìn)方法為隱藏濾波器，Arnault等人在文獻(xiàn)[10]中提出過動(dòng)態(tài)的濾波器方案F-FCSR-DF1和F-FCSR-DF8，這些方案的濾波器由初始密鑰確定，確定之后將不變，但是由于濾波器與密鑰的相關(guān)性，且濾波器在運(yùn)行階段不會(huì)變化，文獻(xiàn)[11]針對(duì)F-FCSR-DF1進(jìn)行了重同步攻擊，因此可以認(rèn)為其安全性不夠。本文提出一種全動(dòng)態(tài)的濾波方案，保持8個(gè)子濾波器，濾波器會(huì)隨著時(shí)刻的不同而不同，使得攻擊者無法獲取濾波器的信息，從而不能列出關(guān)于FCSR主寄存器的線性方程組來還原FCSR主寄存器值。

下面從靜態(tài)的F-FCSR出發(fā)，來構(gòu)造一個(gè)全動(dòng)態(tài)的濾波器DF-FCSR-8，其結(jié)構(gòu)如圖4所示。

用到了2個(gè)FCSR：FCSR1和FCSR2，其中前者作為產(chǎn)生序列的源，而后者作為產(chǎn)生動(dòng)態(tài)濾波器的組成部分，它們的級(jí)數(shù)都為128，選取FCSR1的連接數(shù)q1為強(qiáng)2素?cái)?shù)，根據(jù)定理3和定理4可知，參與運(yùn)算的主寄存器序列都具有極大的線性復(fù)雜度。選取FCSR2的連接數(shù)q2為2素?cái)?shù)可以保證FCSR2的主寄存器狀態(tài)周期最大。q1和q2的值分別為

-q1= 0x199B63C90F4DE193F1FC89DFCD2C484BB

-q2= 0x1AC913013BC417DFF5FD97CF6D318A26B

且有g(shù)cd((|q1|-1)2,(|q2|-1)2)=1。

如同F(xiàn)-FCSR方案一樣，首先選取一個(gè)固定的濾波器，使得FCSR1中所有左邊有進(jìn)位寄存器的主寄存器參與濾波運(yùn)算，這個(gè)固定的濾波器記為Fa，其值為

Fa=d=(|q1|+1)/2

=(CCDB1E487A6F0C9F8FE44EFE6962425E)16

圖4 全動(dòng)態(tài)濾波器結(jié)構(gòu)

8個(gè)子濾波器Fa7,Fa6,…,Fa0表示如下：

Fa7=(1100 0001 1101 0000)2,

Fa6=(1101 1100 0111 1111)2,

Fa5=(0000 1100 0101 1100)2,

Fa4=(0110 1001 0001 0001)2,

Fa3=(1111 1111 1011 1001)2,

Fa2=(1010 0111 1111 0001)2,

Fa1=(0110 1101 1011 0111)2,

Fa0=(0100 0101 1000 1000)2

其次，為了獲得動(dòng)態(tài)的濾波器，需要有一個(gè)動(dòng)態(tài)變化的組件，F(xiàn)CSR或LFSR的主寄存器會(huì)不停地變化，所以本文選擇FCSR2的主寄存器（記為Fd( t)）與靜態(tài)濾波器Fa一起通過按位與運(yùn)算構(gòu)成一個(gè)動(dòng)態(tài)的濾波器。

但是這樣可能會(huì)在某些時(shí)刻出現(xiàn)某些濾波器為全零的情況，從而無法保證生成序列的性質(zhì)。為此，還必須再引入一個(gè)濾波器Fb，使得最終復(fù)合成的動(dòng)態(tài)濾波器F( t)為

其中，“&”表示按位與操作，“|”為按位或操作。特別地，要求：

1)Fb中為1的位置在Fa中也必須為1；

2) 對(duì)于任意子濾波器Fbi而言，其中只包含2個(gè)為1的值，也就是Fbi,0≤i≤7的漢明重量為2；

3) 按8bit分段，每一段中有且僅有1位值為1。

條件1)確保只有FCSR1中左邊有進(jìn)位寄存器的主寄存器才能參與濾波運(yùn)算。同時(shí)考慮到2個(gè)FCSR主寄存器序列進(jìn)行按位模2加之后的生成序列具良好的統(tǒng)計(jì)特性，且破壞了2-adic復(fù)雜度，這樣條件2)可以使每個(gè)子濾波輸出序列固定會(huì)有2個(gè)FCSR1的主寄存器序列參與運(yùn)算，保證輸出序列的性質(zhì)，條件3)使得固定參與模2加運(yùn)算的FCSR1主寄存器序列均勻分布于FCSR1主寄存器中，極大降低了每次參與模2加運(yùn)算的變量的相關(guān)性。

通過計(jì)算，選取了Fb如下：

Fb=(80801040 40200810 01200804 01020204)16

那么Fb的對(duì)應(yīng)8個(gè)子濾波器為

Fb7=(1100 0000 0000 0000)2,

Fb6=(0001 1000 0000 0000)2,

Fb5=(0000 0100 0100 0000)2,

Fb4=(0010 0001 0000 0000)2,

Fb3=(0000 0010 0010 0000)2,

Fb2=(0000 0000 0001 0001)2,

Fb1=(0000 0000 0000 0110)2,

Fb0=(0000 0000 1000 1000)2

根據(jù)式(7)可得動(dòng)態(tài)濾波器F( t)，對(duì)應(yīng)8個(gè)子濾波器由式(3)確定，在t時(shí)刻的子濾波器分別為F7(t),F6(t),…,F0( t)。

FCSR的主寄存器向量(m120(t), m112(t),…,m8( t), m0( t))用(t)表示，而( t),1≤i≤7表示主寄存器值(m120+i(t), m112+i(t),…,m8+i(t), mi( t))。z( t)為DF-FCSR-8在時(shí)刻t的一字節(jié)輸出，最低比特為z0( t)，最高比特為z7( t)，那么輸出字節(jié)z( t)可表示為

其中，F(xiàn)i,j(t)表示向量Fi( t)中的第j個(gè)元素，(t)表示( t)中的第j個(gè)元素。

對(duì)于密鑰流生成器來說，K和初始化向量(IV)的設(shè)置過程是必不可少的，下面介紹全動(dòng)態(tài)濾波密鑰流生成器DF-FCSR-8的K與IV的設(shè)置過程：密鑰K和初始化向量IV的長度皆為128bit，KL為密鑰的低64bit，KH為密鑰的高64bit；IVL為IV的低64bit，IVH為IV的高64bit，約定高位在左。

2) 將FCSR1和FCSR2的進(jìn)位寄存器1C，2C都初始化為0：

3) 運(yùn)行DF-FCSR-8密鑰流生成器32次，每次運(yùn)行得到一個(gè)字節(jié)輸出Si(0≤i≤31)；

4) 利用得到的這些字節(jié)重新初始化主寄存器：

5) 將FCSR1和FCSR2的進(jìn)位寄存器重新初始化為0：C1:=0,C2:=0；

6) 運(yùn)行DF-FCSR-8生成器132個(gè)時(shí)鐘（將這一步的輸出丟棄）。

5 F-FCSR-8密鑰流生成器抗Hell-Johansson攻擊的分析

對(duì)于DF-FCSR-8密鑰流發(fā)生器來說Hell-Johansson攻擊將會(huì)困難得多。下面敘述對(duì)聯(lián)合的F-FCSR流密碼發(fā)生器的可能攻擊。

聯(lián)合的DF-FCSR-8中FCSR1主寄存器單元數(shù)共為128n=，對(duì)DF-FCSR-8定義如下事件：

Et1( r):C1( t)=C1( t+1)=…=C1( t+r )=(0,0,…,0,1,0)

事件Et1( r)發(fā)生時(shí)，F(xiàn)CSR1主寄存器變化情況由式(5)確定，但是由于DF-FCSR-8的濾波函數(shù)F( t)隨時(shí)間變化，且Fd( t)為秘密的，那么攻擊者無法完全確定F( t)的值，僅僅知道，F(xiàn)b中為1的位置上F( t)也為1，F(xiàn)a中為0的位置上F( t)也為0，由Fb中有16個(gè)1，F(xiàn)a中有59個(gè)0，最終可以確定16+59=75bit，剩下53bit。若要正確列出線性方程組，有2種方法：

1) 對(duì)每個(gè)時(shí)刻下的濾波函數(shù)進(jìn)行猜測(cè)，則正確列出t時(shí)刻下的線性方程組的概率為2-53，那么事件Et1( r)發(fā)生時(shí)，正確列出8(r+1)個(gè)線性方程組的概率為2-53(r+1)。

2) 對(duì)產(chǎn)生動(dòng)態(tài)濾波器的FCSR2主寄存器M?2(t)進(jìn)行猜測(cè)，以便獲得每個(gè)時(shí)刻下的濾波器，由于FCSR與密鑰相關(guān)，且無法得到主寄存器的相關(guān)信息，那么猜測(cè)正確的概率為2-128。

圖5 DF-FCSR-8隨機(jī)性測(cè)試通過率

當(dāng)事件Et1( r)發(fā)生時(shí)，就可以列出8(r+1)個(gè)方程，如果能列出正確的線性方程組，根據(jù)第3節(jié)的分析可以得到，能解出FCSR主寄存器的概率如下：

在使用第一種方法的情況下，正確列出線性方程組的概率為2-53(r+1)，聯(lián)合起來，要恢復(fù)FCSR主寄存器，一次實(shí)驗(yàn)的成功概率如下：

可以看出，成功概率與r成反比，在r=1時(shí)，成功概率就小于2-225，所以采用第一種方法是不可行的。

而對(duì)于方法2來說，猜測(cè)出所有時(shí)刻濾波器值的概率就為2-128，而在此基礎(chǔ)上，一次實(shí)驗(yàn)的成功概率如下：

則一次實(shí)驗(yàn)成功的概率下界為2-254+7·15=2-149，所以采用第二種方法也不可行。

6 DF-FCSR-8的其他密碼分析

本文利用美國國家技術(shù)與標(biāo)準(zhǔn)局NIST推出的STS軟件包（版本1.6）[12]對(duì)DF-FCSR-8的生成序列進(jìn)行了測(cè)試。參數(shù)與文獻(xiàn)[9]中的測(cè)試參數(shù)相同，默認(rèn)置信水平α=0.01下為：Block Frequency tests：20 000；Overlapping and Nonoverlapping Template tests：9；Universal test：7(with 1 280 initialization)Approximate Entropy and Serial tests：10；Linear Complexity test：2 000。測(cè)試了1 000組長度為610 bit的生成序列，結(jié)果表明全動(dòng)態(tài)濾波密鑰流生成器DF-FCSR-8生成序列具有良好的隨機(jī)性。測(cè)試通過率如圖5所示，密鑰流生成器的生成序列通過率都在99%左右，偏差在1%之內(nèi)。因此認(rèn)為DF-FCSR-8密鑰流生成器的密鑰流具有良好的統(tǒng)計(jì)特性。

同時(shí)，在一個(gè)動(dòng)態(tài)子濾波器中，會(huì)有固定的2個(gè)輸入序列，通過將其他動(dòng)態(tài)輸入進(jìn)行模2加的結(jié)果看成一個(gè)輸入序列，這樣可以將每個(gè)子濾波器看成3個(gè)輸入變量的線性函數(shù)。那么根據(jù)類似于文獻(xiàn)[9]的分析，可得全動(dòng)態(tài)濾波密鑰流生成器DF-FCSR-8的生成序列在復(fù)雜度上類似于隨機(jī)序列，同時(shí)也能夠抵抗相關(guān)攻擊和代數(shù)攻擊。

7 結(jié)束語

本文分析了基于FCSR濾波的密鑰流生成器F-FCSR。研究了F-FCSR的線性弱點(diǎn)以及F-FCSR-Hv2被攻破的原因的基礎(chǔ)上，提出了全動(dòng)態(tài)濾波密鑰流生成器DF-FCSR-8。該密鑰流生成器利用一個(gè)FCSR來生成動(dòng)態(tài)的濾波器，使得濾波器會(huì)隨著時(shí)鐘脈沖變化，攻擊者無法獲得濾波器，從而使利用FCSR出現(xiàn)線性平移而進(jìn)行的Hell-Johansson攻擊無效。其生成序列也通過了美國技術(shù)與標(biāo)準(zhǔn)局（NIST）的STS 軟件包的16 項(xiàng)隨機(jī)性測(cè)試。最后討論了改進(jìn)流密碼生成器抵抗相關(guān)攻擊和代數(shù)攻擊的能力，結(jié)果表明DF-FCSR-8彌補(bǔ)了F-FCSR方案的缺陷，保證了原有的良好性質(zhì)，生成簡單，速度快，統(tǒng)計(jì)特性良好。所以認(rèn)為DF-FCSR-8密鑰流生成器是成功的。

[1] KLAPPER A, GORESKY M. 2-adic shift register[A]. Fast Software Encryption[C]. Combridge, UK, 1993. 174-178.

[2] GORESKY M, KLAPPER A. Feedback register based on ramified extensions of the 2-adic number[A]. Advances in Cryptology-eurocrypt’94[C]. Perugia, Italy, 1994. 215-222.

[3] KLAPPER A, GORESKY M. Feedback shift registers, 2-adic span and combiners with memory[J]. Journal of Cryptology, 1997, 10(1):111-147.

[4] GORESKY M, KLAPPER A. Fibonacci and galois representations of feedback-with-carry shift registers[J]. IEEE Transactions on Information Theory, 2002, 48(11): 2826-2836.

[5] ARNAULT F, BERGER T P, LAURADOUX C. Update on F-FCSR stream cipher[DB/OL]. http://www.ecrypt.eu.org/stream/,2008.

[6] HELL M, JOHANSSON T. Breaking the F-FCSR-H stream cipher in real time[A]. Advances in Cryptology - ASIACRYPT 2008[C]. Melbourne, Australia, 2008. 557-569.

[7] ARNAULT F, BERGER T P, LAURADOUX C, et al. A new approach for FCSRs[A]. Selected Areas in Cryptography[C]. Springer,2009. 433-448.

[8] SEO C, LEE S, SUNG Y. A lower bound on the linear span of FCSR[J].IEEE Transactions on Information Theory, 2000,43(4): 691-693.

[9] ARNAULT F, BERGER T P. Design and properties of a new pseudorandom generator based on a filtered FCSR automaton[J] .IEEE Transactions on Computers, 2005, 54(11): 1374-1383.

[10] ARNAULT F, BERGER T P. F-FCSR: design of a new class of stream ciphers[A]. Fast Software Encryption 2005[C]. Springer, Berlin,2005. 83-97.

[11] JAULMES E, MULLER F. Cryptanalysis of the F-FCSR stream cipher family[A]. SAC 2005[C]. Springer, Berlin, 2000.20-35 .

[12] RUKHIN A, SOTO J, NECHVATAL J, et al. A statistical test suite for random and pseudorandom number generator for cryptographic applications[EB/OL]. http://csrc.nist. gov/rng/SP800-22b.pdf,2004.