摘  要： 討論了FSR+NLF類序列密碼的可重構處理結構設計，包括總體結構設計、可重構FSR結構設計、可重構NLF結構設計以及互連網絡結構設計。采用該結構的密碼運算單元可以根據需要實現多種此類序列密碼，具有結構簡單、可擴展、運行速度高等特點。
關鍵詞： 序列密碼;可重構計算;線性反饋移位寄存器;非線性反饋移位寄存器;非線性函數

    可重構計算的思想最早由加利福尼亞大學洛杉磯分校的Estrin教授[1]提出來的?？芍貥嬘嬎銢]有嚴格的定義，目前學術界普遍接受的定義是：使用集成了可編程硬件的系統進行計算，該可編程硬件的功能可由一系列定時變化的物理可控點來定義[2]。從這個定義可以看出，可重構計算是通過對結構可變的硬件進行軟件配置，以適應不同算法的處理，故其既具有軟件的靈活性，又具備了ASIC硬件的高速性，是解決資源受限類算法，如多媒體處理算法、DSP、加解密算法的一種理想選擇。
    明文數據流與密鑰流逐位地加密成密文數據流的密碼體制稱為序列密碼(Sequence Cipher)。當密鑰流滿足離散無記憶二元均勻分布，即完全隨機時，則該體制就是“一次一密”密碼體制，香農證明該體制是不可破譯的[3]。實際應用中,序列密碼的密鑰流是用確定的算法產生的，即密鑰流是偽隨機的，但可以通過數學的手段盡可能地提高密鑰流的隨機性,最大程度地逼近“一次一密”，因此序列密碼的保密性較高。此外，由于序列密碼具有容易實現、實時性好、錯誤傳播有限等優點，被廣泛應用于政府、軍事等重要部門。
　 根據序列密碼設計所采用的理論不同，可將序列密碼分為4類：基于信息論設計、基于系統論設計、基于復雜度理論設計和基于隨機化理論設計的序列密碼[4]。其中第1、3、4類序列密碼涉及的數學理論多樣，適于用軟件的方法實現,不適于專用硬件或可重構硬件來實現。而第2類基于系統論設計的序列密碼是目前最為實用的序列密碼，這類序列密碼的密鑰流生成器大多由1個或多個線性或非線性反饋移位寄存器LFSR/NLFSR(Linear/Non-linear Feedback Shift Register)和1個非線性函數NLF(Non-linear Function)構成，本文把符合該特點的序列密碼簡稱為FSR+NLF類序列密碼。這類密碼由于具有相似的運算單元，很適合采用可重構硬件實現。FSR+NLF類序列密碼又分為2個子類： (1)若序列密碼中1個或多個FSR狀態位參與NLF運算，則稱為非線性濾波型序列密碼，相應的NLF稱為非線性濾波函數，其結構如圖1所示，Grain[5]就屬于這類序列密碼；(2)若序列密碼中只有各個FSR的最低狀態位參與NLF運算，則稱為非線性組合型序列密碼，相應的NLF稱為非線性組合函數，其結構如圖2所示，Achterbahn[6]就屬于這類序列密碼。根據FSR運算域的不同，FSR+NLF類序列密碼又有GF(2)域上和GF(2n)域上之分，本文將詳細討論GF(2)域上該類序列密碼的可重構處理結構設計，非線性濾波型和非線性組合型序列密碼均可以在該可重構處理結構上實現。

1 總體結構設計
    對現有的GF(2)域上FSR+NLF類序列密碼分析發現，絕大多數此類密碼的FSR個數不超過8個，長度不超過256 bit，因此其可重構處理總體結構設計如圖3所示。從圖中可以看出，此類密碼的可重構處理結構主要由8個可重構FSR和1個可重構NLF通過互連網絡連接而成。其中，8個可重構FSR分成完全相同的兩組，每組中的4個可重構FSR的最大長度分別為32 bit、64 bit、128 bit和256 bit，以滿足不同算法的需要,又可以減少互連資源。該可重構處理結構采用了特殊的互連網絡結構，外部送入的配置指令經譯碼電路譯碼后存入配置寄存器組，再由配置寄存器組對各可重構FSR、可重構NLF和互連網絡進行配置，從而構成相應的序列密碼算法處理結構。

