《應(yīng)用密碼學(xué)》課件第4章 序列密碼

2.3.3單字符多表替換密碼技術(shù)復(fù)習(xí)：Vernam（弗納姆）密碼技術(shù)1917年美國電話電報公司的GilbertVernam為電報通信設(shè)計了一種十分方便的密碼技術(shù)。后來稱之為Vernam密碼技術(shù).它是一種代數(shù)密碼技術(shù)：其加密方法是，將明文和密鑰分別表示成二進(jìn)制序列，再把它們按位進(jìn)行模2加法。設(shè)明文m=m1m2…，密鑰k=k1k2…，其中mi，ki∈GF(2)，i≥1，則密文c=c1c2…，其中ci=mi

⊕ki。這里

⊕為模2加法。由模2加法的性質(zhì)可知，Vernam密碼技術(shù)的解密方法和加密方法一樣，只是將明文和密文的位置調(diào)換一下：mi=ci

⊕ki。[例2-5]：設(shè)明文m=01100001，密鑰k=01001110，使用Vernam密碼加密求密文。解：加密得：c=m⊕k=01100001⊕01001110=00101111，

為了增強(qiáng)Vernam密碼技術(shù)的安全性，應(yīng)該避免密鑰的重復(fù)使用(?)。假設(shè)我們可以做到密鑰是真正的隨機(jī)序列，密鑰的長度大于或等于明文的長度，一個密鑰只使用一次，那么Vernam密碼技術(shù)是經(jīng)得起攻擊的考驗的。(?)當(dāng)Vernam密碼體制中的密鑰序列是隨機(jī)的“0,1”序列，就是所謂的“一次一密”的密碼體制。香農(nóng)已經(jīng)證明“一次一密”密碼體制在理論上是不可破譯的。但由于隨機(jī)的密鑰序列的產(chǎn)生、存儲以及分配存在的一定困難，因此Vernam密碼體制在當(dāng)時并沒有得到廣泛的應(yīng)用4.1密碼學(xué)中的隨機(jī)數(shù)為什么在密碼學(xué)中要討論隨機(jī)數(shù)的產(chǎn)生？很多密碼算法都需要使用隨機(jī)數(shù)，因而隨機(jī)數(shù)在密碼學(xué)中起著重要的作用。DES加密算法中的密鑰：DES密鑰空間大小為256，如果密鑰k是隨機(jī)產(chǎn)生的，那么對方要嘗試256個可能的密鑰值。但是如果密鑰k這樣產(chǎn)生：選取一個16位隨機(jī)秘密s，然后利用一個復(fù)雜但是公開函數(shù)f將其擴(kuò)展為56位密鑰k，這是對方只要嘗試216個可能的密鑰值就能找到真正密鑰。4.1.1隨機(jī)數(shù)及其性質(zhì)序列密碼的保密性完全取決于密鑰的隨機(jī)性。如果密鑰是真正的隨機(jī)數(shù)，則這種體制在理論上是不可破譯的。但這種方式所需的密鑰量大得驚人，在實際中是不可行的。---有多驚人？因此，目前一般采用偽隨機(jī)序列來代替隨機(jī)序列作為密鑰序列，也就是序列存在著一定的循環(huán)周期性。這樣序列周期的長短就成為保密性的關(guān)鍵。如果周期足夠長，就會有比較好的保密性?，F(xiàn)在周期小于1010的序列很少被采用，周期長達(dá)1050的序列也并不少見。1．隨機(jī)數(shù)關(guān)于隨機(jī)數(shù)，在不同的領(lǐng)域或從不同的角度有許多不同的說法。目前，通常所講的隨機(jī)數(shù)是指沒有規(guī)律的數(shù)據(jù)。2．隨機(jī)數(shù)的性質(zhì)（1）隨機(jī)性隨機(jī)數(shù)在密碼學(xué)的應(yīng)用中的無規(guī)律性，主要體現(xiàn)在：①具有均勻分布、總體良好的隨機(jī)統(tǒng)計特征，能通過均勻性檢驗、獨(dú)立性檢驗、游程檢驗等基本的統(tǒng)計特性檢驗；②不能重復(fù)產(chǎn)生，即在完全相同的條件下，將得到兩個不相關(guān)的隨機(jī)序列。（2）不可預(yù)測性不可預(yù)測性是指即使給出的產(chǎn)生序列的硬件和所有以前產(chǎn)生序列的全部知識，也不能預(yù)測下一個隨機(jī)位是什么，因而隨機(jī)序列是非周期的。在實際的雙向認(rèn)證或會話密鑰產(chǎn)生等的應(yīng)用中，不僅要求隨機(jī)序列具有隨機(jī)性，還要求對序列中的數(shù)是不可預(yù)測的。4.1.2隨機(jī)數(shù)的生成方法計算機(jī)上的隨機(jī)數(shù)產(chǎn)生器并不是隨機(jī)的，因為計算機(jī)一直是具有完全確定性的機(jī)器，特別在行為隨機(jī)性方面表現(xiàn)不盡人意。目前，隨機(jī)數(shù)的生成有以下兩類方法。（1）物理方法：是指利用自然界的一些真的隨機(jī)物理量來生成隨機(jī)數(shù)。比如，放射性衰變、電子設(shè)備的噪聲、宇宙射線的觸發(fā)時間等。一般來說，用物理方法得到的隨機(jī)數(shù)具有很好的隨機(jī)性，但是由于具有的不可重復(fù)性，使得統(tǒng)計模擬和驗證十分困難。此外，該方法產(chǎn)生隨機(jī)數(shù)的速度和物理隨機(jī)數(shù)發(fā)生器的穩(wěn)定性也使得此方法的應(yīng)用受到限制。（2）利用計算機(jī)來產(chǎn)生隨機(jī)數(shù)，即數(shù)學(xué)方法。這類方法由一個初始狀態(tài)（稱為“種子”）開始，通過一個確定的算法來生成隨機(jī)數(shù)。一旦給定算法和種子，輸出的序列就是確定了的，因而產(chǎn)生的序列具有周期性、規(guī)律性和重復(fù)性，不是真正的隨機(jī)數(shù)，而是偽隨機(jī)數(shù)

