摘 要：針對直接由線性反饋移位寄存器(LFSR) 產(chǎn)生的序列的線性復(fù)雜度太小，難以經(jīng)受線性逼近攻擊的問題。在研究序列密碼設(shè)計理論和LFSR的并聯(lián)理論的基礎(chǔ)上，提出一種基于FPGA（Field Programmable Gate Array，現(xiàn)場可編程門陣列）的利用3個LFSR同步并聯(lián)構(gòu)成一個序列生成器的方法。利用VHDL（VHSIC Hardware Description Language）語言編寫其實(shí)現(xiàn)程序，并應(yīng)用FPGA 設(shè)計工具Xilinx ISE7.1i，調(diào)用ModelSim SE6.1c對其進(jìn)行仿真。仿真結(jié)果和密碼強(qiáng)度評估理論分析表明這種序列生成器產(chǎn)生的序列密碼具有很高的強(qiáng)度和抗破譯能力。

關(guān)鍵詞：序列生成器；線性反饋移位寄存器；LFSR同步并聯(lián)；FPGA

中圖分類號：TP368.1 文獻(xiàn)標(biāo)識碼：B

文章編號：1004-373X(2008)10-125-04

Design of Sequence Generator with Synchronous Parallel LFSR Based on FPGA

WANG Xing，SHEN Xiaolin

(School of Information and Communication Engineering，North University of China，Taiyuan，030051，China)

Abstract：The sequence generated by single Linear Feedback Shift Register(LFSR)directly can not resist the linear approximation attack，since it has low linear complexity.The thesis presents a method of constituting a sequence generator with three synchronous parallel LFSRs based on a Field Programmable Gate Array(FPGA) on the foundation of study of the theory of sequence design and parallel LFSR，and provides the implementation program with VHSIC Hardware Description Language(VHDL)，finally uses the designing instrument of FPGA——Xilinx ISE7.1i，and calls ModelSim SE6.1c to simulate it.The result of simulation and the assessment of intensity indicate that the consequence generated by the generator specially designed possess high intensity and the ability of resisting deciphering.

Keywords：sequence generator;LFSR(Linear Feedback Shift Register);synchronous parallel LFSR;FPGA

1 引 言

設(shè)計性能良好的密鑰序列始終是流密碼學(xué)的一個研究熱點(diǎn)。線性反饋移位寄存器（Linear Feedback Shift Register，LFSR）因其實(shí)現(xiàn)簡單、速度快、具有良好的統(tǒng)計學(xué)特性和較為成熟的理論等優(yōu)點(diǎn)而成為產(chǎn)生Golomb偽隨機(jī)序列的主要手段。但是，由于直接由線性反饋移位寄存器產(chǎn)生的序列的線性復(fù)雜度太小，難以經(jīng)受線性逼近攻擊。如果將幾個LFSR按照某種特殊的算法組合成一個偽隨機(jī)序列生成器，就可以獲得加密安全性能方面的額外收益。目前，存在幾種線性和非線性的組合，最基本的組合方法就是LFSR串聯(lián)和并聯(lián)。另外，由于可以用FPGA進(jìn)行逐位的設(shè)計，所以基于LFSR的序列密碼的算法用FPGA實(shí)現(xiàn)會比用DSP實(shí)現(xiàn)更為有效。

2 序列密碼設(shè)計的理論基礎(chǔ)

序列密碼的設(shè)計涉及的數(shù)學(xué)理論較多，根據(jù)Rainer Rueppel的理論，有4種不同的方法設(shè)計序列密碼^[1]：

系統(tǒng)理論方法 使用一套基本的設(shè)計原理和準(zhǔn)則，保證每一個設(shè)計對密碼分析者來說是一個困難且未知的問題；

信息理論方法 使密碼分析者不能得到明文，不論密碼分析者做了多少工作，永遠(yuǎn)得不到惟一解；

復(fù)雜性理論方法 使密碼系統(tǒng)基于或等同于一些已知的難題，比如因子分解或解離散對數(shù)；

隨機(jī)性方法 通過迫使密碼分析者檢測大量無用的數(shù)據(jù)來產(chǎn)生一個難于控制的大難題；

