第2章 流密碼100906教材

第2章流密碼2.1流密碼的基本概念2.2線性反饋移位寄存器2.3線性移位寄存器的一元多項(xiàng)式表示2.4非線性序列習(xí)題

2.1流密碼的基本概念序列密碼又稱流密碼。它是將明文消息字符串逐位地加密成密文字符?，F(xiàn)代密碼體制前面我們學(xué)習(xí)過(guò)所謂的古典密碼體制，其特點(diǎn)是對(duì)字母(或文字)表進(jìn)行操作(移位或替換)。以下我們開(kāi)始學(xué)習(xí)現(xiàn)代密碼體制?，F(xiàn)代密碼的基本出發(fā)點(diǎn)是將信息數(shù)字化(Digitize)，這使人們可以利用更多的數(shù)學(xué)進(jìn)行研究和開(kāi)展想象，并同計(jì)算機(jī)密切聯(lián)系。數(shù)字化是現(xiàn)代科技的重要特征之一。數(shù)據(jù)信息幾乎充斥人們?nèi)粘Ｉ畹姆椒矫婷?，并且越?lái)越為人們所重視。比如，今天傳統(tǒng)的金融和商業(yè)手段越來(lái)越多地被計(jì)算機(jī)所代替，甚至已經(jīng)有人研究所謂“電子貨幣”；又如，有人說(shuō)未來(lái)戰(zhàn)爭(zhēng)的重要武器就是a(atomic),b(biological),c(chemical),d(digital)；等等?，F(xiàn)代密碼體制序列（流）密碼模型一般序列密碼：同步序列密碼：自同步序列密碼：（常見(jiàn)的密文反饋模式）KGKG為計(jì)數(shù)器模式：KG為內(nèi)部反饋模式：（si+1連同s0均與k無(wú)關(guān)）（s0可能與k有關(guān)！）收發(fā)方嚴(yán)格同步?jīng)]有錯(cuò)誤擴(kuò)散具有自同步能力錯(cuò)誤擴(kuò)散有限若則稱為加法序列密碼。實(shí)用中可能更為簡(jiǎn)單在實(shí)用中，同步序列密碼是最為常見(jiàn)的。該種密碼一般并不要求把加密變換Eki設(shè)計(jì)得如何復(fù)雜，甚至采用更為簡(jiǎn)單的加法：即可；此時(shí)，安全性的關(guān)鍵在于密鑰序列生成器KG的設(shè)計(jì)。其實(shí)，一個(gè)KG就是一個(gè)以前講古典密碼時(shí)提到過(guò)的偽隨機(jī)密鑰源。有關(guān)其安全性的基本要求我們以后再講；為了了解它的一般構(gòu)造方法，我們必須首先學(xué)習(xí)所謂的線性反饋移位寄存器。流（序列）密碼2.2線性反饋移位寄存器移位寄存器是流密碼產(chǎn)生密鑰流的一個(gè)主要組成部分。一般反饋移位寄存器（FSR）一般地，一個(gè)n-FSR（n級(jí)反饋移位寄存器）的圖示如下：ai+n=f(ai,ai+1,…,ai+n-1)（反饋）a

記si=(ai,ai+1,…,ai+n-1)——在第i時(shí)刻的狀態(tài)，s0稱為初態(tài)。反饋函數(shù)諸存儲(chǔ)器存儲(chǔ)器編號(hào)———級(jí)數(shù)i=0，1，2，

輸出序列一般反饋移位寄存器（FSR）研討：一個(gè)n-FSR（指給定f）可產(chǎn)生

個(gè)不同的序列；一個(gè)n-FSR序列必呈某種周期性，若周期性重復(fù)從第k(k=0,1,2,…)項(xiàng)開(kāi)始，則k

。n-FSR序列

序列的初態(tài)狀態(tài)變化：(先導(dǎo))(ai,ai+1,…,ai+n-1)