（PseudoRandomNumbaer,PRN），產(chǎn)生偽隨機(jī)數(shù)的算法或硬件一般稱之為偽隨機(jī)數(shù)生成器（PseudoRandomNumbaerGenerator,PRNG）。PRNG是一個生成完全可預(yù)料的數(shù)列（稱為流）的確定性程序。一個編寫得很好的

PRNG可以創(chuàng)建一個序列，而這個序列的屬性與許多真正隨機(jī)數(shù)的序列的屬性是一樣的。例如：PRNG可以以相同幾率在一個范圍內(nèi)生成任何數(shù)字；PRNG可以生成帶任何統(tǒng)計分布的流；由PRNG生成的數(shù)字流不具備可辨別的模。PRNG實現(xiàn)簡單、速度快、經(jīng)濟(jì)，而且在目前的許多應(yīng)用中并不一定必須使用真正的隨機(jī)數(shù)，只要產(chǎn)生的偽隨機(jī)數(shù)的隨機(jī)性能滿足應(yīng)用需求就可以。

就目前而言，PRNG在眾多應(yīng)用都發(fā)揮著重要的作用，比如模擬（蒙特卡洛方法）、電子競技和密碼應(yīng)用等。目前應(yīng)用的隨機(jī)數(shù)都是通過PRNG產(chǎn)生的、滿足一定隨機(jī)性要求的偽隨機(jī)數(shù)。但是在應(yīng)用中，往往要求偽隨機(jī)數(shù)應(yīng)盡可能地接近真的隨機(jī)數(shù)的特性，比如具有良好的統(tǒng)計分布特性（能通過基本的被認(rèn)可的統(tǒng)計檢驗）、具有足夠長的周期等。一般來說，只要產(chǎn)生的偽隨機(jī)數(shù)能夠通過足夠多的、良好的統(tǒng)計檢驗，就可以放心地將偽隨機(jī)數(shù)當(dāng)隨機(jī)數(shù)來使用了。-[補(bǔ)充]

