第五講：序列密碼1

人們試圖用序列密碼方式仿效”一次一密”密碼.從而促成了序列密碼的研究和發展.序列密碼是世界軍事,外交等領域應用的主流密碼體制.在通常的序列密碼中,加解密用的密鑰序列是偽隨機序列,它的產生容易且有較成熟的理論工具,所以序列密碼是當前通用的密碼系統.

序列密碼的安全性主要依賴于密鑰序列,因而什么樣的偽隨機序列是安全可靠的密鑰序列,以及如何實現這種序列就成了序列密碼中研究的一個主要方面.25.1密碼學中的隨機數

在密碼學都要涉及到隨機數？因為許多密碼系統的安全性都依賴于隨機數的生成，例如DES加密算法中的密鑰，RSA加密和數字簽名中的素數。

5.1.1隨機數的使用

序列密碼的保密性完全取決于密鑰的隨機性。如果密鑰是真正的隨機數，則這種體制在理論上就是不可破譯的。但這種方式所需的密鑰量大得驚人，在實際中是不可行的。

目前一般采用偽隨機序列來代替隨機序列作為密鑰序列，也就是序列存在著一定的循環周期。這樣序列周期的長短就成為保密性的關鍵。如果周期足夠長，就會有比較好的保密性?，F在周期小于1010的序列很少被采用，周期長達1050的序列也并不少見。

3何謂偽隨機數生成器（PRNG）？假定需要生成介于1和10之間的隨機數，每一個數出現的幾率都是一樣的。理想情況下，應生成0到1之間的一個值，不考慮以前值，這個范圍中的每一個值出現的幾率都是一樣的，然后再將該值乘以10。

由任何偽隨機數生成器返回的數目會受到0到

N之間整數數目的限制。因為常見情況下，偽隨機數生成器生成0到N之間的一個整數，返回的整數再除以N?？梢缘贸龅臄底挚偸翘幱?和1之間。對生成器隨后的調用采用第一次運行產生的整數，并將它傳給一個函數，以生成0到N之間的一個新整數，然后再將新整數除以N返回。5.1.2偽隨機數產生器4目前，常見隨機數發生器中N是232–1（大約等于40億），對于32位數字來說，這是最大的值。但在密碼學領域，40億個數根本不算大！

偽隨機數生成器將作為“種子”的數當作初始整數傳給函數。由偽隨機數生成器返回的每一個值完全由它返回的前一個值所決定。因此，最初的種子決定了這個隨機數序列。如果知道用于計算任何一個值的那個整數，那么就可以算出從這個生成器返回的下一個值。偽隨機數生成器是一個生成完全可預料的數列（稱為流）的確定性程序。一個編寫得很好的的PRNG可以創建一個序列，而這個序列的屬性與許多真正隨機數的序列的屬性是一樣的。

例如：（1）PRNG可以以相同幾率在一個范圍內生成任何數字；（2）PRNG可以生成帶任何統計分布的流；（3）由PRNG生成的數字流不具備可辨別的模。55.1.3基于密碼算法的隨機數產生器

1．使用軟件方法的隨機數產生器

一個常用的隨機數產生器是屬于線形擬合生成器一類的。這類生成器相當普遍，它們采用很具體的數學公式：Xn+1=(aXn

+b)modc即第

n+1個數等于第

n個數乘以某個常數

a，再加上常數

b。如果結果大于或等于某個常數

c，那么通過除以

c，并取它的余數來將這個值限制在一定范圍內。注意：a、b和

c通常是質數。

2．使用硬件方法的隨機數產生器

目前生成隨機數的幾種硬件設備都是用于商業用途。得到廣泛使用的設備是

ComScireQNG，它是使用并行端口連接到

PC的外部設備，它可以在每秒鐘生成20,000位，這對于大多數注重安全性的應用程序來說已經足夠了。另外Intel公司宣布他們將開始在其芯片組中添加基于熱能的硬件隨機數發生器，而且基本上不會增加客戶的成本。迄今為止，已經交付了一些帶有硬件

PRNG的

CPU。

65.1.4偽隨機數的評價標準

（1）看起來是隨機的，表明它可以通過所有隨機性統計檢驗。

現在的許多統計測試。它們采用了各種形式，但共同思路是它們全都以統計方式檢查來自發生器的數據流，嘗試發現數據是否是隨機的。

確保數據流隨機性的最廣為人知的測試套件就是