(ai+1,ai+2,…,ai+n)(后繼)一個(gè)n-FSR序列的狀態(tài)走勢(shì)必呈如下形狀：（以每點(diǎn)對(duì)應(yīng)的狀態(tài)為初態(tài)的序列都平移等價(jià)）ai+n=f(ai,ai+1,…,ai+n-1)線性反饋移位寄存器（LFSR）當(dāng)一n-FSR的反饋函數(shù)為線性齊次式，即f(ai,ai+1,…,ai+n-1)=c1ai+n-1+c2ai+n-2++cnai(cj=0,1)時(shí)，稱之為n-LFSR。習(xí)慣上，人們常進(jìn)行下標(biāo)變換：k=i+n于是，對(duì)上述n-LFSR，其序列a滿足下列遞推關(guān)系式：ak=c1ak-1+c2ak-2++cnak-n(kn)其結(jié)構(gòu)示意圖通常（在不明確c1,c2,…,cn時(shí)）畫成：a……[c1,c2,…,cn]稱為結(jié)構(gòu)常數(shù)。cncn-1c1ak線性反饋移位寄存器（LFSR）對(duì)于一個(gè)n-LFSR，當(dāng)其結(jié)構(gòu)常數(shù)[c1,c2,…,cn]明確給定時(shí)，我們往往把該n-LFSR的結(jié)構(gòu)示意圖畫得更簡(jiǎn)潔，如以下例：例1.如果一個(gè)4-LFSR的結(jié)構(gòu)常數(shù)為[1,0,1,1]，則該4-LFSR的結(jié)構(gòu)示意圖為若給定上述4-LFSR的初態(tài)為(0,1,1,1)，則可以列出其狀態(tài)的變化過(guò)程，并求出相應(yīng)的輸出序列。(0111000111000111000111000…)aak線性反饋移位寄存器（LFSR）其實(shí)，僅僅給出一個(gè)n-LFSR的如例1之狀態(tài)圖，也就明確了該n-LFSR：例2.如果一個(gè)4-LFSR的結(jié)構(gòu)示意圖為則該4-LFSR的結(jié)構(gòu)常數(shù)為

，遞推關(guān)系為

。進(jìn)一步地可求出對(duì)應(yīng)初態(tài)(1,0,0,0)，(0,0,1,0)，(0,1,1,0)的(輸出)序列。aak[0,1,0,1]ak=0·ak-1+1·ak-2+0·ak-3+1·ak-4=ak-2+ak-4(k4)線性反饋移位寄存器（LFSR）對(duì)一個(gè)給定的n-LFSR，其狀態(tài)空間GF(2)n中所有2n個(gè)點(diǎn)以“先導(dǎo)-后繼”關(guān)系弧線相連接，得到的圖稱為該n-LFSR的狀態(tài)圖。對(duì)于n-LFSR[c1,c2,…,cn]，若cn=1，則其狀態(tài)圖均由圈構(gòu)成；而若cn=0，則其任意輸出序列除前面1bit外將是(n-1)-LFSR[c1,c2,…,cn-1]的輸出序列（退化情形）。以下研究總是指非退化情形。線性反饋移位寄存器（LFSR）一個(gè)n-LFSR序列的狀態(tài)圖要么是單點(diǎn)(0,0,…,0)；要么是一個(gè)不含點(diǎn)(0,0,…,0)的圈。對(duì)于n-LFSR，將其狀態(tài)圖中每一點(diǎn)都用對(duì)應(yīng)狀態(tài)的第一個(gè)分量標(biāo)注，這時(shí)得到的各個(gè)圈稱為序列圈。由這些序列圈可以更明顯地看出n-LFSR的2n個(gè)不同序列之間的關(guān)系：兩序列平移等價(jià)，當(dāng)且僅當(dāng)它們是同一序列圈上不同點(diǎn)開(kāi)始圍繞此圈周而復(fù)始地運(yùn)轉(zhuǎn)下去的結(jié)果。若視平移等價(jià)為本質(zhì)相同，則n-LFSR只能產(chǎn)生其狀態(tài)圖中所含圈數(shù)個(gè)本質(zhì)不同的序列。由一個(gè)n-LFSR的所有序列圈也可確定其狀態(tài)圖(思考)。線性反饋移位寄存器（LFSR）0,1序列a=a0a1a2

