流密碼詳解學(xué)習(xí)資料

第2章流密碼(mìmǎ)李向東中原(zhōngyuán)工學(xué)院計算機學(xué)院124197985@2011.9-2012.11第一頁，共76頁。第2章流密碼(mìmǎ)2.1流密碼(mìmǎ)一般模型2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼(mìmǎ)算法2第二頁，共76頁。2.1流密碼一般(yībān)模型實用密碼體制(tǐzhì)的分類3第三頁，共76頁。2.1流密碼(mìmǎ)一般模型流密碼(mìmǎ)(streamcipher)(序列密碼(mìmǎ))體制模型明文序列:m=m1m2m3…;密鑰序列:z=z1z2z3…;密文(mìwén)序列:c=c1c2c3…;加密變換:ci=E(zi,mi)(i=1,2,3,…);解密變換:mi=D(zi,ci)(i=1,2,3,…).4第四頁，共76頁。課堂(kètáng)討論：加密函數(shù)(hánshù)和解密函數(shù)(hánshù)都用異或運算，行不行？什么樣的加解密算法是高效、安全的？Why？實用的流密碼方案中，加解密算法是什么？5第五頁，共76頁。流密碼(mìmǎ)原理框圖信道ciD(zi,ci)cimiE(zi,mi)mi密鑰流生成器zizi密鑰流生成器kk安全信道2.1流密碼(mìmǎ)一般模型6第六頁，共76頁。流密碼體制的安全性當(dāng)流鑰序列(xùliè)是具有均勻分布的離散無記憶隨機序列(xùliè)時,在理論上是不可破譯的.實用的困難性真正的具有均勻分布的隨機序列(xùliè)是不可能重復(fù)產(chǎn)生的.密鑰序列(xùliè)長(至少與明文序列(xùliè)一樣長),其管理(存儲、分配)難.設(shè)計流密碼體制的關(guān)鍵問題設(shè)計產(chǎn)生密鑰序列(xùliè)的方法.2.1流密碼一般(yībān)模型7第七頁，共76頁。序列密碼(mìmǎ)的分類同步流密碼(mìmǎ)(SSC:synchronousstreamcipher)產(chǎn)生密鑰序列的算法與明文、密文無關(guān).自同步流密碼(mìmǎ)(SSSC:self-synchronousstreamcipher)產(chǎn)生密鑰序列的算法與以前的密文有關(guān).2.1流密碼一般(yībān)模型8第八頁，共76頁。同步流密碼(SSC:synchronousstreamcipher)只要通信雙方的密鑰序列產(chǎn)生器具有相同的“種子序列”和相同的“初始狀態(tài)”,就能產(chǎn)生相同的密鑰序列.通信雙方必須保持精確同步,才能正確解密.容易檢測插入、刪除、重播等主動攻擊.沒有差錯傳播.討論：如何對SSC的這種“同步”性質(zhì)進行(jìnxíng)形式化描述？2.1流密碼一般(yībān)模型9第九頁，共76頁。同步(tóngbù)流密碼(SSC:synchronousstreamcipher)產(chǎn)生密鑰序列的算法與明文、密文無關(guān).ciE(zi,mi)mizi密鑰流生成器k2.1流密碼一般(yībān)模型10第十頁，共76頁。自同步流密碼(SSSC:self-synchronousstreamcipher)產(chǎn)生密鑰序列的算法(suànfǎ)與以前的密文有關(guān).E(zi,mi)mizi密鑰流生成器kci2.1流密碼(mìmǎ)一般模型11第十一頁，共76頁。自同步流密碼(SSSC)密鑰流生成器是一種有記憶變換器密鑰流與明文符號有關(guān)：i時刻的密文不僅取決于i時刻的明文，而且與i時刻之前的l個明文符號有關(guān)具有有限的差錯傳播具有自同步能力把明文每個字符擴散(kuòsàn)在密文多個字符中,強化了抗統(tǒng)計分析的能力問：SSSC是如何自同步的？請email回應(yīng)。2.1流密碼(mìmǎ)一般模型12第十二頁，共76頁。二元加法(jiāfǎ)序列密碼明文序列:m=m1m2m3…;密鑰序列:z=z1z2z3…;密文(mìwén)序列:c=c1c2c3…;加密變換:ci=zimi(i=1,2,3,…);解密變換:mi=zici(i=1,2,3,…).2.1流密碼一般(yībān)模型13第十三頁，共76頁。第2章流密碼(mìmǎ)2.1流密碼一般模型2.2線性反饋移位(yíwèi)寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼算法14第十四頁，共76頁。2.2線性反饋移位(yíwèi)寄存器序列偽隨機(suíjī)序列考慮二元序列:a={ai}=a0a1a2a3….周期序列定義2.1設(shè)a=(a0,a1,…,ai,…)是一個二元序列(xùliè)，若存在正整數(shù)N和非負整數(shù)m，使得ai+N=ai對于任意im成立，則稱二元序列(xùliè)a是終歸周期序列(xùliè)。如果m=0，則稱序列(xùliè)a是嚴(yán)格周期序列(xùliè)，簡稱周期序列(xùliè)。而滿足ai+N＝ai(im)的最小正整數(shù)N被稱為序列(xùliè)a的周期。15第十五頁，共76頁。2.2線性反饋移位(yíwèi)寄存器序列定義2.2設(shè)a=(a0,a1,…,ai,…)是一個(yīɡè)周期為N的二元序列，在一個(yīɡè)周期內(nèi)連續(xù)出現(xiàn)的最多的符號“0”（或1）的串，稱為0（或1）的一個(yīɡè)游程。在一個(yīɡè)游程中，0（或1）的個數(shù)稱為該游程的長度。（討論：該定義有否歧義？）偽隨機序列(xùliè)序列(xùliè)的游程例:在序列k={ki}=001110100000111100中,有長為1的0游程一個;長為4的0游程一個;長為5的0游程一個;長為1的1游程一個;長為3的1游程一個;長為4的1游程一個.16第十六頁，共76頁。2.2線性反饋(fǎnkuì)移位寄存器序列定義(dìngyì)2.3設(shè)a=(a0,a1,…,aN1)和b=(b0,b1,…,bN1)是兩個周期為N的二元周期序列，其相關(guān)函數(shù)定義(dìngyì)為特別地，如果a=b，則Ra,a()被稱為自相關(guān)函數(shù)，其中當(dāng)=0，Ra,a(0)被稱為同相自相關(guān)函數(shù)，而當(dāng)0，Ra,a()被稱為異相自相關(guān)函數(shù)。偽隨機(suíjī)序列序列的相關(guān)函數(shù)17第十七頁，共76頁。2.2線性反饋(fǎnkuì)移位寄存器序列例2.1已知序列a=01011100101110…，則a是周期為7的周期序列;a一共(yīgòng)有4個游程：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.18第十八頁，共76頁。偽隨機(suíjī)序列哥倫布(Golomb,1955)隨性假設(shè)(jiǎshè)(G1)：在一個周期內(nèi)，0與1出現(xiàn)的個數(shù)至多相差(xiānɡchà)1。也即，如果N為偶數(shù)，則在一個周期內(nèi)0與1的數(shù)目各占N/2；如果N為奇數(shù)，則在一個周期內(nèi)0的數(shù)目為(N+1)/2或者(N-1)/2，相應(yīng)地1的數(shù)目為(N-1)/2或者(N+1)/2。(G2)：在一個周期內(nèi)，長度為i的游程個數(shù)占游程總數(shù)的1/2i，i=1,2,…。且在長度為i的游程中，0的游程與1的游程數(shù)目相等或至多相差(xiānɡchà)一個。(G3)：序列的異相自相關(guān)函數(shù)是一個常數(shù)。滿足上述三個條件的序列稱為擬噪聲序列,或偽噪聲序列(pseudonoisesequence),簡記為:PN序列.PN序列在CDMA,通信同步,導(dǎo)航,雷達測距等領(lǐng)域有重要應(yīng)用.19第十九頁，共76頁。SolomonW.Golomb:Shimonoseki,Japan,October10-14,200520第二十頁，共76頁。偽隨機(suíjī)序列密鑰序列k={ki}=k0k1k2k3….滿足的條件(tiáojiàn)G1,G2,G3和以下三個條件(tiáojiàn)：(C1)周期p要長.如p>1050.(C2)生成容易.(C3)具有不可預(yù)測性(unpredictability):當(dāng)密鑰序列k的任何部分泄露時,要分析整個(zhěnggè)密鑰序列,在計算上是不可行的.C3決定了密碼的強度,是序列密碼理論的核心.主要研究問題:線性復(fù)雜度,相關(guān)免疫性,不可預(yù)測性等.21第二十一頁，共76頁。an1…a1a0f(x0,x1,…,xn1)反饋移位寄存器(FSR:FeedbackShiftRegister)n個寄存器:從右至左依次(yīcì)稱為第1,2,…,n級反饋函數(shù)f(x0,x1,…,xn-1):GF(2)nGF(2).工作原理:當(dāng)一個時鐘脈沖來到時,第i級寄存器的內(nèi)容傳送給第i-1級寄存器(i=2,3,…,n),第1級寄存器的內(nèi)容為反饋移位寄存器的輸出.反饋函數(shù)f(x0,x1,…,xn-1)的值傳送給第n級寄存器.FSR的輸出序列:a0,a1,a2,…,an,…稱為反饋移位寄存器序列(FSR序列).偽隨機(suíjī)序列22第二十二頁，共76頁。在任意時刻t,第1至n級寄存器的內(nèi)容st=(at,at+1,…,at+n-1)GF(2)n稱為(chēnɡwéi)FSR在時刻t的狀態(tài)(state).s0=(a0,a1,…,an-1)稱為(chēnɡwéi)FSR的初始狀態(tài).在時刻t+1的狀態(tài)為:st+1=(at+1,at+2,…,at+n),at+n=f(at,at+1,…,at+n-1).共有2n個狀態(tài).反饋函數(shù)f(x1,x2,…,xn)是n個變量的布爾函數(shù)(Booleanfunction).反饋(fǎnkuì)移位寄存器(FSR)23第二十三頁，共76頁。例2.2設(shè)有限域GF(2)上的3級FSR的反饋函數(shù)(hánshù)為:f(x1,x2,x3)=x1x2x3初始狀態(tài)為s0=(1,0,1).求FSR序列.解:反饋移位寄存器序列:a=1011…;周期q=4.反饋(fǎnkuì)移位寄存器(FSR)時刻狀態(tài)輸出3級2級1級01011111002111130111410115110024第二十四頁，共76頁。如果(rúguǒ)反饋函數(shù)f(x1,x2,…,xn)是n個變量的線性函數(shù):f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1(ci{0,1})則稱為線性反饋移位寄存器(LFSR:linearfeedbackshiftregister).輸出的序列稱為線性反饋移位寄存器序列,記為LFSR序列。LFSR序列a=(a0,a1,…,an-1,…)滿足遞推關(guān)系式:線性反饋(fǎnkuì)移位寄存器(LFSR)an1…a1a0cncn-1c125第二十五頁，共76頁。反饋(fǎnkuì)函數(shù):f(x1,x2,…,xn)=c1xn+c2xn-1+…+cnx1(ci{0,1})如果cn=0，則稱LFSR是退化的；否則稱LFSR是非退化的。把多項式：f(x)=1+c1x+c2x2+…+cnxn稱為LFSR的特征多項式(characteristicpolynomial),或級連多項式、或生成多項式。線性反饋(fǎnkuì)移位寄存器(LFSR)26第二十六頁，共76頁。例2.3已知如圖所示的3級LFSR.特征(tèzhē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.線性反饋(fǎnkuì)移位寄存器(LFSR)an1an2an3時刻狀態(tài)輸出3級2級1級0100010100210113110041111501116001127第二十七頁，共76頁。例2.3已知如圖所示的3級LFSR.LFSR序列a=0010111的狀態(tài)(zhuàngtài)轉(zhuǎn)移圖線性反饋(fǎnkuì)移位寄存器(LFSR)時刻狀態(tài)輸出3級2級1級0100010100210113110041111501116001100101010101111110011028第二十八頁，共76頁。線性反饋(fǎnkuì)移位寄存器(LFSR)LFSR序列(xùliè)的性質(zhì)定理2.1任何n級FSR序列都是終歸(zhōngguī)周期序列，且其周期至多是2n1。

定義2.4周期為2n

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

定理2.2

a是周期為2n

1的m-序列的充分必要條件是其特征多項式f(x)為n階本原多項式。29第二十九頁，共76頁。m-序列(xùliè)m-序列(xùliè)的個數(shù)定理2.3設(shè)f(x)是GF(2)上的n次本原多項式,則對任意(rènyì)非0的初始狀態(tài),由f(x)生成的m-序列是循環(huán)等價(cyclicallyequivalent)的.即:一個n次本原多項式只能生成一個m-序列.

定理2.4二元域GF(2)上的n級m序列共有(2n-1)/n個.30第三十頁，共76頁。m-序列(xùliè)例2.33級LFSR的特征(tèzhēng)多項式為:f(x)=1+x2+x3001010101011111100110初始狀態(tài)為:(1,0,1),輸出(shūchū)序列為:a=1011100.001010101011111100110初始狀態(tài)為:(0,0,1),輸出序列為:a=001011131第三十一頁，共76頁。m-序列(xùliè)m-序列(xùliè)的偽隨機性定理2.5設(shè)a是一個n級m序列，周期為2n1，則(1)在一個周期內(nèi)，0、1出現(xiàn)的次數(shù)分別為2n-11和2n-1。(2)在一個周期內(nèi)，總游程數(shù)為2n-1。其中，對1in2，長為i的0游程、1游程各有2n-i-2個；長為n1的0游程1個，長為n的1游程1個。(3)a的自相關(guān)函數(shù)為:

32第三十二頁，共76頁。m-序列(xùliè)m-序列(xùliè)的偽隨機性例2.4已知4級m序列a=100010011010111,有n=47個0,8個1游程(yóuchénɡ)總數(shù)為8長為1的0游程(yóuchénɡ)2個,長為1的1游程(yóuchénɡ)2個長為2的0游程(yóuchénɡ)1個,長為2的1游程(yóuchénɡ)1個長為3的0游程(yóuchénɡ)1個長為4的1游程(yóuchénɡ)1個.33第三十三頁，共76頁。m-序列(xùliè)m-序列的密碼學(xué)性質(zhì)(C1)周期長:p=2n-1.如n=166時,p=1050(9.3536104651049).(C2)生成容易:只要已知n次本原(běnyuán)多項式,容易生成m序列.(C3)m序列極不安全:只要泄露2n位連續(xù)數(shù)字,就可以完全確定反饋多項式的系數(shù),從而得到m序列.已知ai,ai+1,…,ai+2n-1,由以下方程組可唯一解得c0,c1,…,cn-1.34第三十四頁，共76頁。第2章流密碼(mìmǎ)2.1流密碼一般模型2.2線性反饋移位寄存器序列(xùliè)2.3線性復(fù)雜度及B-M算法2.4非線性序列(xùliè)生成器2.5流密碼算法35第三十五頁，共76頁。2.3序列(xùliè)的線性復(fù)雜度給定一個長度為N的二元密鑰流序列a,假定捕獲了a的一個長度為m的部分,不失一般性設(shè)為(a0,a1,…,am1),能否(nénɡfǒu)找到一個級數(shù)最短的LFSR,生成整個密鑰流序列a?序列(xùliè)的密碼分析問題問題一:是否存在LFSR生成整個序列a？問題二:捕獲序列a多長的部分，才能找到LFSR生成整個序列a？怎樣確保得到的LFSR最短？36第三十六頁，共76頁。2.3序列(xùliè)的線性復(fù)雜度序列的LFSR設(shè)a=(a0,a1,…,aN1)是一個長度為N的序列，那么存在(cúnzài)N級LFSR，生成整個序列a。當(dāng)a是LFSR序列(xùliè)時，存在著更短的LFSR生成整個序列(xùliè)當(dāng)a是非LFSR序列(xùliè)時，也可能存在著更短的LFSR生成整個序列(xùliè)a。aN1…a1a037第三十七頁，共76頁。2.3序列(xùliè)的線性復(fù)雜度B-M算法設(shè)a(N)=(a0,a1,…,aN1)是一個長度為N的序列,fN(x)是一個能生成a(N)且級數(shù)最小的LFSR的特征多項式,lN是LFSR的級數(shù),則把<fN(x),lN>稱為a(N)的線性綜合(zōnghé)解.BerleKamp-Massey(1969)提出了求解<fN(x),lN>的迭代算法.38第三十八頁，共76頁。B-M算法(suànfǎ)39第三十九頁，共76頁。B-M算法(suànfǎ)例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合(zōnghé)解.解:40第四十頁，共76頁。B-M算法(suànfǎ)例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合(zōnghé)解.解:41第四十一頁，共76頁。B-M算法(suànfǎ)例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合(zōnghé)解.解:42第四十二頁，共76頁。B-M算法(suànfǎ)例2.5設(shè)a(10)=(0001101111),N=10,求其線性綜合(zōnghé)解.解:a(10)的線性綜合解為:f10(x)=1+x+x2+x5,l10=5.若取初值:a(0)=00011,則f10(x)的LFSR序列(xùliè)a=00011011110011101000…,周期為：25-1=31.43第四十三頁，共76頁。B-M算法(suànfǎ)B-M算法(suànfǎ)的性質(zhì)B-M算法(suànfǎ)的時間復(fù)雜度為O(N2).定理2.6給定(ɡěidìnɡ)長為N的序列a(N)=(a0,a1,…,aN1)，如果用B-M算法得到的線性綜合解為(fN(x),lN)，則以fN(x)為生成多項式，產(chǎn)生的長為lN的LFSR就是生成序列a(N)的最短LFSR。定理2.7給定長為N的序列a(N)=(a0,a1,…,aN1)，用B-M算法得到的線性綜合解為(fN(x),lN)是唯一解的充要條件是2lNN。44第四十四頁，共76頁。B-M算法(suànfǎ)B-M算法(suànfǎ)的性質(zhì)

定理2.8

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

>N時,a(N)線性綜合解的個數(shù)為：45第四十五頁，共76頁。2.3序列(xùliè)的線性復(fù)雜度序列(xùliè)的線性復(fù)雜度給定序列a，生成它的最短LFSR的長度lN就確定了。如果2lNN，只需要捕獲序列a連續(xù)的2lN個比特，就能得到它的唯一解(fN(x),lN)，以fN(x)為特征多項式的lN級LFSR就可以生成整個(zhěnggè)序列a。特別地，對于周期N很大，但lN很小的序列a，比如周期為2n1的n級m-序列，利用B-M算法，只要捕獲序列a連續(xù)的2lN個比特，即序列很小一部分，就可以重構(gòu)整個(zhěnggè)序列。因此，lN實際上度量了序列a的線性的不可預(yù)測性。46第四十六頁，共76頁。2.3序列(xùliè)的線性復(fù)雜度序列(xùliè)的線性復(fù)雜度定義2.5生成長為N的序列a=(a0,a1,…,aN1)的LFSR的最短長度(chángdù)lN被稱為序列a的線性復(fù)雜度。n階m序列的線性復(fù)雜度=n.47第四十七頁，共76頁。第2章流密碼(mìmǎ)2.1流密碼一般模型(móxíng)2.2線性反饋移位寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼算法48第四十八頁，共76頁。2.4非線性序列(xùliè)生成器密鑰流生成器的分解Ruppe將密鑰流生成器分成兩部分：驅(qū)動部分和非線性組合部分驅(qū)動部分：可由m-序列或其它長周期的LFSR序列組成，用于控制(kòngzhì)密鑰流生成器的狀態(tài)序列，并為非線性組合部分提供偽隨機性質(zhì)良好的序列非線性組合部分：利用驅(qū)動部分生成的狀態(tài)序列生成滿足要求的密碼特性好的密鑰流序列………┇驅(qū)動部分┇非線性組合部分┇………49第四十九頁，共76頁。2.4非線性序列(xùliè)生成器非線性準(zhǔn)則非線性組合(zǔhé)部分可由布爾函數(shù)表示n元布爾函數(shù)f(x)的代數(shù)正規(guī)型：50第五十頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)代數(shù)(dàishù)次數(shù)當(dāng)f(x)的代數(shù)次數(shù)為1時，f(x)稱為線性布爾函數(shù)(hánshù)當(dāng)f(x)的代數(shù)次數(shù)大于1時，f(x)稱為非線性布爾函數(shù)(hánshù)對于非線性組合部分的布爾函數(shù)(hánshù)，應(yīng)該具有盡可能大的代數(shù)次數(shù)

