第7講 序列密碼體制

應(yīng)用密碼學(xué)張仕斌萬武南張金全孫宣東編著西安電子科技大學(xué)出版社二00九年十二月2023/2/51第4章序列密碼體制2023/2/52知識(shí)點(diǎn)：

序列密碼的概念

線性反饋移位寄存器

序列和周期

非線性序列簡(jiǎn)介

常用序列密碼2023/2/53起源-一次一密無條件安全：在理論上是不可破譯的但：要求密鑰與明文具有相同長(zhǎng)度、且不可重復(fù)使用，增加了密鑰分配與管理的困難對(duì)策：用一個(gè)較小的密鑰來偽隨機(jī)地生成密鑰流。①人們?cè)噲D以序列密碼方式仿效“一次一密”密碼②序列密碼的理論已經(jīng)比較成熟，而且具有工程實(shí)現(xiàn)容易、效率高等特點(diǎn)③采用一個(gè)短的種子密鑰來控制某種算法產(chǎn)生出長(zhǎng)的密鑰序列，供加、解密使用，而短的種子密鑰的存儲(chǔ)、分配都較容易2023/2/54分組密碼使用的是一個(gè)不隨時(shí)間變化的固定變換，具有擴(kuò)散性好、插入敏感等優(yōu)點(diǎn)；其缺點(diǎn)是：加密處理速度慢。序列密碼vs.分組密碼分組密碼以一定大小的分組作為每次處理的基本單元，而序列密碼則以一個(gè)元素（如一個(gè)字母或一個(gè)比特）作為基本的處理單元。序列密碼使用一個(gè)隨時(shí)間變化的加密變換，具有轉(zhuǎn)換速度快、低錯(cuò)誤傳播的優(yōu)點(diǎn)，硬件實(shí)現(xiàn)電路更簡(jiǎn)單；其缺點(diǎn)是：低擴(kuò)散（意味著混亂不夠）、插入及修改的不敏感性。2023/2/554.1序列密碼的概念序列密碼算法將明文逐位轉(zhuǎn)換成密文，如下圖所示。密鑰流發(fā)生器（也稱為滾動(dòng)密鑰發(fā)生器）輸出一系列比特流：K1，K2，K3，……Ki

。密鑰流（也稱為滾動(dòng)密鑰）跟明文比特流（m1，m2，m3，……mi

）

，進(jìn)行異或運(yùn)算產(chǎn)生密文比特流。

加密：

Ci=mi⊕Ki

在解密端，密文流與完全相同的密鑰流異或運(yùn)算恢復(fù)出明文流。

解密：mi=Ci⊕Ki顯然，mi⊕Ki⊕Ki=mi2023/2/56事實(shí)上，序列密碼算法其安全性依賴于簡(jiǎn)單的異或運(yùn)算和密鑰序列。密鑰流發(fā)生器生成的看似隨機(jī)的密鑰流實(shí)際上是確定的，在解密的時(shí)候能很好的將其再現(xiàn)。密鑰流發(fā)生器輸出的密鑰越接近隨機(jī)，對(duì)密碼分析者來說就越困難。

如果密鑰流發(fā)生器每次都生成同樣的密鑰流的話，對(duì)攻擊來說，破譯該算法就容易了。

假的Alice得到一份密文和相應(yīng)的明文，她就可以將兩者異或恢復(fù)出密鑰流?；蛘?，如果她有兩個(gè)用同一個(gè)密鑰流加密的密文，她就可以讓兩者異或得到兩個(gè)明文互相異或而成的消息。這是很容易破譯的，接著她就可以用明文跟密文異或得出密鑰流。現(xiàn)在，無論她再攔截到什么密文消息，她都可以用她所擁有的密鑰流進(jìn)行解密。另外，她還可以解密，并閱讀以前截獲到的消息。一旦Alice得到一明文/密文對(duì)，她就可以讀懂任何東西了。2023/2/57這就是為什么所有序列密碼需要隨機(jī)密鑰的原因。密鑰流發(fā)生器的輸出是密鑰的函數(shù)。