若滿足：存在正整數(shù)p，使得ai=ai+p，對(duì)一切非負(fù)整數(shù)i成立則稱之為周期序列，且把滿足上式的最小正整數(shù)p稱為周期，記為p(a)。一n-LFSR的所有輸出序列均為周期序列，且周期不超過(guò)

。稱達(dá)到最大周期2n-1的n-LFSR序列為(n-級(jí))m-列。顯然，若某n-LFSR產(chǎn)生一個(gè)m-序列，則其任何非（全）零的輸出序列均是m-序列，此時(shí)稱之為m-序列生成器。2.3線性移位寄存器的一元多項(xiàng)式表示對(duì)GF(2)上給定序列a=a0a1a2…

，稱為a的形式冪級(jí)數(shù)表示，記為A(x)。GF(2)上多項(xiàng)式與n-LFSR[c1,c2,…,cn-1,1]一一對(duì)應(yīng)，稱為L(zhǎng)FSR的特征多項(xiàng)式。記2n-1個(gè)非零序列的全體為G(p(x))。定義2.1給定序列{ai}，冪級(jí)數(shù)A(x)=∑aixi-1稱為該序列的生成函數(shù)。

定理2.1設(shè)p(x)=1+c1x+…+cn-1xn-1+cnxn是GF(2)上的多項(xiàng)式，G(p(x))中任一序列{ai}的生成函數(shù)A(x)滿足：

A(x)=(x)/p(x)其中(x)=∑cn-ixn-i∑ajxj-1定理2.2p(x)|q(x)的充要條件是G(p(x))G(q(x))。定義2.2設(shè)p(x)是GF(2)上的多項(xiàng)式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階。結(jié)論：n級(jí)LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項(xiàng)式p(x)。LFSR遍歷2n-1個(gè)非零狀態(tài)，這時(shí)序列的周期達(dá)到最大2n-1，這種序列就是m序列。問(wèn)題：特征多項(xiàng)式滿足什么條件時(shí)，LFSR的輸出序列為m序列。定理2.4設(shè)p(x)是n次不可約多項(xiàng)式，周期為m，序列{ai}∈G(p(x))，則{ai}的周期為m。例2.4f(x)=x4+x3+x2+x+1為GF(2)上的不可約多項(xiàng)式，這可由x,x+1,x2+x+1都不能整除f(x)得到。以f(x)為特征多項(xiàng)式的LFSR的輸出序列可由ak=ak-1ak-2ak-3ak-4(k≥4)和給定的初始狀態(tài)求出，設(shè)初始狀態(tài)為0001，則輸出序列為000110001100011…，周期為5，不是m序列。定義2.3若n次不可約多項(xiàng)式p(x)的階為2n-1，則稱p(x)是n次本原多項(xiàng)式。例2.5設(shè)p(x)=x4+x+1，由于p(x)|(x15-1)，但不存在小于15的常數(shù)l，使得p(x)|(xl-1)，所以p(x)的階為15。p(x)的不可約性可由x,x+1,x2+x+1都不能整除p(x)得到，所以p(x)是本原多項(xiàng)式。若LFSR以p(x)為特征多項(xiàng)式，則輸出序列的遞推關(guān)系為ak=ak-1ak-4(k≥4)若初始狀態(tài)為1001，則輸出為100100011110101100100011110101…周期為24-1=15，即輸出序列為m序列。上述定理告訴我們：(n-級(jí))m-列的構(gòu)造問(wèn)題(n次)本原多項(xiàng)式的構(gòu)造問(wèn)題。關(guān)于n次本原多項(xiàng)式，目前有快速、可行算法：根據(jù)一個(gè)已知的n次本原多項(xiàng)式，找到所有其它n次本原多項(xiàng)式；當(dāng)n較大時(shí)，檢驗(yàn)一個(gè)n次多項(xiàng)式是否本原只得依賴于定義，這往往很難，好在已有前人的文獻(xiàn)可查；n次本原多項(xiàng)式的數(shù)量很多：一共個(gè)，其中為Euler函數(shù)（(N)的定義為：在{1,2,…,N-1}中與N互素者的數(shù)目，(1)=1）。n-LFSR的一般理論結(jié)果流密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有好的隨機(jī)性，以使密碼分析者對(duì)它無(wú)法預(yù)測(cè)。也就是說(shuō)，即使截獲其中一段，也無(wú)法推測(cè)后面是什么。如果密鑰流是周期的，要完全做到隨機(jī)性是困難的。嚴(yán)格地說(shuō)，這樣的序列不可能做到隨機(jī)，只能要求截獲比周期短的一段時(shí)不會(huì)泄露更多信息，這樣的序列稱為偽隨機(jī)序列。