定義2.6

設(shè)f(x)是一個n元布爾函數(shù)，在f(x)的代數(shù)正規(guī)型中，一個乘積項中變量的個數(shù)稱為該乘積項的次數(shù)。f(x)的代數(shù)正規(guī)型中，全體非零系數(shù)乘積項次數(shù)的最大值稱為f(x)的代數(shù)次數(shù)。51第五十一頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)非線性度是密碼系統(tǒng)為抵抗線性攻擊而提出的指標(biāo)對于非線性組合(zǔhé)部分的布爾函數(shù)，應(yīng)該具有盡可能大的非線性度

定義2.7設(shè)L是Z2上所有線性函數(shù)的集合，即L={ux+v}|uZ2n,vZ2}。則布爾函數(shù)f(x)的非線性度定義為其中dH()是漢明距離.52第五十二頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)退化(tuìhuà)布爾函數(shù)自變量經(jīng)過線性變換后，n元布爾函數(shù)(hánshù)f(x)就簡化為k元布爾函數(shù)(hánshù)g(x)作為非線性組合部分的布爾函數(shù)(hánshù)應(yīng)該避免退化性

定義2.8

設(shè)f(x)是一個n元布爾函數(shù)，如果存在Z2上一個kn（k<n）的矩陣D，使得

f(x)=g(Dx)=g(y),則稱f(x)是退化的。53第五十三頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)布爾函數(shù)(hánshù)的相關(guān)免疫性相關(guān)免疫性是為防止攻擊者對密碼系統(tǒng)進行相關(guān)攻擊而提出的指標(biāo)希望作為(zuòwéi)非線性組合部分的布爾函數(shù)應(yīng)該具有m階相關(guān)免疫性，m盡可能地大