這樣，Alice有一個(gè)明文/密文對(duì)，但她只能讀到用特定密鑰加密的消息。

更換密鑰，攻擊者就不得不重新分析。

流密碼是將明文劃分成字符(如單個(gè)字母)，或其編碼的基本單元(如0,1數(shù)字)，字符分別與密鑰流作用進(jìn)行加密，解密時(shí)以同步產(chǎn)生的同樣的密鑰流實(shí)現(xiàn)。流密碼強(qiáng)度完全依賴于密鑰序列的隨機(jī)性(Randomness)和不可預(yù)測(cè)性(Unpredictability)。

核心問題是密鑰流生成器的設(shè)計(jì)。保持收發(fā)兩端密鑰流的精確同步是實(shí)現(xiàn)可靠解密的關(guān)鍵技術(shù)。2023/2/58-序列密碼的分類:1.自同步序列密碼

自同步序列密碼就是密鑰流的每一位是前面固定數(shù)量密文位的函數(shù)，下圖和下頁(yè)圖描述了其工作原理。其中，內(nèi)部狀態(tài)是前面n比特密文的函數(shù)。該算法的密碼復(fù)雜性在于輸出函數(shù)，它收到內(nèi)部狀態(tài)后生成密鑰序列位。2023/2/59自同步流密碼SSSC(Self-SynchronousStreamCipher)

內(nèi)部狀態(tài)i依賴于(kI,i-1,mi)，使密文ci不僅與當(dāng)前輸入mi有關(guān)，而且ki對(duì)i的關(guān)系還與以前的輸入m1,m2,…,mi-1有關(guān)。一般在有限的n級(jí)存儲(chǔ)下將與mi-1,…,mi-n有關(guān)。2023/2/510自同步序列密碼的特點(diǎn)自同步

自同步的實(shí)現(xiàn)依賴于密文被刪除或插入，因?yàn)榻饷苤蝗Q于先前固定數(shù)量的密文字符。自同步序列密碼在同步丟失后能夠自動(dòng)重新建立正確的解密，只有固定數(shù)量的明文字符不能被恢復(fù)。有限的錯(cuò)誤傳播因?yàn)樽酝叫蛄忻艽a的狀態(tài)取決于n個(gè)已有的密文字符，如果一個(gè)密文字符在傳輸過程中被修改，則解密時(shí)最多影響到后續(xù)n個(gè)字符的解密恢復(fù)，會(huì)發(fā)生有限的錯(cuò)誤傳播。-（由于具有自同步能力，)強(qiáng)化了其抗統(tǒng)計(jì)分析的能力2023/2/5112．同步序列密碼

同步流密碼SSC(SynchronousStreamCipher)：

內(nèi)部狀態(tài)i與明文消息無關(guān)，密鑰流將獨(dú)立于明文。因此，對(duì)于明文而言，這類加密變換是無記憶的，但它是時(shí)變的；只有保持兩端精確同步才能正常工作；無差錯(cuò)傳播(ErrorPropagation)。2023/2/512同步序列密碼的特點(diǎn)-在保密通信過程中，通信的雙方必須保持精確的同步

對(duì)于同步序列密碼，只要通信雙方的密鑰序列產(chǎn)生器具有相同的種子密鑰和相同的初始狀態(tài)，就能產(chǎn)生相同的密鑰序列。-對(duì)失步的敏感性

-收方的解密將一直錯(cuò)誤，直到重新同步為止

-容易檢測(cè)插入、刪除、重播等主動(dòng)攻擊無錯(cuò)誤傳播當(dāng)通信中某些密文字符產(chǎn)生了錯(cuò)誤（如0變成1，或1變成0），只影響相應(yīng)字符的解密，不影響其它字符。

對(duì)主動(dòng)攻擊時(shí)異常敏感而有利于檢測(cè)。

