現(xiàn)代密碼學(xué)(第二章)

第二章：流密碼一、流密碼的基本概念二、線性反饋移位寄存器序列三、非線性組合序列四、鐘控序列2024/7/171一、流密碼的基本概念有關(guān)的概念若m1的取值為0或1，則稱m1為一個(gè)比特（bit）。n個(gè)比特m1m2m3…mn

，稱為一個(gè)長(zhǎng)度為n的比特串。無(wú)窮個(gè)比特m1m2m3…mnmn+1…

，稱為一個(gè)比特流。兩個(gè)比特流：m=m1m2m3…mnmn+1…

，k=k1k2k3…knkn+1…

，做運(yùn)算得到如下一個(gè)新的比特流：c=c1c2c3…cncn+1…

，2024/7/172一、流密碼的基本概念其中cn=mn+kn(mod2)，n=1，2，3，…，稱比特流c是比特流m與比特流k的逐位模2加，或逐比特異或。記作c=m‘+’k注意：此時(shí)有m=c‘+’kk=m‘+’c2024/7/173一、流密碼的基本概念當(dāng)（1）明文是比特流m，稱為明文流；（2）加密密鑰和解密密鑰相同，是比特流k，稱為密鑰流；（3）密文是比特流c，稱為密文流；（4）加密算法和解密算法相同，加密：c=m‘+’k；解密：m=c‘+’k。則稱這樣的加解密算法為流密碼，又稱其為序列密碼。2024/7/174一、流密碼的基本概念隨機(jī)性：密鑰流的理想情形假設(shè)密鑰流k是由完全隨機(jī)的方式生成的。因此從攻擊者的角度來(lái)看，密鑰流k應(yīng)該是真正的隨機(jī)序列，滿足：k1，k2，

k3，

…，

kn

，

kn+1，

…都是具有等概率分布隨機(jī)變量，P(kl=0)=P(kl=1)=1/2，且它們相互獨(dú)立。2024/7/175一、流密碼的基本概念任意兩個(gè)不相重疊的密文段，它們所對(duì)應(yīng)的密鑰段都是相互獨(dú)立的。換句話說(shuō)，每一次加密都使用與以前的密鑰段完全無(wú)關(guān)的新密鑰段。再換句話說(shuō)，此時(shí)的加密方式是一次一密的。因此，此時(shí)達(dá)到了最高的安全性標(biāo)準(zhǔn)：無(wú)條件安全（完善保密）。這樣的密鑰流k具有以下三條重要的性質(zhì)：2024/7/176一、流密碼的基本概念（1）P(kl=0)=P(kl=1)=1/2。（1’）當(dāng)n充分大時(shí)，k1k2k3…kn中0和1的個(gè)數(shù)各占約一半。（2）P(k1k2…kl=10…01)=P(k1k2…kl=01…10)=1/2l。（2’）當(dāng)n充分大時(shí)，在k1k2k3…kn中，長(zhǎng)度為l的比特串10…01（稱為0游程）的個(gè)數(shù)約有n/2l個(gè)；長(zhǎng)度為l的比特串01…10（稱為1游程）的個(gè)數(shù)約有n/2l個(gè)。（3）若k>0，P(kl=kl+k)=P(kl≠kl+k)=1/2。（3’）若k>0，當(dāng)n充分大時(shí)，以下的值（稱為異相自相關(guān)函數(shù)值）約為0。2024/7/177一、流密碼的基本概念2024/7/178一、流密碼的基本概念偽隨機(jī)性：密鑰流的實(shí)用情形實(shí)用的密鑰流k不可能由完全隨機(jī)的方式生成。出于商用目的和標(biāo)準(zhǔn)化要求，密鑰流k必須由確定的方式自動(dòng)生成。不過(guò)從攻擊者的角度來(lái)看，密鑰流k很像真正的隨機(jī)序列，稱為偽隨機(jī)序列。偽隨機(jī)序列應(yīng)該滿足前面提到的性質(zhì)（1’）（2’）（3’）。這三條性質(zhì)就是著名的Golomb隨機(jī)性假設(shè)。2024/7/179一、流密碼的基本概念兩個(gè)不相重疊的密文段，它們所對(duì)應(yīng)的密鑰段可能不同，但未必沒有依賴關(guān)系。換句話說(shuō)，此時(shí)的加密方式未必是一次一密的。因此，此時(shí)未必達(dá)到無(wú)條件安全。因此，偽隨機(jī)的密鑰流只能力爭(zhēng)做到計(jì)算安全。2024/7/1710一、流密碼的基本概念現(xiàn)在對(duì)流密碼進(jìn)行已知明文攻擊。設(shè)攻擊者Eve在以往截獲了密文段c1c2c3…cn，并知道了對(duì)應(yīng)的廢棄明文段m1m2m3…mn，因此計(jì)算出了對(duì)應(yīng)的廢棄密鑰段k1k2k3…kn。希望：由k1k2k3…kn難以預(yù)測(cè)后續(xù)密鑰段kn+1kn+2…

