密碼學(xué)概論第2講流密碼

2.1流密碼的基本概念2.2線性反饋移位寄存器2.3線性移位寄存器的一元多項(xiàng)式表示2.4m序列的偽隨機(jī)性2.5m序列密碼的破譯2.6非線性序列第2章流密碼2023/2/412.1流密碼的基本概念流密碼的基本思想y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密鑰流z=z0z1…，明文串x=x0x1x2…：2023/2/42E的選取二元加法流密碼E可表示為yi=zixi。

2023/2/43流加密舉例0110011111110010110101111001110100100001010110011111110010110101111001110100100001010110011111110100100010110101111011010111110100100001100111112023/2/442.1.3密鑰流產(chǎn)生器狀態(tài)轉(zhuǎn)移函數(shù)φ:σi→σi+1輸出函數(shù)ψ:σi→zi，目前最為流行和實(shí)用的密鑰流產(chǎn)生器是線性反饋移位寄存器。密鑰流由密鑰流發(fā)生器f產(chǎn)生：zi=f(k,σi)，σi是加密器中的記憶元件（存儲(chǔ)器）在時(shí)刻i的狀態(tài)，f是由密鑰k和σi產(chǎn)生的函數(shù)。2023/2/452.2線性反饋移位寄存器2023/2/46反饋移位寄存器狀態(tài)：每一時(shí)刻的狀態(tài)對(duì)應(yīng)于GF(2)上的一個(gè)n維向量(a1,a2,…,an)，ai是第i級(jí)存儲(chǔ)器的內(nèi)容。共有2n種可能的狀態(tài)。工作原理：當(dāng)?shù)趇個(gè)移位時(shí)鐘脈沖到來時(shí)，根據(jù)寄存器此時(shí)的狀態(tài)計(jì)算f(a1,a2,…,an)，作為an+1,每一級(jí)存儲(chǔ)器ai都將其內(nèi)容向下一級(jí)ai-1傳遞，（計(jì)算、移位、反饋、輸出）反饋函數(shù)f(a1,a2,…,an)：n元布爾函數(shù)，即n個(gè)變?cè)猘1,a2,…,an可以獨(dú)立地取0和1這兩個(gè)可能的值，函數(shù)中的運(yùn)算有邏輯與、邏輯或、邏輯補(bǔ)等運(yùn)算。2023/2/47線性反饋移位寄存器LFSR線性反饋移位寄存器LFSR（linearfeedbackshiftregister）:反饋函數(shù)f(a1,a2,…,an)是線性函數(shù).f(a1,a2,…,an)=cna1cn-1a2…c1an其中常數(shù)ci=0或1，是模2加法。ci=0或1可用開關(guān)的斷開和閉合來實(shí)現(xiàn)，GF(2)上的n級(jí)線性反饋移位寄存器輸出序列an+1線性反饋移位寄存器實(shí)現(xiàn)簡(jiǎn)單、速度快、理論成熟,是構(gòu)造密鑰流生成器的最重要的部件。2023/2/48例下圖是一個(gè)5級(jí)線性反饋移位寄存器，其初始狀態(tài)為（a5，a4，a3，a2，a1）=(1,1,0,0,1)輸出序列為滿足遞推關(guān)系ak+5=ak+3+ak1001101001000010101110110001111100110…(a5,a4,a3,a2,a1)輸出010111110011001011011000100100101100010011反饋函數(shù)f(a1,a2,a3,a4,a5)=a4+a1周期312023/2/49LFSR反饋函數(shù)f(a1,a2,a3,a4,a5)=C2a4+C5a1

定義LFSR特征多項(xiàng)式（連接多項(xiàng)式）P(x)=1+x2＋x5C5=1C2=12023/2/4102.3線性移位寄存器的特征多項(xiàng)式與序列周期n級(jí)線性移位寄存器的輸出序列滿足遞推關(guān)系an+k=c1an+k-1c2an+k-2…cnak

