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

第6章序列密碼與移位寄存器主要內(nèi)容序列密碼的基本原理移位寄存器與移位寄存器序列線性移位寄存器的表示線性移位寄存器序列的周期性線性移位寄存器的序列空間線性移位寄存器序列的極小多項(xiàng)式m序列的偽隨機(jī)性B-M算法與序列的線性復(fù)雜度線性移位寄存器的非線性組合6.1

序列密碼的基本原理設(shè)明文、密鑰、密文都是一個(gè)(0,1)序列，他們分別為則加密變換為解密變換為點(diǎn)擊查看序列密碼體制的模型6.2

移位寄存器與移位寄存器序列一個(gè)q元域GF(q)上的n階反饋移位寄存器由n個(gè)寄存器和一個(gè)反饋函數(shù)構(gòu)成,如圖所示.反饋移位寄存器的工作原理：

當(dāng)一個(gè)時(shí)鐘脈沖來(lái)臨時(shí),第i級(jí)寄存器的內(nèi)容傳送給第i-1級(jí)寄存器,i=2,3,···,n.第1級(jí)寄存器的內(nèi)容為反饋移位寄存器的輸出.反饋函數(shù)f的值傳送給第n級(jí)寄存器.t≥0

時(shí)狀態(tài)t+1

時(shí)狀態(tài)反饋移位寄存器序列反饋移位寄存器的狀態(tài)序列,點(diǎn)此查看定義6.1反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)，即n個(gè)變?cè)猘1,a2,…,an可以獨(dú)立地取0和1這兩個(gè)可能的值，函數(shù)中的運(yùn)算有邏輯與、邏輯或、邏輯補(bǔ)等運(yùn)算，最后的函數(shù)值也為0或1。如果f(a1,a2,…,an)是a1,a2,…,an的線性函數(shù)，則稱之為線性反饋移位寄存器LFSR（linearfeedbackshiftregister）。此時(shí)f可寫(xiě)為f(a1,a2,…,an)=cna1

cn-1a2…c1an其中常數(shù)ci=0或1，是模2加法。ci=0或1可用開(kāi)關(guān)的斷開(kāi)和閉合來(lái)實(shí)現(xiàn).輸出序列{at}滿足an+t=c1an+t-1

c2an+t-2…cnat其中t為非負(fù)正整數(shù)。 線性反饋移位寄存器因其實(shí)現(xiàn)簡(jiǎn)單、速度快、有較為成熟的理論等優(yōu)點(diǎn)而成為構(gòu)造密鑰流生成器的最重要的部件之一。132第7時(shí)刻001第0時(shí)刻001第1時(shí)刻100第2時(shí)刻110第3時(shí)刻111第4時(shí)刻011第5時(shí)刻101第6時(shí)刻010產(chǎn)生序列為：1001110……在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一個(gè)不為0，否則f(a1,a2,…,an)≡0，這樣的話，在n個(gè)脈沖后狀態(tài)必然是00…0，且這個(gè)狀態(tài)必將一直持續(xù)下去。 若只有一個(gè)系數(shù)不為0，設(shè)僅有cj不為0，實(shí)際上是一種延遲裝置。 一般對(duì)于n級(jí)線性反饋移位寄存器，總是假定cn=1，若我們說(shuō)該寄存器是退化的，否則是非退化的。。6.3

線性移位寄存器的表示線性移位寄存器的一元多項(xiàng)式表示線性移位寄存器的矩陣表示點(diǎn)擊各項(xiàng)查看詳細(xì)的表示方法6.4

線性移位寄存器序列的周期性定義6.2

設(shè)是GF(q)上的一個(gè)無(wú)窮序列,如果存在正整數(shù)p,使得對(duì)任意i≥0,都有則稱為周期序列.滿足該式的最小正整數(shù)稱為該序列的周期,通常記為定理6.1

設(shè)是GF(q)上的一個(gè)無(wú)窮序列,p是一個(gè)正整數(shù),如果對(duì)任意i≥0,都有成立則的周期一定整除p,即定義6.3設(shè)

是一個(gè)GF(q)上的n階線性移位寄存器序列.如果則稱為GF(q)上的n階m序列.定理6.2一個(gè)GF(q)上的n階線性移位寄存器序列一定是周期序列,并且6.5

移位寄存器序列空間符號(hào)說(shuō)明：G(f)表示以f(x)為聯(lián)系多項(xiàng)式的n級(jí)線性移位寄存器序列構(gòu)成的序列空間定理6.3

設(shè)f(x)是GF(q)上的一個(gè)常數(shù)項(xiàng)為1的一元n次多項(xiàng)式,則由f(x)所確定的線性移位寄存器的序列空間G(f)是GF(q)上的一個(gè)n維線性空間.證明：只需證明G(f)中的任意兩個(gè)序列的任意線性組合也屬于G(f)即可。即證：

特例：當(dāng)q=2時(shí)，G(f)中任意兩個(gè)序列之和仍然屬于G(f)。定理6.4

設(shè)f(x)和h(x)是GF(q)上的兩個(gè)常數(shù)項(xiàng)為1的一元多項(xiàng)式.如果f(x)|h(x),即f(x)整除h(x),則由f(x)所確定的線性移位寄存器的序列空間G(f)是由h(x)所確定的線性移位寄存器的序列空間G(h)的子空間,即G(f)?

G(h).例1：聯(lián)結(jié)多項(xiàng)式為

f(x)=x4+x3+x+1=(x+1)2(x2+x+1)線性遞推式：at=at-4+at-3+at-16.6

線性移位寄存器序列極小多項(xiàng)式定義：對(duì)于一個(gè)移位寄存器序列a，稱其聯(lián)系多項(xiàng)式中次數(shù)最低的多項(xiàng)式為a的極小多項(xiàng)式。定義：滿足f(x)|1-xr