2.4m序列的偽隨機(jī)性為討論序列的隨機(jī)性，我們先討論隨機(jī)序列的一般特性。

設(shè){ai}=(a1a2a3…)為0、1序列，

形如和的一段序列分別稱為a的長(zhǎng)為k的0-游程與長(zhǎng)為L(zhǎng)的1-游程定義2.4：GF(2)上周期為T的序列{ai}的自相關(guān)函數(shù)定義為R(τ)=(1/T)∑(-1)ak(-1)ak+τ,0≤τ≤T-1定義中的和式表示序列{ai}與{ai+τ}（序列{ai}向后平移τ位得到）在一個(gè)周期內(nèi)對(duì)應(yīng)位相同的位數(shù)與對(duì)應(yīng)位不同的位數(shù)之差。當(dāng)τ=0時(shí)，R(τ)=1；當(dāng)τ≠0時(shí)，稱R(τ)為異相自相關(guān)函數(shù)。Golomb對(duì)偽隨機(jī)周期序列提出了應(yīng)滿足的如下3個(gè)隨機(jī)性公設(shè)：①在序列的一個(gè)周期內(nèi)，0與1的個(gè)數(shù)相差至多為1。②在序列的一個(gè)周期內(nèi)，長(zhǎng)為i的游程占游程總數(shù)的1/2i(i=1,2,…)，且在等長(zhǎng)的游程中0的游程個(gè)數(shù)和1的游程個(gè)數(shù)相等。③異相自相關(guān)函數(shù)是一個(gè)常數(shù)。公設(shè)①說(shuō)明{ai}中0與1出現(xiàn)的概率基本上相同;②說(shuō)明0與1在序列中每一位置上出現(xiàn)的概率相同;③意味著通過(guò)對(duì)序列與其平移后的序列做比較，不能給出其他任何信息。從密碼系統(tǒng)的角度看，一個(gè)偽隨機(jī)序列還應(yīng)滿足下面的條件：①{ai}的周期相當(dāng)大。②{ai}的確定在計(jì)算上是容易的。③由密文及相應(yīng)的明文的部分信息，不能確定整個(gè){ai}。定理2.7GF(2)上的n長(zhǎng)m序列{ai}具有如下性質(zhì)：①在一個(gè)周期內(nèi)，0、1出現(xiàn)的次數(shù)分別為2n-1-1和2n-1。②在一個(gè)周期內(nèi)，總游程數(shù)為2n-1；對(duì)1≤i≤n-2，長(zhǎng)為i的游程有2n-i-1個(gè)，且0、1游程各半；長(zhǎng)為n-1的0游程一個(gè)，長(zhǎng)為n的1游程一個(gè)。③{ai}的自相關(guān)函數(shù)為密鑰序列生成器(KG)基本要求<序列密碼>在序列密碼的設(shè)計(jì)中，人們往往將加密變換簡(jiǎn)單地取為加法(即人們經(jīng)常使用的是加法序列密碼)，這時(shí)保密性的關(guān)鍵在于KG的設(shè)計(jì)。對(duì)于KG，雖然種子密鑰k較短、其相應(yīng)的存儲(chǔ)器長(zhǎng)度也受限，但人們總是設(shè)法將它設(shè)計(jì)成：在現(xiàn)有的計(jì)算資源和能力下，難以破解所產(chǎn)生的密鑰序列；或者也可以說(shuō)，按現(xiàn)有的計(jì)算資源和能力估算，破解所產(chǎn)生的密鑰序列的代價(jià)遠(yuǎn)遠(yuǎn)超過(guò)由此而能獲取的利益。為了這樣的目的，人們就目前的想象和預(yù)見(jiàn)，提出以下基本要求：密鑰序列生成器(KG)基本要求種子密鑰k的變化量足夠大，一般應(yīng)在264以上；KG產(chǎn)生的密鑰序列k具極大周期，一般不小于255；k具有均勻的n-元分布，即在一個(gè)周期環(huán)上，某特定形式的n-長(zhǎng)bit串與其求反，兩者出現(xiàn)的頻數(shù)大抵相當(dāng)；(例如，均勻的游程分布)k不可由一個(gè)低級(jí)（比如，小于106級(jí)）的LFSR產(chǎn)生，也不可與一個(gè)低級(jí)LFSR產(chǎn)生的序列只有比率很小的相異項(xiàng)；利用統(tǒng)計(jì)方法由k提取關(guān)于KG結(jié)構(gòu)或K的信息在計(jì)算上不可行；混亂性.即k的每一bit均與k的大多數(shù)bit有關(guān)；擴(kuò)散性.即k任一bit的改變要引起k在全貌上的變化。KG的一般結(jié)構(gòu)通常，人們總是把KG設(shè)計(jì)得具有一定的結(jié)構(gòu)特點(diǎn)，從而稍加分析和論證其強(qiáng)度，以增加使用者的置信度。如此，積習(xí)而成以下模式：驅(qū)動(dòng)子系統(tǒng)f（可線性）非線性組合子系統(tǒng)F種子密鑰k…

