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

徐建博，戴紫彬，李 偉，蘇 陽(yáng)

(解放軍電子技術(shù)學(xué)院，河南 鄭州 450004)

序列密碼具有實(shí)現(xiàn)簡(jiǎn)單、加密速度快、密文傳輸中的錯(cuò)誤不會(huì)在明文中產(chǎn)生擴(kuò)散等優(yōu)點(diǎn)，因此應(yīng)用越來(lái)越廣泛[1]?？芍貥?gòu)技術(shù)融合了ASIC高效性和通用微處理器靈活性的實(shí)現(xiàn)方式，已經(jīng)廣泛應(yīng)用到序列密碼算法中[2]。抽取與插入單元可重構(gòu)操作解決了算法中比特級(jí)初始信息位寬不相同的操作限制，實(shí)現(xiàn)了算法的靈活性和高效性，具有非常好的現(xiàn)實(shí)意義和創(chuàng)新性。

針對(duì)序列密碼算法運(yùn)算操作位寬不同的特點(diǎn)，抽取與插入操作能夠從移位寄存器狀態(tài)中快速提取出有效狀態(tài)位來(lái)參與后續(xù)密碼運(yùn)算，解決了位寬不同的問(wèn)題，從而降低了資源消耗并提高了運(yùn)算速度。例如密鑰流的生成、復(fù)雜更新函數(shù)計(jì)算等都運(yùn)用到這種操作。所以對(duì)抽取與插入單元的基本原理與實(shí)現(xiàn)功能的研究，對(duì)提高序列密碼處理速度和節(jié)約序列密碼算法芯片資源具有重要的意義。

1 序列密碼算法中抽取與插入單元操作

序列密碼算法主要由移位寄存器、反饋函數(shù)運(yùn)算單元和密鑰流函數(shù)運(yùn)算單元構(gòu)成，其中反饋函數(shù)運(yùn)算單元用于計(jì)算移位寄存器的更新值，密鑰流函數(shù)運(yùn)算單元用于計(jì)算最終的密鑰流。不論是反饋函數(shù)的計(jì)算還是密鑰流生成函數(shù)的運(yùn)算都需要將參與運(yùn)算的一個(gè)或多個(gè)移位寄存器的有效狀態(tài)位提取出來(lái)繼續(xù)完成運(yùn)算。參與運(yùn)算的一個(gè)或多個(gè)移位寄存器的有效狀態(tài)位提取出來(lái)的操作稱(chēng)為抽取與插入操作。

抽取操作過(guò)程可以用圖1（a）描述：根據(jù)預(yù)先產(chǎn)生的控制信息序列Ctr對(duì)受控序列In進(jìn)行操作?？刂菩畔⑿蛄蠧tr中為“1”的控制位對(duì)應(yīng)的受控?cái)?shù)據(jù)依次排在Out的右側(cè)，其余為“0”的控制位對(duì)應(yīng)受控?cái)?shù)據(jù)依次排在 Out的左側(cè)，這樣能夠?qū)崿F(xiàn)有效狀態(tài)位和無(wú)效狀態(tài)位的分離。序列密碼算法實(shí)現(xiàn)過(guò)程中，有時(shí)需要將抽取操作結(jié)果的每一位都保存下來(lái)，并且能夠在有效位運(yùn)算完成后再將其插入到原始的位置上去[3]。插入操作過(guò)程可以用圖1（b）描述：當(dāng)插入單元與抽取單元控制信息序列 Ctr相同時(shí)，插入單元操作能夠?qū)⒊槿卧僮鞯挠行顟B(tài)位還原，也就是說(shuō)抽取與插入單元的操作是可逆的。

圖1 抽取與插入單元操作實(shí)現(xiàn)過(guò)程

在對(duì)NESSIE工程、ECRYPT工程[4]中的序列密碼算法分析后，三十多種算法的運(yùn)算環(huán)節(jié)包含了抽取單元操作，雖然單元操作對(duì)應(yīng)的初始信息位寬相對(duì)比較復(fù)雜，但是多數(shù)序列密碼算法操作位寬都可以歸為32 bit、64 bit、128 bit、256 bit四種位寬以?xún)?nèi)。例如 A5-1算法中LFSR級(jí)數(shù)為19時(shí)，運(yùn)用抽取操作將參加下輪運(yùn)算的第19、18、17、14這四個(gè)有效位比特抽取出來(lái)，然后進(jìn)行后續(xù)操作，其余算法在這里不再贅述。表1中列出了9種序列密碼算法中密鑰流生成函數(shù)和反饋函數(shù)的運(yùn)算情況，包括變量個(gè)數(shù)和對(duì)應(yīng)源操作數(shù)據(jù)的位寬，可以得出抽取操作的源操作數(shù)位寬和目的操作數(shù)位寬。

