基于循環替換原理的高性能偽隨機序列

摘 要：在介紹了現有隨機序列的優缺點以及分析隨機序列主要產生方法的基礎上，提出了一種基于循環替換原理的偽隨機序列產生方法，并用FPGA加以實現。該方法產生的偽隨機序列完全符合FIPS140-2標準，并具有周期長、線性復雜度高、相關性好以及產生時間短的特性，能廣泛應用于信息安全等系統中。

關鍵詞：循環；替換；相關性；線性復雜度

中圖分類號：TN929-1 文獻標識碼：B

文章編號：1004373X(2008)0511003

High Performance Pseudorandom Sequence Based on Substitution and Recurrence Structure

CHEN Ruisen1，2

(1.Xiamen Ocean College，Xiamen，361012，China;2.EDA Lab，Department of Physics，Xiamen University，Xiamen，361005，China)

Abstract：Based on the introduction of the merit and shortcoming and the analysis of the generate methods of the main random sequences，we propose a new method which is based on the substitution and recurrence structure，and the method is implemented by FPGA.The generated sequences by this method not only can pass the test of the FIPS 140-2 standard，but also have high performance:long period，high linear complexity，good correlation function value and high generation speed，it can be used widely in information security system and so on.

Keywords：recurrence;substitution;correlation;linear complexity

隨機序列在流密碼、信道編碼、擴頻通信等領域有著廣泛的應用，特別是在信息安全領域，他是以現代密碼學為基礎的信息安全系統的基石。幾乎所有已知的信息安全體系中的協議和方法都離不開隨機序列^[1]，因此研制高性能的隨機序列顯得尤為重要。評價一個偽隨機序列優劣的基本準則是偽隨機性，現在有許多指標來描述一個周期序列的偽隨機性，比如周期、線性復雜度、均衡性、相關性、穩定性等。雖然現在已經研制出一些較高性能的偽隨機序列，如m序列、GMW序列以及廣義GMW序列等，但他們都還存在一些不足。周期為2n-1的m序列雖具有良好的多維分布和游程分布，但其線性復雜度只有n；GMW序列以及廣義GMW序列，雖具有良好自相關特性，也具有良好的多維分布和游程分布，但其線性復雜度也僅僅為n的冪^[2]。本文的目標研制出一個高性能的偽隨機序列，本序列具有周期長、線性復雜度高、相關性好以及產生時間短、產生方法簡單的特性。

1 循環替換的偽隨機序列

本文的偽隨機序列產生方法是在分析現在主要的3種隨機序列產生方法的優缺點的基礎上提出來的。現在主要的三種隨機序列產生方法^[3]是：

基于純計算機算法的隨機序列產生方法 該方法是目前最常用隨機序列產生方法，他基于事先確定的序列生成方法，依賴“種子”來產生隨機序列，該方法對于給定的輸入，具有確定的輸出，因此從理論上講這樣的隨機序列都是可以預測的，因此被稱為“偽隨機序列產生方法”；

基于人工的方法 這類方法通過擲硬幣、扔股子等隨機方式獲得隨機序列，是目前人工的最安全的隨機序列產生方法之一，但這種方法效率極低，不實用，不能適應現代信息安全系統對隨機序列產生量的需求；

基于隨機噪聲發生檢測方法 這類隨機序列產生方法通過產生、測量自然界的具有高度隨機性的噪聲信號，但這種產生方法需要信號發生裝置，而這些裝置結構復雜、操作繁瑣、價格高，產生的隨機序列效率低、速度慢，不方便也不實用。

考慮到現在存在的一些高性能隨機序列生成方法速度慢、效率低，無法滿足信息安全系統需求等問題，以及上面分析的后兩種方法中存在的局限，所以不再采用后兩種方法，采用第一種方法，同時加入一些改進方法，使他產生的序列具備周期足夠長，復雜度高、相關性好以及產生時間短的特性，以符合現代信息安全系統的要求。我們采用不可分解多相式式(1)來構造二進制偽隨機序列，同時在輸出過程中，對固定的輸出元素進行替換，采用替換在硬件上實現比較簡單：

