面向序列密碼的抽取與插入單元可重構(gòu)設(shè)計研究

摘 要： 研究了抽取與插入單元的基本原理，提出了一種可重構(gòu)的抽取與插入硬件電路，并對核心模塊控制信息生成電路進(jìn)行了深入研究?？芍貥?gòu)硬件電路通過配置能夠靈活高效地實現(xiàn)32 bit、64 bit、128 bit、256 bit等位寬抽取與插入操作。該設(shè)計在Altera公司的FPGA上進(jìn)行了功能驗證，并在Synopsys公司的Design Compiler上進(jìn)行了邏輯綜合、優(yōu)化。結(jié)果表明，在CMOS 0.13 ?滋m工藝下，可重構(gòu)移位單元硬件架構(gòu)核心頻率可以達(dá)到350 MHz。
關(guān)鍵詞： 抽?。徊迦?；可重構(gòu)；控制信息生成

序列密碼具有實現(xiàn)簡單、加密速度快、密文傳輸中的錯誤不會在明文中產(chǎn)生擴(kuò)散等優(yōu)點，因此應(yīng)用越來越廣泛[1]?？芍貥?gòu)技術(shù)融合了ASIC高效性和通用微處理器靈活性的實現(xiàn)方式，已經(jīng)廣泛應(yīng)用到序列密碼算法中[2]。抽取與插入單元可重構(gòu)操作解決了算法中比特級初始信息位寬不相同的操作限制，實現(xiàn)了算法的靈活性和高效性，具有非常好的現(xiàn)實意義和創(chuàng)新性。
針對序列密碼算法運算操作位寬不同的特點，抽取與插入操作能夠從移位寄存器狀態(tài)中快速提取出有效狀態(tài)位來參與后續(xù)密碼運算，解決了位寬不同的問題，從而降低了資源消耗并提高了運算速度。例如密鑰流的生成、復(fù)雜更新函數(shù)計算等都運用到這種操作。所以對抽取與插入單元的基本原理與實現(xiàn)功能的研究，對提高序列密碼處理速度和節(jié)約序列密碼算法芯片資源具有重要的意義。
1 序列密碼算法中抽取與插入單元操作
序列密碼算法主要由移位寄存器、反饋函數(shù)運算單元和密鑰流函數(shù)運算單元構(gòu)成，其中反饋函數(shù)運算單元用于計算移位寄存器的更新值，密鑰流函數(shù)運算單元用于計算最終的密鑰流。不論是反饋函數(shù)的計算還是密鑰流生成函數(shù)的運算都需要將參與運算的一個或多個移位寄存器的有效狀態(tài)位提取出來繼續(xù)完成運算。參與運算的一個或多個移位寄存器的有效狀態(tài)位提取出來的操作稱為抽取與插入操作。
抽取操作過程可以用圖1（a）描述：根據(jù)預(yù)先產(chǎn)生的控制信息序列Ctr對受控序列In進(jìn)行操作?？刂菩畔⑿蛄蠧tr中為“1”的控制位對應(yīng)的受控數(shù)據(jù)依次排在Out的右側(cè)，其余為“0”的控制位對應(yīng)受控數(shù)據(jù)依次排在Out的左側(cè)，這樣能夠?qū)崿F(xiàn)有效狀態(tài)位和無效狀態(tài)位的分離。序列密碼算法實現(xiàn)過程中，有時需要將抽取操作結(jié)果的每一位都保存下來，并且能夠在有效位運算完成后再將其插入到原始的位置上去[3]。插入操作過程可以用圖1（b）描述：當(dāng)插入單元與抽取單元控制信息序列Ctr相同時，插入單元操作能夠?qū)⒊槿卧僮鞯挠行顟B(tài)位還原，也就是說抽取與插入單元的操作是可逆的。