偽隨機(jī)數(shù)（PRNG）生成器算法實現(xiàn)（1）C程序?qū)崿F(xiàn)-程序（rand01.c）完整地闡述了隨機(jī)數(shù)產(chǎn)生的過程：

首先，主程序調(diào)用random_start()方法

random_start()方法中”movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);”函數(shù)用來移動內(nèi)存數(shù)據(jù)，其中FP_SEG（farpointertosegment）是取temp數(shù)組段地址的函數(shù)，F(xiàn)P_OFF（farpointertooffset）是取temp數(shù)組相對地址的函數(shù)，movedata函數(shù)的作用是把位于0040:006CH存儲單元中的雙字放到數(shù)組temp的聲明的兩個存儲單元中。這樣可以通過temp數(shù)組把0040:006CH處的一個16位的數(shù)送給RAND_SEED。

緊接著，輸出隨機(jī)數(shù)（調(diào)用random()方法）

Random()是根據(jù)隨機(jī)種子RAND_SEED的值計算得出隨機(jī)數(shù)：RAND_SEED=(RAND_SEED*123+59)%65536;注意：隨機(jī)數(shù)的計算方法在不同的計算機(jī)中是不同的，即使在相同的計算機(jī)中安裝的不同的操作系統(tǒng)中也是不同的。（比如在linux和windows下相同的隨機(jī)種子在這兩種操作系統(tǒng)中生成的隨機(jī)數(shù)是不同的，這說明它們的計算方法不同。）

隨機(jī)種子是從哪兒獲得的？

隨機(jī)種子為什么是在內(nèi)存的0040:006CH處??？那么0040:006CH處存放的是什么？

學(xué)過《計算機(jī)組成原理》課程應(yīng)該記得在編制ROMBIOS時鐘中斷服務(wù)程序時，會用到Intel8253定時/計數(shù)器，它與Intel8259中斷芯片的通信使得中斷服務(wù)程序得以運(yùn)轉(zhuǎn)，主板每秒產(chǎn)生的18.2次中斷正是處理器根據(jù)定時/記數(shù)器值控制中斷芯片產(chǎn)生的。在計算機(jī)的主機(jī)板上都會有這樣一個定時/記數(shù)器用來計算當(dāng)前系統(tǒng)時間，每過一個時鐘信號周期都會使記數(shù)器加一，而這個記數(shù)器的值存放在哪兒呢？

這個記數(shù)器的值就存在內(nèi)存的0040:006CH處，其實這一段內(nèi)存空間是這樣定義的：

TIMER_LOWDW?；地址為0040:006CHTIMER_HIGHDW?；地址為0040:006EHTIMER_OFTDB?；地址為0040:0070H

時鐘中斷服務(wù)程序中，每當(dāng)TIMER_LOW轉(zhuǎn)滿時，此時記數(shù)器也會轉(zhuǎn)滿，記數(shù)器的值歸零，即TIMER_LOW處的16位二進(jìn)制歸零，而TIMER_HIGH加1。

在程序rand01.c中的”movedata(0x0040,0x006c,FP_SEG(temp),FP_OFF(temp),4);”正是把TIMER_LOW和TIMER_HIGH兩個16位二進(jìn)制數(shù)放進(jìn)temp數(shù)組，再送往RAND_SEED，從而獲得了“隨機(jī)種子”。因此，我們可以確定的是：隨機(jī)種子來自系統(tǒng)時鐘，確切地說，是來自計算機(jī)主板上的定時/計數(shù)器在內(nèi)存中的記數(shù)值。

由此可知，隨機(jī)數(shù)是由隨機(jī)種子根據(jù)一定的計算方法計算出來的數(shù)值。所以，只要計算方法一定，隨機(jī)種子一定，那么產(chǎn)生的隨機(jī)數(shù)就不會變。（2）C++程序?qū)崿F(xiàn)1