系統(tǒng)理論方法的優(yōu)點(diǎn)是設(shè)計出序列密碼可直接滿足要求，因此目前幾乎所有實(shí)用的序列密碼的設(shè)計都基于系統(tǒng)理論方法。

多年來，人們已總結(jié)出基于LFSR的序列密碼設(shè)計標(biāo)準(zhǔn)中的一套設(shè)計準(zhǔn)則，歸納起來主要有4種：大周期狀態(tài)序列自動生成的設(shè)計技術(shù)、鐘控邏輯的設(shè)計技術(shù)、非線性組合邏輯的設(shè)計技術(shù)和RAM表及參數(shù)的使用技術(shù)。在4種基本設(shè)計技術(shù)中，大周期狀態(tài)序列自動生成的設(shè)計技術(shù)是此類密碼體制的基礎(chǔ)，用此確保生成的亂數(shù)序列具有足夠大的周期。后3項(xiàng)基本設(shè)計技術(shù)或通過動作的不規(guī)則使得輸出序列不再具有原來的線性關(guān)系，或通過對輸出的線性序列做非線性的組合變換提高復(fù)雜度。一個密碼體制的設(shè)計，通常復(fù)合地采用其中的某幾項(xiàng)技術(shù)，尤其是RAM表及參數(shù)的使用技術(shù)有可能可以迅速提高密碼算法的整體強(qiáng)度。

序列密碼設(shè)計最終要達(dá)到5個基本目的：長周期；大的線性復(fù)雜度，包括線性復(fù)雜性曲線和局部線性復(fù)雜度；統(tǒng)計特性（如理想的k元分布）；混亂與擴(kuò)散，使每個輸出比特位必定是所有密鑰位的復(fù)雜變換，子結(jié)構(gòu)中的冗余度必須擴(kuò)大到大范圍的統(tǒng)計特性中去；布爾函數(shù)的非線性準(zhǔn)則，比如m階相關(guān)免疫、與線性函數(shù)的距離以及雪崩準(zhǔn)則等。

3 序列密碼的算法設(shè)計

實(shí)際使用的序列密碼體制。按其LFSR是否有不規(guī)則運(yùn)動及LFSR的輸出序列是否經(jīng)過非線性組合邏輯的變換可分為3種^[1]：

（1） 僅采用鐘控邏輯的密碼體制。采用鐘控邏輯的密碼體制，鐘控LFSR的輸出序列直接參與亂數(shù)的線性合成。這里需要說明的是，僅采用鐘控邏輯的密碼體制，是指受鐘控邏輯控制的LFSR的輸出序列在合成亂數(shù)序列時不再經(jīng)過非線性組合邏輯的變化。至于鐘控邏輯中則完全可能采用非線性邏輯以生成控制序列。

（2） 不采用鐘控邏輯而采用對線性序列做非線性組合變換的密碼體制。此種密碼體制中各LFSR都做規(guī)則運(yùn)動，線性序列經(jīng)過非線性組合邏輯的變換生成亂數(shù)。

（3） 復(fù)合采用鐘控邏輯與非線性組合邏輯的密碼體制。此種密碼體制中，LFSR在鐘控邏輯的作用下輸出鐘控序列，但輸出的鐘控序列作為非線性組合邏輯的輸入經(jīng)過變換后參與亂數(shù)的合成。

從一般意義上說，第三種密碼體制可獲得較之前2種密碼體制更強(qiáng)的抗破譯能力。但這3種密碼體制中，任何一種密碼體制在設(shè)計科學(xué)、密鑰管理體制嚴(yán)密、實(shí)際運(yùn)行穩(wěn)定可靠的條件下，都可以獲得理想的抗破譯強(qiáng)度；反之，在密碼設(shè)計、密鑰管理體制設(shè)置、實(shí)際運(yùn)行的3個環(huán)節(jié)中存在弱點(diǎn)，則任何一種密碼體制都有被破譯的可能。正確地評估一種密碼體制設(shè)計的強(qiáng)度，主要不是考察其采用的基本環(huán)節(jié)的數(shù)量，而是考察其邏輯的內(nèi)在強(qiáng)度。

4 線性反饋移位寄存器

移位寄存器（特別是線性反饋移位寄存器）是序列密碼中密鑰流生成器的一個重要組成部分。一個GF（2）上的反饋移位寄存器可用圖1表示。