在對NESSIE工程、ECRYPT工程[4]中的序列密碼算法分析后，三十多種算法的運算環(huán)節(jié)包含了抽取單元操作，雖然單元操作對應(yīng)的初始信息位寬相對比較復(fù)雜，但是多數(shù)序列密碼算法操作位寬都可以歸為32 bit、64 bit、128 bit、256 bit四種位寬以內(nèi)。例如A5-1算法中LFSR級數(shù)為19時，運用抽取操作將參加下輪運算的第19、18、17、14這四個有效位比特抽取出來，然后進(jìn)行后續(xù)操作，其余算法在這里不再贅述。表1中列出了9種序列密碼算法中密鑰流生成函數(shù)和反饋函數(shù)的運算情況，包括變量個數(shù)和對應(yīng)源操作數(shù)據(jù)的位寬，可以得出抽取操作的源操作數(shù)位寬和目的操作數(shù)位寬。
2 抽取與插入單元的可重構(gòu)硬件電路總體架構(gòu)
可重構(gòu)抽取與插入單元硬件電路架構(gòu)包括inverse butterfly網(wǎng)絡(luò)的抽取與插入基本單元電路和inverse butterfly網(wǎng)絡(luò)的控制信息生成電路[5]。inverse butterfly網(wǎng)絡(luò)的控制信息生成電路能夠同時控制inverse butterfly網(wǎng)絡(luò)的抽取與插入基本單元電路。對于初始信息位寬長度為nbit的抽取與插入單元操作，基本單元電路由級inverse butterfly網(wǎng)絡(luò)構(gòu)成，每級網(wǎng)絡(luò)需要n/2 bit控制信息，一共需要nlogn/2 bit的控制信息并且由nbit的初始信息通過控制信息生成電路生成。
例如初始信息位寬為256 bit的抽取與插入單元操作中，對應(yīng)的單元基本電路由8級inverse butterfly網(wǎng)絡(luò)構(gòu)成，共需要1 024 bit控制信息。當(dāng)兩個單元初始控制信息相同時，控制信息生成電路生成的控制信息有以下關(guān)系：抽取基本單元電路的第1級控制信息與插入基本單元電路的第8級控制信息相同，需要將抽取單元的各級電路生成信息還原為各自對應(yīng)輸入信息時，能夠利用插入單元的特點：在控制信息相同的情況下，可以將抽取單元各級的生成信息作為插入單元的輸入信息來實現(xiàn)。由此得到抽取與插入單元電路的實現(xiàn)是一個可逆的過程。

3 可重構(gòu)控制信息生成電路
3.1 控制信息的生成算法
通過對benes、butterfl、inverse butterfly、banyan以及clos等多種網(wǎng)絡(luò)結(jié)構(gòu)的分析和研究得知，抽取與插入單元運用了inverse butterfly網(wǎng)絡(luò)控制信息生成算法[6]。nbit初始信息對應(yīng)的inverse butterfly網(wǎng)絡(luò)需要nlogn/2 bit控制信息，這些信息均由nbit初始信息譯碼生成，控制信息算法[6]如下：
(1)計算初始控制信息抽頭
PPC[0]=control[0]
For i=1，2，……，n-2
PPC[i]=PPC[i-1]+control[i]
(2)計算inverse butterfly網(wǎng)絡(luò)控制信息生成算法
sel={}
For i=1，2，……，lg(n)
k=2i-1
For j=0，1，……，n/2i-1
temp=LROTC(0K，PPC[j?鄢2i+k-1])
sel[i]=temp||sel[i]
其中：
①LROTC(a, rot)表示左循環(huán)取反填充，a是輸入，rot是左循環(huán)次數(shù)。
②0k代表長度為k的“0”比特串。
③PPC[a]代表從原始控制信息的第0抽頭到第a抽頭的1的個數(shù)。
④i表示inverse butterfly網(wǎng)絡(luò)的第i級。
⑤k表示第i級中每個子單元需要的控制信息位數(shù)，也表示每個子單元中處在右側(cè)部分的輸入位數(shù)。
3.2 控制信息生成連加電路算法設(shè)計
針對控制信息生成電路位寬多變的特點，連加比特電路有多種實現(xiàn)模式。在處理連加電路時，提出了相鄰比特兩兩相加以減少電路寄存器數(shù)目的操作，大幅度減小了電路設(shè)計面積并且提高了電路運行效率。以8 bit十進(jìn)制連加電路為例，(其中a0～7表示8 bit連加電路初始信息位寬，b1～4表示連加電路相鄰2 bit相加信息位寬，U1～8表示連加電路結(jié)果信息位寬)如圖2所示。