密碼學概論 第2講流密碼

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

2024/6/23流加密舉例0110011111110010110101111001110100100001010110011111110010110101111001110100100001010110011111110100100010110101111011010111110100100001100111112024/6/242.1.3密鑰流產(chǎn)生器狀態(tài)轉(zhuǎn)移函數(shù)φ:σi→σi+1輸出函數(shù)ψ:σi→zi，目前最為流行和實用的密鑰流產(chǎn)生器是線性反饋移位寄存器。密鑰流由密鑰流發(fā)生器f產(chǎn)生：zi=f(k,σi)，σi是加密器中的記憶元件（存儲器）在時刻i的狀態(tài)，f是由密鑰k和σi產(chǎn)生的函數(shù)。2024/6/252.2線性反饋移位寄存器2024/6/26反饋移位寄存器狀態(tài)：每一時刻的狀態(tài)對應于GF(2)上的一個n維向量(a1,a2,…,an)，ai是第i級存儲器的內(nèi)容。共有2n種可能的狀態(tài)。工作原理：當?shù)趇個移位時鐘脈沖到來時，根據(jù)寄存器此時的狀態(tài)計算f(a1,a2,…,an)，作為an+1,每一級存儲器ai都將其內(nèi)容向下一級ai-1傳遞，（計算、移位、反饋、輸出）反饋函數(shù)f(a1,a2,…,an)：n元布爾函數(shù)，即n個變元a1,a2,…,an可以獨立地取0和1這兩個可能的值，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算。2024/6/27線性反饋移位寄存器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)的斷開和閉合來實現(xiàn)，GF(2)上的n級線性反饋移位寄存器輸出序列an+1線性反饋移位寄存器實現(xiàn)簡單、速度快、理論成熟,是構(gòu)造密鑰流生成器的最重要的部件。2024/6/28例下圖是一個5級線性反饋移位寄存器，其初始狀態(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周期312024/6/29LFSR反饋函數(shù)f(a1,a2,a3,a4,a5)=C2a4+C5a1

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

用一個一元高次多項式表示P(x)=1+c1x+…＋cn-1xn-1＋cnxn稱這個多項式為LFSR的特征多項式（連接多項式）2024/6/211序列周期序列周期使對所有k，ak+r=ak

成立的的最小整數(shù)r多項式的周期使f(x)除盡xp-1的最小整數(shù)p的取值。序列的周期r與特征多項式的周期p密切相關(guān)。(r/p)特征多項式是n次既約多項式周期為p，則生成序列的周期為p。輸出序列最大周期為2n-1。不可約多項式最大周期達到2n-1。序列為m序列的充要條件特征多項式為本原多項式。本原多項式m序列2024/6/2122024/6/213特征多項式x3+x+1多項式周期7輸出序列ak+3=ak+ak+210100111010…10100111010…序列周期

7 x3+x2+1 7

ak+3=ak+ak+1 1011100

1011…

7特征多項式x3+x2+x+1多項式周期4輸出序列

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

2 x3+1 3

ak+3=ak

101101…

3初始1012024/6/214m序列的偽隨機性隨機性:如果密鑰流是周期的，要完全做到隨機性是困難的。游程:設(shè){ai}=(a1a2a3…)為0、1序列，例如00110111，其前兩個數(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+τ}在一個周期內(nèi)對應位相同的位數(shù)與對應位不同的位數(shù)之差。當τ=0時，R(τ)=1；當τ≠0時，稱R(τ)為異相自相關(guān)函數(shù)。10100111010R(1)=R(2)=….=-1/72024/6/215①在序列一個周期內(nèi)，0與1出現(xiàn)個數(shù)相差至多為1;（0和1出現(xiàn)概率基本相同）②長為l的游程占1/2l，在等長的游程中，“0”游程和“1”游程個數(shù)相等或至多差一個。（0和1在各位置上出現(xiàn)概率基本相同）③異相自相關(guān)函數(shù)是常數(shù),與白噪聲的自相關(guān)函數(shù)(

函數(shù))相近（序列平移不能提供更多信息）PN序列可用于通信中同步序列、碼分多址(CDMA)、導航中多基站碼、雷達測距碼等。PN序列雖與白噪聲序列相似，但遠還不能滿足密碼體制要求。Golomb隨機性假設(shè)－PN序列m序列滿足Golomb的三條偽隨機假設(shè)。101001110102024/6/216滿足密碼體制的另外三個條件①周期p要足夠大，如大于1050；②序列{ai}產(chǎn)生易于高速生成；③當序列{ai}的任何部分暴露時，要分析整個序列，在計算上是不可行的

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

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

2024/6/227例令m=2,n=3，兩個驅(qū)動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中的一個，通過密碼分析的方法得到序列{ak}和{bk}。為了克服上述缺點，Pless提出了由多個J-K觸發(fā)器序列驅(qū)動的多路復合序列方案2024/6/2282.6.3Pless生成器2024/6/2292.6.4鐘控序列生成器鐘控序列最基本的模型是用一個LFSR控制另外一個LFSR的移位時鐘脈沖.易于由硬件實現(xiàn)。當LFSR1輸出1時，移位時鐘脈沖通過與門使LFSR2進行一次移位。當LFSR1輸出0時，移位時鐘脈沖無法通過與門影響LFSR2,LFSR2狀態(tài)不改變。2024/6/230前提：LFSR1和LFSR2輸出序列分別是{ak}和{bk}對應極小特征多項式分別為GF(2)上的m和n次本原多項式f1(x)和f2(x)，且m|n結(jié)論：序列{ck}周期p=(2m-1)(2n-1)線性復雜度為n(2m-1)極小特征多項式為相關(guān)結(jié)論2024/6/231例設(shè)LFSR1為3級m序列生成器，其特征多項式為f1(x)=1+x+x3。設(shè)初態(tài)為(1,1,1)，輸出序列為{ak}=1,1,1,0,1,0,0,…。又設(shè)LFSR2為3級m序列生成器，其特征多項式為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,….2024/6/232序號狀態(tài)輸出0111110111200113100031000401004010040100{ck}=1,1,1,0,0,0,0,0,bk+3bk+1bkck{bk}=1,1,1,0,0,1,0，…。2024/6/233{ck}的周期（23-1）*（23-1）=49極小特征多項式為1+x14+x21線性復雜度為3·（23-1）=21線性等價生成器如下圖f2(x)=1+x2+x3周期p=(2m-1)(2n-1)線性復雜度為n(2m-1)極小特征多項式2024/6/234有限狀態(tài)自動機具有離散輸入和輸出的一種數(shù)學模型由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時，輸出為A(2)k，而狀態(tài)轉(zhuǎn)移為sh。2024/6/235例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)12024/6/236同步流密碼的密鑰流產(chǎn)生器可看成一個有限狀態(tài)自動機。由一個輸出符號集Z、一個狀態(tài)集∑、兩個函數(shù)φ和ψ以及一個初始狀態(tài)σ0組成。2024/6/237藍牙是一種用于替代某些電子設(shè)備上使用電纜或連線的短距離無線連接技術(shù)。具有同樣藍牙接口的設(shè)備連接可以實現(xiàn)無線連接，有效連接距離達10米，一般的傳輸速度都有1M目前配置藍牙接口的電子設(shè)備卻不是很多；沒有藍牙接口的電腦可通過加裝藍牙適配器來實現(xiàn)無線連接，適配器一般都是USB接口，可以插在電腦上，使用方便。采用無線電波為載體，安全性差，信息傳輸需加密加密算法使用流密碼.流密碼的應用——藍牙Bluetooth2024/6/238藍牙流加密原理2024/6/2394個LFSR比特長度分別為25，31，33，39；長度之和是128bit特征多項式都是本原多項式設(shè)xti

為LSFRi的第t個符號2024/6/240IEEE802.11是當今無線局域網(wǎng)WLAN通用的標準，IEEE802.11安全框架中包括站點接入認證方法、數(shù)據(jù)加密WEP