上面的替換原理其實在以前已經有人做了研究，文獻[4]中就對序列中有k個符號替換、插入或刪除的情況進行過分析，也有人對單符號替換、插入和刪除的情況進行研究，研究表明線性復雜度會有變化(增加或減少)，這就提供了一種提高線性復雜度的可能方法。但如果只對一個周期為N的序列進行替換、插入或刪除等變換，線性復雜度的提高是很有限的，并且不能保證線性復雜度一定會提高，還需要加入循環的原理，才可能極大地提高序列的周期和線性復雜度。因為00，01，10，11總共有4×3×2=24種組合方法，所以如果每個周期N的序列用一種組合來替代其中相應的位，那同一個“種子”通過替換原理就可以產生24個不同的序列，把24個序列進行組合，那同一個種子產生序列的周期就可能擴大到24N，線性復雜度也可能大大的提高，仿真實驗證明這種方法是可行的，周期擴大到原來的24倍，線性復雜度也大大提高，同時序列還有良好的隨機性和相關特性。

2 性能分析

下面將具體分析構造出來的序列的周期、相關特性、隨機特性和線性復雜度。

2.1 周期和相關特性

一個序列如果對于所有的i都滿足Si=Si+N ，則他的周期為N，經過仿真可以確定，序列的最小周期為24N，達到749 952。同時他具有很好的相關特性，他具有尖銳的自相關特性和幾乎處處為零的互相關特性。自相關特性ΘS，S(Γ)檢查的是序列和他本身移動Γ位后兩序列的一致性情況;互相關特性 ΘS，T(Γ) 檢查的是序列S和T序列移動Γ位后的序列的一致性情況。公式ΘS，S(Γ) 定義如下:

表1列出了3個實際仿真值，從這個表中，就可以知道本文構造的序列具有尖銳的自相關特性和幾乎處處為零的互相關特性。

2.2 隨機性測試

在所有隨機序列質量檢測方法中，以美國國際技術標準局NIST于2001年5月發布的關于密碼系統的信息安全標準FIPS 140-2^[5](Federal Information Processing Publication，FIPS)最為出名。在FIPS 140-2中指定了4種測試方式對隨機序列的質量指標進行測試：單比特測試(the monobit test)、撲克測試(the poker test)、游程測試(the runs test)、長游程測試(long runs test)。我們采用FIPS 140-2標準對本文產生的序列進行測試，測試結果全部通過，表2列出了其中的3組測試結果。

2.3 線性復雜度

序列線性復雜度是衡量序列隨機性的重要指標，著名的Berlekamp-Massey^[6]算法指出，當我們得到一個序列中連續2C(s)個位時(C(s)表示這個序列的復雜度)，就可以知道整個序列。由此可見，一個隨機性強的序列必須擁有大的線性復雜度，當然線性復雜度高并不代表著就安全，這還與其他性質有關，如相關性等，在上面已經分析過。現在計算線性復雜度的主要有Chan-Games算法^[7]和文獻[8]算法等，不同的算法得到的線性復雜度可以差別很大，但從不同的算法得到的線性復雜度的大小可以反映出序列的隨機指標。其中Chan-Games算法對周期為2n的序列更加有效，主要應用Chan-Games 算法和文獻[8]對我們的序列進行線性復雜度測試。

Chan-Games 算法的基本原理是：如果一個序列具有周期2n，那么可以把這個序列分成兩部分S1和S2，S1代表序列的前2n-1位，S2代表序列的后2n -1位，把S1和S2相應位進行相加并對2取余，結果得到一個2n-1位的序列B，如果B為全0的序列，則C(S)=C(S1)=C(S2)，否則C(S)=2n-1+C(B)，依次類推，可得到最后的復雜度。Chan-Games的算法原理決定了他只能具體計算周期2n的序列的線性復雜度，本文序列的周期為749 912，并不符合Chan-Games算法的要求，因此只應用Chan-Games算法對序列的前524 288位(219)的線性復雜度進行計算，前524 288位的線性復雜度就可以反映出本文序列的線性復雜度情況。