定義2.9設(shè)f(x1,x2,…,xn)是n個彼此獨立、對稱的二元隨機變量的布爾函數(shù)，稱f(x)是m階相關(guān)免疫的當(dāng)且僅當(dāng)f=f(x1,x2,…,xn)與x1,x2,…,xn中的任意m個隨機變量54第五十四頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)布爾函數(shù)(hánshù)的相關(guān)免疫性定義2.10設(shè)f(x1,x2,…,xn)是一個(yīɡè)n元布爾函數(shù)，f(x)的Walsh變換定義為55第五十五頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)布爾函數(shù)(hánshù)的相關(guān)免疫性雪崩(xuěbēng)準(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)是一個n元布爾函數(shù)，如果對于任意滿足:wH(e)=1的e=(e1,e2,…,en)Z2n，f(x)+f(x+e)是平衡函數(shù)，則稱f(x)為滿足嚴(yán)格雪崩準(zhǔn)則.56第五十六頁，共76頁。2.4.1非線性準(zhǔn)則(zhǔnzé)擴散(kuòsàn)準(zhǔn)則定義2.12設(shè)f(x)是一個n元布爾函數(shù)，1≤m≤n2，如果對于任意滿足(mǎnzú):1≤wH(e)≤m的e=(e1,e2,…,en)Z2n，f(x)+f(x+e)是平衡函數(shù)，則稱f(x)為滿足(mǎnzú)m次擴散準(zhǔn)則.非線性序列設(shè)計準(zhǔn)則代數(shù)次數(shù)非線性度退化性相關(guān)免疫性雪崩準(zhǔn)則擴散準(zhǔn)則

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