在相同的平臺環(huán)境下，編譯生成exe后，每次運(yùn)行它，顯示的隨機(jī)數(shù)都是一樣的。這是因為在相同的編譯平臺環(huán)境下，由隨機(jī)種子生成隨機(jī)數(shù)的計算方法都是一樣的，再加上隨機(jī)種子一樣，所以產(chǎn)生的隨機(jī)數(shù)就是一樣的。（3）C++程序?qū)崿F(xiàn)2

本實現(xiàn)中，用戶和其他程序沒有設(shè)定隨機(jī)種子，則使用系統(tǒng)定時/計數(shù)器的值做為隨機(jī)種子，所以在相同的平臺環(huán)境下，編譯生成exe后，每次運(yùn)行它，顯示的隨機(jī)數(shù)會是偽隨機(jī)數(shù)，即每次運(yùn)行顯示的結(jié)果會有不同。（4）生成隨機(jī)串(C++程序)實現(xiàn)4.1.3偽隨機(jī)數(shù)的評價標(biāo)準(zhǔn)如果一序列產(chǎn)生器是偽隨機(jī)的，它應(yīng)有下面的性質(zhì)：（1）看起來是隨機(jī)的，表明它可以通過所有隨機(jī)性統(tǒng)計檢驗?，F(xiàn)在有許多統(tǒng)計測試。它們采用了各種形式，但共同思路是它們?nèi)家越y(tǒng)計方式檢查來自發(fā)生器的數(shù)據(jù)流，嘗試發(fā)現(xiàn)數(shù)據(jù)是否是隨機(jī)的。確保數(shù)據(jù)流隨機(jī)性的最廣為人知的測試套件就是GeorgeMarsaglia的DIEHARD軟件包（請參閱/pub/diehard/）。另一個適合此類測試的合理軟件包是pLab（請參閱http://random.mat.sbg.ac.at/tests/）。（2）它是不可預(yù)測的。即使給出產(chǎn)生序列的算法或硬件和所有以前產(chǎn)生的比特流的全部知識，也不可能通過計算來預(yù)測下一個隨機(jī)比特應(yīng)是什么。（3）它不能可靠地重復(fù)產(chǎn)生。如果用完全同樣的輸入對序列產(chǎn)生器操作兩次將得到兩個不相關(guān)的隨機(jī)序列。（？）4.2序列密碼的基本原理4.2.1序列密碼的概念序列密碼算法將明文逐位轉(zhuǎn)換成密文，如下圖所示。在序列密碼中，明文按一定長度分組后表示成一個序列，稱為明文流（序列中的每一項稱為明文字）。加密時，先由種子密鑰（或稱為主密鑰）通過密鑰流產(chǎn)生器產(chǎn)生一個密鑰流序列，該序列的每一項和明文字具有相同的比特長度，稱為密鑰字；然后依次把明文流和密鑰流中的對應(yīng)項做二元加法運(yùn)算（異或運(yùn)算），產(chǎn)生相應(yīng)的密文字，由密文字構(gòu)成密文流輸出。解密過程是將同樣的密鑰流與密文流中的對應(yīng)項做二元加法運(yùn)算，恢復(fù)出原來的明文流。假設(shè)明文流m=m1,m2,m3,…,mi,…；密鑰流k=k1，k2，k3，…,ki,…序列密碼的加密算法為：ci

=mi⊕ki序列密碼的解密算法為：mi

=ci⊕ki由于mi⊕ki⊕ki=mi，所以解密算法是正確的。[例5-3]：假設(shè)當(dāng)前的明文字為01101010，密鑰流生成器生成的當(dāng)前密鑰字為10110111，加解密均為按位異或加運(yùn)算，則得到的密文字為：01101010⊕10110111=11011101解密時用相同的密鑰字為：11011101⊕10110111=01101010實際的序列密碼算法安全性依賴于密鑰生成器所產(chǎn)生的密鑰流的性質(zhì)。如果密鑰流是無周期的（真正隨機(jī)的）無限長隨機(jī)序列，那么此時的序列密碼即為“一次一密”的密碼體制。4.2.2序列密碼體制的分類

