基于Benes網(wǎng)絡結構的比特置換在處理器中的實現(xiàn)

目前，通用微處理器大多是以字為單位進行操作的，它的指令結構isa（instruction-set architecture）不支持小于一個字的數(shù)據(jù)操作，而單比特的置換操作在分組密碼算法中使用頻率非常高，是提高算法安全性的重要手段；而且比特置換操作在處理器中快速高效的特點，也將影響密碼處理得整體性能，但在現(xiàn)有的指令結構處理器中，任意的比特置換通常都采用邏輯操作或查找表的方式實現(xiàn)[1]，即使一個簡單的置換操作（如循環(huán)位移），也需要多條指令才能完成。根據(jù)相關研究可知，一個n比特的置換操作，它的指令級復雜度是0（n），處理速度也就隨著n的增加而不斷降低，對于，目前實時的網(wǎng)絡通信來說，這顯然是不可容忍的，因此，針對這一問題在一些專用指令集微處理器asip（application-specific instruction-set processor）中，增加了特殊的置換指令，如多媒體處理器plx中增加了mix、mux和perm等指令 [2]，但這些指令并不能滿足n-bit數(shù)據(jù)的任意置換操作，本文提出了一種在處理器中實現(xiàn)比特置換的方法，給出了相應的比特置換指令及其操作結構。

1 密碼學中的比特置換及其一般實現(xiàn)方式

1.1 密碼學中的比特置換

比較置換操作能使輸入數(shù)據(jù)中第i比特置換到輸出數(shù)據(jù)的第j比特上，而且置換過程中各位源數(shù)據(jù)之間不發(fā)生計算關系，輸入的n比特數(shù)據(jù)需要log2n比特位置信息或配置信息。

置換是密碼算法中隱藏明文信息中冗余度的重要手段，通過位置置換可以實現(xiàn)明文到密文的擴散。置換按明密文映射關系分為三類：直接置換、擴展置換和壓縮置換，直接置換指明密文間是一一映射關系，且明文的每一位都有到密文的映射，擴展置換指明密文間為一對多的映射關系，它使得密文對明文的依賴性傳播得更快，壓縮置換指明密文間是一一映射關系，但并不是明文的每一位都有到密文的映射，置換輸入和輸出位寬根據(jù)算法和置換類型的不同而有所不同，例如des算法中有64bit的初始置換ip、末尾置換ip-1以及輪運算中的32-bit p置換[3]。

1.2 邏輯操作方式

邏輯操作方式是指采用and、or、shift等簡單邏輯操作實現(xiàn)復雜的比特置換操作，在此方式下，每對1bit進行置換，處理器需要進行四步操作，1）產(chǎn)生目標比特的mask參數(shù)；2）提取相應比特值（and指令）；3）將該比特移至相應位置（shift指令）；4）存儲到相應寄存器中（or指令）。由上述過程可知，一個n-bit的位置操作需要4n條指令才能完成，盡管一些處理器中針對這一問題有所改進，將1bit置換操作的指令壓縮到2條--汲取指令（extract）和放置指令（deposit），但n-bit置換操作仍需要2n條指令，處理性能沒有明顯提高。

1.3 查找表方式

查找表方式是另一種實現(xiàn)比特置換的方法，它在速度上與邏輯操作相比有所提高，但需要大量的存儲空間放置控制信息，完成一個n-bit的置換操作需要m個查找表，每個表的容量為2n/m×nbit，以64-bit輸入數(shù)據(jù)為例，當m=1時，完成一次任意置換需要一個264×64bit的查找表，這在現(xiàn)有微處理器結構中是無法實現(xiàn)的；當m=8時，完成一次任意置換需要8個容量為28×64bit的查找表，每個表代表源操作數(shù)中連續(xù)8-bit的置換，表中除了8-bit置換的目標位置外，其他位置均為0，此時共需要23條指令來完成64-bit置換，8條extract指令獲得表的索引值、8條load指令置換相應比特、7條or指令連接8個8-bit置換后的數(shù)據(jù)，這種方法相對于邏輯操作方式來說指令條數(shù)減少了很多，但它在實際執(zhí)行中，load指令往往遇到未命中cache的情況，所以實現(xiàn)n-bit的置換操作需要的復雜度一般為o（n）。