用一個(gè)一元高次多項(xiàng)式表示P(x)=1+c1x+…＋cn-1xn-1＋cnxn稱這個(gè)多項(xiàng)式為L(zhǎng)FSR的特征多項(xiàng)式（連接多項(xiàng)式）2023/2/411序列周期序列周期使對(duì)所有k，ak+r=ak成立的的最小整數(shù)r多項(xiàng)式的周期使f(x)除盡xp-1的最小整數(shù)p的取值。序列的周期r與特征多項(xiàng)式的周期p密切相關(guān)。(r/p)特征多項(xiàng)式是n次既約多項(xiàng)式周期為p，則生成序列的周期為p。輸出序列最大周期為2n-1。不可約多項(xiàng)式最大周期達(dá)到2n-1。序列為m序列的充要條件特征多項(xiàng)式為本原多項(xiàng)式。本原多項(xiàng)式m序列2023/2/4122023/2/413特征多項(xiàng)式x3+x+1多項(xiàng)式周期7輸出序列ak+3=ak+ak+210100111010…10100111010…序列周期

7 x3+x2+1 7

ak+3=ak+ak+1 1011100

1011…

7特征多項(xiàng)式x3+x2+x+1多項(xiàng)式周期4輸出序列

ak+3=ak+ak+1+ak+210101010…序列周期

2 x3+1 3

ak+3=ak

101101…

3初始1012023/2/414m序列的偽隨機(jī)性隨機(jī)性:如果密鑰流是周期的，要完全做到隨機(jī)性是困難的。游程:設(shè){ai}=(a1a2a3…)為0、1序列，例如00110111，其前兩個(gè)數(shù)字是00，稱為0的2游程；接著是11，是1的2游程；再下來是0的1游程和1的3游程。自相關(guān)函數(shù):R(τ)=(1/T)∑k=1T(-1)ak(-1)ak+τ,序列向后平移τ位，0≤τ≤T-1定義中的和式表示序列{ai}與{ai+τ}在一個(gè)周期內(nèi)對(duì)應(yīng)位相同的位數(shù)與對(duì)應(yīng)位不同的位數(shù)之差。當(dāng)τ=0時(shí)，R(τ)=1；當(dāng)τ≠0時(shí)，稱R(τ)為異相自相關(guān)函數(shù)。10100111010R(1)=R(2)=….=-1/72023/2/415①在序列一個(gè)周期內(nèi)，0與1出現(xiàn)個(gè)數(shù)相差至多為1;（0和1出現(xiàn)概率基本相同）②長(zhǎng)為l的游程占1/2l，在等長(zhǎng)的游程中，“0”游程和“1”游程個(gè)數(shù)相等或至多差一個(gè)。（0和1在各位置上出現(xiàn)概率基本相同）③異相自相關(guān)函數(shù)是常數(shù),與白噪聲的自相關(guān)函數(shù)(函數(shù))相近（序列平移不能提供更多信息）PN序列可用于通信中同步序列、碼分多址(CDMA)、導(dǎo)航中多基站碼、雷達(dá)測(cè)距碼等。PN序列雖與白噪聲序列相似，但遠(yuǎn)還不能滿足密碼體制要求。Golomb隨機(jī)性假設(shè)－PN序列m序列滿足Golomb的三條偽隨機(jī)假設(shè)。101001110102023/2/416滿足密碼體制的另外三個(gè)條件①周期p要足夠大，如大于1050；②序列{ai}產(chǎn)生易于高速生成；③當(dāng)序列{ai}的任何部分暴露時(shí)，要分析整個(gè)序列，在計(jì)算上是不可行的