在序列密碼中，根據(jù)狀態(tài)函數(shù)是否獨(dú)立于明文或密文，可以將序列密碼分為同步序列密碼和自同步序列密碼兩類。1．同步序列密碼在同步序列密碼中，密鑰流獨(dú)立于消息流產(chǎn)生。同步密鑰流生成器模型，它具有以下特點(diǎn)：（1）同步：在一個同步序列中，發(fā)送方和接收方必須是同步的，即用同樣的密鑰且該密鑰操作在同樣的位置（狀態(tài)），才能保證正確的解密。（2）無錯誤傳播：在傳輸期間，一個密文字（或位）被改變（不是刪除和插入）只能影響該密文字（或位）的恢復(fù)，不會對后續(xù)密文字（或位）產(chǎn)生影響。（3）主動攻擊破壞同步：按照同步要求，一個主動攻擊對密文進(jìn)行插入、刪除或重放操作都會立即破壞其同步，從而可能被解密器檢測出來。作為無錯誤傳播的結(jié)果，主動攻擊者可能有選擇地對密文進(jìn)行改動，并準(zhǔn)確地知道這些改動對明文的影響，這時可以采用為數(shù)據(jù)源提供認(rèn)證并保證數(shù)據(jù)完整性的技術(shù)。-同步密鑰流生成器

舉例OFB模式OFB模式的特性：

2．自同步序列密碼自同步序列密碼也稱為異步流密碼，其密鑰流的產(chǎn)生不是獨(dú)立于明文流和密文流的，與種子密鑰和其前面已產(chǎn)生若干密文字有關(guān)。-自同步序列密碼

舉例CFB模式自同步密鑰流生成器模型，它具有以下特點(diǎn)：（1）自同步：自同步的實現(xiàn)依賴于密文字被刪除或插入，這是因為解密只取決于先前固定數(shù)量的密文字。自同步序列密碼在同步丟失后能夠自動重新建立同步，并正確地解密，只有固定數(shù)量的明文字不能解密。（2）有限的錯誤傳播：因為自同步序列的狀態(tài)取決于t個已有的密文字符，若一個密文字（或位）在傳輸過程中被修改（插入或刪除），則解密時最多只影響到后續(xù)

t個密文字的解密，即只發(fā)生有限的錯誤傳播。（3）難檢測主動攻擊：相比于同步，自同步使得主動攻擊者發(fā)起的對密文字的插入、刪除、重放等攻擊只會產(chǎn)生非常有限的影響，正確的解密能很快自動重建。因此，主動攻擊對自同步序列密碼很困難的，可能需要采用為數(shù)據(jù)源提供認(rèn)證并保證數(shù)據(jù)完整性的技術(shù)。有限的錯誤傳播特性使得主動攻擊者對密文字的任何改動都會引起一些密文字解密出錯。（4）密文統(tǒng)計擴(kuò)散：每個明文字都會影響其后的整個密文，即密文的統(tǒng)計特性被擴(kuò)散到密文中。所以，自同步序列密碼體制在抵抗利用明文冗余度而發(fā)起的攻擊方面要強(qiáng)于同步序列密碼。從CFB看自同步流密碼DES是分組長為64bits的分組密碼，但利用CFB模式或OFB模式可將DES轉(zhuǎn)換為流密碼。流密碼不需要對消息填充，而且運(yùn)行是實時的。因此如果傳送字母流，可使用流密碼對每個字母直接加密并傳送。流密碼具有密文和明文一樣長這一性質(zhì)?！院蠡剡^頭來看CFB模式