GeorgeMarsaglia

的

DIEHARD軟件包（請參閱http:///pub/diehard/）。另一個適合此類測試的合理軟件包是

pLab（請參閱http://random.mat.sbg.ac.at/tests/）。（2）它是不可預測的。即使給出產生序列的算法或硬件和所有以前產生的比特流的全部知識，也不可能通過計算來預測下一個隨機比特應是什么。（3）它不能可靠地重復產生。如果用完全同樣的輸入對序列產生器操作兩次將得到兩個不相關的隨機序列。

75.2序列密碼的概念及模型

序列密碼算法將明文逐位轉換成密文，如下圖所示。m密鑰流發生器（也稱為滾動密鑰發生器）輸出一系列比特流：K1，K2，K3，……Ki

。密鑰流（也稱為滾動密鑰）跟明文比特流，m1，m2，m3，……mi，進行異或運算產生密文比特流。

加密：

Ci=mi⊕Ki

在解密端，密文流與完全相同的密鑰流異或運算恢復出明文流。

解密：mi=Ci⊕Ki顯然，mi⊕Ki⊕Ki=mi8事實上，序列密碼算法其安全性依賴于簡單的異或運算和一次一密亂碼本。密鑰流發生器生成的看似隨機的密鑰流實際上是確定的，在解密的時候能很好的將其再現。密鑰流發生器輸出的密鑰越接近隨機，對密碼分析者來說就越困難。

如果密鑰流發生器每次都生成同樣的密鑰流的話，對攻擊來說，破譯該算法就容易了。

假的Alice得到一份密文和相應的明文，她就可以將兩者異或恢復出密鑰流。或者，如果她有兩個用同一個密鑰流加密的密文，她就可以讓兩者異或得到兩個明文互相異或而成的消息。這是很容易破譯的，接著她就可以用明文跟密文異或得出密鑰流。現在，無論她再攔截到什么密文消息，她都可以用她所擁有的密鑰流進行解密。另外，她還可以解密，并閱讀以前截獲到的消息。一旦Alice得到一明文/密文對，她就可以讀懂任何東西了。9這就是為什么所有序列密碼也有密鑰的原因。密鑰流發生器的輸出是密鑰的函數。

這樣，Alice有一個明文/密文對，但她只能讀到用特定密鑰加密的消息。

更換密鑰，攻擊者就不得不重新分析。

流密碼是將明文劃分成字符(如單個字母)，或其編碼的基本單元(如0,1數字)，字符分別與密鑰流作用進行加密，解密時以同步產生的同樣的密鑰流實現。流密碼強度完全依賴于密鑰序列的隨機性(Randomness)和不可預測性(Unpredictability)。

核心問題是密鑰流生成器的設計。保持收發兩端密鑰流的精確同步是實現可靠解密的關鍵技術。10流密碼的分類:1.自同步序列密碼

自同步序列密碼就是密鑰流的每一位是前面固定數量密文位的函數，下圖和下頁圖描述了其工作原理。其中，內部狀態是前面n比特密文的函數。該算法的密碼復雜性在于輸出函數，它收到內部狀態后生成密鑰序列位。11自同步流密碼SSSC(Self-SynchronousStreamCipher)

內部狀態i依賴于(kI,i-1,mi)，使密文ci不僅與當前輸入mi有關，而且由于ki對i的關系而與以前的輸入m1,m2,…,mi-1有關。一般在有限的n級存儲下將與mi-1,…,mi-n有關。12特點:①密鑰流不僅依賴于種子密鑰和密鑰流產生器的結構，還與密文流（或明文流）有關。初始向量IV在這里相當于初始密文的作用，要求收、發雙方必須相同。②自同步。解密只取決于先前特定數量的密文字符，因此，即使出現刪除、插入等非法攻擊，收方最終都能夠自動重建同步解密，因而收、發雙方不再需要外部同步。③有差錯傳播。因為密鑰流與密文流有關，所以一個密文的傳輸錯誤會影響下面有限個密文的解密。13自同步序列密碼舉例例

