【文章內(nèi)容簡介】 (x)|(x151)，但不存在小于 15的常數(shù) ，使得 p(x)|(xl1)，所以 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=ak1? ak4(k≥4)多項(xiàng)式表示中的部分概念70n 若初始狀態(tài)為 1001，則輸出為：100100011110101100100011110101…n 狀態(tài)序列為： 1001， 0100， 0010， 0001，1000， 1100， 1110， 1111， 0111， 1011，0101， 1010， 1101， 0110， 0011， 1001，0100， 0010， 0001……n 可見，它是周期為 241=15，即輸出序列為m序列。多項(xiàng)式表示中的部分概念71例：(100110101111000) 按前面的性質(zhì)有： 游程的總數(shù)為 8，分別為 1， 00，11， 0， 1， 0， 1111， 0000。其中有一半的游程長度為 2，長度為 2的游程為四分之一，最后有一個(gè)長度為 4的游程和一個(gè)長度為 3的游程。輸出序列72 序列密碼的安全性取決于密鑰流的安全性，要求密鑰流序列有好的隨機(jī)性，以使密碼分析者對它無法預(yù)測。也就是說，即使截獲其中一段，也無法推測后面是什么。如果密鑰流是周期的，要完全做到隨機(jī)性是困難的。嚴(yán)格地說，這樣的序列不可能做到隨機(jī)，只能要求截獲比周期短的一段時(shí)不會泄露更多信息，這樣的序列稱為 偽隨機(jī)序列 。 4. m序列的偽隨機(jī)性73 為討論序列的隨機(jī)性，我們先討論隨機(jī)序列的一般特性。 設(shè) {ai}=(a1a2a3…)為 0、 1序列，例如00110111，其前兩個(gè)數(shù)字是 00，稱為 0的 2游程；接著是 11，是 1的 2游程；再下來是 0的 1游程和 1的 3游程。隨機(jī)序列的特性74 定義： GF(2)上周期為 T的序列 {ai}的自相關(guān)函數(shù)定義為R(τ)=(1/T)∑ (1)ak(1)ak+τ,0≤τ≤T1 定義中的和式表示序列 {ai}與 {ai+τ}（序列 {ai}向后平移 τ位得到）在一個(gè)周期內(nèi)對應(yīng)位相同的位數(shù)與對應(yīng)位不同的位數(shù)之差。當(dāng) τ=0時(shí)， R(τ)=1；當(dāng) τ≠0時(shí)，稱 R(τ)為 異相自相關(guān)函數(shù) 。隨機(jī)序列的特性75 Golomb對偽隨機(jī)周期序列提出了應(yīng)滿足的如下 3個(gè)隨機(jī)性公設(shè)： ① 在序列的一個(gè)周期內(nèi)， 0與 1的個(gè)數(shù)相差至多為 1。隨機(jī)序列的特性76n ② 在序列的一個(gè)周期內(nèi)，長為 i的游程占游程總數(shù)的 1/2i (i=1,2,…)，且在等長的游程中0的游程個(gè)數(shù)和 1的游程個(gè)數(shù)相等。n ③ 異相自相關(guān)函數(shù)是一個(gè)常數(shù)。n 公設(shè) ① 說明 {ai}中 0與 1出現(xiàn)的概率基本上相同 。 ② 說明 0與 1在序列中每一位置上出現(xiàn)的概率相同 。 ③ 意味著通過對序列與其平移后的序列做比較，不能給出其他任何信息。隨機(jī)序列的特性77 從密碼系統(tǒng)的角度看，一個(gè)偽隨機(jī)序列還應(yīng)滿足下面的條件： ① {ai}的周期相當(dāng)大。② {ai}的確定在計(jì)算上是容易的。③ 由密文及相應(yīng)的明文的部分信息，不能確定整個(gè) {ai}。偽隨機(jī)序列應(yīng)滿足的條件78m序列概念稱周期達(dá)到最大值 2n1的 nLFSR（ 輸出） 序列 為 （ n級） m序列 。顯然，若某 nLFSR產(chǎn)生 一個(gè) m序列，則其狀態(tài)圖除了單點(diǎn) (00? 0)構(gòu)成的圈外，就是由 F2n\{(00? 0)}中所有 點(diǎn) 排列而成的一個(gè)大圈，因而其任何非全零的輸出序列均是 m序列，故稱之為 m序列生成器 。例 .4LFSR[1,0,0,1]。79 下一定理說明， m序列滿足 Golomb的 3個(gè)隨機(jī)性公設(shè)。 定理 GF(2)上的 n長 m序列 {ai}具有如下性質(zhì)： ① 0,1平衡性： 在一個(gè)周期內(nèi)， 0、 1出現(xiàn)的次數(shù)分別為 2n11和 2n1。② 游程特性： 在一個(gè)周期內(nèi)，總游程數(shù)為2n1； 對 1≤i≤n2， 長為 i的游程有 2ni1個(gè)，且0、 1游程各半；長為 n1的 0游程一個(gè)，長為n的 1游程一個(gè)。m序列的特性80n ③ {ai}的自相關(guān)函數(shù) 為m序列的特性81周期 p序列 a=a0a1a2? 的自相關(guān)函數(shù)定義如下：自相關(guān)函數(shù)計(jì)算 . 對給定的 周期序列 a，① 找出 a的周期段： a0a1a2 ? ap1② 計(jì)算：周期序列的自相關(guān)函數(shù)計(jì)算82 (1)a0 (1)a1 (1)a2 ? (1)ap1 （左環(huán)移 t位） (1)at (1)at+1 (1)at+2 ? (1)at1 對位相乘后再相加，即得 pCa(t)。例 .對 a=(10011101101)?， 計(jì)算 Ca(4)。自相關(guān)特性是說， n級 m序列 a的 自相關(guān)函數(shù)值如下 ： (a?(at)非全零且滿足 a的線性遞歸關(guān)系 )周期序列的自相關(guān)函數(shù)計(jì)算83證明： ① 在 n長 m序列的一個(gè)周期內(nèi)，除了全 0狀態(tài)外，每個(gè) n長狀態(tài)（共有 2n1個(gè)）都恰好出現(xiàn)一次，這些狀態(tài)中有 2n1個(gè)在 a1位是 1，其余 2n12n1=2n11個(gè)狀態(tài)在 a1位是 0。② 對 n=1,2， 易證結(jié)論成立。對 n2， 當(dāng) 1≤i≤n2時(shí)， n長 m序列的一個(gè)周期內(nèi)，長為 i的 0游程數(shù)目等于序列中如下形式的狀態(tài)數(shù)目： 100…01*…*，其中 ni2個(gè) *可任取 0或 1。這種狀態(tài)共有 2ni2個(gè)。同理可得長為 i的 1游程數(shù)目也等于 2ni2， 所以長為 i的游程總數(shù)為 2ni1。m序列的特性84 由于寄存器中不會出現(xiàn)全 0狀態(tài)，所以不會出現(xiàn) 0的 n游程，但必有一個(gè) 1的 n游程，而且 1的游程不會更大，因?yàn)槿舫霈F(xiàn) 1的 n+1游程，就必然有兩個(gè)相鄰的全 1狀態(tài)，但這是不可能的。這就證明了 1的 n游程必然出現(xiàn)在如下的串中： 當(dāng)這 n+2位通過移位寄存器時(shí)，便依次產(chǎn)生以下狀態(tài)： m序列的特性85由于 ， 這兩個(gè)狀態(tài)只能各出現(xiàn)一次，所以不會有 1的 n1游程。于是在一個(gè)周期內(nèi)，總游程數(shù)為m序列的特性86③ {ai}是周期為 2n1的 m序列，對于任一正整數(shù) τ(0τ2n1)， {ai}+{ai+τ}在一個(gè)周期內(nèi)為 0的位的數(shù)目正好是序列 {ai}和 {ai+τ}對應(yīng)位相同的位的數(shù)目。設(shè)序列 {ai}滿足遞推關(guān)系： ah+n=c1ah+n1? c2ah+n2? …? ah故 ah+n+τ=c1ah+n+τ1? c2ah+n+τ2? …? ah+τ ah+n? ah+n+τ=c1(ah+n1? ah+n+τ1)? c2(ah+n2? ah+n+τ2)? …? (ah? ah+τ)m序列的特性87 令 bj=aj? aj+τ， 由遞推序列 {ai}可推得遞推序列 {bi}， {bi}滿足bh+n=c1bh+n1? c2bh+n2? …? bh {bi}也是 m序列。為了計(jì)算 R(τ)， 只要用 {bi}在一個(gè)周期中 0的個(gè)數(shù)減去 1的個(gè)數(shù)，再除以 2n1， 即 （證畢）m序列的特性88一個(gè) nLFSR（ 給定結(jié)構(gòu)常數(shù)）具有 “ 由一個(gè)短的種子產(chǎn)生一個(gè)長的序列 ” 的功能：以短的種子作為初態(tài)，產(chǎn)生的輸出序列可以任意長！上述表明，任一 nLFSR都初步具有作為一個(gè) KG的資格；但從作為 KG的效用來講，自然更希望所使用的 nLFSR進(jìn)一步是 m序列生成器。m序列的特性89線性反饋移位寄存器（ LFSR） 的綜合nFSR的結(jié)構(gòu)常數(shù) +初態(tài) nFSR序列分析綜合前面我們講過， m序列是滿足 Golomb三條 隨機(jī)性公設(shè)的 PN序列 ，但其 不可以作為一個(gè)序列密碼的密鑰序列。因?yàn)椋簩?m序列，知道其少量的比特以后是可以預(yù)測的！現(xiàn)在就講怎么樣僅憑已知的少量比特來找出整個(gè)序列所滿足的線性遞推關(guān)系。一般地，把有關(guān)反饋移位寄存器的求解問題，從正反兩個(gè)方面分為 分析 與 綜合 ：90線性反饋移位寄存器（ LFSR） 的綜合線性反饋移位寄存器的綜合問題就在于 根據(jù)序列的少量比特求出整個(gè)序列所滿足的線性遞推關(guān)系 。一個(gè)自然的想法就是：先假定線性遞推關(guān)系，然后由序列的各項(xiàng)應(yīng)該適合之而導(dǎo)出線性方程組；但這樣的方法有其不易行之處在于：?不容易確定所適用的 LFSR的級數(shù) n，從而就不能導(dǎo)致恰當(dāng)規(guī)模的線性方程組；?當(dāng)上述的 n很大時(shí)，求解相應(yīng)規(guī)模的線性方程組也很困難。91事實(shí)上，對于 線性反饋移位寄存器的綜合問題已經(jīng)出現(xiàn)了著名的解法：BerlekampMassey迭代算法 ，簡稱 BM算法 。線性反饋移位寄存器（ LFSR） 的綜合92BM算法描述Input： SN=a0a1a2? aN1Step1：置 f0(x)=1， L0=0（ 初值）Step2： 設(shè) fi(x),Li， i=0,1,2,…,n （ 0?nN） 均已求出，且 L0?L1?L2?? ?Ln。 設(shè) ,由此計(jì)算 。Step3：當(dāng) dn=0時(shí)，取 fn+1(x)=fn(x),Ln+1=Ln。 當(dāng) dn=1時(shí)，若 Ln=0,則取 fn+1(x)=xn+1+1,Ln+1=n+1； 否則 ,找出 m(0?mn)使 LmLm+1=Lm+2 =? =Ln,取 fn+1(x)=fn(x)+xnmfm(x),Ln+1=max{Ln,n+1 Ln}。對于 n=0,1,2,? ， 重復(fù) Step2與 Step3， 直至 n=N1Output： fN(x),LN93BM算法舉例 輸入： S8=10101111輸出： 1+x3+x4,494有關(guān) BM算法的結(jié)果定理定理 1. 應(yīng)用 BM算法，若以 N長序列 SN為輸入，得到輸出 fN(x),LN， 則⑴ 以 fN(x)為聯(lián)接多項(xiàng)式的 LNLFSR是產(chǎn)生 SN的最短 LFSR， 且當(dāng) 時(shí)，迭代至第2LN步就得到最終輸出，即： 。⑵ 當(dāng) 時(shí)，產(chǎn)生 SN的最短 LFSR只是上述一個(gè)；當(dāng) 時(shí)，產(chǎn)生 SN的最短 LFSR一共有 個(gè)。由上述定理知，在前面的例子中， 以f8(x)=1+x3+x4為聯(lián)接多項(xiàng)式的 4LFSR是唯一的產(chǎn)生 S8=10101111的最短 LFSR。95有關(guān) BM算法的結(jié)果考慮問題：? S6=101011?f6(x)=1+x2+x3?如何解釋？—— 其實(shí)，對 ?， 由于 L6=4， 故 4LFSR [0,1,1,0]生成 S6； 對 ?， 由于 L1+N=1， 故 1LFSR[0]生成 S2（ 規(guī)定： f(x)=1產(chǎn)生全零序列）。 96有關(guān) BM算法的結(jié)果對于周期序列，也可應(yīng)用 BM算法求出產(chǎn)生它的最短 LFSR的聯(lián)接多項(xiàng)式，不過須注意： 一定得是針對兩個(gè)周期段去求才正確 ！定理定理 2. 對周期為 p的序列 a=a0a1a2? ，⑴ 應(yīng)用 BM算法于 S2p=a0a1? ap1a0a1? ap1求出 f2p(x),L2p時(shí)，必 f2p(x)的次數(shù)必為 L2p，且以 f2p(x)為聯(lián)接多項(xiàng)式的 L2pLFSR是唯一的產(chǎn)生 a的最短 LFSR。⑵ 。97應(yīng)用 BM算法舉例 求產(chǎn)生序列 a的最低次多項(xiàng)式 ， 這里⑴ a=111001， ⑵ a=(111001)?解：可見答案為： ⑴ 1+x2+x3； ⑵ 1+x2+x4。98應(yīng)用 BM算法舉例 注注 . 對于 ⑵ 中 周期序列 a，其實(shí)以前介紹過一種求生成它的