c0=a0,

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

c2=(a2+b2+1)c1+a2,…JK

ck00011011ck-1

01{ak}{ck}{bk}LFSR1JKLFSR261第六十一頁，共76頁。J-K觸發(fā)器如果gcd(m,n)=1，且a0+b0=0，則輸出序列{ck}的周期為:(2m-1)(2n-1).J-K觸發(fā)器輸出序列{ck}隨機性好不安全已知cn與cn+1,便能對an+1與bn+1的一個(yīɡè)作出判斷.cn=cn+1=0an+1=0;cn=0,cn+1=1an+1=1;cn=1,cn+1=0bn+1=1;cn=cn+1=1bn+1=0.62第六十二頁，共76頁。J-K觸發(fā)器例2.4.1令m=2,n=3,且a0+b0=0,LFSR1輸出(shūchū)序列{at}=011…,LFSR2輸出(shūchū)序列{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.JK

ck00011011ck-1

01

63第六十三頁，共76頁。2.4.2非線性序列(xùliè)生成器鐘控序列生成器鐘控生成器（Clockcontrolledgenerator）是由一個或幾個FSR輸出序列，控制另一個FSR的時鐘。走停生成器（Stop-and-Gogenerator）當(dāng)LFSR1輸出1時，時鐘脈沖通過與門使LFSR2進行一次移位，從而生成下一位；當(dāng)LFSR1輸出0，時鐘脈沖無法(wúfǎ)通過與門使LFSR2移位（走），從而LFSR2重復(fù)輸出前一位（停）LFSR1LFSR264第六十四頁，共76頁。鐘控序列(xùliè)生成器鐘控序列的周期(zhōuqī)設(shè)LFSR1輸出序列{ak},周期(zhōuqī)為2m-1，LFSR2輸出序列{bk},周期(zhōuqī)為2n-1，則鐘控序列{ck}的周期(zhōuqī)為：(2m-1)(2n-1).鐘控序列{ck}的線性復(fù)雜度為：n(2m-1).65第六十五頁，共76頁。鐘控序列(xùliè)生成器例2.6設(shè)LFSR1為一個3級m-序列，其特征多項式為：f1(x)=1+x+x3，取初始值為a0=a1=a2=1,則輸出(shūchū)序列{ak}=1110100,周期為231=7.設(shè)LFSR2為一個3級m-序列，其特征多項式為：f1(x)=1+x2+x3，取初始值為b0=b1=b2=1,則輸出(shūchū)序列{bk}=1110010,周期為23-1=7.鐘控序列:{ck}=1110000010111111000111011111100110001111000010011…周期為：(2m1)(2n1)=(231)(231)=49.線性復(fù)雜度為：n(2m1)=3(231)=21.66第六十六頁，共76頁。第2章流密碼(mìmǎ)2.1流密碼一般模型2.2線性反饋移位(yíwèi)寄存器序列2.3線性復(fù)雜度及B-M算法2.4非線性序列生成器2.5流密碼算法67第六十七頁，共76頁。2.5流密碼(mìmǎ)算法RC4算法RC4是由Rivest于1987年開發(fā)的一種序列密碼,它已被廣