假設種子密鑰為k=h，之后的密鑰是上一個密文。采用移位密碼，明文為cryptography，列表給出它的加密和解密過程。一個字符的差錯傳播不需要同步142．同步序列密碼在同步序列密碼中，密鑰流的產生獨立于明文和密文。分組加密的OFB模式就是一個同步序列加密的例子。1）同步要求。在一個同步序列密碼中，發送方和接收方必須是同步的，用同樣的密鑰且該秘鑰操作在同樣的位置，才能保證解密。如果在傳輸過程中密文字符有插入或刪除導致同步丟失，則解密失敗，且只能通過重新同步來實現恢復。2）無錯誤傳輸。在傳輸期間，一個密文字符被改變只影響該字符的恢復，不會對后繼字符產生影響。152．同步序列密碼

同步流密碼SSC(SynchronousStreamCipher)：

內部狀態i與明文消息無關，密鑰流將獨立于明文。特點：對于明文而言，這類加密變換是無記憶的。但它是時變的。只有保持兩端精確同步才能正常工作。對主動攻擊時異常敏感而有利于檢測無差錯傳播(ErrorPropagation)16同步序列密碼同樣可防止密文中的插入和刪除，因為它們會使系統失去同步而立即被發現。然而，卻不能避免單個位被竄改。優點：具有自同步能力，強化了其抗統計分析的能力缺點：有n位長的差錯傳播。密鑰流序列的性質密碼設計者的最大愿望是設計出一個滾動密鑰生成器，使得密鑰經其擴展成的密鑰流序列具有如下性質：

極大的周期良好的統計特性抗線性分析抗統計分析。17實際上,序列密碼不可能做到“一次一密”但若密鑰流生成器生成的密鑰周期足夠長，且隨機性好，其安全強度可以得到保證！

因此，序列密碼的設計核心在于密鑰流生成器的設計，序列密碼的安全強度取決于密鑰流生成器生成的密鑰周期、復雜度、隨機（偽隨機）特性等。185.3線性反饋移位寄存器(linearfeedbackshiftregister，LFSR)異或表達式----線性反饋如果n級線性反饋移位寄存器產生的輸出序列的周期為2n-1，則稱為m序列產生器。m序列不僅周期長，而且偽隨機特性好，這正是序列密碼的密鑰流所需要的特性。195.3線性反饋移位寄存器產生密鑰序列的最重要部件是線性反饋移位寄存器(LFSR),是因為:

(1)LFSR非常適合于硬件實現;(2)能產生大的周期序列;(3)能產生較好統計特性的序列;(4)其結構能應用代數方法進行很好的分析.移位寄存器是流密碼產生密鑰流的一個主要組成部分。GF(2)上一個n級反饋移位寄存器由n個二元存儲器與一個反饋函數f(a1,a2,…,an)組成，如下頁圖所示。

20每一存儲器稱為移位寄存器的一級，在任一時刻，這些級的內容構成該反饋移位寄存器的狀態，每一狀態對應于GF(2)上的一個n維向量，共有2n種可能的狀態。每一時刻的狀態可用n長序列“a1,a2,…,an”n維向量“(a1,a2,…,an)”來表示，其中ai是第i級存儲器的內容。初始狀態由用戶確定，當第i個移位時鐘脈沖到來時，每一級存儲器ai都將其內容向下一級ai-1傳遞，并計算f(a1,a2,…,an)作為下一時刻的an。21反饋函數f(a1,a2,…,an)是n元布爾函數，即n個變元a1,a2,…,an

可以獨立地取0和1兩個可能的值，函數中的運算有邏輯與、邏輯或、邏輯補等運算，最后的函數值也為0或1。例：下圖是一個3級反饋移位寄存器，其初始狀態為(a1,a2,a3)=(1,0,1)，輸出可由下表求出。

即輸出序列為101110111011…，周期為4。22如果f(a1,a2,…,an)是(a1,a2,…,an)的線性函數，則稱之為線性反饋移位寄存器LFSR（linearfeedbackshiftregister），否則稱為非線性移位寄存器。此時f可寫為：f(a1,a2,…,an)=cna1

cn-1a2…c1an其中常數ci=0或1，是模2加法。ci=0或1可用開關的斷開和閉合來實現，如下圖所示，這樣的線性函數共有2n個。23輸出序列{at}滿足：an+t=cnatcn-1at+1…c1an+t-1

其中，t為非負正整數。線性反饋移位寄存器因其實現簡單、速度快、有較為成熟的理論等優點而成為構造密鑰流生成器的最重要的部件之一。例：下圖是一個5級線性反饋移位寄存器，其初始狀態為（a1,a2,a3,a4,a5）=(1,0,0,1,1)，可求出輸出序列為1001101001000010101110110001111100110…，周期為31。24在線性反饋移位寄存器中總是假定c1,c2,…,cn中至少有一個不為0，否則f(a1,a2,…,an)≡0，這樣的話，在n個脈沖后狀態必然是00…0，且這個狀態必將一直持續下去。

