現(xiàn)在密碼學(xué)第13講序列密碼與移位寄存器

1、第第6章章 序列密碼與移位寄存器主要內(nèi)容主要內(nèi)容序列密碼的基本原理移位寄存器與移位寄存器序列線性移位寄存器的表示線性移位寄存器序列的周期性線性移位寄存器的序列空間線性移位寄存器序列的極小多項式m 序列的偽隨機性B-M 算法與序列的線性復(fù)雜度線性移位寄存器的非線性組合6. 1 序列密碼的基本原理設(shè)明文、密鑰、密文都是一個(0, 1)序列，他們分別為則加密變換為解密變換為點擊查看序列密碼體制的模型6. 2 移位寄存器與移位寄存器序列一個q 元域GF(q) 上的n 階反饋移位寄存器由n 個寄存器和一個反饋函數(shù)構(gòu)成, 如圖所示. 反饋移位寄存器的工作原理： 當一個時鐘脈沖來臨時, 第i級寄存器的內(nèi)容傳

2、送給第i-1 級寄存器, i = 2, 3, , n.第1 級寄存器的內(nèi)容為反饋移位寄存器的輸出. 反饋函數(shù)f的值傳送給第n 級寄存器.t t 00 時狀態(tài)t t +1+1 時狀態(tài)反饋移位寄存器序列反饋移位寄存器的狀態(tài)序列,點此查看定義6.1),(11ntttntaaafav 反饋函數(shù)f(a1,a2,an)是n元布爾函數(shù)，即n個變元a1,a2,an可以獨立地取0和1這兩個可能的值，函數(shù)中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數(shù)值也為0或1。v 如果f(a1,a2,an)是a1,a2,an的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linear feedback shift regi

3、ster）。此時f可寫為f(a1,a2,an) =cna1cn-1a2c1an其中常數(shù)ci=0或1，是模2加法。ci=0或1可用開關(guān)的斷開和閉合來實現(xiàn).輸出序列at滿足an+t= c1an+t-1 c2an+t-2 cnat其中t為非負正整數(shù)。線性反饋移位寄存器因其實現(xiàn)簡單、速度快、有較為成熟的理論等優(yōu)點而成為構(gòu)造密鑰流生成器的最重要的部件之一。132第7時刻 0 0 1第0時刻 0 0 1第1時刻 1 0 0第2時刻 1 1 0第3時刻 1 1 1第4時刻 0 1 1第5時刻 1 0 1第6時刻 0 1 0產(chǎn)生序列為：1001110在線性反饋移位寄存器中總是假定c1,c2,cn中至少有一個不

4、為0，否則f(a1,a2,an)0，這樣的話，在n個脈沖后狀態(tài)必然是000，且這個狀態(tài)必將一直持續(xù)下去。若只有一個系數(shù)不為0，設(shè)僅有cj不為0，實際上是一種延遲裝置。一般對于n級線性反饋移位寄存器，總是假定cn=1，若若 我們說該寄存器是我們說該寄存器是退化的，退化的，否則是否則是非退化的非退化的。 。0nc 6. 3 線性移位寄存器的表示線性移位寄存器的一元多項式表示線性移位寄存器的矩陣表示點擊各項查看詳細的表示方法6. 4 線性移位寄存器序列的周期性定義6.2 設(shè) 是GF(q) 上的一個無窮序列, 如果存在正整數(shù)p, 使得對任意i 0, 都有則稱 為周期序列. 滿足該式的最小正整數(shù)稱為該序

5、列的周期, 通常記為定理6.1 設(shè) 是GF(q) 上的一個無窮序列, p是一個正整數(shù), 如果對任意i 0, 都有 成立則 的周期一定整除p, 即定義6.3設(shè) 是一個GF(q) 上的n 階線性移位寄存器序列. 如果 則稱 為GF(q) 上的n 階m序列.定理6.2一個GF(q) 上的n 階線性移位寄存器序列 一定是周期序列, 并且6. 5 移位寄存器序列空間移位寄存器序列空間v 符號說明：G(f)表示以f(x)為聯(lián)系多項式的n級線性移位寄存器序列構(gòu)成的序列空間v 定理6.3 設(shè)f(x) 是GF(q) 上的一個常數(shù)項為1 的一元n 次多項式, 則由f(x) 所確定的線性移位寄存器的序列空間G(f)

6、 是GF(q) 上的一個n 維線性空間.v 證明：只需證明G(f)中的任意兩個序列的任意線性組合也屬于G(f)即可。即證： v 特例：當q=2時，G(f)中任意兩個序列之和仍然屬于G(f)。)(,),(),(),(qGFfGbafGbfGa定理6.4 設(shè)f(x) 和h(x) 是GF(q) 上的兩個常數(shù)項為1 的一元多項式. 如果f(x)|h(x), 即f(x) 整除h(x), 則由f(x) 所確定的線性移位寄存器的序列空間G(f) 是由h(x) 所確定的線性移位寄存器的序列空間G(h) 的子空間, 即G(f) G(h).v 例1：聯(lián)結(jié)多項式為 f(x)=x4+x3+x+1=(x+1)2(x2+

7、x+1)v 線性遞推式：at=at-4+at-3+at-16. 6 線性移位寄存器序列極小多項式定義：對于一 個移位寄存器序列a，稱其聯(lián)系多項式中次數(shù)最低的多項式為a的極小多項式。定義：滿足f(x)|1-xr 的最小正整數(shù)r為f(x)的周期，記為p(f(x)，簡記為p(f)。例子：x4+x3+x2+x+1的周期為5 (x4+x3+x2+x+1)(x+1)=x5+1v 序列和周期一般地，一個移存器序列表示為： r級線性反饋移存器的最長周期: ，能達到最長周期的線性移存器序列稱為m序列。 在密碼學(xué)中，我們希望參與變換的序列周期越長越好，因此對線性反饋移存器我們更感興趣的是能達到最長周期的序列，即m

8、序列。.210iaaaaa12 r本原多項式本原多項式v 若n次多項式f(x)是不可約多項式且p(f)=qn-1，則稱f(x)是GF(q)上的本原多項式。v 以本原多項式為聯(lián)系多項式產(chǎn)生的非零序列均是m序列6. 7 m序列的偽隨機性GF(2) 上的隨機序列的一般特性1. 分布特性對任意的 都有2. 相關(guān)特性對任意的 有3. 游程特性對任意的i 0, k 1, 有 點擊查看GF(2) 上偽隨機序列的性質(zhì)6. 7 m序列的偽隨機性定義6.8 設(shè) 是GF(2) 上的一個周期為T 的序列。稱為序列 的自相關(guān)函數(shù)。6. 7 m序列的偽隨機性定理6.11 設(shè) 是GF(2) 上的一個n 階m序列, 則 在一

9、個周期內(nèi), 0 和1 的出現(xiàn)次數(shù)分別為 和 在一個周期內(nèi), 游程總數(shù)為 ; 對任意的 長為i 的0 游程和1 游程都有 個; 長為 的0 游程有一個, 長為n 的1游程有一個. 的自相關(guān)函數(shù)為自相關(guān)函數(shù)反映一個周期內(nèi)平均每位的相同程度自相關(guān)函數(shù)反映一個周期內(nèi)平均每位的相同程度m m序列的游程分布規(guī)律序列的游程分布規(guī)律性質(zhì)性質(zhì)2 2：將n級m序列的一個周期段首尾相接，其游程總數(shù)為N=2n-1；其中沒有長度大于n的游程；有1個長度為n的1游程，沒有長度為n的0游程；沒有長度為 n-1的1游程，有1個長度為n-1的0游程；有 個長度為 的1游程，有 個長度 為 的0游程。)21 (nkkkn22kn

10、22)21 (nkk習(xí) 題例、已知 是6次本原多項式，a是 生成的m序列，（1） a的周期是多少？（2） a在的一個周期內(nèi)，0、1各出現(xiàn)多少次？（3） a在的一個周期內(nèi)，游程分布如何？1)(6xxxf)(xf將LFSR的輸出序列直接作為密鑰序列，即將LFSR作為密鑰序列產(chǎn)生器，可行嗎？50年代開始用作密鑰序列，并用于軍用;60年代發(fā)現(xiàn)其是不安全的m m序列密碼的破譯序列密碼的破譯設(shè)m序列的LFSR的狀態(tài)為則，其下一狀態(tài)為其中，寫成矩陣形式：其中，依據(jù)LFSR的結(jié)構(gòu)，可定義iinninninacacaca1211. ? (i=1,2,)2mod1iiMSSnccccM.0.1000.010321

11、TininiiaaaS),.,(111TininiiaaaS),.,(12假設(shè)假設(shè)敵手知道一段敵手知道一段長為長為2n2n的明的明- -密文對密文對，即已知，即已知于是，于是，可求出一段長為可求出一段長為2n2n的密鑰序列的密鑰序列z z 其中其中nnyyyymmmm221221.,.iiiiiinymzmmzzzzz)(.221m m序列密碼的破譯序列密碼的破譯m m序列密碼的破譯序列密碼的破譯v由此，可推出線性反饋移位寄存器連續(xù)的n+1個狀態(tài)：11 21 222 312 311122122nnnnnnnnnnnSz zzaaaSz zza aaSzzza aa記為記為記為構(gòu)造矩陣構(gòu)造矩陣根

12、據(jù)根據(jù) 可推出：可推出：若若X X可逆，則可逆，則TnnSSSY),.,(12TnnSSSX),.,(112mod1iiMSS2modMXY 2mod1YXMm m序列密碼的破譯序列密碼的破譯m m序列密碼的破譯序列密碼的破譯v對于n級LFSR，只需要知道長為2n的明-密文對(mi,yi)，就可求出矩陣M，便確定出聯(lián)系多項式p(x)，從而可完全確定LFSR的結(jié)構(gòu) 求出n位的密鑰序列ai 12211432321321232125431432.0.1000.010.nnnnnnnnnnnnnaaaaaaaaaaaaccccaaaaaaaaaaaa122114323213212321.).().(n

13、nnnnnnnnnnaaaaaaaaaaaaccccaaaaxy例：例： 設(shè)敵手得到密文串設(shè)敵手得到密文串101101011110010101101011110010和相應(yīng)的明文串和相應(yīng)的明文串011001111111001011001111111001，因此可計算出相應(yīng)的密鑰流為，因此可計算出相應(yīng)的密鑰流為110100100011010010000101101011。進一步假定敵手還知道密鑰序列是使用。進一步假定敵手還知道密鑰序列是使用5 5級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前的前1010個比特和明文串中的前個比特和明文

14、串中的前1010個比特建立如下方程個比特建立如下方程例題例題987658765476543654325432154321109876)()(aaaaaaaaaaaaaaaaaaaaaaaaacccccaaaaa點擊此處返回定義6.1 如果一個GF(q) 上的n 階反饋移位寄存器的反饋函數(shù)形如其中 則稱其為線性反饋移位寄存器; 否則, 稱其為非線性反饋移位寄存器.顯然, 一個n 階線性移位寄存器序列滿足遞推關(guān)系式點擊此處返回點擊此處返回設(shè)一個GF(q) 上的n 階線性移位寄存器的反饋函數(shù)為其中，該線性移位寄存器的輸出序列滿足遞推關(guān)系式即令D 表示線性移位寄存器序列的延遲算子, 即令則用未定元x 取代D, 我們稱一元多項式為線性移位寄存器的聯(lián)系多項式.v 線性遞推式（一元多項式）： at+n=c1at+n-1+c2at+n-2+cnat ,t=0v 聯(lián)系多項式(令ai=xn+t-i): f(x)=1+c1x+c2x2+cnxn點擊此處返回實例實例（畫出移存器的邏輯框圖，寫出相應(yīng)的線性（畫出移存器的邏輯框圖，寫出相應(yīng)的線性 遞推式）遞推式）多項式多項式答案：答案：線性遞推式： at=at-4+at-3+at-2432( )1f xxxxx1x2x3x4點擊此處返回則其聯(lián)系多項式