表1 序列密碼算法中的密鑰流生成函數(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ò)的控制信息生成電路能夠同時(shí)控制inverse butterfly網(wǎng)絡(luò)的抽取與插入基本單元電路。對(duì)于初始信息位寬長(zhǎng)度為nbit的抽取與插入單元操作，基本單元電路由級(jí)inverse butterfly網(wǎng)絡(luò)構(gòu)成，每級(jí)網(wǎng)絡(luò)需要 n/2 bit控制信息，一共需要nlogn/2 bit的控制信息并且由nbit的初始信息通過(guò)控制信息生成電路生成。

例如初始信息位寬為256 bit的抽取與插入單元操作中，對(duì)應(yīng)的單元基本電路由8級(jí)inverse butterfly網(wǎng)絡(luò)構(gòu)成，共需要1 024 bit控制信息。當(dāng)兩個(gè)單元初始控制信息相同時(shí)，控制信息生成電路生成的控制信息有以下關(guān)系：抽取基本單元電路的第1級(jí)控制信息與插入基本單元電路的第8級(jí)控制信息相同，需要將抽取單元的各級(jí)電路生成信息還原為各自對(duì)應(yīng)輸入信息時(shí)，能夠利用插入單元的特點(diǎn)：在控制信息相同的情況下，可以將抽取單元各級(jí)的生成信息作為插入單元的輸入信息來(lái)實(shí)現(xiàn)。由此得到抽取與插入單元電路的實(shí)現(xiàn)是一個(gè)可逆的過(guò)程。

3 可重構(gòu)控制信息生成電路

3.1 控制信息的生成算法

通過(guò)對(duì)benes、butterfl、inverse butterfly、banyan 以 及clos等多種網(wǎng)絡(luò)結(jié)構(gòu)的分析和研究得知，抽取與插入單元運(yùn)用了inverse butterfly網(wǎng)絡(luò)控制信息生成算法[6]。nbit初始信息對(duì)應(yīng)的inverse butterfly網(wǎng)絡(luò)需要nlogn/2 bit控制信息，這些信息均由nbit初始信息譯碼生成，控制信息算法[6]如下：

(1)計(jì)算初始控制信息抽頭

(2)計(jì)算inverse butterfly網(wǎng)絡(luò)控制信息生成算法

其中：

①LROTC(a,rot)表示左循環(huán)取反填充，a是輸入，rot是左循環(huán)次數(shù)。

②0k代表長(zhǎng)度為k的“0”比特串。

③PPC[a]代表從原始控制信息的第0抽頭到第a抽頭的1的個(gè)數(shù)。

④i表示inverse butterfly網(wǎng)絡(luò)的第i級(jí)。

⑤k表示第i級(jí)中每個(gè)子單元需要的控制信息位數(shù)，也表示每個(gè)子單元中處在右側(cè)部分的輸入位數(shù)。

3.2 控制信息生成連加電路算法設(shè)計(jì)

針對(duì)控制信息生成電路位寬多變的特點(diǎn)，連加比特電路有多種實(shí)現(xiàn)模式。在處理連加電路時(shí)，提出了相鄰比特兩兩相加以減少電路寄存器數(shù)目的操作，大幅度減小了電路設(shè)計(jì)面積并且提高了電路運(yùn)行效率。以8 bit十進(jìn)制連加電路為例，(其中 a0～7表示 8 bit連加電路初始信息位寬，b1～4表示連加電路相鄰 2 bit相加信息位寬，U1～8表示連加電路結(jié)果信息位寬)如圖2所示。

圖2 8 bit控制信息生成連加電路

根據(jù)電路圖所示有以下關(guān)系公式：

假設(shè)Um表示m比特連加電路運(yùn)算，并且U0=b0，因而可以得到：

通過(guò)（1）、（2）兩個(gè)公式可以極大地節(jié)省連加電路的運(yùn)算時(shí)間，而且降低了寄存器對(duì)功耗的影響。提高了整體運(yùn)算電路的運(yùn)算速度。

4 基于inverse butterfly網(wǎng)絡(luò)的可重構(gòu)抽取與插入操作基本單元

抽取與插入單元是序列密碼算法實(shí)現(xiàn)高效性和靈活性的核心模塊。基于inverse butterfly網(wǎng)絡(luò)提出了抽取與插入操作基本單元，且nbit的操作數(shù)位寬對(duì)應(yīng)inverse butterfly網(wǎng)絡(luò)共有l(wèi)ogn級(jí)，抽取操作基本單元的特點(diǎn)是級(jí)數(shù)由上到下逐級(jí)增大，并且在第i級(jí)中，共有n/2i個(gè)子單元，每個(gè)子單元輸入數(shù)據(jù)位寬為2ibit。對(duì)于每級(jí)中的子單元，左右單元各占一半的輸入，左右部分的位寬均為2i-1bit，而且每個(gè)子單元都需要2i-1bit的控制信息。

圖3 抽取基本單元4級(jí)inverse butterfly網(wǎng)絡(luò)