。這種不可預(yù)測(cè)性又稱為偽隨機(jī)性。因此希望密鑰流k滿足Golomb隨機(jī)性假設(shè)（1’）（2’）（3’）。但這還不夠，還必須具有“很高的線性復(fù)雜度”。（將在以后介紹）2024/7/1711二、線性反饋移位寄存器序列線性反饋移位寄存器序列若比特流k由如下的方式生成：（1）選擇長(zhǎng)度為n的比特串k1k2k3…kn；（2）當(dāng)l>n后，kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n。其中常數(shù)c1、c2、…、cn都是比特值，且cn=1。2024/7/1712二、線性反饋移位寄存器序列則稱比特流k為n階線性反饋移位寄存器序列，又稱為n階線性遞歸序列；稱常數(shù){c1、c2、…、cn}為抽頭系數(shù)；稱比特串k1k2k3…kn為初始狀態(tài)；稱f(x)=1‘+’c1x1

‘+’c2x2

‘+’…‘+’cnxn為此線性反饋移位寄存器序列的特征多項(xiàng)式。2024/7/1713線性反饋移位寄存器

(linearfeedbackshiftregister)

(LFSR)2024/7/1714二、線性反饋移位寄存器序列線性反饋移位寄存器序列的性質(zhì)（不給出證明）設(shè)比特流k為n階線性反饋移位寄存器序列。（1）k是周期序列，最小周期不超過(guò)2n-1。（2）k由抽頭系數(shù){c1，c2，…，cn}和初始狀態(tài)k1k2k3…kn唯一確定。（3）如果k的最小周期達(dá)到了2n-1，此時(shí)稱k為n階m序列。m序列具有以下的特殊性質(zhì)。（Golomb隨機(jī)性假設(shè)）2024/7/1715二、線性反饋移位寄存器序列（3.1）k在自己的一個(gè)最小周期內(nèi)（即連續(xù)2n-1個(gè)比特內(nèi)），0出現(xiàn)2n-1-1次，1出現(xiàn)2n-1次。（3.2）取定j，3≤j≤n，觀察k的連續(xù)2n-1個(gè)長(zhǎng)l的比特串：klkl+1kl+2…kl+j-1，l=1,2,…,2n-1。10…01出現(xiàn)2n-l次；（長(zhǎng)為l-2的0游程）01…10出現(xiàn)2n-l次。（長(zhǎng)為l-2的1游程）觀察k的連續(xù)2n-1個(gè)長(zhǎng)n+1的比特串：kl~kl+n，l=1~2n-1。10…01出現(xiàn)1次。（長(zhǎng)為n-1的0游程）觀察k的連續(xù)2n-1個(gè)長(zhǎng)n+2的比特串：kl~kl+n+1，l=1~2n-1。01…10出現(xiàn)1次。（長(zhǎng)為n-1的0游程）2024/7/1716二、線性反饋移位寄存器序列（3.3）對(duì)任何1≤j≤2n-2