若只有一個系數不為0，設僅有cj不為0，實際上是一種延遲裝置。一般對于n級線性反饋移位寄存器，總是假定cn=1。n級線性反饋移位寄存器的狀態周期小于等于2n-1。輸出序列的周期與狀態周期相等，也小于等于2n-1。只要選擇合適的反饋函數便可使序列的周期達到最大值2n-1。

定義1：n級線性反饋移位寄存器產生的序列{ai}的周期達到最大值2n-1時，稱{ai}為n級m序列。25根據密碼學需要，對于線性移位寄存器需考慮以下問題：

（1）如何利用級數盡可能小的線性移位寄存器產生周期長、統計性能好的序列；（2）已知一個序列{ai}，如何構造一個盡可能短的線性移位寄存器來產生它。因為n級線性移位寄存器的輸出序列{ai}滿足遞推關系：

an+k=c1an+k-1c2an+k-2…cnak，對任何k≥1成立。這種遞推關系可用一個一元高次多項式

p(x)=1+c1x+…＋cn-1xn-1＋cnxn

表示，稱這個多項式為LFSR的特征多項式。

由于ai∈GF(2)(i=1,2,…,n)，所以共有2n組初始狀態，即有2n個遞推序列，其中非恒零的有2n-1個，記2n-1個非零序列的全體為G(p(x))。26

定義2：給定序列{ai}，冪級數，稱為該序列的生成函數。

定義3：設p(x)是GF(2)上的多項式，使p(x)|(xp-1)的最小p稱為p(x)的周期或階。

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

A(x)=Ф(x)/p(x)，其中

=(a1+a2x+…+anxn-1)+c1x(a1+a2x+…+an－1xn-2)+c2x(a1+a2x+…+an－2xn-3)+…+cn-1xn-1a1。

定理1說明了n級線性移位寄存器的特征多項式和它的生成函數之間的關系。定理2：若序列{ai}的特征多項式p(x)定義在GF(2)上，p是p(x)的周期，則{ai}的周期r|p。n級LFSR輸出序列的周期r不依賴于初始條件，而依賴于特征多項式p(x)。我們感興趣的是LFSR遍歷2n-1個非零狀態，這時序列的周期達到最大2n-1，這種序列就是m序列。27例3：設f(x)=x4+x3+x2+x+1是GF(2)上的不可約多項式，但是它的輸出序列是000110001100011…，周期是5，不是m序列。解：f(x)的不可約性由多項式x，x+1，x2+x+1不能整除f(x)而得。對于k≥5，輸出序列用ak=ak-1ak-2ak-3ak－4

檢驗即可。

定義4：僅能被非零常數或者本身的常數倍除盡，不能被其他多項式整除的多項式稱為不可約多項式。

特征多項式滿足什么條件時，LFSR的輸出序列為m序列。

定理3：n級LFSR產生的序列有最大周期2n-1的必要條件是其特征多項式為不可約多項式。該定理的逆不成立，即LFSR產生的特征多項式為不可約多項式，但其輸出序列不一定是m序列。

28定義5：若n次不可約多項式p(x)的階為2n-1，稱其為n次本原多項式。定理4：{ai}為n級m序列的充要條件是其特征多項式p(x)為n次本原多項式。例4：設p(x)=x4+x+1,是4次本原多項式，以其為特征多項式的線性移位寄存器的輸出是10010001111010110010001111010…,周期是24-1=15的m序列。

解：p(x)|(x15-1),但是不存在l<15，使得p(x)|(xl-1)，所以p(x)階是15。

p(x)的不可約性由x，x+1，x2+x+1不能整除p(x)而得，因此p(x)是本原多項式。

對于k≥5，輸出序列用ak=ak-1ak－4

檢驗即可。

雖然n級線性移位寄存器產生的m序列具有良好的偽隨機性，但是直接用其構造密鑰流序列是極不安全的。因為利用2n個輸出位可以找到它的起始狀態和特征多項式。29若特征多項式p(x)=x3+x+1，初始狀態為（101）的移位寄存器產生序列為(101001)。設明文為（011010），那么密文為（110011）。破譯者計算mc得到密鑰系列(101001)，那么可以得到下列矩陣方程式：