文獻[8]算法的基本原理是：他對序列的周期沒有限制，他先看序列的第一位，第一位前面肯定找不到已經出現和他相同的位，把他看成子序列，然后看第2位，如果前面(第2位的前面)不能找到和他相同的位，則第2位也形成子序列，否則繼續看第2位和第3位合起來的兩位序列，看前面(第3位以前)的序列中有沒有和他們相同的，如果沒有則第2位和第3位也形成子序列，如果有的話，則看第2，3，4位合起來的序列的情況，依次類推。例如一個序列為0001101001000101，那么他可以分成以下幾個子序列0，001，10，100，1000，101，那么他的線性復雜度可以看成6。表3是采用Chan-Games 算法和文獻[8]算法對本文序列的線性復雜度進行計算的結果，從表中可以看出本文的序列具有高的線性復雜度。

以上從3個大的方面對構造出來的序列的性能進行了仿真測試，從上面的結果可以看出，我們構造的序列具有良好的特性。

3 FPGA實現

隨機產生器是否容易用硬件來實現也是一個重要的方面，如在信息安全領域，需要加密的數字量是很大的，增長也很快，如果隨機序列產生過程以及加密過程能在同一硬件模塊中實現，將能更好地節省芯片面積、存儲面積、芯片接口以及設計時間等。因此用硬件描述語言對本隨機序列產生方法進行描述，進行前仿真，然后綜合進行后仿真，最后下載到Xilinx公司的xc2v1000 FPGA上加以驗證。現場可編程陣列(FPGA)在電子領域的應用越來越廣泛，在很多高速設計和高速測試的場合下，在FPGA中直接構造偽隨機序列發生器是一種很好的選擇。下面為截取的部分FPGA輸出序列。

4 結 語

本文具體提出了一種偽隨機序列產生方法，并對由此方法產生的序列進行性能測試，結果顯示本文提出的方法是一種高效的偽隨機序列產生方法，能滿足信息安全等系統的要求。同時本文的結構是一種可擴展的結構，通過不同的代替以及循環機制，還可以產生更大線性復雜度以及周期的序列，具有較好的工程使用價值。

參考文獻

［1］Bruce Schneier.Applied Cryptography:Protocols，Algorithms，and Source Code in C [M].Second Edition.New York:John Wiley Sons，Inc，1996.

［2］胡予濮.一類理想自相關序列的偽隨機性[J].電子學報，2003，31(2):245-247.

［3］肖攸安，周祖德.高效真隨機序列生成方法的研究[J].計算機工程與應用，2006(16):1-3.

［4］Jiang S，Dai Z，Imamura K.Liner Complexities of a Sequence Obtained from a Periodic Sequence by Either Substituting，Inserting or Deleting k Symbols Within One Period[J].IEEE Transactions on Information Theory，2000，46(3):1 174-1 177.

［5］National Institute of Standards and Technology[S].Federal Information Processing Standards Publication FIPS 140-2:Security Requirements for Cryptographic Modules，2001.

［6］May J L.Shift-Register Synthesis and BCH Decoding[J].IEEE Trans.Inform.Theory，1969，15(1):122-127.

［7］Games R，Chan A.A Fast Algorithm for Determining the Complexity of a Binary Sequence with Period 2n[J].IEEE Trans Inform Theory，1983，29(1):144-146.

［8］[JP2]Abraham Lempel，Jacob ZIV.On the Complexity of Finite Sequences[J].IEEE Trans.Inform.Theory，1976，22(1):75-81.

作者簡介

陳瑞森 男， 1981年出生，助教，博士生。主要研究方向為集成電路設計，無線電。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”