基于ＦＰＧＡ的同步并聯ＬＦＳＲ序列生成器設計

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

關鍵詞：序列生成器；線性反饋移位寄存器；LFSR同步并聯；FPGA

中圖分類號：TP368.1 文獻標識碼：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 引 言

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

2 序列密碼設計的理論基礎

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

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

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

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

隨機性方法 通過迫使密碼分析者檢測大量無用的數據來產生一個難于控制的大難題；

系統理論方法的優點是設計出序列密碼可直接滿足要求，因此目前幾乎所有實用的序列密碼的設計都基于系統理論方法。

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

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

3 序列密碼的算法設計

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

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

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

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

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

4 線性反饋移位寄存器

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

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

圖1 線性反饋移位寄存器

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

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

這個ai+n又是移位寄存器的輸入。在ai+n的驅動下，移位寄存器的各個數據向前推移一位，使狀態變為si+1=(ai+1，…，ai+n)，同時，整個移位寄存器的輸出為ai。由此得到一系列數據：a1，a2，…，an。

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

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

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

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

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

5 LFSR的并聯理論

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

圖2 LFSR的并聯

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

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

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

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

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 序列密碼的實現

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

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

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

7 基于FPGA的并聯LFSR序列生成器設計

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



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的運行節拍保持一致，在每個時鐘周期，3個LFSR同步移位，最后3個LFSR產生的序列并聯，也就是3個序列按位進行對應邏輯或（or）操作，其結果作為序列生成器的輸出序列。其原理圖如圖3所示。

圖3 3個LFSR同步并聯序列發生器示意圖

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

應用FPGA設計工具Xilinx ISE7.1i，調用ModelSim SE6.1c對其進行仿真，仿真結果如下。

圖4 三個LFSR同步并聯或（or）操作仿真結果

圖5 三個LFSR同步并聯異或（xor）操作仿真結果

8 強度評估

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

9 結 語

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

參 考 文 獻

［1］王衍波，薛通.應用密碼學［M］.北京：機械工業出版社，2003.

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

［3］Uwe Meyer-Baese.數字信號處理的FPGA實現［M］.劉凌，譯.北京:清華大學出版社，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］白恩鍵，王靜，肖國鎮.［a，b］-自縮減生成器［J］.計算機科學，2004，31(5):107-110.

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

［9］束禮寶，宋克柱，王硯方.偽隨機數發生器的FPGA實現與研究［J］.2003，8(3):121-124.

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



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

沈小林 中北大學副教授、研究生導師。

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