摘 要： 討論了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ì)算是通過對(duì)結(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ì)
對(duì)現(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)譯碼電路譯碼后存入配置寄存器組,，再由配置寄存器組對(duì)各可重構(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è)最長級(jí)數(shù)為n的可重構(gòu)FSR結(jié)構(gòu)設(shè)計(jì)如圖4所示,。其結(jié)構(gòu)總體上分為3部分：中間是1個(gè)級(jí)數(shù)為n的移位寄存器SR，其移動(dòng)方向?yàn)閺膎-1級(jí)到0級(jí),；SR以上的部分為反饋函數(shù)部分,；SR以下部分為前饋函數(shù)部分，因?yàn)橛械男蛄忻艽a的FSR帶有前饋輸出(例如Achterbahn),。
對(duì)現(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的級(jí)數(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的各級(jí)狀態(tài)與CR1的對(duì)應(yīng)位相“與”，得到的各位結(jié)果相“異或”即得到F的所有一次項(xiàng)模2加的和,即x0+x3+xn-2的結(jié)果,；SR的各級(jí)狀態(tài)與CR2的對(duì)應(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的最后一級(jí),，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某些級(jí)狀態(tài)的1個(gè)線形函數(shù),，其中必定包含F(xiàn)SR的最低一級(jí)狀態(tài)。該結(jié)構(gòu)設(shè)計(jì)中,，采用1個(gè)n bit的前饋函數(shù)配置寄存器CRff和SR的各級(jí)狀態(tài)進(jìn)行組合運(yùn)算即得到前饋輸出FF_out,，CRff的配置方式和運(yùn)算過程與CR11相同。當(dāng)CRff中只有某一位被配置為“1”時(shí)，則FF_out輸出即為FSR對(duì)應(yīng)一級(jí)的狀態(tài),，特別是這樣可以得到FSR最低一級(jí)的狀態(tài)輸出,，用于另一個(gè)FSR的FV_ext輸入或NLF的輸入。
該可重構(gòu)FSR的最長級(jí)數(shù)為n,，通過對(duì)其各個(gè)寄存器的配置,，可以將其配置為級(jí)數(shù)小于等于n的任意FSR。例如,，當(dāng)n=32時(shí),，要得到一個(gè)級(jí)數(shù)為30的FSR，則將配置寄存器CR1的第0位和第1位都配置為“0”,，將CR2~CR31的第0位和第1位都配置為“1”,，則SR的第0級(jí)和第1級(jí)沒有參與反饋運(yùn)算，相應(yīng)的FSR退化為30級(jí),，其有效級(jí)為第2~31級(jí),。
n位輸出信號(hào)線Data_out 輸出FSR的n級(jí)狀態(tài)，當(dāng)NLF為濾波函數(shù)時(shí)作為其輸入,。外部輸入信號(hào)線有配置使能信號(hào)線Cfg_en、運(yùn)行使能信號(hào)線Run _en,、時(shí)鐘Clk以及32 bit寬的配置數(shù)據(jù)線Cfg_data,。配置使能信號(hào)Cfg_en有效后,外部配置寄存器組通過Cfg_data對(duì)FSR內(nèi)部各寄存器進(jìn)行配置，配置完成后運(yùn)行使能信號(hào)Run_en變?yōu)橛行?，F(xiàn)SR在時(shí)鐘控制下開始運(yùn)行,。
3 可重構(gòu)NLF結(jié)構(gòu)
FSR+NLF 類序列密碼中的NLF單元對(duì)輸入的信號(hào)進(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的前饋輸出信號(hào)FF_out與可重構(gòu)NLF單元的數(shù)據(jù)輸入信號(hào)Data_in(0~7) 分別相連,；當(dāng)實(shí)現(xiàn)濾波型序列密碼時(shí),，由于此類密碼中FSR一般為1個(gè)，個(gè)別為2個(gè)，因此選擇組1中級(jí)數(shù)最長的2個(gè)可重構(gòu)FSR3和FSR4參與互連,，組2中的4個(gè)和組1中的其他2個(gè)可重構(gòu)FSR這種情況下不參與互連,。
具體連接規(guī)則是：可重構(gòu)FSR3的128 bit狀態(tài)輸出信號(hào)Data_out分別與可重構(gòu)FSR1~FSR8的前饋輸出信號(hào)FF_out通過8個(gè)129選1選路器MUX0~MUX7與可重構(gòu)NLF的數(shù)據(jù)輸入信號(hào)Data_in(0~7)相連；可重構(gòu)FSR3的128 bit狀態(tài)輸出信號(hào)Data_out再通過8個(gè)128選1選路器MUX8~MUX15與可重構(gòu)NLF的數(shù)據(jù)輸入信號(hào)Data_in(8~15)相連,；可重構(gòu)FSR4的128 bit狀態(tài)輸出信號(hào)Data_out通過16個(gè)128選1選路器MUX16~MUX31與可重構(gòu)NLF的數(shù)據(jù)輸入信號(hào)Data_in(16~31)相連,；同時(shí)，為了滿足有些序列密碼算法中某一個(gè)FSR的最低一級(jí)輸出要參與另一個(gè)FSR的反饋的情況,將可重構(gòu)FSR3,、FSR4的FF_out分別與對(duì)方的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.