得到c3＝1，c2＝0，c1＝1，從而得到特征多項式：p(x)=x3+x+130線性反饋移位寄存器舉例一個周期的輸出序列100010011010111m序列產生器序列周期長，偽隨機特性好。LFSR的結構過于簡單，只要攻擊者得到2n位密文和對應的明文，就可以導出n級LFSR序列產生器的代數結構。不適宜直接作為密鑰流產生器使用。315.4非線性序列簡介

線性移位寄存器序列密碼在已知明文攻擊下是可破譯的這一事實促使人們向非線性領域探索。目前研究的比較充分的由非線性移位寄存器，對線性移位寄存器進行非線性組合等。為了使密鑰流生成器輸出的二元序列盡可能復雜，應保證其周期盡可能大、線性復雜度和不可預測性盡可能高，因此常使用多個LFSR來構造二元序列，稱每個LFSR的輸出序列為驅動序列，顯然密鑰流生成器輸出序列的周期不大于各驅動序列周期的乘積，因此，提高輸出序列的線性復雜度應從極大化其周期開始。

1．Geffe序列生成器

Geffe序列生成器由3個LFSR組成（如下圖），其中LFSR2作為控制生成器使用。32當LFSR2輸出1時，LFSR2與LFSR1相連接；當LFSR2輸出0時，LFSR2與LFSR3相連接。

若設LFSRi的輸出序列為{a(i)k}(i=1,2,3)，則輸出序列{bk}可以表示為：設LFSRi的特征多項式分別為ni次本原多項式，且ni兩兩互素，則Geffe序列的周期為

，線性復雜度為

。332．J-K觸發器

其中，x1和x2分別是J和K端的輸入。J-K觸發器如下圖所示，它的兩個輸入端分別用J和K表示，其輸出ck不僅依賴于輸入，還依賴于前一個輸出位ck-1，即在下圖中，令驅動序列{ak}和{bk}分別為m級和n級m序列，則有

利用J-K觸發器的非線性序列生成器

如果令c-1=0，則輸出序列的最初3項為：

當m與n互素且a0+b0=1時，序列{ck}的周期為(2m-1)(2n-1)。343．Pless生成器

Pless生成器由8個LFSR、4個J-K觸發器和1個循環計數器構成，由循環計數器進行選通控制，如下圖所示。假定在時刻t輸出第t(mod4)個單元，則輸出序列為：a0b1c2d3a4b5d6355.鐘控發生器

鐘控發生器是由控制序列（由一個或多個移位寄存器來控制生成）的當前值決定被采樣的序列寄存器移動次數（即由控制序列的當前值確定采樣序列寄存器的時鐘脈沖數目）。控制序列和被采樣序列可以是源于同一個LFSR（稱為自控），也可以源于不同的LFSR（稱為他控），還可以相互控制（稱為互控）。鐘控發生器示意圖如下圖所示。36

當控制序列當前值為1時，被采樣序列生成器被時鐘驅動k次后輸出；當控制序列當前值為0時，被采樣序列生成器被時鐘驅動d次后輸出。

另外，停走式發生器也是一種鐘控模型，它由2個LFSR組成。其中，LFSR-1控制LFSR-2的時鐘輸入。

當且僅當LFSR-1的時間t-1的輸出為1時，LFSR-2在時間t改變狀態（也即LFSR-1輸出時鐘脈沖，使LFSR-2進行輸出并反饋以改變移位寄存器的狀態）。

375．收縮和自收縮發生器

收縮發生器是又控制序列的當前值決定被采樣序列移位寄存器是否輸出。

該發生器由2個LFSR組成。LFSR-1、LFSR-2分別按各自時鐘運行，LFSR-1在時間t-1時刻的輸出為1時，LFSR-2在時間t時刻輸出為密鑰流，否則舍去。