4.2.3序列密碼與分組密碼的比較分組密碼和序列密碼的不同主要表現(xiàn)在以下兩方面：（1）分組密碼是以一定的固定長度的分組作為每次處理的基本單元；而序列密碼則是以一個元素（一個字符或一個比特位）作為基本處理單元。（2）分組密碼使用的是一個不隨時間變化的固定變換，具有擴(kuò)散性好、插入敏感等優(yōu)勢，其缺點(diǎn)是加密處理速度慢，存在錯誤傳播；而序列密碼是用的一個隨時間變換的加密變換，具有傳播速度快、低錯誤傳播和硬件實現(xiàn)電路簡單等優(yōu)勢，其缺點(diǎn)是低擴(kuò)散（意味著混亂不夠）、插入及修改不敏感。序列密碼體制的安全性取決于密鑰流的性能，當(dāng)密鑰流是完全的隨機(jī)序列時，序列密碼是不可破的；隨機(jī)序列的主要特點(diǎn)表現(xiàn)為無規(guī)律性和不可預(yù)測性。如果密鑰流能做到真正的隨機(jī)，此時的序列密碼就是“一次一密”的密碼體制，是絕對安全的。在實際應(yīng)用中，密鑰流都是用有限存儲和有限復(fù)雜邏輯的電路來產(chǎn)生的，此時的密鑰流只有有限個狀態(tài)。這樣的密鑰流生成器遲早要回到初始狀態(tài)而使其呈現(xiàn)出周期性。但如果密鑰流周期足夠長，且隨機(jī)性好，其安全強(qiáng)度是可以得到保證的。因此，序列密碼的安全強(qiáng)度取決于密鑰流生成器的設(shè)計。目前，產(chǎn)生密鑰流最重要的部件是線性反饋移位寄存器（LFSR，LinearFeedbackShiftRegister），這是因為LFSR非常適合硬件實現(xiàn)、能產(chǎn)生較大周期和統(tǒng)計特性良好的序列，以及能夠用代數(shù)方法對產(chǎn)生的序列進(jìn)行很好的分析。常見的密鑰序列產(chǎn)生器目前，最為流行和實用的密鑰流產(chǎn)生器大多基于線性反饋移位寄存器（LinearFeedbackShiftRegister,LSFR）。如下圖所示，其驅(qū)動部分是一個或多個線性反饋移位寄存器。LFSR………FLFSR1LFSR2LFSRn……FFF2024/3/19374.3線性反饋移位寄存器

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

cn-1a2

…

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

cn-1at+2

…

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

每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)，每一狀態(tài)對應(yīng)于GF(2)上的一個n維向量，共有2n種可能的狀態(tài)。移位寄存器是流密碼產(chǎn)生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數(shù)f(a1,a2,…,an)組成，如右圖所示。2024/3/1940ajaj-2aj-1第7時刻001第0時刻001第1時刻100第2時刻110第3時刻111第4時刻011第5時刻101第6時刻010產(chǎn)生序列為：10011101……比如：2024/3/1941an-1an-2an-3an-4an2、反饋多項式表示一個r級線性移存器的反饋多項式表示為：x1x2x3x4通常，用來表示一個LFSR。2024/3/1942例：下圖是一個3級反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由下表求出。即輸出序列為101110111011…，周期為4。2024/3/1943-具體來說：在初始狀態(tài)下,即0時刻在第一個時鐘到來時101f(a1,a2,a3)=a1a2⊕a3第1級第2級第3級S0=(1,0,1)輸出10f(a1,a2,a3)=a1a2⊕a3第1級第2級第3級S1=(0,1,1)a1=1,a2=0,a3=11輸出1a02024/3/1944每一時刻的狀態(tài)可用n長序列“a1,a2,…,an

”n維向量“(a1,a2,…,an)”來表示，其中ai是第i級存儲器的內(nèi)容。初始狀態(tài)由用戶確定，當(dāng)?shù)趇個移位時鐘脈沖到來時，每一級存儲器ai都將其內(nèi)容向下一級ai-1傳遞，并計算f(a1,a2,…,an)作為下一時刻的an。反饋函數(shù)f(a1,a2,…,an)是n元布爾函數(shù)，即n個變元a1,a2,…,an

可以獨(dú)立地取0和1兩個可能的值，函數(shù)中的運(yùn)算有邏輯與、邏輯或、邏輯補(bǔ)等運(yùn)算，最后的函數(shù)值也為0或1。-表示方法1、線性遞推式表示一個r級線性移存器的線性遞推式表示為：2024/3/1945則其輸出序列和狀態(tài)序列如下:

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

輸出序列:101110….

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

101111000100110101111000100110……

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

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

