資源描述:
《現(xiàn)代密碼學 第2章.ppt》由會員上傳分享,免費在線閱讀,更多相關內容在PPT專區(qū)-天天文庫。
1、第2章流密碼2.1流密碼的基本概念2.2線性反饋移位寄存器2.3線性移位寄存器的一元多項式表示2.4m序列的偽隨機性2.5m序列密碼的破譯2.6非線性序列流密碼的基本思想是利用密鑰k產生一個密鑰流z=z0z1…,并使用如下規(guī)則對明文串x=x0x1x2…加密:y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密鑰流由密鑰流發(fā)生器f產生:zi=f(k,σi),這里σi是加密器中的記憶元件(存儲器)在時刻i的狀態(tài),f是由密鑰k和σi產生的函數(shù)。流密碼的滾動密鑰z0=f(k,σ0)由函數(shù)f、密鑰k和指定的初態(tài)σ0完全確定。2.1流密碼的基本概念分組密碼與流密碼的區(qū)別就在于有
2、無記憶性。圖2.1分組密碼和流密碼的比較2.1流密碼的基本概念根據加密器中記憶元件的存儲狀態(tài)σi是否依賴于輸入的明文字符,流密碼可進一步分成同步和自同步兩種。σi獨立于明文字符的叫做同步流密碼,否則叫做自同步流密碼。在同步流密碼中,由于zi=f(k,σi)與明文字符無關,因而此時密文字符yi=Ezi(xi)也不依賴于此前的明文字符。因此,可將同步流密碼的加密器分成密鑰流產生器和加密變換器兩個部分。2.1.1同步流密碼圖2.2同步流密碼體制模型2.1.1同步流密碼常用的流密碼:在有限域CF(2)上討論的二元加法流密碼,其加密變換可表示為yi=zixi。2.1.1同步流密碼圖2.3加法
3、流密碼體制模型有限狀態(tài)自動機是具有離散輸入和輸出(輸入集和輸出集均有限)的一種數(shù)學模型,由以下3部分組成:①有限狀態(tài)集S={si
4、i=1,2,…,l}。②有限輸入字符集A1={A(1)j
5、j=1,2,…,m}和有限輸出字符集A2={A(2)k
6、k=1,2,…,n}。③轉移函數(shù)A(2)k=f1(si,A(1)j),sh=f2(si,A(1)j)即在狀態(tài)為si,輸入為A(1)j時,輸出為A(2)k,而狀態(tài)轉移為sh。2.1.2有限狀態(tài)自動機例2.1S={s1,s2,s3},A1={A(1)1,A(1)2,A(1)3},A2={A(2)1,A(2)2,A(2)3},轉移函數(shù)由表2.1給出
7、。2.1.2有限狀態(tài)自動機A(1)1A(1)2A(1)3s1A(2)1A(2)3A(2)2s2A(2)2A(2)1A(2)3s3A(2)3A(2)2A(2)1A(1)1A(1)2A(1)3s1s2s1s3s2s3s2s1s3s1s3s2有限狀態(tài)自動機可用有向圖表示,稱為轉移圖。轉移圖的頂點對應于自動機的狀態(tài),若狀態(tài)si在輸入A(1)i時轉為狀態(tài)sj,且輸出一字符A(2)j,則在轉移圖中,從狀態(tài)si到狀態(tài)sj有一條標有(A(1)i,A(2)j)的弧線,見圖2.4。2.1.2有限狀態(tài)自動機圖2.4有限狀態(tài)自動機的轉移圖2.1.2有限狀態(tài)自動機例2.1中,若輸入序列為A(1)1A(1)2
8、A(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)12.1.2有限狀態(tài)自動機同步流密碼的關鍵是密鑰流產生器。一般可將其看成一個參數(shù)為k的有限狀態(tài)自動機,由一個輸出符號集Z、一個狀態(tài)集∑、兩個函數(shù)φ和ψ以及一個初始狀態(tài)σ0組成(如圖2.5)。2.1.3密鑰流產生器圖2.5作為有限狀態(tài)自動機的密鑰流生成器狀態(tài)轉移函數(shù)φ:σi→σi+1,將當前狀態(tài)σi變?yōu)橐粋€新狀態(tài)σi+1,輸出函數(shù)ψ:σi→zi,當前狀態(tài)σi變?yōu)檩敵龇柤械囊粋€元素zi。密鑰流生成器設計的關鍵:找出
9、適當?shù)臓顟B(tài)轉移函數(shù)φ和輸出函數(shù)ψ,使得輸出序列z滿足密鑰流序列z應滿足的幾個條件,并且要求在設備上是節(jié)省的和容易實現(xiàn)的。為了實現(xiàn)這一目標,必須采用非線性函數(shù)。2.1.3密鑰流產生器驅動部分控制生成器的狀態(tài)轉移,并為非線性組合部分提供統(tǒng)計性能好的序列;而非線性組合部分要利用這些序列組合出滿足要求的密鑰流序列。圖2.6密鑰流生成器的分解2.1.3密鑰流產生器目前最為流行和實用的密鑰流產生器如圖2.7所示,其驅動部分是一個或多個線性反饋移位寄存器。圖2.7常見的兩種密鑰流產生器2.1.3密鑰流產生器移位寄存器是流密碼產生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二
10、元存儲器與一個反饋函數(shù)f(a1,a2,…,an)組成,如圖2.8所示。2.2線性反饋移位寄存器圖2.8GF(2)上的n級反饋移位寄存器例2.2圖2.9是一個3級反饋移位寄存器,其初始狀態(tài)為(a1,a2,a3)=(1,0,1),輸出可由表2.2求出。圖2.9一個3級反饋移位寄存器2.2線性反饋移位寄存器表2.2一個3級反饋移位寄存器的狀態(tài)和輸出狀態(tài)(a1,a2,a3)輸出1011101110111011101011102.2線性反饋移位寄存器即輸出序列為10111011