摘 要： 討論了FSR+NLF類序列密碼的可重構(gòu)處理結(jié)構(gòu)設計，包括總體結(jié)構(gòu)設計、可重構(gòu)FSR結(jié)構(gòu)設計、可重構(gòu)NLF結(jié)構(gòu)設計以及互連網(wǎng)絡結(jié)構(gòu)設計。采用該結(jié)構(gòu)的密碼運算單元可以根據(jù)需要實現(xiàn)多種此類序列密碼，具有結(jié)構(gòu)簡單、可擴展、運行速度高等特點。
關鍵詞： 序列密碼;可重構(gòu)計算;線性反饋移位寄存器;非線性反饋移位寄存器;非線性函數(shù)
可重構(gòu)計算的思想最早由加利福尼亞大學洛杉磯分校的Estrin教授[1]提出來的。可重構(gòu)計算沒有嚴格的定義，目前學術界普遍接受的定義是：使用集成了可編程硬件的系統(tǒng)進行計算，該可編程硬件的功能可由一系列定時變化的物理可控點來定義[2]。從這個定義可以看出，可重構(gòu)計算是通過對結(jié)構(gòu)可變的硬件進行軟件配置，以適應不同算法的處理，故其既具有軟件的靈活性，又具備了ASIC硬件的高速性，是解決資源受限類算法，如多媒體處理算法、DSP、加解密算法的一種理想選擇。
明文數(shù)據(jù)流與密鑰流逐位地加密成密文數(shù)據(jù)流的密碼體制稱為序列密碼(Sequence Cipher)。當密鑰流滿足離散無記憶二元均勻分布，即完全隨機時，則該體制就是“一次一密”密碼體制，香農(nóng)證明該體制是不可破譯的[3]。實際應用中,序列密碼的密鑰流是用確定的算法產(chǎn)生的，即密鑰流是偽隨機的，但可以通過數(shù)學的手段盡可能地提高密鑰流的隨機性,最大程度地逼近“一次一密”，因此序列密碼的保密性較高。此外，由于序列密碼具有容易實現(xiàn)、實時性好、錯誤傳播有限等優(yōu)點，被廣泛應用于政府、軍事等重要部門。
根據(jù)序列密碼設計所采用的理論不同，可將序列密碼分為4類：基于信息論設計、基于系統(tǒng)論設計、基于復雜度理論設計和基于隨機化理論設計的序列密碼[4]。其中第1、3、4類序列密碼涉及的數(shù)學理論多樣，適于用軟件的方法實現(xiàn),不適于專用硬件或可重構(gòu)硬件來實現(xiàn)。而第2類基于系統(tǒng)論設計的序列密碼是目前最為實用的序列密碼，這類序列密碼的密鑰流生成器大多由1個或多個線性或非線性反饋移位寄存器LFSR/NLFSR(Linear/Non-linear Feedback Shift Register)和1個非線性函數(shù)NLF(Non-linear Function)構(gòu)成，本文把符合該特點的序列密碼簡稱為FSR+NLF類序列密碼。這類密碼由于具有相似的運算單元，很適合采用可重構(gòu)硬件實現(xiàn)。FSR+NLF類序列密碼又分為2個子類： (1)若序列密碼中1個或多個FSR狀態(tài)位參與NLF運算，則稱為非線性濾波型序列密碼，相應的NLF稱為非線性濾波函數(shù)，其結(jié)構(gòu)如圖1所示，Grain[5]就屬于這類序列密碼；(2)若序列密碼中只有各個FSR的最低狀態(tài)位參與NLF運算，則稱為非線性組合型序列密碼，相應的NLF稱為非線性組合函數(shù)，其結(jié)構(gòu)如圖2所示，Achterbahn[6]就屬于這類序列密碼。根據(jù)FSR運算域的不同，F(xiàn)SR+NLF類序列密碼又有GF(2)域上和GF(2n)域上之分，本文將詳細討論GF(2)域上該類序列密碼的可重構(gòu)處理結(jié)構(gòu)設計，非線性濾波型和非線性組合型序列密碼均可以在該可重構(gòu)處理結(jié)構(gòu)上實現(xiàn)。
1 總體結(jié)構(gòu)設計
對現(xiàn)有的GF(2)域上FSR+NLF類序列密碼分析發(fā)現(xiàn)，絕大多數(shù)此類密碼的FSR個數(shù)不超過8個，長度不超過256 bit，因此其可重構(gòu)處理總體結(jié)構(gòu)設計如圖3所示。從圖中可以看出，此類密碼的可重構(gòu)處理結(jié)構(gòu)主要由8個可重構(gòu)FSR和1個可重構(gòu)NLF通過互連網(wǎng)絡連接而成。其中，8個可重構(gòu)FSR分成完全相同的兩組，每組中的4個可重構(gòu)FSR的最大長度分別為32 bit、64 bit、128 bit和256 bit，以滿足不同算法的需要,又可以減少互連資源。該可重構(gòu)處理結(jié)構(gòu)采用了特殊的互連網(wǎng)絡結(jié)構(gòu)，外部送入的配置指令經(jīng)譯碼電路譯碼后存入配置寄存器組，再由配置寄存器組對各可重構(gòu)FSR、可重構(gòu)NLF和互連網(wǎng)絡進行配置，從而構(gòu)成相應的序列密碼算法處理結(jié)構(gòu)。
2 可重構(gòu)FSR結(jié)構(gòu)設計
基于以上基本理論，1個最長級數(shù)為n的可重構(gòu)FSR結(jié)構(gòu)設計如圖4所示。其結(jié)構(gòu)總體上分為3部分：中間是1個級數(shù)為n的移位寄存器SR，其移動方向為從n-1級到0級；SR以上的部分為反饋函數(shù)部分；SR以下部分為前饋函數(shù)部分，因為有的序列密碼的FSR帶有前饋輸出(例如Achterbahn)。
對現(xiàn)有的FSR+NLF類序列密碼反饋函數(shù)分析發(fā)現(xiàn)：反饋函數(shù)F中二次及二次以上項的總數(shù)不超過20項。為此，該結(jié)構(gòu)中為一次項設計了1個配置寄存器CR1；為二次及二次以上項設計了30個配置寄存器CR2~CR31，共計31個配置寄存器。這31個配置寄存器的位數(shù)均與SR的級數(shù)相同，為n bit。
該結(jié)構(gòu)中反饋函數(shù)部分工作原理：假設反饋函數(shù)F=x0+x3+xn-2+x1x2+x5xn-1+x6x9x12+x1x3x7x10xn-3xn-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的各級狀態(tài)與CR1的對應位相“與”，得到的各位結(jié)果相“異或”即得到F的所有一次項模2加的和,即x0+x3+xn-2的結(jié)果；SR的各級狀態(tài)與CR2的對應位相“或”，得到的各位結(jié)果再一起相“與”即得到x1x2的結(jié)果；CR3、CR4、CR5進行與CR2相同的運算后可分別得到x5xn-1、x6x9x12、x1x3x7x10xn-3xn-2的結(jié)果，其余各配置寄存器運算與CR21也相同，得到的結(jié)果為“1”。然后，通過1個32 bit的組合配置寄存器CRcom將各項結(jié)果組合運算后即得到F，F(xiàn)反饋給SR的最后一級，CRcom的配置方式和運算過程與CR1相同。CRcom在進行組合運算時，還有1個外部反饋值FV_ext參與了運算，這是因為一些序列密碼中，有外部數(shù)據(jù)參與了FSR的反饋(例如Grain)。
該可重構(gòu)FSR結(jié)構(gòu)中，SR以下是1個前饋函數(shù)部分，因為在有些序列密碼中，F(xiàn)SR帶有前饋輸出(例如Achterbahn)。前饋函數(shù)F′ 是FSR某些級狀態(tài)的1個線形函數(shù)，其中必定包含F(xiàn)SR的最低一級狀態(tài)。該結(jié)構(gòu)設計中，采用1個n bit的前饋函數(shù)配置寄存器CRff和SR的各級狀態(tài)進行組合運算即得到前饋輸出FF_out，CRff的配置方式和運算過程與CR11相同。當CRff中只有某一位被配置為“1”時，則FF_out輸出即為FSR對應一級的狀態(tài)，特別是這樣可以得到FSR最低一級的狀態(tài)輸出，用于另一個FSR的FV_ext輸入或NLF的輸入。
該可重構(gòu)FSR的最長級數(shù)為n，通過對其各個寄存器的配置，可以將其配置為級數(shù)小于等于n的任意FSR。例如，當n=32時，要得到一個級數(shù)為30的FSR，則將配置寄存器CR1的第0位和第1位都配置為“0”，將CR2~CR31的第0位和第1位都配置為“1”，則SR的第0級和第1級沒有參與反饋運算，相應的FSR退化為30級，其有效級為第2~31級。
n位輸出信號線Data_out 輸出FSR的n級狀態(tài)，當NLF為濾波函數(shù)時作為其輸入。外部輸入信號線有配置使能信號線Cfg_en、運行使能信號線Run _en、時鐘Clk以及32 bit寬的配置數(shù)據(jù)線Cfg_data。配置使能信號Cfg_en有效后,外部配置寄存器組通過Cfg_data對FSR內(nèi)部各寄存器進行配置，配置完成后運行使能信號Run_en變?yōu)橛行В現(xiàn)SR在時鐘控制下開始運行。
3 可重構(gòu)NLF結(jié)構(gòu)
FSR+NLF 類序列密碼中的NLF單元對輸入的信號進行非線性變換后輸出密鑰，其定義與(1)式相同，故可重構(gòu)NLF 的結(jié)構(gòu)與可重構(gòu)FSR結(jié)構(gòu)中的反饋函數(shù)部分相似。與可重構(gòu)FSR結(jié)構(gòu)不同的是,在可重構(gòu)NLF中設計了32個配置寄存器NCR1~NCR32，而且由于輸入數(shù)據(jù)線Data_in寬度固定為32 bit，因此32個配置寄存器NCR1~NCR32均為32 bit。輸入數(shù)據(jù)Data_in分別與各配置寄存器進行組合運算后得到NLF各項結(jié)果，各項結(jié)果通過NCRcom組合運算后輸出NLF值，即密鑰Key。
4 互連網(wǎng)絡結(jié)構(gòu)
本文討論的序列密碼可重構(gòu)處理結(jié)構(gòu)可以實現(xiàn)濾波型和非線性組合型兩類序列密碼，因此，其互連網(wǎng)絡結(jié)構(gòu)應能滿足這兩類序列密碼的連接需要，基于此要求設計的互連網(wǎng)絡結(jié)構(gòu)如圖5所示。
該互連網(wǎng)絡結(jié)構(gòu)總的設計思路：當實現(xiàn)非線性組合型序列密碼時,可重構(gòu)FSR1~FSR8的前饋輸出信號FF_out與可重構(gòu)NLF單元的數(shù)據(jù)輸入信號Data_in(0~7) 分別相連；當實現(xiàn)濾波型序列密碼時，由于此類密碼中FSR一般為1個，個別為2個，因此選擇組1中級數(shù)最長的2個可重構(gòu)FSR3和FSR4參與互連，組2中的4個和組1中的其他2個可重構(gòu)FSR這種情況下不參與互連。
具體連接規(guī)則是：可重構(gòu)FSR3的128 bit狀態(tài)輸出信號Data_out分別與可重構(gòu)FSR1~FSR8的前饋輸出信號FF_out通過8個129選1選路器MUX0~MUX7與可重構(gòu)NLF的數(shù)據(jù)輸入信號Data_in(0~7)相連；可重構(gòu)FSR3的128 bit狀態(tài)輸出信號Data_out再通過8個128選1選路器MUX8~MUX15與可重構(gòu)NLF的數(shù)據(jù)輸入信號Data_in(8~15)相連；可重構(gòu)FSR4的128 bit狀態(tài)輸出信號Data_out通過16個128選1選路器MUX16~MUX31與可重構(gòu)NLF的數(shù)據(jù)輸入信號Data_in(16~31)相連；同時，為了滿足有些序列密碼算法中某一個FSR的最低一級輸出要參與另一個FSR的反饋的情況,將可重構(gòu)FSR3、FSR4的FF_out分別與對方的FV_ext相連。
本文論述的FSR+NLF類序列密碼可重構(gòu)處理結(jié)構(gòu)的配置寄存器都是32 bit的整數(shù)倍，故規(guī)定其重構(gòu)粒度為32 bit，配置數(shù)據(jù)線Cfg_data寬度為32 bit。從功能上來看，該可重構(gòu)處理結(jié)構(gòu)除可以滿足FSR+NLF類序列密碼的處理需求外，還可以和自收縮式發(fā)生器、有限狀態(tài)機等單元結(jié)合使用來處理一些該類衍生的序列密碼。
此外,該可重構(gòu)處理結(jié)構(gòu)具有可擴展性，可重構(gòu)FSR的個數(shù)、各可重構(gòu)FSR的最大長度、各可重構(gòu)FSR的反饋函數(shù)部分與可重構(gòu)NLF中二次以上項的項數(shù)都可以根據(jù)需要進行擴展。
本文論述的FSR+NLF類序列密碼可重構(gòu)處理結(jié)構(gòu)的原型已經(jīng)在Altera公司生產(chǎn)的EP2S60F1020C5型 FPGA上實現(xiàn)，所需資源約為2.2萬門，最高工作頻率為200 MHz。由此可見，該可重構(gòu)處理結(jié)構(gòu)簡單，實現(xiàn)時占用資源較少，運行速度較高。
參考文獻
[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.