2024/3/1949/wiki/KeeLoq2015年11月份，由“神話”行動的一位18歲的安全研究員發(fā)現(xiàn)了汽車鑰匙芯片Keeloq算法的漏洞。HCS滾碼芯片和keeloq算法是目前很多汽車和門禁遙控鑰匙采取的軟硬件解決方案，車主每次按下鑰匙的鎖車鍵、開車鍵都會觸發(fā)一次新的信號發(fā)出，車輛在收到信號后快速計算，決定是否打開車門。祖沖之算法集（ZUC算法）是由我國學(xué)者自主設(shè)計的加密和完整性算法（序列密碼），包括祖沖之算法、加密算法128-EEA3和完整性算法128-EIA3，已經(jīng)被國際組織3GPP推薦為4G無線通信的第三套國際加密和完整性標(biāo)準(zhǔn)的侯選算法。/item/祖沖之算法集/7177910?fr=aladdin4.3.2密鑰序列的偽隨機(jī)性*-（略）4.4非線性反饋移位寄存器（略）4.5序列密碼算法的破譯（略）

已知反饋多項式(或線性遞推式)及初始狀態(tài)可獲得所產(chǎn)生的序列。而初始狀態(tài)總是可以假定的，故知道了反饋多項式(或線性遞推式)也就知道了該反饋多項式(或線性遞推式)所產(chǎn)生的序列。那么反過來，已知序列能否獲得相應(yīng)的反饋多項式(或線性遞推式)呢？答案是肯定的。4.5序列密碼算法的破譯（略）1.插入攻擊2.已知明文攻擊可得到c3＝1，c2＝0，c1＝1，從而得到特征多項式：p(x)=x3+x+1比如：若特征多項式p(x)=x3+x+1，初始狀態(tài)為（101）的移位寄存器產(chǎn)生序列為(101001)。設(shè)明文為（011010），那么密文為（110011）。破譯者計算mc得到密鑰系列(101001)，那么可以得到下列矩陣方程式：

已知序列a是由n級線性移存器產(chǎn)生的，并且知道a的連續(xù)2n位，可用解線性方程組的方法得到線性遞推式（特征多項式）和起始狀態(tài)。2024/3/1954例：設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰序列是使用5級線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個比特和明文串中的前10個比特建立如下方程：例題2024/3/1955即：2024/3/1956從而得到：所以：

從而得到特征多項式：p(x)=x4+x+12024/3/19574.6常用的序列密碼算法

基于LFSR的序列密碼非常適合于硬件實現(xiàn)，但是不特別適合軟件實現(xiàn)。這導(dǎo)致出現(xiàn)了一些關(guān)于序列密碼被計劃用于快速軟件實現(xiàn)的新建議，因為這些建議大部分具有專利，因此這里不討論它們的技術(shù)細(xì)節(jié)。比較常用的序列密碼是A5、SEAL和RC4序列密碼算法，A5是典型的基于LFSR的序列密碼算法，SEAL和RC4不是基于LFSR的序列密碼算法，而是基于分組密碼的輸出反饋模式（OFB）和密碼反饋模式（CFB）來實現(xiàn)的。其他不基于LFSR的序列密碼生成器的安全性基于數(shù)論問題的難解性，這些生成器比基于LFSR的生成器要慢很多。4.6.1A5序列密碼算法*（略）4.6.2

SEAL序列密碼算法*

（略）4.6.3

RC4序列密碼算法RC4是美國RSA數(shù)據(jù)安全公司1987年設(shè)計的一種一個可變密鑰長度（40至2048比特可變）、面向字節(jié)（256個bytes

）操作的序列密碼。RSA數(shù)據(jù)安全公司將其收集在加密工具軟件BSAFE中。最初并沒有公布RC4的算法。人們通過軟件進(jìn)行逆向分析得到了算法；在這種情況下，RSA數(shù)據(jù)安全公司于1997年公布了RC4密碼算法；

基本思想：對于n位長的字（RC4是8位長的字），它總共N=2n（RC4是28個）個可能的內(nèi)部置換狀態(tài)矢