流密碼詳解課件

第2章流密碼李向東中原工學(xué)院計(jì)算機(jī)學(xué)院124197985@2011.9-2012.11第2章流密碼李向東1第2章流密碼2.1流密碼一般模型2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼算法2第2章流密碼2.1流密碼一般模型22.1流密碼一般模型實(shí)用密碼體制的分類32.1流密碼一般模型實(shí)用密碼體制的分類32.1流密碼一般模型流密碼(streamcipher)(序列密碼)體制模型明文序列:m=

m1m2m3…;密鑰序列:z=z1z2z3…;密文序列:c=

c1c2c3…;加密變換:

ci=E(zi,mi)(i=1,2,3,…);解密變換:

mi=D(zi,ci)(i=1,2,3,…).42.1流密碼一般模型流密碼(streamcipher課堂討論：加密函數(shù)和解密函數(shù)都用異或運(yùn)算，行不行？什么樣的加解密算法是高效、安全的？Why？實(shí)用的流密碼方案中，加解密算法是什么？5課堂討論：加密函數(shù)和解密函數(shù)都用異或運(yùn)算，行不行？5流密碼原理框圖信道ciD(zi,ci)cimiE(zi,mi)mi密鑰流生成器zizi密鑰流生成器kk安全信道2.1流密碼一般模型6流密碼原理框圖信道ciD(zi,ci)cimiE(zi,mi流密碼體制的安全性當(dāng)流鑰序列是具有均勻分布的離散無記憶隨機(jī)序列時(shí),在理論上是不可破譯的.實(shí)用的困難性真正的具有均勻分布的隨機(jī)序列是不可能重復(fù)產(chǎn)生的.密鑰序列長(至少與明文序列一樣長),其管理(存儲(chǔ)、分配)難.設(shè)計(jì)流密碼體制的關(guān)鍵問題設(shè)計(jì)產(chǎn)生密鑰序列的方法.2.1流密碼一般模型7流密碼體制的安全性2.1流密碼一般模型7序列密碼的分類同步流密碼(SSC:synchronousstreamcipher)產(chǎn)生密鑰序列的算法與明文、密文無關(guān).自同步流密碼(SSSC:self-synchronousstreamcipher)產(chǎn)生密鑰序列的算法與以前的密文有關(guān).2.1流密碼一般模型8序列密碼的分類2.1流密碼一般模型8同步流密碼(SSC:synchronousstreamcipher)只要通信雙方的密鑰序列產(chǎn)生器具有相同的“種子序列”和相同的“初始狀態(tài)”,就能產(chǎn)生相同的密鑰序列.通信雙方必須保持精確同步,才能正確解密.容易檢測插入、刪除、重播等主動(dòng)攻擊.沒有差錯(cuò)傳播.討論：如何對SSC的這種“同步”性質(zhì)進(jìn)行形式化描述？2.1流密碼一般模型9同步流密碼(SSC:synchronousstream同步流密碼(SSC:synchronousstreamcipher)產(chǎn)生密鑰序列的算法與明文、密文無關(guān).ciE(zi,mi)mizi密鑰流生成器k2.1流密碼一般模型10同步流密碼(SSC:synchronousstream自同步流密碼(SSSC:self-synchronousstreamcipher)產(chǎn)生密鑰序列的算法與以前的密文有關(guān).E(zi,mi)mizi密鑰流生成器kci2.1流密碼一般模型11自同步流密碼(SSSC:self-synchronous自同步流密碼(SSSC)密鑰流生成器是一種有記憶變換器密鑰流與明文符號(hào)有關(guān)：

i時(shí)刻的密文不僅取決于i時(shí)刻的明文，而且與i時(shí)刻之前的l個(gè)明文符號(hào)有關(guān)具有有限的差錯(cuò)傳播具有自同步能力把明文每個(gè)字符擴(kuò)散在密文多個(gè)字符中,強(qiáng)化了抗統(tǒng)計(jì)分析的能力問：SSSC是如何自同步的？請email回應(yīng)。2.1流密碼一般模型12自同步流密碼(SSSC)2.1流密碼一般模型12二元加法序列密碼明文序列:m=

m1m2m3…;密鑰序列:z=

z1z2z3…;密文序列:c=

c1c2c3…;加密變換:

ci=zi

mi(i=1,2,3,…);解密變換:

mi=zi

ci(i=1,2,3,…).2.1流密碼一般模型13二元加法序列密碼明文序列:m=m1m2m3…;第2章流密碼2.1流密碼一般模型2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼算法14第2章流密碼2.1流密碼一般模型142.2線性反饋移位寄存器序列偽隨機(jī)序列考慮二元序列:a={ai}=a0a1a2a3….周期序列定義2.1設(shè)a=(a0,a1,…,ai,…)是一個(gè)二元序列，若存在正整數(shù)N和非負(fù)整數(shù)m，使得ai+N=ai對于任意i

m成立，則稱二元序列a是終歸周期序列。如果m=0，則稱序列a是嚴(yán)格周期序列，簡稱周期序列。而滿足ai+N＝ai(i

m)的最小正整數(shù)N被稱為序列a的周期。152.2線性反饋移位寄存器序列偽隨機(jī)序列定義2.1設(shè)a=2.2線性反饋移位寄存器序列定義2.2設(shè)a=(a0,a1,…,ai,…)是一個(gè)周期為N的二元序列，在一個(gè)周期內(nèi)連續(xù)出現(xiàn)的最多的符號(hào)“0”（或1）的串，稱為0（或1）的一個(gè)游程。在一個(gè)游程中，0（或1）的個(gè)數(shù)稱為該游程的長度。（討論：該定義有否歧義？）偽隨機(jī)序列序列的游程例:在序列k={ki}=001110100000111100中,有長為1的0游程一個(gè);長為4的0游程一個(gè);長為5的0游程一個(gè);長為1的1游程一個(gè);長為3的1游程一個(gè);長為4的1游程一個(gè).162.2線性反饋移位寄存器序列定義2.2設(shè)a=(a02.2線性反饋移位寄存器序列定義2.3設(shè)a=(a0,a1,…,aN

1)和b=(b0,b1,…,bN

1)是兩個(gè)周期為N的二元周期序列，其相關(guān)函數(shù)定義為特別地，如果a=b，則Ra,a(

)被稱為自相關(guān)函數(shù)，其中當(dāng)

=0，Ra,a(0)被稱為同相自相關(guān)函數(shù)，而當(dāng)

0，Ra,a(

)被稱為異相自相關(guān)函數(shù)。偽隨機(jī)序列序列的相關(guān)函數(shù)172.2線性反饋移位寄存器序列定義2.3設(shè)a=(a0,2.2線性反饋移位寄存器序列例2.1

已知序列a=01011100101110…，則

a是周期為7的周期序列;

a一共有4個(gè)游程：00,1,0,111，長度分別為2,1,1,3；求a的自相關(guān)函數(shù):a=0101110,a=1011100…,

Ra,a(0)=(-1)0+0+(-1)1+1+(-1)0+0+(-1)1+1+(-1)1+1+(-1)1+1+(-1)0+0=7,a=0101110,Ta=1011100…,

Ra,a(1)=(-1)0+1+(-1)1+0+(-1)0+1+(-1)1+1+(-1)1+1+(-1)1+0+(-1)0+0=-1,a=0101110,T2a=0111001…,

Ra,a(2)=(-1)0+0+(-1)1+1+(-1)0+1+(-1)1+1+(-1)1+0+(-1)1+0+(-1)0+1=-1,

Ra,a(3)=Ra,a(4)=Ra,a(5)=Ra,a(6)=-1.182.2線性反饋移位寄存器序列例2.1已知序列a=0偽隨機(jī)序列哥倫布(Golomb,1955)隨性假設(shè)

(G1)：在一個(gè)周期內(nèi)，0與1出現(xiàn)的個(gè)數(shù)至多相差1。也即，如果N為偶數(shù)，則在一個(gè)周期內(nèi)0與1的數(shù)目各占N/2；如果N為奇數(shù)，則在一個(gè)周期內(nèi)0的數(shù)目為(N+1)/2或者(N-1)/2，相應(yīng)地1的數(shù)目為(N-1)/2或者(N+1)/2。(G2)：在一個(gè)周期內(nèi)，長度為i的游程個(gè)數(shù)占游程總數(shù)的1/2i，i=1,2,…。且在長度為i的游程中，0的游程與1的游程數(shù)目相等或至多相差一個(gè)。(G3)：序列的異相自相關(guān)函數(shù)是一個(gè)常數(shù)。滿足上述三個(gè)條件的序列稱為擬噪聲序列,或偽噪聲序列(pseudonoisesequence),簡記為:PN序列.PN序列在CDMA,通信同步,導(dǎo)航,雷達(dá)測距等領(lǐng)域有重要應(yīng)用.19偽隨機(jī)序列哥倫布(Golomb,1955)隨性假設(shè)SolomonW.Golomb:Shimonoseki,Japan,October10-14,200520SolomonW.Golomb:Shimonoseki偽隨機(jī)序列密鑰序列k={ki}=k0k1k2k3….滿足的條件

G1,G2,G3和以下三個(gè)條件：(C1)周期p要長.如p>1050.

(C2)生成容易.

(C3)具有不可預(yù)測性(unpredictability):當(dāng)密鑰序列k的任何部分泄露時(shí),要分析整個(gè)密鑰序列,在計(jì)算上是不可行的.C3決定了密碼的強(qiáng)度,是序列密碼理論的核心.主要研究問題:線性復(fù)雜度,相關(guān)免疫性,不可預(yù)測性等.21偽隨機(jī)序列密鑰序列k={ki}=k0k1k2k3….滿足的an

1…a1a0f(x0,x1,…,xn

1)反饋移位寄存器(FSR:FeedbackShiftRegister)n個(gè)寄存器:從右至左依次稱為第1,2,…,n級(jí)反饋函數(shù)f(x0,x1,…,xn-1):GF(2)n

GF(2).工作原理:當(dāng)一個(gè)時(shí)鐘脈沖來到時(shí),第i級(jí)寄存器的內(nèi)容傳送給第i-1級(jí)寄存器(i=2,3,…,n),第1

級(jí)寄存器的內(nèi)容為反饋移位寄存器的輸出.反饋函數(shù)f(x0,x1,…,xn-1)的值傳送給第n級(jí)寄存器.FSR的輸出序列:a0,a1,a2,…,an,…稱為反饋移位寄存器序列(FSR序列).偽隨機(jī)序列22an1…a1a0f(x0,x1,…,xn1)反饋移位在任意時(shí)刻t,第1至n級(jí)寄存器的內(nèi)容

st=(at,at+1,…,at+n-1)

GF(2)n稱為FSR在時(shí)刻t的狀態(tài)(state).s0=(a0,a1,…,an-1)稱為FSR的初始狀態(tài).在時(shí)刻t+1

的狀態(tài)為:

st+1=(at+1,at+2,…,at+n),

at+n=f(at,at+1,…,at+n-1).共有2n個(gè)狀態(tài).反饋函數(shù)f(x1,x2,…,xn)是n個(gè)變量的布爾函數(shù)(Booleanfunction).反饋移位寄存器(FSR)23在任意時(shí)刻t,第1至n級(jí)寄存器的內(nèi)容反饋移位寄存器(FSR例2.2設(shè)有限域GF(2)上的3級(jí)FSR的反饋函數(shù)為:

f(x1,x2,x3)=x1

x2

x3初始狀態(tài)為s0=(1,0,1).求FSR序列.

解:反饋移位寄存器序列:a=1011…;周期q=4.反饋移位寄存器(FSR)24例2.2設(shè)有限域GF(2)上的3級(jí)FSR的反饋函數(shù)為:反如果反饋函數(shù)f(x1,x2,…,xn)是n個(gè)變量的線性函數(shù):f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1

(ci

{0,1})則稱為線性反饋移位寄存器(LFSR:linearfeedbackshiftregister).輸出的序列稱為線性反饋移位寄存器序列,記為LFSR序列。

LFSR序列a=(a0,a1,…,an-1,…)滿足遞推關(guān)系式:線性反饋移位寄存器(LFSR)an

1…a1a0cncn-1c125如果反饋函數(shù)f(x1,x2,…,xn)是n個(gè)變量的線性函反饋函數(shù):f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1

(ci

{0,1})如果cn=0，則稱LFSR是退化的；否則稱LFSR是非退化的。把多項(xiàng)式：f(x)=1+c1x+c2x2+…+cnxn

稱為LFSR的特征多項(xiàng)式(characteristicpolynomial),或級(jí)連多項(xiàng)式、或生成多項(xiàng)式。線性反饋移位寄存器(LFSR)26反饋函數(shù):線性反饋移位寄存器(LFSR)26例2.3已知如圖所示的3級(jí)LFSR.特征多項(xiàng)式為：f(x)=1+x2+x3LFSR序列a=(a0,a1,…,an-1,…)滿足遞推關(guān)系式:an=an-2+an-3.如果設(shè)初始狀態(tài)為:(0,0,1)即a0=0,a1=0,a2=1，輸出序列為:0010111周期為7.線性反饋移位寄存器(LFSR)an

1an

2an

327例2.3已知如圖所示的3級(jí)LFSR.線性反饋移位寄存器例2.3已知如圖所示的3級(jí)LFSR.LFSR序列a=0010111的狀態(tài)轉(zhuǎn)移圖線性反饋移位寄存器(LFSR)00101010101111110011028例2.3已知如圖所示的3級(jí)LFSR.線性反饋移位寄存器線性反饋移位寄存器(LFSR)LFSR序列的性質(zhì)

定理2.1任何n級(jí)FSR序列都是終歸周期序列，且其周期至多是2n

1

。

定義2.4周期為2n

1的n級(jí)線性LFSR序列稱為最大長度(Maximallength)序列，簡稱為m-序列。m-序列

定理2.2

a是周期為2n

1的m-序列的充分必要條件是其特征多項(xiàng)式f(x)為n階本原多項(xiàng)式。29線性反饋移位寄存器(LFSR)LFSR序列的性質(zhì)m-序列m-序列的個(gè)數(shù)

定理2.3

設(shè)f(x)是GF(2)上的n次本原多項(xiàng)式,則對任意非0的初始狀態(tài),由f(x)生成的m-序列是循環(huán)等價(jià)(cyclicallyequivalent)的.即:一個(gè)n次本原多項(xiàng)式只能生成一個(gè)m-序列.

定理2.4二元域GF(2)上的n級(jí)m序列共有

(2n-1)/n個(gè).30m-序列m-序列的個(gè)數(shù)定理2.3設(shè)f(xm-序列例2.33級(jí)LFSR的特征多項(xiàng)式為:f(x)=1+x2+x3

001010101011111100110初始狀態(tài)為:(1,0,1),輸出序列為:a=1011100.001010101011111100110初始狀態(tài)為:(0,0,1),輸出序列為:a=001011131m-序列例2.33級(jí)LFSR的特征多項(xiàng)式為:f(m-序列m-序列的偽隨機(jī)性

定理2.5設(shè)a是一個(gè)n級(jí)m序列，周期為2n

1，則(1)在一個(gè)周期內(nèi)，0、1出現(xiàn)的次數(shù)分別為2n-1

1和2n-1。(2)在一個(gè)周期內(nèi)，總游程數(shù)為2n-1。其中，對1

i

n

2，長為i的0游程、1游程各有2n-i-2個(gè)；長為n

1的0游程1個(gè)，長為n的1游程1個(gè)。(3)a的自相關(guān)函數(shù)為:

32m-序列m-序列的偽隨機(jī)性定理2.5設(shè)a是一個(gè)n級(jí)mm-序列m-序列的偽隨機(jī)性

例2.4已知4級(jí)m序列a=100010011010111,有n=47個(gè)0,8個(gè)1游程總數(shù)為8長為1的0游程2個(gè),長為1的1游程2個(gè)長為2的0游程1個(gè),長為2的1游程1個(gè)長為3的0游程1個(gè)長為4的1游程1個(gè).33m-序列m-序列的偽隨機(jī)性例2.4已知4級(jí)m序列a=m-序列m-序列的密碼學(xué)性質(zhì)(C1)周期長:p=2n-1.如n=166時(shí),

p=1050(9.353610465

1049).

(C2)生成容易:只要已知n次本原多項(xiàng)式,容易生成m序列.(C3)m序列極不安全:只要泄露2n位連續(xù)數(shù)字,就可以完全確定反饋多項(xiàng)式的系數(shù),從而得到m序列.已知ai,ai+1,…,ai+2n-1,由以下方程組可唯一解得

c0,c1,…,cn-1.34m-序列m-序列的密碼學(xué)性質(zhì)34第2章流密碼2.1流密碼一般模型2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼算法35第2章流密碼2.1流密碼一般模型352.3序列的線性復(fù)雜度給定一個(gè)長度為N的二元密鑰流序列a,假定捕獲了a的一個(gè)長度為m的部分,不失一般性設(shè)為(a0,a1,…,am

1),能否找到一個(gè)級(jí)數(shù)最短的LFSR,生成整個(gè)密鑰流序列a?序列的密碼分析問題問題一:是否存在LFSR生成整個(gè)序列a？問題二:捕獲序列a多長的部分，才能找到LFSR生成整個(gè)序列a？怎樣確保得到的LFSR最短？362.3序列的線性復(fù)雜度給定一個(gè)長度為N的二元密鑰流序列a2.3序列的線性復(fù)雜度序列的LFSR設(shè)a=(a0,a1,…,aN

1)是一個(gè)長度為N的序列，那么存在N級(jí)LFSR，生成整個(gè)序列a。

當(dāng)a是LFSR序列時(shí)，存在著更短的LFSR生成整個(gè)序列當(dāng)a是非LFSR序列時(shí)，也可能存在著更短的LFSR生成整個(gè)序列a。aN

1…a1a0372.3序列的線性復(fù)雜度序列的LFSR當(dāng)a是LFSR序列時(shí)2.3序列的線性復(fù)雜度B-M算法設(shè)a(N)=(a0,a1,…,aN

1)是一個(gè)長度為N的序列,fN(x)是一個(gè)能生成a(N)且級(jí)數(shù)最小的LFSR的特征多項(xiàng)式,lN是LFSR的級(jí)數(shù),則把<fN(x),lN>稱為a(N)的線性綜合解.

BerleKamp-Massey(1969)提出了求解<fN(x),lN>的迭代算法.382.3序列的線性復(fù)雜度B-M算法38B-M算法39B-M算法39B-M算法例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合解.解:40B-M算法例2.5設(shè)a(10)=(0001101111)B-M算法例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合解.解:41B-M算法例2.5設(shè)a(10)=(0001101111B-M算法例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合解.解:42B-M算法例2.5設(shè)a(10)=(0001101111B-M算法例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合解.解:a(10)的線性綜合解為:f10(x)=1+x+x2+x5,l10=5.若取初值:a(0)=00011,則f10(x)的LFSR序列a=00011011110011101000…,周期為：25-1=31.43B-M算法例2.5設(shè)a(10)=(0001101111B-M算法B-M算法的性質(zhì)B-M算法的時(shí)間復(fù)雜度為O(N2).定理2.6

給定長為N的序列a(N)=(a0,a1,…,aN

1)，如果用B-M算法得到的線性綜合解為(fN(x),lN)，則以fN(x)為生成多項(xiàng)式，產(chǎn)生的長為lN的LFSR就是生成序列a(N)的最短LFSR。定理2.7給定長為N的序列a(N)=(a0,a1,…,aN

1)，用B-M算法得到的線性綜合解為(fN(x),lN)是唯一解的充要條件是2lN

N。44B-M算法B-M算法的性質(zhì)定理2.6給定長為N的序列a(NB-M算法B-M算法的性質(zhì)

定理2.8

設(shè)a(N)={a0,a1,..,aN-1}是一個(gè)長為N的序列,lN是能產(chǎn)生a(N)并且階數(shù)最小的LFSR的階數(shù).則當(dāng)2lN

>N時(shí),a(N)線性綜合解的個(gè)數(shù)為：45B-M算法B-M算法的性質(zhì)定理2.8設(shè)a2.3序列的線性復(fù)雜度序列的線性復(fù)雜度給定序列a，生成它的最短LFSR的長度lN就確定了。如果2lN

N，只需要捕獲序列a連續(xù)的2lN個(gè)比特，就能得到它的唯一解(fN(x),lN)，以fN(x)為特征多項(xiàng)式的lN級(jí)LFSR就可以生成整個(gè)序列a。特別地，對于周期N很大，但lN很小的序列a，比如周期為2n

1的n級(jí)m-序列，利用B-M算法，只要捕獲序列a連續(xù)的2lN個(gè)比特，即序列很小一部分，就可以重構(gòu)整個(gè)序列。因此，lN實(shí)際上度量了序列a的線性的不可預(yù)測性。

462.3序列的線性復(fù)雜度序列的線性復(fù)雜度給定2.3序列的線性復(fù)雜度序列的線性復(fù)雜度

定義2.5生成長為N的序列a=(a0,a1,…,aN

1)的LFSR的最短長度lN被稱為序列a的線性復(fù)雜度。n階m序列的線性復(fù)雜度=n.472.3序列的線性復(fù)雜度序列的線性復(fù)雜度定第2章流密碼2.1流密碼一般模型2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器

2.5流密碼算法48第2章流密碼2.1流密碼一般模型482.4非線性序列生成器密鑰流生成器的分解Ruppe將密鑰流生成器分成兩部分：驅(qū)動(dòng)部分和非線性組合部分

驅(qū)動(dòng)部分：可由m-序列或其它長周期的LFSR序列組成，用于控制密鑰流生成器的狀態(tài)序列，并為非線性組合部分提供偽隨機(jī)性質(zhì)良好的序列非線性組合部分：利用驅(qū)動(dòng)部分生成的狀態(tài)序列生成滿足要求的密碼特性好的密鑰流序列………┇驅(qū)動(dòng)部分┇非線性組合部分┇………492.4非線性序列生成器密鑰流生成器的分解………┇驅(qū)動(dòng)部分2.4非線性序列生成器非線性準(zhǔn)則

非線性組合部分可由布爾函數(shù)表示

n元布爾函數(shù)f(x)的代數(shù)正規(guī)型：502.4非線性序列生成器非線性準(zhǔn)則502.4.1非線性準(zhǔn)則代數(shù)次數(shù)當(dāng)f(x)的代數(shù)次數(shù)為1時(shí)，f(x)稱為線性布爾函數(shù)當(dāng)f(x)的代數(shù)次數(shù)大于1時(shí)，f(x)稱為非線性布爾函數(shù)對于非線性組合部分的布爾函數(shù)，應(yīng)該具有盡可能大的代數(shù)次數(shù)

定義2.6

設(shè)f(x)是一個(gè)n元布爾函數(shù)，在f(x)的代數(shù)正規(guī)型中，一個(gè)乘積項(xiàng)中變量的個(gè)數(shù)稱為該乘積項(xiàng)的次數(shù)。f(x)的代數(shù)正規(guī)型中，全體非零系數(shù)乘積項(xiàng)次數(shù)的最大值稱為f(x)的代數(shù)次數(shù)。512.4.1非線性準(zhǔn)則代數(shù)次數(shù)當(dāng)f(x)的代數(shù)次數(shù)為1時(shí)，f2.4.1非線性準(zhǔn)則非線性度是密碼系統(tǒng)為抵抗線性攻擊而提出的指標(biāo)對于非線性組合部分的布爾函數(shù)，應(yīng)該具有盡可能大的非線性度

定義2.7設(shè)L是Z2上所有線性函數(shù)的集合，即L={u

x+v}|u

Z2n,v

Z2}。則布爾函數(shù)f(x)的非線性度定義為其中dH(

)是漢明距離.522.4.1非線性準(zhǔn)則非線性度是密碼系統(tǒng)為抵抗線性攻擊而提出2.4.1非線性準(zhǔn)則退化布爾函數(shù)自變量經(jīng)過線性變換后，n元布爾函數(shù)f(x)就簡化為k元布爾函數(shù)g(x)作為非線性組合部分的布爾函數(shù)應(yīng)該避免退化性

定義2.8

設(shè)f(x)是一個(gè)n元布爾函數(shù)，如果存在Z2上一個(gè)k

n（k<n）的矩陣D，使得

f(x)=g(Dx)=g(y),則稱f(x)是退化的。532.4.1非線性準(zhǔn)則退化布爾函數(shù)自變量經(jīng)過線性變換后，n元2.4.1非線性準(zhǔn)則布爾函數(shù)的相關(guān)免疫性相關(guān)免疫性是為防止攻擊者對密碼系統(tǒng)進(jìn)行相關(guān)攻擊而提出的指標(biāo)希望作為非線性組合部分的布爾函數(shù)應(yīng)該具有m階相關(guān)免疫性，m盡可能地大

定義2.9設(shè)f(x1,x2,…,xn)是n個(gè)彼此獨(dú)立、對稱的二元隨機(jī)變量的布爾函數(shù)，稱f(x)是m階相關(guān)免疫的當(dāng)且僅當(dāng)f=f(x1,x2,…,xn)與x1,x2,…,xn中的任意m個(gè)隨機(jī)變量542.4.1非線性準(zhǔn)則布爾函數(shù)的相關(guān)免疫性相關(guān)免疫性是為防止2.4.1非線性準(zhǔn)則布爾函數(shù)的相關(guān)免疫性

定義2.10

設(shè)

f(x1,x2,…,xn)是一個(gè)n元布爾函數(shù)，f(x)的Walsh變換定義為552.4.1非線性準(zhǔn)則布爾函數(shù)的相關(guān)免疫性定義2.4.1非線性準(zhǔn)則布爾函數(shù)的相關(guān)免疫性雪崩準(zhǔn)則

定理2.9設(shè)1≤m≤n,n元布爾函數(shù)f=f(x1,x2,…,xn)是m階相關(guān)免疫的當(dāng)且僅當(dāng)對于任意滿足1≤wH(

)≤m的

=(

1,

2,…,

n)

Z2n，f(x)的Walsh譜都為0，即

Sf(

)=0.這里wH(

)是漢明重量.

定義2.11

設(shè)f(x)是一個(gè)n元布爾函數(shù)，如果對于任意滿足:wH(e)=1的e=(e1,e2,…,en)

Z2n，f(x)+f(x+e)是平衡函數(shù)，則稱f(x)為滿足嚴(yán)格雪崩準(zhǔn)則.562.4.1非線性準(zhǔn)則布爾函數(shù)的相關(guān)免疫性雪崩準(zhǔn)則2.4.1非線性準(zhǔn)則擴(kuò)散準(zhǔn)則

定義2.12

設(shè)f(x)是一個(gè)n元布爾函數(shù)，1≤m≤n

2，如果對于任意滿足:1≤wH(e)≤m的e=(e1,e2,…,en)

Z2n，f(x)+f(x+e)是平衡函數(shù)，則稱f(x)為滿足m次擴(kuò)散準(zhǔn)則.非線性序列設(shè)計(jì)準(zhǔn)則代數(shù)次數(shù)非線性度退化性相關(guān)免疫性雪崩準(zhǔn)則擴(kuò)散準(zhǔn)則

572.4.1非線性準(zhǔn)則擴(kuò)散準(zhǔn)則定義2.122.4.2非線性序列生成器濾波生成器（Filtergeneator）濾波生成器又叫前饋生成器，由幾個(gè)LFSR和濾波（前饋）函數(shù)g(x)兩部分組成濾波函數(shù)要求具有很好的非線性性質(zhì)，以增強(qiáng)生成器的抗攻擊能力…LFSRg(x)582.4.2非線性序列生成器濾波生成器（Filterge濾波生成器Geffe生成器使用三個(gè)級(jí)數(shù)兩兩互素的LFSR，其中LFSR1和LFSR3作為多路復(fù)合器的輸入，LFSR2控制多路復(fù)合器的輸出濾波函數(shù)LFSR1多路復(fù)合器選擇控制LFSR3LFSR2設(shè)a1、a2和a3分別是LFSR、LFSR2和LFSR3的輸出，則Geffe生成器的輸出b為:59濾波生成器Geffe生成器LFSR1多路復(fù)合器選擇控制LFS濾波生成器Geffe生成器大的周期和線性復(fù)雜度設(shè)LFSR1、LFSR2和LFSR3周期分別為T1,T2和T3，級(jí)數(shù)分別為n1,n2和n3，則Geffe生成器的周期為T1T2T3，線性復(fù)雜度為(n1＋1)n2＋n1n3.不安全由于生成器的輸出與LFSR2的輸出有75％是相同的，通過觀察輸出序列可以獲得LFSR的初態(tài)和輸出序列，即所謂的相關(guān)攻擊破譯Geffe生成器。因此Geffe生成器是不安全的.60濾波生成器Geffe生成器60濾波生成器J-K觸發(fā)器LFSR1輸出序列{ak},周期為m.LFSR2輸出序列{bk},周期為n.J-K觸發(fā)器輸出序列{ck}令c-1=0,有

c0=a0,

c1=(a1+b1+1)a0+a1,

c2=(a2+b2+1)c1+a2,…{ak}{ck}{bk}LFSR1JKLFSR261濾波生成器J-K觸發(fā)器令c-1=0,有{ak}{J-K觸發(fā)器如果gcd(m,n)=1，且a0+b0=0，則輸出序列{ck}的周期為:(2m-1)(2n-1).J-K觸發(fā)器輸出序列{ck}隨機(jī)性好不安全已知cn與cn+1,便能對an+1與bn+1的一個(gè)作出判斷.

cn=cn+1=0

an+1=0;cn=0,cn+1=1

an+1=1;cn=1,cn+1=0

bn+1=1;cn=cn+1=1

bn+1=0.62J-K觸發(fā)器如果gcd(m,n)=1，且a0+b0=J-K觸發(fā)器例2.4.1令m=2,n=3,且a0+b0=0,LFSR1輸出序列{at}=011…,LFSR2輸出序列{bt}=1001011….有

c0=a0=0,

c1=(a1+b1+1)a0+a1=(1+0+1)0+1=1,

c2=(a2+b2+1)c1+a2=(1+0+1)1+1=1,…{bk}=011010011101010010010….周期為:

L=(2m-1)(2n-1)=(22-1)(23-1)=21.63J-K觸發(fā)器例2.4.1令m=2,n=3,且a0+2.4.2非線性序列生成器鐘控序列生成器鐘控生成器（Clockcontrolledgenerator）是由一個(gè)或幾個(gè)FSR輸出序列，控制另一個(gè)FSR的時(shí)鐘。走停生成器（Stop-and-Gogenerator）當(dāng)LFSR1輸出1時(shí)，時(shí)鐘脈沖通過與門使LFSR2進(jìn)行一次移位，從而生成下一位；當(dāng)LFSR1輸出0，時(shí)鐘脈沖無法通過與門使LFSR2移位（走），從而LFSR2重復(fù)輸出前一位（停）

LFSR1LFSR2642.4.2非線性序列生成器鐘控序列生成器LFSR1LFS鐘控序列生成器鐘控序列的周期設(shè)LFSR1輸出序列{ak},周期為2m-1，LFSR2輸出序列{bk},周期為2n-1，則鐘控序列{ck}的周期為：(2m-1)(2n-1).鐘控序列{ck}的線性復(fù)雜度為：n(2m-1).65鐘控序列生成器鐘控序列的周期65鐘控序列生成器例2.6設(shè)LFSR1為一個(gè)3級(jí)m-序列，其特征多項(xiàng)式為：f1(x)=1+x+x3，取初始值為a0=a1=a2=1,則輸出序列{ak}=1110100,周期為23

1=7.設(shè)LFSR2為一個(gè)3級(jí)m-序列，其特征多項(xiàng)式為：f1(x)=1+x2+x3，取初始值為b0=b1=b2=1,則輸出序列{bk}=1110010,周期為23-1=7.鐘控序列:{ck}=1110000010111111000111011111100110001111000010011…周期為：(2m

1)(2n

1)=(23

1)(23

1)=49.線性復(fù)雜度為：n(2m

1)=3(23

1)=21.66鐘控序列生成器例2.6設(shè)LFSR1為一個(gè)3級(jí)m-序列，其第2章流密碼2.1流密碼一般模型2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器

2.5流密碼算法67第2章流密碼2.1流密碼一般模型672.5流密碼算法RC4算法RC4是由Rivest于1987年開發(fā)的一種