自收縮發生器從一個LFSR抽出2條序列，其中一條為控制序列，另一條為百采樣序列。當控制序列輸出為1時，采樣序列輸出為密鑰流，否則舍去。此外，還有多路復合序列，這類序列也歸結為非線性組合序列。38基于LFSR的序列密碼非常適合于硬件實現，但是不特別適合軟件實現。這導致出現了一些關于序列密碼被計劃用于快速軟件實現的新建議，因為這些建議大部分具有專利，因此這里不討論它們的技術細節。比較常用的序列密碼是A5、SEAL和RC4序列密碼算法，A5是典型的基于LFSR的序列密碼算法，SEAL和RC4不是基于LFSR的序列密碼算法，而是基于分組密碼的輸出反饋模式（OFB）和密碼反饋模式（CFB）來實現的。其他不基于LFSR的序列密碼生成器的安全性基于數論問題的難解性，這些生成器比基于LFSR的生成器要慢很多。5.5常用的序列密碼算法39A5序列密碼算法是利用歐洲數字蜂窩移動電話（GSM）加密的序列密碼算法，它用于從用戶手機至基站的連接加密，GSM會話每幀數據包含228比特，A5算法每次會話將產生228比特的密鑰，算法的密鑰長度為64比特，還包含有一個22比特的幀數。A5算法有兩個版本：強A5/1和弱A5/2。A5算法是一種典型的基于LFSR的序列密碼算法，它由三個LFSR組成，是一種集控制與停走于一體的鐘控模型，但是A5算法沒有完全公開，因而各種資料的描述也不盡相同，重要是第二個和第三個LFSR的聯接多項式以及鐘控的位置。A5算法的3個LFSR中LFSR-1、LFSR-2、LFSR-3的級數分別為19、22和23。LFSR-1的反饋抽頭是18、17、16、13，LFSR-2的反饋抽頭是21、20、16、12，LFSR-3的反饋抽頭是22、21、18、17（如下頁圖的數字表示抽頭的位置）。5.5.1A5序列密碼算法4041425.5.2SEAL序列密碼算法434445464748

5.5.3RC4序列密碼體制

RC4是RonRivest1987年為RSA設計，是一個可變密鑰長度、面向字節操作的序列密碼

基本思想：

對于n位長的字，它總共N=2n個可能的內部置換狀態矢量S，這些狀態是保密的，密鑰流K由S中N個元素按照一定方式選出一個元素而生成。每生成一個K值，S中的元素就被重新置換一次密鑰調度算法（KSA）偽隨機數生成算法（PRGA）49密鑰調度算法KSAKSA算法描述如下：Fori=0toN-1doS[i]=i;j=0;Fori=0toN-1doJ=(j+S[i]+K[ImodL])modN;Swap(S[i],S[j])50偽隨機數生成算法PRGAi=0；J=0；While(true）i=（i+1）modN；J=（j+S[i])modN;Swap(S[i],S[j]);T=(S[i]+S[j])modN;Outputk=S[t];51實例525354RC4目前使用在：（1）SSL（安全套接字）中廣泛使用（2）WEP(WiredEquivalentPrivacy:有線對等保密)IEEE802.11(/159/2027659_1.shtml)55三、密鑰流的局部隨機性檢驗真隨機序列的特性①統計的隨機性。即序列能夠通過數學上已知的所有的隨機性檢驗，滿足這個要求的序列稱為偽隨機序列。②不可預測性。即無論采用何種方法，也無法根據以前的任意多元素預測序列的下一個元素。③不可再生性。即使使用完全相同的輸入參數，也無法產生完全相同的輸出序列。真隨機序列特性雖好，但難以在實際密碼系統中應用。實際密碼系統中使用的密鑰流都是偽隨機序列。56三、密鑰流的局部隨機性檢驗1、偽隨機序列的統計特性戈龍（Golomb）提出的三條隨機性公設：①平衡特性。任何隨機的二元周期序列，在一個周期P內，不同元素出現的概率應該是相同的。如果P為偶數，一個周期內所含有的“0”和“1”的個數應該相等；如果P為奇數，一個周期內所含有的“0”和“1”的個數應該只相差1個。57戈龍（Golomb）提出的三條隨機性公設②游程特性。游程是指一串相同的元素序列，其前導和后繼都不同，而相同元素的個數叫做游程的長度。由一串“1”構成的游程叫做“1”游程（也叫塊組），由一串“0”構成的游程叫做“0”游程（也叫間隔）。例如，序列“1110010”有1個長度為3的“1”游程（111）、1個長度為2的“0”游程（00）、1個長度為1的“1”游程（1）和1個長度為1的“0”游程（0）。任意隨機的二元周期序列，在一個周期P內，長度為n的游程數應占游程總數的1/2n，并且對于每一種長度，“0”游程的個數應和“1”游程的個數同樣多。58戈龍（Golomb）提出的三條隨機性公設③自相關特性。假定S是一個周期為P的二元序列，對于任意固定的τ，把S