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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

時(shí)鐘中斷服務(wù)程序中，每當(dāng)TIMER_LOW轉(zhuǎn)滿時(shí)，此時(shí)記數(shù)器也會(huì)轉(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兩個(gè)16位二進(jìn)制數(shù)放進(jìn)temp數(shù)組，再送往RAND_SEED，從而獲得了“隨機(jī)種子”。因此，我們可以確定的是：隨機(jī)種子來(lái)自系統(tǒng)時(shí)鐘，確切地說(shuō)，是來(lái)自計(jì)算機(jī)主板上的定時(shí)/計(jì)數(shù)器在內(nèi)存中的記數(shù)值。

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

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

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

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

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

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

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

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

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

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

cn-1a2

…

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

cn-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ì)：2024/3/1939-工作原理(如下圖)假設(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)組成，如右圖所示。2024/3/1940ajaj-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……比如：2024/3/1941an-1an-2an-3an-4an2、反饋多項(xiàng)式表示一個(gè)r級(jí)線性移存器的反饋多項(xiàng)式表示為：x1x2x3x4通常，用來(lái)表示一個(gè)LFSR。2024/3/1942例：下圖是一個(gè)3級(jí)反饋移位寄存器，其初始狀態(tài)為(a1,a2,a3)=(1,0,1)，輸出可由下表求出。即輸出序列為101110111011…，周期為4。2024/3/1943-具體來(lái)說(shuō)：在初始狀態(tài)下,即0時(shí)刻在第一個(gè)時(shí)鐘到來(lái)時(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輸出1a02024/3/1944每一時(shí)刻的狀態(tài)可用n長(zhǎng)序列“a1,a2,…,an

”n維向量“(a1,a2,…,an)”來(lái)表示，其中ai是第i級(jí)存儲(chǔ)器的內(nèi)容。初始狀態(tài)由用戶確定，當(dāng)?shù)趇個(gè)移位時(shí)鐘脈沖到來(lái)時(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í)線性移存器的線性遞推式表示為：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é)果可以看出，這個(gè)反饋移位寄存器的狀態(tài)序列和輸出序列都是周期序列，其周期為4。在第二個(gè)時(shí)鐘到來(lái)時(shí)11f(a1,a2,a3)=a1a2⊕a3第1級(jí)第2級(jí)第3級(jí)S2=(1,1,1)a1=1,a2=1,a3=01輸出0a02024/3/19462024/3/1947例：一個(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＋輸出序列2024/3/1948（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。

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

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

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

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

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

SEAL序列密碼算法*

（略）4.6.3

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

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

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