圖1中標(biāo)有a1，a2，…，an－1，an的小方框表示二值（0，1）存儲單元，可以是一個雙穩(wěn)態(tài)觸發(fā)器，信號流從左向右。這n個二值存儲單元稱為該反饋移位寄存器的級。在任一時刻，這些級的內(nèi)容構(gòu)成該反饋移位寄存器的狀態(tài)。這個反饋移位寄存器的狀態(tài)對應(yīng)于一個GF（2）上的n維向量，共有2n種可能的狀態(tài)。每個時刻的狀態(tài)可用n長序列a1，a2，…，an－1，an或n維向量(a1，a2，…，an－1，an)表示，其中ai為當(dāng)時第i級存儲器中的內(nèi)容。

圖1 線性反饋移位寄存器

在主時鐘確定的周期區(qū)間上，每一級存儲器這個反饋移位寄存器ai都將其內(nèi)容向下一級ai－1傳遞，并根據(jù)存儲器當(dāng)時的狀態(tài)計算f(a1，a2，…，an－1，an)作為an下一時間周期的內(nèi)容，稱函數(shù)f(a1，a2，…，an－1，an)為反饋函數(shù)，其中反饋函數(shù)f(a1，a2，…，an－1，an)為n元布爾函數(shù)。在時鐘脈沖時，如果反饋移位寄存器的狀態(tài)為si=(ai，ai+1，…，ai+n－1)，則:

ai+n=f(ai，ai+1，…，ai+n－1)(1)

這個ai+n又是移位寄存器的輸入。在ai+n的驅(qū)動下，移位寄存器的各個數(shù)據(jù)向前推移一位，使?fàn)顟B(tài)變?yōu)閟i+1=(ai+1，…，ai+n)，同時，整個移位寄存器的輸出為ai。由此得到一系列數(shù)據(jù)：a1，a2，…，an。

該序列稱為滿足關(guān)系式（1）的一個反饋移位寄存器序列。

若式（1）中的移位寄存器的反饋函數(shù)f(a1，a2，…，an－1，an)是(a1，a2，…，an－1，an)的線性函數(shù)，則稱為線性移位寄存器LFSR（Linear Feedback Shift Register）。

設(shè)f(a1，a2，…，an－1，an)為線性函數(shù)，則f可寫成：

f(a1，a2，…，an－1，an)=cna1⊕cn－1c2⊕…⊕c1an

其中ci=0或1，c1，c2，…，cn為反饋系數(shù)，假定其中至少有一個系數(shù)非零，一般總假定cn=1。

5 LFSR的并聯(lián)理論

2個移位寄存器LFSR1和LFSR2的并聯(lián)可用圖2來表示。

圖2 LFSR的并聯(lián)

設(shè)LFSR1和LFSR2的生成多項(xiàng)式分別為本原多項(xiàng)式f1(x)=1+d1x+d2x2+…+dnxn和f2(x)=1+d1′x+d2′x2+…+dm′xm，并且滿足(f1(x)，f2(x))=1，其初始狀態(tài)分別為(a0，a1，…，an－1)，(b0，b1，…，bm－1)，所以他們輸出序列的多項(xiàng)式分別為：

a(x)=a(x)f1(x)=a0+a1x+a2x2+a3x3+…

b(x)=b(x)f2(x)=b0+b1x+b2x2+b3x3+…

設(shè)c(x)=c0+c1x+c2x2+…+ckxk+…為輸出序列c的多項(xiàng)式表示，則:

c(x)=f2(x)a(x)+f1(x)b(x)f1(x)+f2(x)

由f1（x），f2（x）的本原性知f1（x），f2(x)|(a(x)+f1(x)b(x))，而且deg［f2（x）a(x)+f1(x)b(x)］

6 序列密碼的實(shí)現(xiàn)

