第2章 流密碼100906教材

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

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

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

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

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

。n-FSR序列

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

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

，遞推關(guān)系為

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

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

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

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

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

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

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

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

…k=k0k1k2

f——

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

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

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

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

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

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