條件③決定了密碼的強(qiáng)度，是流密碼理論的核心。它包含了流密碼要研究的許多主要問題，如線性復(fù)雜度、相關(guān)免疫性、不可預(yù)測(cè)性等等。2023/2/4172.4m序列的偽隨機(jī)性m序列否滿足密碼要求？n級(jí)m序列的周期為2n－1，n大，周期指數(shù)地加大，例如n=166時(shí)，p=1050(9.353610465×1049)。只要知道n次本原多項(xiàng)式，m序列極易生成。m序列極不安全，只要泄露2n位連續(xù)數(shù)字，就可完全確定出反饋多項(xiàng)式系數(shù)。定理m序列滿足Golomb的三條偽隨機(jī)假設(shè)。2023/2/418由于X可逆序列遞推關(guān)系:限制了其在密碼學(xué)中的應(yīng)用2.5m序列密碼破譯n級(jí)LFSR2023/2/419若X可逆序列遞推關(guān)系:令限制了其在密碼學(xué)中的應(yīng)用2023/2/420因?yàn)閄是由S1,S2,…,Sn作為列向量，要證X可逆，只要證明這n個(gè)向量線性無關(guān)。設(shè)m是使S1,S2,…,Sm線性相關(guān)的最小整數(shù)，即存在不全為0的系數(shù)l1,l2,…,lm，其中不妨設(shè)l1=1，使得證明X是可逆的2023/2/421設(shè)序列{ai}滿足線性遞推關(guān)系：Sh+1=M·Sh密鑰流的級(jí)數(shù)m-1=n

故m=n+1S1,S2,…,Sn線性無關(guān)，由此構(gòu)成的X可逆2023/2/422攻擊實(shí)例：設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計(jì)算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰流是使用5級(jí)線性反饋移位寄存器產(chǎn)生的，那么敵手可用密鑰流的前10個(gè)比特建立如下方程已知明文攻擊2023/2/4232023/2/424非線性移位寄存器序列f(a1,a2,a3)=a1a2+a3輸出序列10111011....，周期為4.對(duì)線性移位寄存器序列進(jìn)行非線性組合非線性移位寄存器研究困難，對(duì)線性移位寄存器研究充分。2.6非線性序列2023/2/425密鑰流生成器驅(qū)動(dòng)子系統(tǒng)一個(gè)或多個(gè)LFSR來實(shí)現(xiàn)非線性組合子系統(tǒng)用非線性組合函數(shù)F來實(shí)現(xiàn)生成序列評(píng)價(jià)周期極大化線性復(fù)雜度最短LFSR級(jí)數(shù)極小特征多項(xiàng)式：最短LFSR的特征多項(xiàng)式非線性組合2023/2/4262.6.2J-K觸發(fā)器令c-1=0驅(qū)動(dòng)序列{ak}和{bk}分別為m級(jí)和n級(jí)m序列m、n互素a0+b0=1{Ck}周期p=(2m-1)(2n-1)