序列密碼的實(shí)現(xiàn)分為軟件和硬件2種方法^[1]。軟件實(shí)現(xiàn)是利用計算機(jī)完成密碼編制，產(chǎn)生亂數(shù)流的過程。硬件實(shí)現(xiàn)是借助于物理器件，利用邏輯電路完成密碼編制，產(chǎn)生亂數(shù)流的過程。目前，所有的序列加密產(chǎn)品都是特定的硬件加密形式，這些硬件的加/解密模塊被嵌入到通信線路中，對通過的信息進(jìn)行加密。雖然序列密碼的軟件產(chǎn)品應(yīng)用很廣，但是，硬件產(chǎn)品才是政府首腦和軍事應(yīng)用的主要選擇。

加密算法通常由很多復(fù)雜的數(shù)學(xué)運(yùn)算組成，序列密碼中的長比特位的乘法和除法運(yùn)算在普通微處理器上運(yùn)行效率較低。盡管一些密碼設(shè)計者不斷嘗試使他們的算法更適合軟件實(shí)現(xiàn)，但特殊的硬件（如FPGA或ASIC）將一直占速度的優(yōu)勢。通常，軟件實(shí)現(xiàn)的密碼算法加/解密速率在2 Mb/s以下，而硬件實(shí)現(xiàn)的密碼算法加/解密速率可達(dá)100 Mb/s以上。在今天要求百兆甚至千兆高速加密的情況下，硬件實(shí)現(xiàn)序列密碼將是發(fā)展趨勢。硬件加密具有效率高、安全性好、易于安裝等優(yōu)勢。

本文討論的基于線性反饋移位寄存器LFSR的序列生成算法不需要大規(guī)模的表，非常適合用FPGA實(shí)現(xiàn)^[3]。

7 基于FPGA的并聯(lián)LFSR序列生成器設(shè)計

基于以上對序列密碼設(shè)計理論和并聯(lián)LFSR理論的研究，本文提出一種基于FPGA的利用3個LFSR并聯(lián)構(gòu)成一個LFSR序列生成器的方法，并利用VHDL語言編寫其實(shí)現(xiàn)程序，原程序代碼如下：



entity lfsr8bc is

port ( clk:instd_logic;

y : out std_logic_vector(8 downto 1));

end lfsr8bc;

architecture Behavioral of lfsr8bc is

signal ca : std_logic_vector(8 downto 1):=\"10010001\"; 

signal tca : std_logic_vector(8 downto 1):=\"11010001\";

signal mca : std_logic_vector(8 downto 1):=\"10001010\";

begin

process(clk) 

begin

if(clk′event and clk=′1′)then

ca(1) <= not (ca(7) xor ca(8)); --LFSR1

for i in 8 downto 2 loop

ca(i) <= ca(i-1); -- shift one 

end loop;

for n in 8 downto 1 loop--LFSR2

tca(n) <= ca(n);

end loop;

tca(1) <= not (tca(7) xor tca(8));

for j in 8 downto 2 loop 

tca(j) <= tca(j-1); -- shift one 

end loop;

for n in 8 downto 1 loop --LFSR3[HJ*4]

mca(n) <= tca(n);

end loop;

mca(1) <= not (mca(7) xor mca(8));

for j in 8 downto 2 loop 

mca(j) <= mca(j-1); -- shift one 

end loop;

end if;

end process ;

process(ca，tca，mca) 

begin 

for k in 1 to 8 loop

y(k) <= ca(k) or tca(k) or mca(k); 

end loop;

end process;

end Behavioral;

其工作原理是：3個LFSR在同一個時鐘信號的控制下工作，也即3個LFSR的運(yùn)行節(jié)拍保持一致，在每個時鐘周期，3個LFSR同步移位，最后3個LFSR產(chǎn)生的序列并聯(lián)，也就是3個序列按位進(jìn)行對應(yīng)邏輯或（or）操作，其結(jié)果作為序列生成器的輸出序列。其原理圖如圖3所示。

圖3 3個LFSR同步并聯(lián)序列發(fā)生器示意圖

另外，還可以把3個LFSR產(chǎn)生的序列進(jìn)行邏輯與（and），邏輯異或（xor）等非線性操作以使序列生成器產(chǎn)生的最終輸出序列達(dá)到很高的線性復(fù)雜度和抗破譯能力。

應(yīng)用FPGA設(shè)計工具Xilinx ISE7.1i，調(diào)用ModelSim SE6.1c對其進(jìn)行仿真，仿真結(jié)果如下。