，下式為0。（自相關(guān)函數(shù)）2024/7/1717二、線性反饋移位寄存器序列從以上性質(zhì)可以看出，n階m序列滿足Golomb隨機(jī)性假設(shè)。而且當(dāng)n并不大時(shí)，通信伙伴生成n階m序列的復(fù)雜度很小，得到的最小周期2n-1卻極大。如此看來(lái)，m序列似乎非常適合用作密鑰流。其實(shí)不然。如果n階線性反饋移位寄存器序列用作密鑰流，攻擊者Eve截獲了密文段c1c2c3…c2n，并知道了對(duì)應(yīng)的明文段m1m2m3…m2n，因此計(jì)算出了對(duì)應(yīng)的廢棄密鑰段k1k2k3…k2n。則Eve獲得了關(guān)于抽頭系數(shù){c1、c2、…、cn}的以下方程組。2024/7/1718二、線性反饋移位寄存器序列kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n，其中l(wèi)=n+1，n+2，…，2n。注意到這是在有限域GF(2)上的線性方程組，很容易解出抽頭系數(shù){c1、c2、…、cn}。實(shí)際上，當(dāng)Eve獲得了n階線性反饋移位寄存器序列的任何一段的連續(xù)2n個(gè)比特kj+1kj+2kj+3…kj+2n，他就獲得了關(guān)于抽頭系數(shù){c1、c2、…、cn}的以下方程組。kl=c1kl-1‘+’c2kl-2‘+’…‘+’cnkl-n，其中l(wèi)=j+n+1，j+n+2，…，j+2n。2024/7/1719二、線性反饋移位寄存器序列2024/7/1720二、線性反饋移位寄存器序列以上方程組中的加法和乘法都是在域GF(2)上進(jìn)行的（即(mod2)運(yùn)算）。以上事實(shí)說(shuō)明，當(dāng)Eve獲得了n階線性反饋移位寄存器序列的任意連續(xù)2n個(gè)比特，Eve就獲得了整個(gè)密鑰流。實(shí)際上，對(duì)線性反饋移位寄存器序列還有更為有效的攻擊方法。當(dāng)Eve不知道階數(shù)n時(shí)，他還可以進(jìn)行測(cè)試。這種測(cè)試攻擊方法被稱為序列的綜合。2024/7/1721二、線性反饋移位寄存器序列線性反饋移位寄存器序列的綜合定理如果一個(gè)比特流是一個(gè)周期序列，則它一定是線性反饋移位寄存器序列。證明設(shè)比特流k的最小周期是N。則l>N后，kl=kl-N。因此比特流k為N階線性反饋移位寄存器序列，抽頭系數(shù)為

