摘 要：在介紹了現(xiàn)有隨機(jī)序列的優(yōu)缺點(diǎn)以及分析隨機(jī)序列主要產(chǎn)生方法的基礎(chǔ)上，提出了一種基于循環(huán)替換原理的偽隨機(jī)序列產(chǎn)生方法，并用FPGA加以實(shí)現(xiàn)。該方法產(chǎn)生的偽隨機(jī)序列完全符合FIPS140-2標(biāo)準(zhǔn)，并具有周期長(zhǎng)、線性復(fù)雜度高、相關(guān)性好以及產(chǎn)生時(shí)間短的特性，能廣泛應(yīng)用于信息安全等系統(tǒng)中。

關(guān)鍵詞：循環(huán)；替換；相關(guān)性；線性復(fù)雜度

中圖分類號(hào)：TN929-1 文獻(xiàn)標(biāo)識(shí)碼：B

文章編號(hào)：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

隨機(jī)序列在流密碼、信道編碼、擴(kuò)頻通信等領(lǐng)域有著廣泛的應(yīng)用，特別是在信息安全領(lǐng)域，他是以現(xiàn)代密碼學(xué)為基礎(chǔ)的信息安全系統(tǒng)的基石。幾乎所有已知的信息安全體系中的協(xié)議和方法都離不開隨機(jī)序列^[1]，因此研制高性能的隨機(jī)序列顯得尤為重要。評(píng)價(jià)一個(gè)偽隨機(jī)序列優(yōu)劣的基本準(zhǔn)則是偽隨機(jī)性，現(xiàn)在有許多指標(biāo)來(lái)描述一個(gè)周期序列的偽隨機(jī)性，比如周期、線性復(fù)雜度、均衡性、相關(guān)性、穩(wěn)定性等。雖然現(xiàn)在已經(jīng)研制出一些較高性能的偽隨機(jī)序列，如m序列、GMW序列以及廣義GMW序列等，但他們都還存在一些不足。周期為2n-1的m序列雖具有良好的多維分布和游程分布，但其線性復(fù)雜度只有n；GMW序列以及廣義GMW序列，雖具有良好自相關(guān)特性，也具有良好的多維分布和游程分布，但其線性復(fù)雜度也僅僅為n的冪^[2]。本文的目標(biāo)研制出一個(gè)高性能的偽隨機(jī)序列，本序列具有周期長(zhǎng)、線性復(fù)雜度高、相關(guān)性好以及產(chǎn)生時(shí)間短、產(chǎn)生方法簡(jiǎn)單的特性。

1 循環(huán)替換的偽隨機(jī)序列

本文的偽隨機(jī)序列產(chǎn)生方法是在分析現(xiàn)在主要的3種隨機(jī)序列產(chǎn)生方法的優(yōu)缺點(diǎn)的基礎(chǔ)上提出來(lái)的。現(xiàn)在主要的三種隨機(jī)序列產(chǎn)生方法^[3]是：

基于純計(jì)算機(jī)算法的隨機(jī)序列產(chǎn)生方法 該方法是目前最常用隨機(jī)序列產(chǎn)生方法，他基于事先確定的序列生成方法，依賴“種子”來(lái)產(chǎn)生隨機(jī)序列，該方法對(duì)于給定的輸入，具有確定的輸出，因此從理論上講這樣的隨機(jī)序列都是可以預(yù)測(cè)的，因此被稱為“偽隨機(jī)序列產(chǎn)生方法”；

基于人工的方法 這類方法通過(guò)擲硬幣、扔股子等隨機(jī)方式獲得隨機(jī)序列，是目前人工的最安全的隨機(jī)序列產(chǎn)生方法之一，但這種方法效率極低，不實(shí)用，不能適應(yīng)現(xiàn)代信息安全系統(tǒng)對(duì)隨機(jī)序列產(chǎn)生量的需求；

基于隨機(jī)噪聲發(fā)生檢測(cè)方法 這類隨機(jī)序列產(chǎn)生方法通過(guò)產(chǎn)生、測(cè)量自然界的具有高度隨機(jī)性的噪聲信號(hào)，但這種產(chǎn)生方法需要信號(hào)發(fā)生裝置，而這些裝置結(jié)構(gòu)復(fù)雜、操作繁瑣、價(jià)格高，產(chǎn)生的隨機(jī)序列效率低、速度慢，不方便也不實(shí)用。

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

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

2 性能分析

下面將具體分析構(gòu)造出來(lái)的序列的周期、相關(guān)特性、隨機(jī)特性和線性復(fù)雜度。

2.1 周期和相關(guān)特性

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

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

2.2 隨機(jī)性測(cè)試

在所有隨機(jī)序列質(zhì)量檢測(cè)方法中，以美國(guó)國(guó)際技術(shù)標(biāo)準(zhǔn)局NIST于2001年5月發(fā)布的關(guān)于密碼系統(tǒng)的信息安全標(biāo)準(zhǔn)FIPS 140-2^[5](Federal Information Processing Publication，F(xiàn)IPS)最為出名。在FIPS 140-2中指定了4種測(cè)試方式對(duì)隨機(jī)序列的質(zhì)量指標(biāo)進(jìn)行測(cè)試：?jiǎn)伪忍販y(cè)試(the monobit test)、撲克測(cè)試(the poker test)、游程測(cè)試(the runs test)、長(zhǎng)游程測(cè)試(long runs test)。我們采用FIPS 140-2標(biāo)準(zhǔn)對(duì)本文產(chǎn)生的序列進(jìn)行測(cè)試，測(cè)試結(jié)果全部通過(guò)，表2列出了其中的3組測(cè)試結(jié)果。

2.3 線性復(fù)雜度

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

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

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

以上從3個(gè)大的方面對(duì)構(gòu)造出來(lái)的序列的性能進(jìn)行了仿真測(cè)試，從上面的結(jié)果可以看出，我們構(gòu)造的序列具有良好的特性。

3 FPGA實(shí)現(xiàn)

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

4 結(jié) 語(yǔ)

本文具體提出了一種偽隨機(jī)序列產(chǎn)生方法，并對(duì)由此方法產(chǎn)生的序列進(jìn)行性能測(cè)試，結(jié)果顯示本文提出的方法是一種高效的偽隨機(jī)序列產(chǎn)生方法，能滿足信息安全等系統(tǒng)的要求。同時(shí)本文的結(jié)構(gòu)是一種可擴(kuò)展的結(jié)構(gòu)，通過(guò)不同的代替以及循環(huán)機(jī)制，還可以產(chǎn)生更大線性復(fù)雜度以及周期的序列，具有較好的工程使用價(jià)值。

參考文獻(xiàn)

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

［2］胡予濮.一類理想自相關(guān)序列的偽隨機(jī)性[J].電子學(xué)報(bào)，2003，31(2):245-247.

［3］肖攸安，周祖德.高效真隨機(jī)序列生成方法的研究[J].計(jì)算機(jī)工程與應(yīng)用，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.

作者簡(jiǎn)介

陳瑞森 男， 1981年出生，助教，博士生。主要研究方向?yàn)榧呻娐吩O(shè)計(jì)，無(wú)線電。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文?！?/p>