圖3所示抽取操作基本單元位寬為16 bit的4級(jí)inverse butterfly網(wǎng)絡(luò)[7]，第一級(jí)有 8個(gè)子單元，每個(gè)子單元對(duì)應(yīng)2 bit數(shù)據(jù)輸入和1 bit控制信息；第二級(jí)有4個(gè)單元，每個(gè)子單元對(duì)應(yīng)4 bit數(shù)據(jù)輸入和2 bit控制信息；第三級(jí)有2個(gè)單元，每個(gè)子單元對(duì)應(yīng)8 bit數(shù)據(jù)輸入和4 bit控制信息；第四級(jí)有1個(gè)單元，單元對(duì)應(yīng)16 bit數(shù)據(jù)輸入和8 bit控制信息。

插入單元的nbit操作數(shù)位寬對(duì)應(yīng)的inverse butterfly網(wǎng)絡(luò)和抽取單元同樣有l(wèi)ogn級(jí)。綜上所述，當(dāng)兩個(gè)單元控制信息相同時(shí)，抽取與插入基本單元的實(shí)現(xiàn)過(guò)程是可逆的，插入操作運(yùn)算能夠?qū)⒊槿〔僮鬟\(yùn)算結(jié)果還原為初始數(shù)據(jù)信息。圖4為插入基本單元位寬為16 bit的4級(jí)inverse butterfly網(wǎng)絡(luò)，可知第一級(jí)有1個(gè)子單元，子單元對(duì)應(yīng)16 bit數(shù)據(jù)輸入和 8 bit控制信息；第二級(jí)有 2個(gè)單元，每個(gè)子單元對(duì)應(yīng)8 bit數(shù)據(jù)輸入和4 bit控制信息；第三級(jí)有4個(gè)單元，每個(gè)子單元對(duì)應(yīng)4 bit數(shù)據(jù)輸入和2 bit控制信息；第四級(jí)有8個(gè)子單元，每個(gè)子單元對(duì)應(yīng)2 bit數(shù)據(jù)輸入和1 bit控制信息。由此可以得到位寬為256 bit的8級(jí)inverse butterfly網(wǎng)絡(luò)，在此不再贅述。

圖4 插入單元4級(jí)inverse butterfly網(wǎng)絡(luò)

5 性能分析

本文提出的設(shè)計(jì)采用Verilog語(yǔ)言描述，在Quartus9.0環(huán)境下編譯，選用Altera StratixIII系列器件的EP3SL340F1760C4為目標(biāo)器件進(jìn)行了綜合，表2給出抽取和插入單元加載到FPGA中的時(shí)鐘頻率和資源占用情況。另外本設(shè)計(jì)使用NC-Verilog對(duì)批量數(shù)據(jù)進(jìn)行了仿真測(cè)試，驗(yàn)證結(jié)果均正確?；贑MOS 0.13 μm工藝庫(kù)，在Synopsys公司的Design Compiler上進(jìn)行了邏輯綜合、優(yōu)化。結(jié)果如表3所示。

綜上所述，本文基于抽取和插入單元的基本原理，提出并實(shí)現(xiàn)了可重構(gòu)硬件電路，在保證單元運(yùn)算靈活性和準(zhǔn)確性的同時(shí)，有效降低了功耗，并且滿(mǎn)足了不同位寬序列密碼的操作要求。通過(guò)在FPGA上驗(yàn)證，抽取與插入單元的設(shè)計(jì)結(jié)果正確、高效。能夠滿(mǎn)足多種對(duì)稱(chēng)密碼算法的實(shí)現(xiàn)需求，同時(shí)為可重構(gòu)密碼芯片的設(shè)計(jì)和運(yùn)用奠定了良好的基礎(chǔ)。

表2 基于FPGA可重構(gòu)抽取和插入單元性能分析

表3 基于ASIC可重構(gòu)抽取和插入單元性能分析

[1]Luo Qibin，Zhang Jian，Status Quo.Development of stream cipher.Information And Electronic Engineering，2007，1(2).

[2]ADAM J E.Reconfigurable computing for Symmetric-Key[D].2002.

[3]Shi Zhijie，Ruby B L.Subword sorting with versatile permuta-tion instructions.Proceedings of the International Conference on Com-puter Design(ICCD 2002)，2002(9)：234-241.

[4]Liu Yunyi，Qin Tuanfa，Ni Wansun，et al.The brief evaluations of the candidates to the ECRYPT stream ciphers.Information Securityand Communication Secrecy，2006，7.

[5]LEE R B，RIVEST R.L，ROBSHAW M.J.B，et al.On permutation operations in cipher design.Proceedings of the International Conference on Information Technology(ITCC)，2004，2(4)：569-577.

[6]SHI Z J，Ruby B.L.Implementation complexity of bit permutation instructions department of electrical engineering.Princeton University，Princeton，NJ 08544 USA，2003.

[7]YANG X，VACHHARAJANI M，LEE R B.Fast subword permutation instructions based on butterfly networks，Proceedings of Media Processors 2000(SPIE 2000)，2000(1)：80-86.