2023/2/427例令m=2,n=3，兩個(gè)驅(qū)動(dòng)m序列分別為{ak}=0,1,1,0,1,1…和{bk}=1,0,0,1,0,1,1,…輸出序列{ck}其周期為(22-1)(23-1)=21。0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,1,0,0,1,0,如果知道{ck}中相鄰位的值ck-1和ck，就可以推斷出ak和bk中的一個(gè)，通過密碼分析的方法得到序列{ak}和{bk}。為了克服上述缺點(diǎn)，Pless提出了由多個(gè)J-K觸發(fā)器序列驅(qū)動(dòng)的多路復(fù)合序列方案2023/2/4282.6.3Pless生成器2023/2/4292.6.4鐘控序列生成器鐘控序列最基本的模型是用一個(gè)LFSR控制另外一個(gè)LFSR的移位時(shí)鐘脈沖.易于由硬件實(shí)現(xiàn)。當(dāng)LFSR1輸出1時(shí)，移位時(shí)鐘脈沖通過與門使LFSR2進(jìn)行一次移位。當(dāng)LFSR1輸出0時(shí)，移位時(shí)鐘脈沖無法通過與門影響LFSR2,LFSR2狀態(tài)不改變。2023/2/430前提：LFSR1和LFSR2輸出序列分別是{ak}和{bk}對(duì)應(yīng)極小特征多項(xiàng)式分別為GF(2)上的m和n次本原多項(xiàng)式f1(x)和f2(x)，且m|n結(jié)論：序列{ck}周期p=(2m-1)(2n-1)線性復(fù)雜度為n(2m-1)極小特征多項(xiàng)式為相關(guān)結(jié)論2023/2/431例設(shè)LFSR1為3級(jí)m序列生成器，其特征多項(xiàng)式為f1(x)=1+x+x3。設(shè)初態(tài)為(1,1,1)，輸出序列為{ak}=1,1,1,0,1,0,0,…。又設(shè)LFSR2為3級(jí)m序列生成器，其特征多項(xiàng)式為f2(x)=1+x2+x3且初態(tài)為(1,1,1)則{bk}=1,1,1,0,0,1,0，…。LFSR2狀態(tài)向量為σk，則變化為:{ck}的周期為(23-1)2=49ak+3=ak+ak+2bk+3=bk+bk+1{ck}=1,1,1,0,0,0,0,0, 1,0,1,1,1,1,1, 1,0,0,0,1,1,1, 0,1,1,1,1,1,1, 0,0,1,1,0,0,0,….2023/2/432序號(hào)狀態(tài)輸出0111110111200113100031000401004010040100{ck}=1,1,1,0,0,0,0,0,bk+3bk+1bkck{bk}=1,1,1,0,0,1,0，…。2023/2/433{ck}的周期（23-1）*（23-1）=49極小特征多項(xiàng)式為1+x14+x21線性復(fù)雜度為3·（23-1）=21線性等價(jià)生成器如下圖f2(x)=1+x2+x3周期p=(2m-1)(2n-1)線性復(fù)雜度為n(2m-1)極小特征多項(xiàng)式2023/2/434有限狀態(tài)自動(dòng)機(jī)具有離散輸入和輸出的一種數(shù)學(xué)模型由3部分組成：①有限狀態(tài)集S={si|i=1,2,…,l}。②有限輸入字符集A1={A(1)j|j=1,2,…,m}和有限輸出字符集A2={A(2)k|k=1,2,…,n}。③輸出函數(shù)A(2)k=f1(si,A(1)j)，轉(zhuǎn)移函數(shù)sh=f2(si,A(1)j)即在狀態(tài)為si，輸入為A(1)j時(shí)，輸出為A(2)k，而狀態(tài)轉(zhuǎn)移為sh。2023/2/435例S={s1,s2,s3}，A1={A(1)1,A(1)2,A(1)3}，A2={A(2)1,A(2)2,A(2)3}，轉(zhuǎn)移函數(shù)由表2.1給出。輸入序列為A(1)1A(1)2A(1)1A(1)3A(1)3A(1)1，初始狀態(tài)為s1，則得到狀態(tài)序列s1s2s2s3s2s1s2輸出字符序列A(2)1A(2)1A(2)2A(2)1A(2)3A(2)12023/2/436同步流密碼的密鑰流產(chǎn)生器可看成一個(gè)有限狀態(tài)自動(dòng)機(jī)。由一個(gè)輸出符號(hào)集Z、一個(gè)狀態(tài)集∑、兩個(gè)函數(shù)φ和ψ以及一個(gè)初始狀態(tài)σ0組成。2023/2/437藍(lán)牙是一種用于替代某些電子設(shè)備上使用電纜或連線的短距離無線連接技術(shù)。具有同樣藍(lán)牙接口的設(shè)備連接可以實(shí)現(xiàn)無線連接，有效連接距離達(dá)10米，一般的傳輸速度都有1M目前配置藍(lán)牙接口的電子設(shè)備卻不是很多；沒有藍(lán)牙接口的電腦可通過加裝藍(lán)牙適配器來實(shí)現(xiàn)無線連接，適配器一般都是USB接口，可以插在電腦上，使用方便。采用無線電波為載體，安全性差，信息傳輸需加密加密算法使用流密碼.流密碼的應(yīng)用——藍(lán)牙Bluetooth2023/2/438藍(lán)牙流加密原理2023/2/4394個(gè)LFSR比特長(zhǎng)度分別為25，31，33，39；長(zhǎng)度之和是128bit特征多項(xiàng)式都是本原多項(xiàng)式設(shè)xti為L(zhǎng)SFRi的第t個(gè)符號(hào)2023/2/440IEEE802.11是當(dāng)今無線局域網(wǎng)WLAN通用的標(biāo)準(zhǔn)，IEEE802.11安全框架中包括站點(diǎn)接入認(rèn)證方法、數(shù)據(jù)