的最小正整數(shù)r為f(x)的周期，記為p(f(x))，簡(jiǎn)記為p(f)。例子：x4+x3+x2+x+1的周期為5

(x4+x3+x2+x+1)(x+1)=x5+1序列和周期一般地，一個(gè)移存器序列表示為：r級(jí)線性反饋移存器的最長(zhǎng)周期:，能達(dá)到最長(zhǎng)周期的線性移存器序列稱為m序列。在密碼學(xué)中，我們希望參與變換的序列周期越長(zhǎng)越好，因此對(duì)線性反饋移存器我們更感興趣的是能達(dá)到最長(zhǎng)周期的序列，即m序列。本原多項(xiàng)式若n次多項(xiàng)式f(x)是不可約多項(xiàng)式且p(f)=qn-1，則稱f(x)是GF(q)上的本原多項(xiàng)式。以本原多項(xiàng)式為聯(lián)系多項(xiàng)式產(chǎn)生的非零序列均是m序列6.7

m序列的偽隨機(jī)性GF(2)上的隨機(jī)序列的一般特性1.分布特性對(duì)任意的

都有2.相關(guān)特性對(duì)任意的有3.游程特性對(duì)任意的i≥0,k≥1,有點(diǎn)擊查看GF(2)

上偽隨機(jī)序列的性質(zhì)6.7

m序列的偽隨機(jī)性定義6.8

設(shè)

是GF(2)上的一個(gè)周期為T的序列。稱為序列

的自相關(guān)函數(shù)。6.7

m序列的偽隨機(jī)性定理6.11

設(shè)是GF(2)上的一個(gè)n階m序列,則①在一個(gè)周期內(nèi),0和1的出現(xiàn)次數(shù)分別為和②在一個(gè)周期內(nèi),游程總數(shù)為;對(duì)任意的長(zhǎng)為i的0游程和1游程都有個(gè);長(zhǎng)為的0游程有一個(gè),長(zhǎng)為n的1游程有一個(gè).③的自相關(guān)函數(shù)為自相關(guān)函數(shù)反映一個(gè)周期內(nèi)平均每位的相同程度m序列的游程分布規(guī)律性質(zhì)2：將n級(jí)m序列的一個(gè)周期段首尾相接，其游程總數(shù)為N=2n-1；其中沒(méi)有長(zhǎng)度大于n的游程；有1個(gè)長(zhǎng)度為n的1游程，沒(méi)有長(zhǎng)度為n的0游程；沒(méi)有長(zhǎng)度為n-1的1游程，有1個(gè)長(zhǎng)度為n-1的0游程；有個(gè)長(zhǎng)度為的1游程，有個(gè)長(zhǎng)度為的0游程。習(xí)題例、已知是6次本原多項(xiàng)式，a是生成的m序列，（1）a的周期是多少？（2）a在的一個(gè)周期內(nèi)，0、1各出現(xiàn)多少次？（3）a在的一個(gè)周期內(nèi)，游程分布如何？將LFSR的輸出序列直接作為密鑰序列，即將LFSR作為密鑰序列產(chǎn)生器，可行嗎？50年代開(kāi)始用作密鑰序列，并用于軍用;60年代發(fā)現(xiàn)其是不安全的m序列密碼的破譯設(shè)m序列的LFSR的狀態(tài)為則，其下一狀態(tài)為其中，寫(xiě)成矩陣形式：其中，依據(jù)LFSR的結(jié)構(gòu)，可定義

(i=1,2,…)假設(shè)敵手知道一段長(zhǎng)為2n的明-密文對(duì)，即已知于是，可求出一段長(zhǎng)為2n的密鑰序列z其中m序列密碼的破譯m序列密碼的破譯由此，可推出線性反饋移位寄存器連續(xù)的n+1個(gè)狀態(tài)：構(gòu)造矩陣根據(jù)可推出：若X可逆，則m序列密碼的破譯m序列密碼的破譯對(duì)于n級(jí)LFSR，只需要知道長(zhǎng)為2n的明-密文對(duì)(mi,yi)，就可求出矩陣M，便確定出聯(lián)系多項(xiàng)式p(x)，從而可完全確定LFSR的結(jié)構(gòu)求出n位的密鑰序列ai

xy例：設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計(jì)算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰序列是使用5級(jí)線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個(gè)比特和明文串中的前10個(gè)比特建立如下方程例題ThankYou!點(diǎn)擊此處返回定義6.1

如果一個(gè)GF(q)上的n階反饋移位寄存器的反饋函數(shù)形如其中則稱其為線性反饋移位寄存器;否則,稱其為非線性反饋移位寄存器.顯然,一個(gè)n階線性移位寄存器序列滿足遞推關(guān)系式點(diǎn)擊此處返回點(diǎn)擊此處返回設(shè)一個(gè)GF(q)上的n階線性移位寄存器的反饋函數(shù)為其中，該線性移位寄存器的輸出序列滿足遞推關(guān)系式即令D表示線性移位寄存器序列的延遲算子,即令則用未定元x取代D,我們稱一元多項(xiàng)式為線性移位寄存器的聯(lián)系多項(xiàng)式.線性遞推式（一元多項(xiàng)式）：

at+n=c1at+n-1+c2at+n-2+…+cnat,t>=0聯(lián)系多項(xiàng)式(令ai=xn+t-i):

f(x)=1+c1x+c2x2+…+cnxn點(diǎn)擊此處返回實(shí)例（畫(huà)出移存器的邏輯框圖，寫(xiě)出相應(yīng)的線性遞推式）多項(xiàng)式答案：線性遞推式：at=at-4+at-3+at-2x1x2x3x4