資源描述:
《現(xiàn)代密碼學(xué)第2章》由會員上傳分享,免費在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第2章流密碼2.1流密碼的基本概念2.2線性反饋移位寄存器2.3線性移位寄存器的一元多項式表示2.4m序列的偽隨機性2.5m序列密碼的破譯2.6非線性序列習(xí)題流密碼可以認為是起源于20世紀20年代的Vernam密碼體制。當(dāng)Vernam密碼中的密鑰序列是隨機的(0,1)序列時,它就是“一次一密”密碼體制。Shannon已經(jīng)證明了“一次一密”密碼體制在理論上是不可破譯的。這給予序列密碼技術(shù)的研究和應(yīng)用于強大的支持。由于隨機的密鑰的產(chǎn)生、存儲和分配等方面存在一定的困難,Vernam密碼在當(dāng)時并沒有得到廣泛的應(yīng)用。隨著微電子技術(shù)和數(shù)
2、學(xué)理論的發(fā)展與完善,基于偽隨機序列的流密碼得到了長足的發(fā)展和2.1流密碼的基本概念應(yīng)用,在流密碼中,加密和解密所用的密鑰序列都是偽隨機序列。偽隨機序列的產(chǎn)生比較容易并且有比較成熟的數(shù)學(xué)理論工具。目前,流密碼是世界各國的軍事和外交等領(lǐng)域中使用的主要密碼體制之一。流密碼的基本思想是利用密鑰k產(chǎn)生一個密鑰流z=z0z1…,并使用如下規(guī)則對明文串x=x0x1x2…加密:y=y0y1y2…=Ez0(x0)Ez1(x1)Ez2(x2)…。密鑰流由密鑰流發(fā)生器f產(chǎn)生:zi=f(k,σi),這里σi是加密器中的記憶元件(存儲器)在時刻i的狀
3、態(tài),f是由密鑰k和σi產(chǎn)生的函數(shù)。分組密碼與流密碼的區(qū)別就在于有無記憶性(如圖2.1)。流密碼的滾動密鑰z0=f(k,σ0)由函數(shù)f、密鑰k和指定的初態(tài)σ0完全確定。此后,由于輸入加密器的明文可能影響加密器中內(nèi)部記憶元件的存儲狀態(tài),因而σi(i>0)可能依賴于k,σ0,x0,x1,…,xi-1等參數(shù)。圖2.1分組密碼和流密碼的比較根據(jù)加密器中記憶元件的存儲狀態(tài)σi是否依賴于輸入的明文字符,流密碼可進一步分成同步和自同步兩種。σi獨立于明文字符的叫做同步流密碼,否則叫做自同步流密碼。由于自同步流密碼的密鑰流的產(chǎn)生與明文有關(guān),因
4、而較難從理論上進行分析。目前大多數(shù)研究成果都是關(guān)于同步流密碼的。在同步流密碼中,由于zi=f(k,σi)與明文字符無關(guān),因而此時密文字符yi=Ezi(xi)也不依賴于此前的明文字符。因此,可將同步流密碼的加密器分成密鑰流產(chǎn)生器和加密變換器兩個部分。如果與上述加密變換對應(yīng)的解密變換為xi=Dzi(yi),則可給出同步流密碼體制的模型如圖2.2所示。2.1.1同步流密碼圖2.2同步流密碼體制模型同步流密碼的加密變換Ezi可以有多種選擇,只要保證變換是可逆的即可。實際使用的數(shù)字保密通信系統(tǒng)一般都是二元系統(tǒng),因而在有限域CF(2)上
5、討論的二元加法流密碼(如圖2.3)是目前最為常用的流密碼體制,其加密變換可表示為yi=zixi。圖2.3加法流密碼體制模型一次一密密碼是加法流密碼的原型。事實上,如果zi=ki(即密鑰用作滾動密鑰流),則加法流密碼就退化成一次一密密碼。實際使用中,密碼設(shè)計者的最大愿望是設(shè)計出一個滾動密鑰生成器,使得密鑰經(jīng)其擴展成的密鑰流序列具有如下性質(zhì):極大的周期、良好的統(tǒng)計特性、抗線性分析、抗統(tǒng)計分析。有限狀態(tài)自動機是具有離散輸入和輸出(輸入集和輸出集均有限)的一種數(shù)學(xué)模型,由以下3部分組成:①有限狀態(tài)集S={si
6、i=1,2,…,l}。
7、②有限輸入字符集A1={A(1)j
8、j=1,2,…,m}和有限輸出字符集A2={A(2)k
9、k=1,2,…,n}。③轉(zhuǎ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)轉(zhuǎn)移為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},轉(zhuǎn)移函數(shù)由表2.1給出。(見16頁表2.1)有限狀態(tài)自動機可用有向圖表示,稱為轉(zhuǎn)移圖。轉(zhuǎn)移圖的頂點對應(yīng)于自動機的狀態(tài)
10、,若狀態(tài)si在輸入A(1)i時轉(zhuǎn)為狀態(tài)sj,且輸出一字符A(2)j,則在轉(zhuǎn)移圖中,從狀態(tài)si到狀態(tài)sj有一條標有(A(1)i,A(2)j)的弧線,見圖2.4。圖2.4有限狀態(tài)自動機的轉(zhuǎn)移圖例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)1同步流密碼的關(guān)鍵是密鑰流產(chǎn)生器。一般可將其看成一個參數(shù)為k的有限狀態(tài)自動機,由一個輸出符號集Z、一個狀態(tài)集∑、兩個函數(shù)φ和ψ以
11、及一個初始狀態(tài)σ0組成(如圖2.5)。狀態(tài)轉(zhuǎn)移函數(shù)φ:σi→σi+1,將當(dāng)前狀態(tài)σi變?yōu)橐粋€新狀態(tài)σi+1,輸出函數(shù)ψ:σi→zi,當(dāng)前狀態(tài)σi變?yōu)檩敵龇柤械囊粋€元素zi。這種密鑰流生成器設(shè)計的關(guān)鍵在于找出適當(dāng)?shù)臓顟B(tài)轉(zhuǎn)移函數(shù)φ和輸出函數(shù)ψ,使得輸出序列z滿足密鑰流序列z應(yīng)滿足的幾個條件