{c1、c2、…、cN}={0、0

、…0、1}（即極小多項(xiàng)式f(x)=1‘+’xN），初始狀態(tài)為k1k2k3…kN。2024/7/1722二、線性反饋移位寄存器序列定義一個(gè)周期序列作為一個(gè)線性反饋移位寄存器序列，它的最小階數(shù)稱為它的線性復(fù)雜度。對(duì)應(yīng)于這個(gè)階的特征多項(xiàng)式稱為該序列的極小多項(xiàng)式.（注意一個(gè)周期序列作為一個(gè)線性反饋移位寄存器序列，可以有很多不同的階數(shù)，其中它的最小周期就是它的一個(gè)階數(shù)。因此，周期序列的線性復(fù)雜度一定不超過(guò)它的最小周期）所謂序列的綜合，就是尋找周期序列的線性復(fù)雜度n，并且求出極小多項(xiàng)式f(x)。序列的綜合的兩種最著名的算法是B-M算法和Games-Chan算法。2024/7/1723二、線性反饋移位寄存器序列B-M算法輸入：周期序列的一段長(zhǎng)度為N的比特串sN=s0s1s2…sN-1。目的：求出比特串sN的最短的線性遞歸關(guān)系。當(dāng)N≥周期序列的線性復(fù)雜度的2倍時(shí)，該線性遞歸關(guān)系的階數(shù)就是線性復(fù)雜度，該線性遞歸關(guān)系就給出了抽頭系數(shù)。2024/7/1724二、線性反饋移位寄存器序列步驟1：找n0使得當(dāng)j=0~n0-1時(shí)，sj=0；當(dāng)j=n0時(shí)，sj=1。取初始值對(duì)于j=0~n0-1，令dj=0；對(duì)于j=n0，令dj=sl；對(duì)于0≤j≤n0，令fj(x)=1，lj=0；再對(duì)于j=n0+1，令fj(x)=1‘+’dj-1xj，lj=j。2024/7/1725二、線性反饋移位寄存器序列步驟2：設(shè){(fj(x),lj)；0≤j≤n}已經(jīng)求出。如果n=N，則直接轉(zhuǎn)步驟3；否則計(jì)算dn=fn(E)sn（此處E是“時(shí)間延遲算子”。即：當(dāng)fn(x)=a0‘+’a1x‘+’a2x2‘+’…‘+’atxt時(shí)，fn(E)sn=a0sn‘+’a1sn-1‘+’a2sn-2‘+’…‘+’atsn-t。）2024/7/1726二、線性反饋移位寄存器序列（1）如果dn=0，則令fn+1(x)=

fn(x)；ln+1=

ln；轉(zhuǎn)步驟2。（2）如果dn=1，則：找出m使得lm<lm+1=lm+2=…=

ln；令fn+1(x)=

fn(x)‘+’xn-mfm(x)；ln+1=max{ln,n+1-

ln}；轉(zhuǎn)步驟2。

2024/7/1727二、線性反饋移位寄存器序列步驟3：最后得到了(fN(x),lN)。（fN(x)的全體系數(shù)就是比特串sN的一個(gè)最短的齊次線性遞歸關(guān)系；該齊次線性遞歸關(guān)系的長(zhǎng)度為lN。如果N不小于周期序列的線性復(fù)雜度的2倍，lN就是該周期序列的線性復(fù)雜度，fN(x)就是該周期序列的極小多項(xiàng)式?？梢钥闯觯珺-M算法簡(jiǎn)單快速，攻擊線性復(fù)雜度小的序列極為有效。）2024/7/1728二、線性反饋移位寄存器序列Games-Chan算法定理比特流的最小周期為2的冪時(shí)，其線性復(fù)雜度大于其最小周期的一半。（不給出證明）設(shè)比特流的最小周期為N=2n。

輸入：周期序列的一個(gè)最小周期sN=s0s1s2…sN-1；令Lc=0；f(x)=1。2024/7/1729二、線性反饋移位寄存器序列步驟1：令L=(s0,s1,s2,…,sN/2-1)；R=(sN/2,sN/2+1,sN/2+2,…,sN-1)；計(jì)算B=L‘+’R。步驟2：如果B≠0，則令Lc=

Lc+N/2，f(x)=f(x)(1‘+’x)N/2，s=B，轉(zhuǎn)步驟3；如果B=0，則令s=L，轉(zhuǎn)步驟3。

步驟3：令N=N/2。步驟4：如果N=1，B≠0，則輸出(Lc,f(x))，停止；如果N=1，B=0，s≠0，則令Lc=Lc+1，f(x)=f(x)(1-x)，輸出(Lc,f(x))，停止；如果N≠1，則轉(zhuǎn)步驟1。

2024/7/1730二、線性反饋移位寄存器序列最后輸出的(Lc,f(x))是序列s的線性復(fù)雜度和極小多項(xiàng)式。注意到雖然序列的線性復(fù)雜度大于2n-1，用Games-Chan算法至多迭代n步就可求出，因此對(duì)此類大的線性復(fù)雜度，Games-Chan比B-M算法更加快速。由于需要序列的一個(gè)周期參加運(yùn)算，存儲(chǔ)量巨大，故Games-Chan算法還不能算是一個(gè)有效的算法。