圖4 三個LFSR同步并聯(lián)或（or）操作仿真結(jié)果

圖5 三個LFSR同步并聯(lián)異或（xor）操作仿真結(jié)果

8 強(qiáng)度評估

密碼強(qiáng)度的評估分為2種情況：理論強(qiáng)度和實(shí)際強(qiáng)度。對于以上序列生成器產(chǎn)生的序列密碼，線性復(fù)雜度較高，從實(shí)際強(qiáng)度的角度分析，由于LFSR的8位初始狀態(tài)就有一定的隨機(jī)性，而且經(jīng)過3個LFSR并聯(lián)進(jìn)行逐位邏輯或（or）、邏輯與（and）、邏輯異或（xor）等非線性操作產(chǎn)生的序列隨機(jī)性更大，即使破譯者可以獲得足夠多的信息來破譯密碼，但是破譯者的工作從時間和和經(jīng)濟(jì)方面來說是不可行的，其破譯難度比單LFSR大得多。

9 結(jié) 語

本文針對直接由線性反饋移位寄存器(LFSR) 產(chǎn)生的序列的線性復(fù)雜度太小，難以經(jīng)受線性逼近攻擊的問題，研究LFSR的并聯(lián)理論，提出一種基于FPGA的利用3個LFSR同步并聯(lián)構(gòu)成一個序列生成器的方法，還提出對3個LFSR產(chǎn)生的序列逐位進(jìn)行邏輯或（or）、邏輯與（and）、邏輯異或（xor）等非線性操作以產(chǎn)生高復(fù)雜度和高抗破譯能力的序列。并對其進(jìn)行仿真。仿真結(jié)果和密碼強(qiáng)度評估理論分析表明這種序列生成器產(chǎn)生的序列密碼具有很高的強(qiáng)度和抗破譯能力。本文提出的方法為高強(qiáng)度密碼序列生成器的發(fā)展和進(jìn)一步研究提供了重要依據(jù)，并為其實(shí)現(xiàn)提供了一種新的更為快速、高效、安全和可靠的途徑。

參 考 文 獻(xiàn)

［1］王衍波，薛通.應(yīng)用密碼學(xué)［M］.北京：機(jī)械工業(yè)出版社，2003.

［2］楊義先，鈕心忻.應(yīng)用密碼學(xué)［M］.北京:北京郵電大學(xué)出版社，2005.

［3］Uwe Meyer-Baese.數(shù)字信號處理的FPGA實(shí)現(xiàn)［M］.劉凌，譯.北京:清華大學(xué)出版社，2006.

［4］Taejoo Chang，Iickho Song.Maximum Length Cellular Automaton Sequences and Its Application［J］.Signal Processing，1997，56：199-203.

［5］Slobodan Bojanic，Gabriel Caffarena.FPGA for Pseudorandom Generator Cryptanalysis［J］.Microprocessors and Microsystems，2006(3):63-71.

［6］Jiang Zhengtao，Zhan Yang.Two Methods of Directly Constructing Probabilistic Public-Key Encryption Primitives Based on Third-order LFSR Sequences［J］.Applied Mathematics and Computation，2005(171) :900-911.

［7］白恩鍵，王靜，肖國鎮(zhèn).［a，b］-自縮減生成器［J］.計算機(jī)科學(xué)，2004，31(5):107-110.

［8］崔巋，李承恕.線性反饋移位寄存器的改進(jìn)算法及其電路實(shí)現(xiàn)［J］.北京交通大學(xué)學(xué)報，2004，28(5):70-72.

［9］束禮寶，宋克柱，王硯方.偽隨機(jī)數(shù)發(fā)生器的FPGA實(shí)現(xiàn)與研究［J］.2003，8(3):121-124.

［10］陳玉泉.一種并行CRC算法的實(shí)現(xiàn)方法[J].現(xiàn)代電子技術(shù)，2005，28(22):21-23，26.



作者簡介 王 星 女，1983年出生。重慶人，中北大學(xué)（原華北工學(xué)院）通信與信息工程學(xué)院，碩士研究生。主要從事數(shù)字圖像處理及CPLD/FPGA的應(yīng)用研究。

沈小林 中北大學(xué)副教授、研究生導(dǎo)師。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。