2 比特置換操作的優(yōu)化實現(xiàn)

2.1 butterfly結構

目前，butterfly結構[4]及其他一些相似的結構都廣泛應用于信息處理領域中，如數(shù)字信號處理中的快速傅里葉變換（fft）等，圖1（a而）中給出了8-bit輸入的butterfly結構，圖1（b）中給出了相應的inverse butterfly結構。

2.2 benes網(wǎng)絡結構

benes網(wǎng)絡結構由一個butterfly結構鏈接一個inverse butterfly 結構組成，它是一種可重排網(wǎng)絡，能實現(xiàn)輸入端到輸出端的所有置換，完成n-bit置換操作需log2n級butterfly變換和log2n級inverse butterfly變換，對于一個64-bit置換，則需要2 log2n=12級變換，且每一級需要n/2-bit配置信息，在處理器中執(zhí)行置換操作需要一條butterfly指令和一條inverse butterfly指令及l(fā)og2n個n-bit配置信息。

圖2給出了一個8-bit輸出的bense網(wǎng)絡結構，能完成（abcdefgh）到（cfghbdea）的置換，根據(jù)配置信息，它的置換過程如下：butterfly指令完成（abcdefgh）->（abgdefch）->（gdabehcf）->（dgabehfc）；inverse butterfly指令完成（dgabehfc）->（gcbaehcf）->（bdgacfeh）->（cfghbdea）。

2.3 比特置換指令

比特置換單元內部設置了一定的緩存區(qū)，用于存儲配置信息，如圖3所示的b1、b2、b3和i1、i2、i3。由于不同asip中指令格式存在差異，這些內部緩存區(qū)是可選擇的，由于inverse butterfly指令類似于butterfly指令，下面以butterfly指令為例進行說明，對于超長指令字格式（vliw），支持多操作數(shù)方式，不需要內部寄存器存儲配置信息，其指令可描述為：butterfly rd，rs，b1，b2，b3。其中rd為置換數(shù)據(jù)目的地址，rs為置換數(shù)據(jù)地址，b1、b2、b3為配置信息的外部存儲地址，即一條butterfly指令包括rs、b1、b2、b3四個源操作數(shù)，對于精簡指令格式（risc），最多支持兩個源操作，相應指令可描述為：butterfly rd，rs，b3，即需要將配置信息b1、b2、i1、i2在進行置換操作前裝入到置換單元內部緩存區(qū)中，而b3、i3則從外部存儲器中獲得，對于超標量結構處理器，假設其有兩路并行處理通路，則butterfly 指令與inverse butterfly 指令可并行執(zhí)行，對于所采用的不同指令格式，具體操作指令數(shù)也不同。

3 性能比較

如果一個處理器可以支持比特置換操作，則其比特置換操作的延時必須與邏輯運算單元（alu）的時鐘頻率相匹配，在alu中主要是乘法器[5]延時較大，通常占用3-5個時鐘周期，因此只有使比特置換操作延時小于乘法運算延時，才能在不影響處理器整體性能的前提下，使處理器支持比特置換操作，而邏輯操作方式與查找表方式的比特置換實現(xiàn)方法所占用的時鐘周期都遠遠大于3個時鐘周期，如表1所示，當采用benes網(wǎng)絡結構時，僅執(zhí)行兩次butterfly指令，在性能得到了很大提高，使n-bit的比特置換操作的復雜度從o（n）降至o（log（n））。

比特置換是現(xiàn)代對稱密碼算法中的一個基本操作，但由于它比其他操作延時大且需要大量的控制信息，使得目前的通用處理器并不支持比特置換操作，本文針對上述兩個問題提出的解決方案，使其可以在處理器中快速實現(xiàn)，并以64-bit置換為例，在fpga上對這一結構進行了驗證，結果僅占用700個邏輯單元，最高時鐘頻率達到了200mhz，采用asic實現(xiàn)時，其性能還將在此基礎上顯著提高，從而滿足網(wǎng)絡通信等方面的需求。