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