2023/2/513-序列密碼-密鑰流序列應(yīng)具備的性質(zhì)密碼設(shè)計(jì)者的最大愿望是設(shè)計(jì)出一個(gè)滾動(dòng)密鑰生成器，使得密鑰經(jīng)其擴(kuò)展成的密鑰流序列具有如下性質(zhì)：

-極大的周期；

-良好的統(tǒng)計(jì)特性；

-抗線性分析；

-抗統(tǒng)計(jì)分析。實(shí)際上,序列密碼不可能做到“一次一密”但若密鑰流生成器生成的密鑰周期足夠長(zhǎng)，且隨機(jī)性好，其安全強(qiáng)度可以得到保證！因此，序列密碼的設(shè)計(jì)核心在于密鑰流生成器的設(shè)計(jì)，序列密碼的安全強(qiáng)度取決于密鑰流生成器生成的密鑰周期、復(fù)雜度、隨機(jī)（偽隨機(jī)）特性等。2023/2/514常見的密鑰序列產(chǎn)生器目前，最為流行和實(shí)用的密鑰流產(chǎn)生器大多基于線性反饋移位寄存器。如下圖所示，其驅(qū)動(dòng)部分是一個(gè)或多個(gè)線性反饋移位寄存器。LFSR………FLFSR1LFSR2LFSRn……FFF2023/2/515預(yù)備知識(shí)：布爾函數(shù)一般地，我們把n元布爾函數(shù)定義為如下映射：記為，其中

布爾函數(shù)是研究數(shù)字邏輯電路的重要數(shù)學(xué)工具，在序列密碼、分組密碼和公鑰密碼中，布爾函數(shù)都有重要的應(yīng)用。特別在序列密碼中，布爾函數(shù)是重要的數(shù)學(xué)工具之一。2023/2/5161、真值表

小項(xiàng)表示實(shí)際上是布爾代數(shù)表達(dá)方式，即邏輯表達(dá)方式，此方法常用于布爾函數(shù)的設(shè)計(jì)實(shí)現(xiàn)。2、小項(xiàng)表示上例的小項(xiàng)表示為3、多項(xiàng)式表示因?yàn)?，將小?xiàng)表示中的邏輯非的形式換掉即得多項(xiàng)式表示。2023/2/5174.2線性反饋移位寄存器

-定義：反饋移存器的反饋邏輯電路可用一布爾函數(shù)f(a1,a2,…,an)來表示，若對(duì)應(yīng)的布爾函數(shù)是線性函數(shù)，則稱該反饋移存器為線性反饋移存器LFSR(linearfeedbackshiftregister)，否則稱為非線性反饋移存器。ajaj-2aj-3aj-1圖1線性反饋移位寄存器ajaj-2aj-3圖2非線性反饋移位寄存器2023/2/518此時(shí)LFSR函數(shù)可寫為：f(a1,a2,…,an)=cna1

cn-1a2…c1an上圖中，常數(shù)ci=0或1，是模2加法。ci=0或1可用開關(guān)的斷開和閉合來實(shí)現(xiàn)，這樣的線性函數(shù)共有2n個(gè)。輸出序列{at}滿足：a1+t=cnat+1cn-1at+2…c1an+t

其中，t為非負(fù)正整數(shù)。如下圖所示，是一個(gè)LFSR:（1）線性反饋移位寄存器因其實(shí)現(xiàn)簡(jiǎn)單、速度快、有較為成熟的理論等優(yōu)點(diǎn)而成為構(gòu)造密鑰流生成器的最重要的部件之一，也非常適合用硬件實(shí)現(xiàn)；（2）可以產(chǎn)生大周期序列；（3）可以產(chǎn)生具有良好統(tǒng)計(jì)性質(zhì)的序列；（4）易于利用代數(shù)方法對(duì)其進(jìn)行分析。n級(jí)線性移存器的線性遞推式表示-優(yōu)勢(shì)：2023/2/519-工作原理(如下圖)假設(shè)在j時(shí)刻其內(nèi)部狀態(tài)為：在j+1時(shí)刻其內(nèi)部狀態(tài)變?yōu)椋浩渲校捍藭r(shí)的輸出為j時(shí)刻的最高級(jí)：n級(jí)反饋移位寄存器