2 可重構FSR結構設計
   

     基于以上基本理論，1個最長級數為n的可重構FSR結構設計如圖4所示。其結構總體上分為3部分：中間是1個級數為n的移位寄存器SR，其移動方向為從n-1級到0級；SR以上的部分為反饋函數部分；SR以下部分為前饋函數部分，因為有的序列密碼的FSR帶有前饋輸出(例如Achterbahn)。

　 對現有的FSR+NLF類序列密碼反饋函數分析發現：反饋函數F中二次及二次以上項的總數不超過20項。為此，該結構中為一次項設計了1個配置寄存器CR1；為二次及二次以上項設計了30個配置寄存器CR2~CR31，共計31個配置寄存器。這31個配置寄存器的位數均與SR的級數相同，為n bit。
　 該結構中反饋函數部分工作原理：假設反饋函數F=x₀+x₃+x_n-2+x₁x₂+x₅x_n-1+x₆x₉x₁₂+x₁x₃x₇x₁₀x_n-3x_n-2，配置時，將CR1的第0、3、n-2位配置為“1”，其余位配置為“0”；將CR2的第1、2位配置為“0”，其余位配置為“1”；將CR3的第5、n-1位配置為“0”，其余位配置為“1”；將CR4的第6、9、12位配置為“0”，其余位配置為“1”；將CR5的第1、3、7、10、n-3、n-2位配置為“0”，其余位配置為“1”；其余的配置寄存器各位均配置為“1”。配置完成后，SR的各級狀態與CR1的對應位相“與”，得到的各位結果相“異或”即得到F的所有一次項模2加的和,即x₀+x₃+x_n-2的結果；SR的各級狀態與CR2的對應位相“或”，得到的各位結果再一起相“與”即得到x1x2的結果；CR3、CR4、CR5進行與CR2相同的運算后可分別得到x₅x_n-1、x₆x₉x₁₂、x₁x₃x₇x₁₀x_n-3x_n-2的結果，其余各配置寄存器運算與CR21也相同，得到的結果為“1”。然后，通過1個32 bit的組合配置寄存器CRcom將各項結果組合運算后即得到F，F反饋給SR的最后一級，CRcom的配置方式和運算過程與CR1相同。CRcom在進行組合運算時，還有1個外部反饋值FV_ext參與了運算，這是因為一些序列密碼中，有外部數據參與了FSR的反饋(例如Grain)。
　 該可重構FSR結構中，SR以下是1個前饋函數部分，因為在有些序列密碼中，FSR帶有前饋輸出(例如Achterbahn)。前饋函數F′ 是FSR某些級狀態的1個線形函數，其中必定包含FSR的最低一級狀態。該結構設計中，采用1個n bit的前饋函數配置寄存器CRff和SR的各級狀態進行組合運算即得到前饋輸出FF_out，CRff的配置方式和運算過程與CR11相同。當CRff中只有某一位被配置為“1”時，則FF_out輸出即為FSR對應一級的狀態，特別是這樣可以得到FSR最低一級的狀態輸出，用于另一個FSR的FV_ext輸入或NLF的輸入。
　 該可重構FSR的最長級數為n，通過對其各個寄存器的配置，可以將其配置為級數小于等于n的任意FSR。例如，當n=32時，要得到一個級數為30的FSR，則將配置寄存器CR1的第0位和第1位都配置為“0”，將CR2~CR31的第0位和第1位都配置為“1”，則SR的第0級和第1級沒有參與反饋運算，相應的FSR退化為30級，其有效級為第2~31級。
　 n位輸出信號線Data_out 輸出FSR的n級狀態，當NLF為濾波函數時作為其輸入。外部輸入信號線有配置使能信號線Cfg_en、運行使能信號線Run _en、時鐘Clk以及32 bit寬的配置數據線Cfg_data。配置使能信號Cfg_en有效后,外部配置寄存器組通過Cfg_data對FSR內部各寄存器進行配置，配置完成后運行使能信號Run_en變為有效，FSR在時鐘控制下開始運行。
3 可重構NLF結構
　 FSR+NLF 類序列密碼中的NLF單元對輸入的信號進行非線性變換后輸出密鑰，其定義與(1)式相同，故可重構NLF 的結構與可重構FSR結構中的反饋函數部分相似。與可重構FSR結構不同的是,在可重構NLF中設計了32個配置寄存器NCR1~NCR32，而且由于輸入數據線Data_in寬度固定為32 bit，因此32個配置寄存器NCR1~NCR32均為32 bit。輸入數據Data_in分別與各配置寄存器進行組合運算后得到NLF各項結果，各項結果通過NCRcom組合運算后輸出NLF值，即密鑰Key。
4 互連網絡結構
    本文討論的序列密碼可重構處理結構可以實現濾波型和非線性組合型兩類序列密碼，因此，其互連網絡結構應能滿足這兩類序列密碼的連接需要，基于此要求設計的互連網絡結構如圖5所示。

    該互連網絡結構總的設計思路：當實現非線性組合型序列密碼時,可重構FSR1~FSR8的前饋輸出信號FF_out與可重構NLF單元的數據輸入信號Data_in(0~7) 分別相連；當實現濾波型序列密碼時，由于此類密碼中FSR一般為1個，個別為2個，因此選擇組1中級數最長的2個可重構FSR3和FSR4參與互連，組2中的4個和組1中的其他2個可重構FSR這種情況下不參與互連。
    具體連接規則是：可重構FSR3的128 bit狀態輸出信號Data_out分別與可重構FSR1~FSR8的前饋輸出信號FF_out通過8個129選1選路器MUX0~MUX7與可重構NLF的數據輸入信號Data_in(0~7)相連；可重構FSR3的128 bit狀態輸出信號Data_out再通過8個128選1選路器MUX8~MUX15與可重構NLF的數據輸入信號Data_in(8~15)相連；可重構FSR4的128 bit狀態輸出信號Data_out通過16個128選1選路器MUX16~MUX31與可重構NLF的數據輸入信號Data_in(16~31)相連；同時，為了滿足有些序列密碼算法中某一個FSR的最低一級輸出要參與另一個FSR的反饋的情況,將可重構FSR3、FSR4的FF_out分別與對方的FV_ext相連。