2024/7/1731二、線性反饋移位寄存器序列線性反饋移位寄存器序列的小結(jié)線性反饋移位寄存器序列能夠?qū)崿F(xiàn)：小的計(jì)算量（n階線性遞歸生成，通常n不大）；極大的最小周期（對(duì)于m序列，最小周期為2n-1）；良好的偽隨機(jī)性（對(duì)于m序列，Golomb隨機(jī)性假設(shè)成立）。2024/7/1732二、線性反饋移位寄存器序列然而小的計(jì)算量得到小的線性復(fù)雜度（對(duì)于m序列，線性復(fù)雜度為n），很容易由短的一段（對(duì)于m序列，由長(zhǎng)度為2n的一段）推斷出整個(gè)序列（用B-M算法）。因此，線性反饋移位寄存器序列不能作為密鑰流。（能否讓線性復(fù)雜度很大？不能）兼顧小的計(jì)算量和大的線性復(fù)雜度，需要使用非線性的生成方式。2024/7/1733三、非線性組合序列域GF(2)上的n維函數(shù)（n維布爾函數(shù)）n維布爾函數(shù)是這樣的函數(shù)y=g(x1,x2,…,xn)：n個(gè)自變量x1,x2,…,xn取值均為0和1；因變量y取值為0和1。2024/7/1734三、非線性組合序列n維布爾函數(shù)的代數(shù)正規(guī)型：y=g(x1,x2,…,xn)=a(0)‘+’a(1)x1‘+’a(2)x2‘+’…‘+’a(n)xn‘+’a(1,2)x1x2‘+’…‘+’a(n-1,n)xn-1xn‘+’a(1,2,3)x1x2x3‘+’…‘+’a(n-2,n-1,n)xn-2xn-1xn‘+’…‘+’a(1,…,n)x1…xn2024/7/1735三、非線性組合序列其中常數(shù){a(0)，a(1)~a(n)，a(1,2)~a(n-1,n)，a(1,2,3)~a(n-2,n-1,n)，…，a(1,…,n)}稱為系數(shù)，它們?nèi)?或1為值。使得系數(shù)不為0的項(xiàng)的最高次數(shù)稱為n維布爾函數(shù)的次數(shù)。（關(guān)于n維布爾函數(shù)的注解：x12≡x1，因此只有混合高次項(xiàng)；又因此最高次數(shù)不超過(guò)n；系數(shù)組{a(0)~a(1,…,n)}中一共有2n個(gè)系數(shù)；函數(shù)g(x1,x2,…,xn)與系數(shù)組相互唯一）2024/7/1736三、非線性組合序列當(dāng)g(x1,x2,…,xn)只含有一次項(xiàng)時(shí)，稱g為線性函數(shù)；當(dāng)g(x1,x2,…,xn)只含有0次項(xiàng)和一次項(xiàng)時(shí)，稱g為仿射函數(shù)；當(dāng)g(x1,x2,…,xn)含有高次項(xiàng)時(shí)，稱g為非線性函數(shù)。2024/7/1737三、非線性組合序列非線性前饋序列若比特流k由如下的方式生成：（1）選擇n階m序列s=s1s2s3…，其極小多項(xiàng)式為f(x)，其初始狀態(tài)為s1s2s3…sn；（2）對(duì)每個(gè)l>0，kl=g(sl,sl+1,…,sl+n-1)。其中g(shù)(x1,x2,…,xn)為非線性的n維布爾函數(shù)。則稱比特流k為非線性前饋序列。稱m序列s為驅(qū)動(dòng)序列。2024/7/1738三、非線性組合序列2024/7/1739三、非線性組合序列當(dāng)非線性前饋序列用作密鑰流時(shí)，通常只有三個(gè)部分可能作為通信伙伴的原始密鑰：初始狀態(tài)，極小多項(xiàng)式，非線性布爾函數(shù)。有以下三種不同的用法：（1）原始密鑰是初始狀態(tài)，而將極小多項(xiàng)式和非線性布爾函數(shù)公開。此時(shí)原始密鑰最短，但需要精心設(shè)計(jì)非線性布爾函數(shù)。（2）原始密鑰是初始狀態(tài)和極小多項(xiàng)式，而將非線性布爾函數(shù)公開。此時(shí)原始密鑰長(zhǎng)一些，但對(duì)非線性布爾函數(shù)的要求低一些。（3）原始密鑰是初始狀態(tài)、極小多項(xiàng)式、非線性布爾函數(shù)。此時(shí)原始密鑰最長(zhǎng)，但對(duì)非線性布爾函數(shù)的要求最低。2024/7/1740三、非線性組合序列為什么g必須是非線性函數(shù)？如果g是線性函數(shù)，則前饋序列k還是n階m序列，并且與驅(qū)動(dòng)序列s有相同的極小多項(xiàng)式（不給出證明）。如果g是仿射函數(shù)，則前饋序列k是n階m序列的補(bǔ)序列。希望：非線性前饋序列的線性復(fù)雜度極大，應(yīng)該與2n具有相同的數(shù)量級(jí)。2024/7/1741三、非線性組合序列前饋序列k的偽隨機(jī)性如何？2n-1是前饋序列k的一個(gè)周期（容易證明）。換句話說(shuō)，前饋序列k的最小周期必然是2n-1的因子。希望：前饋序列k的最小周期就是2n-1。希望：前饋序列k是0-1基本均衡的，即在一個(gè)最小周期內(nèi)0和1的數(shù)量近似相等。這些都需要精心地設(shè)計(jì)非線性布爾函數(shù)g。前饋序列最難做到的是游程分布的偽隨機(jī)性和自相關(guān)的的偽隨機(jī)性。2024/7/1742三、非線性組合序列非線性組合序列若比特流k由如下的方式生成：（1）M個(gè)n階m序列s(j)=s(j)1s(j)2s(j)3…；j=1~M；（2）對(duì)每個(gè)l>0，kl=g(s(1)l,s(2)l,…,s(M)l)。其中g(shù)(x1,x2,…,xM)為非線性的M維布爾函數(shù)。則稱比特流k為非線性組合序列。稱M個(gè)n階m序列s(j)為驅(qū)動(dòng)序列。2024/7/1743三、非線性組合序列2024/7/1744三、非線性組合序列J-K觸發(fā)器J和K分別表示兩個(gè)m序列，它們?cè)谌我鈺r(shí)刻的輸出是J-K觸發(fā)器的輸入。這兩個(gè)輸入與J-K觸發(fā)器上一個(gè)時(shí)刻的內(nèi)部狀態(tài)ql-1相結(jié)合，得到J-K觸發(fā)器本時(shí)刻的內(nèi)部狀態(tài)ql，同時(shí)J-K觸發(fā)器在本時(shí)刻輸出該狀態(tài)ql。如下表所示。一般令q-1=0。J0011K0101本時(shí)刻的狀態(tài)及輸出：ql上一狀態(tài)：ql-101上一狀態(tài)取補(bǔ)：1-ql-12024/7/1745四、鐘控序列鐘控序列鐘控序列的種類很多，大體上采用如下的結(jié)構(gòu)：（1）選擇2個(gè)同步的m序列s(j)=s(j)1s(j)2s(j)3…；j=1，2；（2）在任何一個(gè)時(shí)刻，根據(jù)s(1)的“當(dāng)前情況”，決定是否輸出s(2)的“對(duì)應(yīng)比特”；當(dāng)輸出時(shí)，輸出s(2)的“哪些比特”。最終輸出的序列就是鐘控序列。稱s(1)為控制序列。稱s(2)為受控序列。請(qǐng)注意，鐘控序列與非線性前饋序列不同。鐘控序列并不是每個(gè)時(shí)刻都輸出一個(gè)比特。2024/7/1746四、鐘控序列2024/7/1747四、鐘控序列鐘控序列的的設(shè)計(jì)思想：對(duì)m序列進(jìn)行適當(dāng)?shù)摹白冃巍焙汀凹舨谩?，使得原本線性復(fù)雜度很低的m序列變成線性復(fù)雜度級(jí)高的鐘控序列。設(shè)m序列的階為n。作為密鑰流，鐘控序列與非線性前饋序列相比，有以下的優(yōu)點(diǎn)和缺點(diǎn)（不給出證明）：（1）鐘控序列能夠更容易地使線性復(fù)雜度達(dá)到極大。（2）鐘控序列不是等間隔輸出，而是不定時(shí)的輸出，使得必須額外地進(jìn)行時(shí)間同步，配備緩存器。（3）鐘控序列對(duì)m序列的某些比特跳過(guò)不輸出，造成了一定的浪費(fèi)。2024/7/1748四、鐘控序列停-走生成器此工作屬于BethT.。所給出的停-走生成器如下。設(shè)GF(2)上兩個(gè)n級(jí)m-序列：控制序列a=a0a1a2…；受控序列b=b0b1b2…。記G(t)=a0+a1+a2+