每一存儲(chǔ)器稱為移位寄存器的一級(jí)，在任一時(shí)刻，這些級(jí)的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對(duì)應(yīng)于GF(2)上的一個(gè)n維向量，共有2n種可能的狀態(tài)。移位寄存器是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。GF(2)上一個(gè)n級(jí)反饋移位寄存器由n個(gè)二元存儲(chǔ)器與一個(gè)反饋函數(shù)f(a1,a2,…,an)組成，如右圖所示。2023/2/520ajaj-2aj-1第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)生序列為：10011101……比如：2023/2/521每一時(shí)刻的狀態(tài)可用n長(zhǎng)序列“a1,a2,…,an

”n維向量“(a1,a2,…,an)”來表示，其中ai是第i級(jí)存儲(chǔ)器的內(nèi)容。初始狀態(tài)由用戶確定，當(dāng)?shù)趇個(gè)移位時(shí)鐘脈沖到來時(shí)，每一級(jí)存儲(chǔ)器ai都將其內(nèi)容向下一級(jí)ai-1傳遞，并計(jì)算f(a1,a2,…,an)作為下一時(shí)刻的an。反饋函數(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。-表示方法1、線性遞推式表示一個(gè)r級(jí)線性移存器的線性遞推式表示為：2023/2/522an-1an-2an-3an-4an2、反饋多項(xiàng)式表示一個(gè)r級(jí)線性移存器的反饋多項(xiàng)式表示為：x1x2x3x4通常，用來表示一個(gè)LFSR。2023/2/523例：下圖是一個(gè)3級(jí)反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由下表求出。即輸出序列為101110111011…，周期為4。2023/2/524-具體來說：在初始狀態(tài)下,即0時(shí)刻在第一個(gè)時(shí)鐘到來時(shí)101f(a1,a2,a3)=a1a2⊕a3第1級(jí)第2級(jí)第3級(jí)S0=(1,0,1)輸出10f(a1,a2,a3)=a1a2⊕a3第1級(jí)第2級(jí)第3級(jí)S1=(0,1,1)a1=1,a2=0,a3=11輸出1a02023/2/525則其輸出序列和狀態(tài)序列如下:

狀態(tài)序列:(1,0,1)(0,1,1)(1,1,1)(1,1,0)(1,0,1)(0,1,1)….

輸出序列:101110….

由上面的結(jié)果可以看出，這個(gè)反饋移位寄存器的狀態(tài)序列和輸出序列都是周期序列，其周期為4。在第二個(gè)時(shí)鐘到來時(shí)11f(a1,a2,a3)=a1a2⊕a3第1級(jí)第2級(jí)第3級(jí)S2=(1,1,1)a1=1,a2=1,a3=01輸出0a02023/2/5262023/2/527例：一個(gè)5級(jí)線性反饋移位寄存器例設(shè)一個(gè)GF(2)上的4階線性反饋移位寄存器如下圖所示，其反饋函數(shù)為f(x1，x2，x3，x4)＝x1⊕x2，初始狀態(tài)為S0＝（1，0，1，1）容易驗(yàn)證該線性反饋移位寄存器的輸出序列為：

101111000100110101111000100110……

這個(gè)線性移位寄存器序列是一個(gè)周期序列，周期為15。x4x3x2x1＋輸出序列2023/2/528（1）在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一個(gè)不為0，否則f(a1,a2,…,an)≡0，這樣的話，在n個(gè)脈沖后狀態(tài)必然是00…0，且這個(gè)狀態(tài)必將一直持續(xù)下去。

注：（2）若只有一個(gè)系數(shù)不為0，設(shè)僅有cj不為0，實(shí)際上是一種延遲裝置。一般對(duì)于n級(jí)線性反饋移位寄存器，總是假定cn=1。（3）n級(jí)線性反饋移位寄存器的狀態(tài)周期小于等于2n-1。輸出序列的周期與狀態(tài)周期相等，也小于等于2n-1。只要選擇合適的反饋函數(shù)便可使序列的周期達(dá)到最大值2n-1。

2023/2/5294.3序列和周期一般地，一個(gè)移存器序列表示為：

對(duì)于序列，若存在整數(shù)p使得對(duì)任意正整數(shù)k有成立，稱滿足該式的最小正整數(shù)p為序列的周期。

即：n級(jí)線性反饋移存器的最長(zhǎng)周期:，能達(dá)到最長(zhǎng)周期的線性移存器序列稱為m序列。-在密碼學(xué)中，我們希望參與變換的序列周期越長(zhǎng)越好，因此對(duì)線性反饋移存器我們更感興趣的是能達(dá)到最長(zhǎng)周期的序列，即m序列。定義1：n級(jí)線性反饋移位寄存器產(chǎn)生的序列{ai}的周期達(dá)到最大值2n-1時(shí)，稱{ai}為n級(jí)m序列。2023/2/530（1）如何利用級(jí)數(shù)盡可能小的線性移位寄存器產(chǎn)生周期長(zhǎng)、統(tǒng)計(jì)性能好的序列；（2）已知一個(gè)序列{ai}，如何構(gòu)造一個(gè)盡可能短的線性移位寄存器來產(chǎn)生它。-m序列的隨機(jī)性：序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有良好的隨機(jī)性，以使密碼分析者對(duì)它無法預(yù)測(cè)。也就是說，即使截獲其中一段，也無法推測(cè)后面是什么。如果密鑰流是周期的，要完全做到隨機(jī)性是困難的。嚴(yán)格地說，這樣的序列不可能做到隨機(jī)，只能要求截獲比周期短的一段時(shí)不會(huì)泄露更多信息，這樣的序列稱為偽隨機(jī)序列。2023/2/5311.

Golomb隨機(jī)性假設(shè)

為了度量周期序列的隨機(jī)性，Golomb提出了下列三條標(biāo)準(zhǔn)：凡滿足這三條隨機(jī)性假設(shè)的序列，被Golomb稱為偽隨機(jī)序列或者偽噪聲序列。（1）一個(gè)周期中0、1的個(gè)數(shù)相差不超過1個(gè)；（2）一個(gè)周期段中，長(zhǎng)度為k的游程占游程總數(shù)的（這里假定至少有兩個(gè)長(zhǎng)為k的游程）；（3）周期自相關(guān)函數(shù)是二值函數(shù)。2、m序列統(tǒng)計(jì)特性性質(zhì)1

：r級(jí)m序列的一個(gè)周期中，1出現(xiàn)個(gè),0出現(xiàn)個(gè)。1）m序列的“0、1”信號(hào)的頻次規(guī)律2）m序列的游程分布規(guī)律2023/2/532

若干個(gè)信號(hào)連續(xù)出現(xiàn)的現(xiàn)象稱游程。對(duì)于序列a，稱a中形如01…10或10…01的段為一個(gè)1游程或0游程，游程中所含1或0的個(gè)數(shù)稱為該游程的長(zhǎng)度，如0110為一個(gè)長(zhǎng)為2的1游程，101為一個(gè)長(zhǎng)為1的0游程。性質(zhì)2：將r級(jí)m序列的一個(gè)周期段首尾相接，其游程總數(shù)為N=2r-1；其中沒有長(zhǎng)度大于r的游程；有1個(gè)長(zhǎng)度為r的1游程，沒有長(zhǎng)度為r的0游程；沒有長(zhǎng)度為r-1的1游程，有1個(gè)長(zhǎng)度為r-1的0游程；有個(gè)長(zhǎng)度為的1游程，有個(gè)長(zhǎng)度為

的0游程。再如00110111，其前兩個(gè)數(shù)字是00，稱長(zhǎng)為2的0游程；接著是11，是長(zhǎng)為2的1游程；再下來是長(zhǎng)為1的0游程和長(zhǎng)為3的0游程。選講2023/2/533

3）

m序列的自相關(guān)特性

若是一個(gè)周期為p的0、1序列，定義{0,1}上的映射為：，定義序列的自相關(guān)函數(shù)為:性質(zhì)3：若是一個(gè)r級(jí)m序列，那么

Golomb隨機(jī)性假設(shè)只是隨機(jī)性的必要條件，一隨機(jī)序列應(yīng)該滿足Golomb隨機(jī)性假設(shè)。但滿足上述標(biāo)準(zhǔn)的周期序列并不一定能滿足我們對(duì)密鑰流序列在安全性上的要求，這種安全性是寓于隨機(jī)性之中的。選講2023/2/534例如：m序列完全滿足Golomb隨機(jī)性假設(shè)，但m序列是高度可預(yù)測(cè)的。-線性移位寄存器的輸出序列因?yàn)閚級(jí)線性移位寄存器的輸出序列{ai}滿足遞推關(guān)系:

an+k=c1an+k-1c2an+k-2…cnak，對(duì)任何k≥1成立。這種遞推關(guān)系可用一個(gè)一元高次多項(xiàng)式

p(x)=1+c1x+…＋cn-1xn-1＋cnxn

表示，稱這個(gè)多項(xiàng)式為L(zhǎng)FSR的特征多項(xiàng)式。由于ai∈GF(2)(i=1,2,…,n)，所以共有2n組初始狀態(tài)，即有2n個(gè)遞推序列，其中非恒零的有2n-1個(gè)，記2n-1個(gè)非零序列的全體為G(p(x))。定義2：給定序列{ai}，冪級(jí)數(shù)，稱為該序列的生成函數(shù)。2023/2/535

定義3：設(shè)p(x)是GF(2)上的多項(xiàng)式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階。（選講）

定理2：若序列{ai}的特征多項(xiàng)式p(x)定義在GF(2)上，p是p(x)的周期，則{ai}的周期r|p。（選講）n級(jí)LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項(xiàng)式p(x)。實(shí)際上，我們感興趣的是LFSR遍歷2n-1個(gè)非零狀態(tài)，這時(shí)序列的周期達(dá)到最大2n-1，這種序列就是m序列。特征多項(xiàng)式滿足什么條件時(shí)，LFSR的輸出序列為m序列。

定義4：僅能被非零常數(shù)或者本身的常數(shù)倍除盡，不能被其他多項(xiàng)式整除的多項(xiàng)式稱為不可約多項(xiàng)式。定理3：n級(jí)LFSR產(chǎn)生的序列有最大周期2n-1的必要條件是其特征多項(xiàng)式為不可約多項(xiàng)式。2023/2/536但該定理的逆命題不成立，即LFSR產(chǎn)生的特征多項(xiàng)式為不可約多項(xiàng)式，但其輸出序列不一定是m序列。例3：設(shè)f(x)=x4+x3+x2+x+1是GF(2)上的不可約多項(xiàng)式，但是它的輸出序列是000110001100011…，周期是5，不是m序列。解：f(x)的不可約性由多項(xiàng)式x，x+1，x2+x+1不能整除f(x)而得。對(duì)于k≥5，輸出序列用ak=ak-1ak-2ak-3ak－4

檢驗(yàn)即可。定義5：若n次不可約多項(xiàng)式p(x)的階為2n-1，稱其為n次本原多項(xiàng)式。（選講）定理4：{ai}為n級(jí)m序列的充要條件是其特征多項(xiàng)式p(x)為