　 本文論述的FSR+NLF類序列密碼可重構處理結構的配置寄存器都是32  bit的整數倍，故規定其重構粒度為32  bit，配置數據線Cfg_data寬度為32  bit。從功能上來看，該可重構處理結構除可以滿足FSR+NLF類序列密碼的處理需求外，還可以和自收縮式發生器、有限狀態機等單元結合使用來處理一些該類衍生的序列密碼。
　 此外,該可重構處理結構具有可擴展性，可重構FSR的個數、各可重構FSR的最大長度、各可重構FSR的反饋函數部分與可重構NLF中二次以上項的項數都可以根據需要進行擴展。
　 本文論述的FSR+NLF類序列密碼可重構處理結構的原型已經在Altera公司生產的EP2S60F1020C5型 FPGA上實現，所需資源約為2.2萬門，最高工作頻率為200 MHz。由此可見，該可重構處理結構簡單，實現時占用資源較少，運行速度較高。
參考文獻
[1]     ESTRIN G, BUSSEL B. Parallel processing in a restructurable computer system[J]. IEEE Trans. Elect comput, 1963. 747-755.
[2]     COMPTON K, HAUCK S. Reconfigurable computing: a  survey of systems and software[J]. ACM Computing Surveys.    2002, 34（2）：171-210.
[3]     SHANNON C E. Communication theory of secrecy systems     [EB/OL]. http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf. 2009-01.
[4]     馮登國，裴定一.密碼學導引[M]. 北京：科學出版社，1999:486-100.
[5]     GAMMEL B, GOTTFERT R. The achterbahn stream cipher [EB/OL]. http://www.ecrypt.eu.org/stream/papers.html. 2009-02.
[6]     HELL M, JOHANSSON T, MEIER W. Grain-a stream cipher for constrained  environments[EB/OL].
    http://www.it.Ith.se/grain/grainV1.pdf. 2009.02.