…+at-1。（不是(mod2)加法）停-走序列u=u0u1u2…為：ut=bG(t)，t=0,1,2,…。

2024/7/1749四、鐘控序列縮減序列：互縮序列

此工作屬于DonCoppersmith。所給出的互縮序列如下。設(shè)GF(2)上兩個(gè)n級(jí)m-序列：控制序列a=a0a1a2…；受控序列b=b0b1b2…。當(dāng)at=1時(shí)，輸出bt；當(dāng)at=0時(shí)，放棄輸出。如此得到的輸出序列u=u0u1u2…稱為互縮序列。2024/7/1750四、鐘控序列縮減序列：廣義自縮序列

所給出的廣義自縮序列如下。設(shè)GF(2)上一個(gè)n級(jí)m-序列a=a0a1a2…。取G=(g0,g1,…,gn-1)∈GF(2)n。記vt=g0at‘+’g1at-1‘+’…‘+’gn-1at-n+1。當(dāng)at=1時(shí)，輸出vt；當(dāng)at=0時(shí)，放棄輸出。如此得到的輸出序列b=b0b1b2…稱為廣義自縮序列?？梢钥闯?，控制序列是a=a0a1a2…，受控序列是v=v0v1v2…，其中vt=g0at‘+’g1at-1‘+’…‘+’gn-1at-n+1。2024/7/1751四、鐘控序列注解一：關(guān)于受控序列v

當(dāng)G=(g0,g1,…,gn-1)∈GF(2)n是全0向量時(shí)，受控序列v是全0序列；當(dāng)G=(g0,g1,…,gn-1)∈GF(2)n是不為全0的向量時(shí)，受控序列v是控制序列a的平移序列。（即：v=v0v1v2…=akak+1ak+2…。這是m序列的一個(gè)基本結(jié)論，不給出證明。此時(shí)，控制序列a與受控序列v具有相同的極小多項(xiàng)式，僅僅初始狀態(tài)不同。這就是序列被稱為“廣義自縮序列”的理由）2024/7/1752四、鐘控序列注解二：關(guān)于廣義自縮序列的最小周期

控制序列a的最小周期是2n-1，在一個(gè)最小周期中，“1”出現(xiàn)2n-1次；當(dāng)G=(g0,g1,…,gn-1)∈GF(2)n是不為全0的向量時(shí)，受控序列v的最小周期也是2n-1。這就是說(shuō)，每當(dāng)廣義自縮序列輸出了2n-1個(gè)比特后，再輸出就是重復(fù)這2n-1個(gè)比特。