…k=k0k1k2

f——

一般由LFSR或NLFSR等序列生成器構(gòu)成，提供若干周期大、統(tǒng)計(jì)特性好的序列(稱為驅(qū)動(dòng)序列)。F——

對(duì)多條驅(qū)動(dòng)序列，綜合運(yùn)用下面介紹的基本編碼手段，有效地破壞和掩蓋其中存在的規(guī)律或關(guān)系。KG結(jié)構(gòu)分解示意圖

例2.6設(shè)敵手得到密文串101101011110010和相應(yīng)的明文串011001111111001，因此可計(jì)算出相應(yīng)的密鑰流為110100100001011。進(jìn)一步假定敵手還知道密鑰流是使用5級(jí)線性反饋移位寄存器產(chǎn)生的，那么敵手可分別用密文串中的前10個(gè)比特和明文串中的前10個(gè)比特建立如下方程即而從而得到所以密鑰流的遞推關(guān)系為在前面已介紹密鑰流生成器可分解為驅(qū)動(dòng)子系統(tǒng)和非線性組合子系統(tǒng)，非線性序列驅(qū)動(dòng)子系統(tǒng)常用一個(gè)或多個(gè)線性反饋移位寄存器來(lái)實(shí)現(xiàn)，

非線性組合子系統(tǒng)用非線性組合函數(shù)F來(lái)實(shí)現(xiàn)。

本節(jié)介紹第2部分非線性組合子系統(tǒng)。

J-K觸發(fā)器如圖2.14所示，它的兩個(gè)輸入端分別用J和K表示，其輸出ck不僅依賴于輸入，還依賴于前一個(gè)輸出位ck-1，即其中x1和x2分別是J和K端的輸入。由此可得J-K觸發(fā)器的真值表，如表2.3。（見(jiàn)26頁(yè)表2.3）2.6.1J-K觸發(fā)器圖2.14J-K觸發(fā)器圖2.15利用J-K觸發(fā)器的非線性序列生成器在圖2.15中，令驅(qū)動(dòng)序列{ak}和{bk}分別為m級(jí)和n級(jí)m序列，則有如果令c-1=0，則輸出序列的最初3項(xiàng)為當(dāng)m與n互素且a0+b0=1時(shí)，序列{ck}的周期為(2m-1)(2n-1)。例2.7令m=2,n=3，兩個(gè)驅(qū)動(dòng)m序列分別為{ak}=0,1,1,…和{bk}=1,0,0,1,0,1,1,…于是，輸出序列{ck}是0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,0,