摘 要： 在分析多種對稱密碼算法" title="密碼算法">密碼算法的基礎上，總結出常用的S盒運算模式，設計并實現了高效、靈活、安全的可重構" title="可重構">可重構S盒運算單元，并且給出了此單元通用的指令格式。
關鍵詞： 密碼算法 可重構? S盒? LUT
?
在信息安全技術飛速發展的今天,密碼算法的使用范圍越來越廣泛。對稱密碼算法在密碼算法應用中占有非常重要的位置,它可以用于構造偽隨機數產生器、流密碼、認證碼和Hash函數等,也可以作為消息或實體認證、數據完整性和數字簽名等方案的核心部分。在各種各樣安全技術需求的促使下,可重構密碼芯片已成為當今研究的一個方向。目前,可重構技術的研究已經非常廣泛,在不同領域有著不同的研究層次。按照可重構處理單元的規模可劃分細粒度可重構和粗粒度可重構。細粒度可重構是指以位為可重構的基本單元,例如: 現場可編程門陣列(FPGA);粗粒度可重構是指以能單獨完成某些功能的單元為基本單元,例如:應用于特定領域的可重構系統MATRIX[1]。本文所設計的可重構S盒運算單元RSU(Reconfigurable Sbox Unit)即為粗粒度的可重構單元。可重構密碼運算單元是可重構密碼系統的重要組成部分,RSU就是其中一種密碼運算單元。S盒運算單元靈活、高效的設計與實現,將會使一個芯片內集成更多的密碼算法。針對這一問題,本文對S盒運算的特性進行了研究與分析,提出了一種能支持4-4、6-4、8-8、8-32四種運算模式的RSU。對于4-4模式,RSU一次可以配置16 個配置頁CP(Configurable Pages);對于6-4模式,RSU一次可以配置4 CP;對于8-8模式,RSU一次可以配置2 CP;對于8-32模式,RSU一次可以配置2 CPs。如此高效、靈活的RSU設計方案,為可重構密碼系統的設計與實現提供了基礎。
1 S盒的應用及其實現方式的分析
1.1 對稱密碼算法中的S盒
在對稱密碼算法中,S盒運算單元的使用頻率非常高。但在不同的算法中,S盒的使用方式各不相同。下面給出常用的20種對稱密碼算法中S盒運算模式的使用情況,如表1所示。
可重構S盒運算單元的設計主要是為了滿足不同算法的要求,通過一致的接口和不同的控制信號" title="控制信號">控制信號,共同使用一個模塊,完成不同模式的S盒運算。分析以上密碼算法可知,常用的S盒運算有4-4、6-4、8-8、8-32四種運算模式,所以本文提出的RSU至少要支持這四種運算模式的操作。
1.2 S盒實現方式的分析
目前,常用的S盒的實現方法" title="實現方法">實現方法有兩種:基于邏輯電路的實現方法和基于查找表(LUT)的實現方法。
(1)基于邏輯電路的實現方法
S盒字節變換的映射關系通常是由某個算法指定的,而這個特定的算法是用邏輯電路實現的,從而得到S盒的運算結果。例如:在MARS密碼算法中,S盒映射關系由SHA-1摘要算法指定[3],而SHA-1摘要算法用邏輯電路實現,將S盒源操作數按要求輸入SHA-1電路,那么SHA-1電路的運算結果便可作為S盒的結果輸出。這種方法的好處在于使用的資源較少,但運算速度" title="運算速度">運算速度慢,會成為整個芯片的瓶頸。最主要的是,一個固定的電路只能完成一種運算,不具有可配置性,攻擊手段較易成功,芯片本身的安全性較低。
(2)基于LUT的實現方法
設計者按照S盒字節變換的映射關系,將所有可能的結果(一般地,算法設計者會給出相應的數據向量表)放在一個存儲器(RAM、ROM或是寄存器堆)內,當進行S盒運算時,將操作數作為查找地址,直接對存儲單元進行查找,查找的結果作為S盒運算結果輸出。基于LUT的實現方法如圖1所示。
這種方法占用了較多的存儲單元,但運算速度非常快,路徑上的延遲只有寄存器或存儲器的輸出延遲。最主要的是它具有可配置性和較高的靈活性,能滿足當前多種密碼運算的需要,并且當芯片不進行配置時它本身不帶有任何的算法信息,使得芯片本身更具有安全性。RSU的設計就是基于LUT方式,并加入了可重構的設計思想,使得RSU具有更高的靈活性和安全性。
2 RSU的設計
2.1 RSU電路的設計
為了使RSU能夠配置不同S盒的LUT,本設計選擇了可重寫的RAM作為存儲器,它可以動態地、重復地配置LUT;為使RAM的讀地址和查找結果的映射關系為可重構的,以滿足常用S盒輸入位寬的大小,可重構的控制節點參加RAM讀寫地址的譯碼,控制RAM的讀寫模式,實現常用的4bit、6bit、8bit幾種位寬。以上幾種LUT模式的輸入位寬最大為8bit,所以 RAM的深度至少為256。常用S盒輸出位寬最寬為32bit,所以RAM的輸出位寬至少為32bit。對于程序員來說,一種算法最好只需要進行一次配置,而MARS密碼算法的S盒有兩組256×32bit的LUT數據,所以RAM塊最小應為512×32bit,但為了減小輸出的路徑延遲,選擇以256×64bit的形式來實現,在物理上RSU是以8塊256×8bit的RAM塊來實現的,RSU整體電路結構如圖2所示。
RSU_Datain為RSU的數據輸入端口,RSU_CP為頁面選擇信號,RSU_mode為模式選擇信號,RSU_ren為RAM塊的讀使能,RSU_clk為系統時鐘,RSU_conf_wen為RSU的配置使能信號,RSU_conf_addr為RSU的配置地址輸入。RSU的內部主要由四個RAM組構成,RAM組1的電路如圖3所示。
RAM組1分為兩個256×8bit的RAM塊。信號RSU_G1_operater_H、RSU_G1_operater_L、RSU_G1_conf_address、RSU_G1_sel1、RSU_G1_sel2是由原驅動信號RSU_Datain、RSU_conf_addr在可重構控制節點RSU_mode、RSU_CP控制下生成的,作為控制信號和源操作數參加RAM組1的配置和運算操作。
當RSU_conf_wen有效時,RSU執行配置操作;當RSU_ren有效時,RSU進行運算操作。RSU_mode信號分別為00、01、10、11時,RSU分別完成8-8、8-32、4-4、6-4四種模式的配置和運算操作。RSU_CP為0000~1111時,分別對第0~15個配置頁面進行讀或寫。在以上的可重構節點的控制下,RSU就可以完成相應的配置和運算操作,并且最優化地利用了資源:對于配置操作,在4-4模式下,本運算單元一次可以配置16CP;在6-4模式下,本單元一次可以配置8CP;在8-8模式下,本單元一次可以配置2CP;在8-32模式下,本單元一次可以配置2CP。對于運算法操作,配置完成后,在運算時由RS_CP指定相應的CP參加運算,在4-4模式下,一個執行時鐘內可以完成8組運算;在6-4模式下,一個執行時鐘內可以完成4組運算;在8-8模式下,一個執行時鐘內可以完成4組運算;在8-32模式下,一個執行時鐘內可以完成1組運算。
2.2 RSU指令的設計
將RSU應用到處理器中需要有相應的指令啟動不同模式的配置和運算操作。下面根據RSU所支持的多CP配置和所支持的不同模式的運算操作,給出配置和運算的指令格式及編碼格式。指令助記符的格式如下:
配置指令格式:CSB.nTm.CP RD RS
運算指令格式:ESB. nTm.CP RD RS
CSB表示執行配置操作,ESB表示執行運算操作,nTm表示模式選擇,CP表示CP選擇,RD為目的操作數,RS為源操作數,n的取值范圍為4、6、8,m的取值范圍為4、8、32,CP的取值范圍為1~16。舉例說明如下:
CSB.4T4.2 RD RS 表示在模式4-4,將源操作數RS作為配置數據配置到地址為RD的RAM單元中。
ESB. 4T4.2 RD RS 表示在模式4-4,將RS作為源操作數進行S盒運算,結果放在地址為RD的RAM單元中。
由以上可知,指令機器碼中的控制信息至少要包括操作選擇、模式選擇和CP選擇字段;對于操作數,在不同處理器中有不同的目的及源操作數寄存器的地址位數。圖4給出控制字段所對應的機器碼格式。
指令中相應字段編碼如表2所示。
在4-4模式下,CP選擇字段的取值范圍為0000~1111;在6-4模式下,CP選擇字段的取值范圍為0000~0011;在8-8模式下,CP選擇字段的取值范圍為0000~0011;在8-32模式下,CP選擇字段的取值范圍為0000~0001。指令譯碼可以獲得可重構節點的控制信號,RSU在這些控制信號的控制下執行配置或運算操作。
3 RSU的性能測試
以上設計采用verilog語言描述,在QuartusII 5.0環境下編譯綜合,選用Altera StratixII系列器件作為目標器件進行整體綜合、仿真和底層布局。對多組數據進行測試仿真,均得到正確結果。
該模塊的運算速度可以通過以下公式得出:
運算速度＝每個時鐘運算數據的長度×系統頻率
將實現的可重構S盒運算單元下載到Altera StratixII系列器件EP2S15F484C3后,測得的主要性能指標如表3所示。
本文提出的支持4-4、6-4、8-8、8-32四種運算模式的可重構的S盒運算單元,在執行配置操作時,對于4-4模式,可以一次配置16CP;對于6-4模式,可以一次配置8CP;對于8-8模式,可以一次配置2CP;對于8-32模式,可以一次配置2CP。在執行運算操作時,在一個運算時鐘周期內可以完成8組4-4的運算,或者4組6-4的運算,或者4組8-8的運算,或者1組8-32的運算,并且當芯片不進行配置時它本身不帶有任何特定算法的信息,滿足了密碼芯片設計所需的安全性。經過在FPGA上的驗證,其運行結果正確,且運算速度較快,由于工藝的不同,當采用ASIC實現時,其性能還將在此基礎上明顯提高,從而能夠滿足實現多種密碼算法的密碼芯片的需求,為可重構密碼芯片提供了新的支持。
參考文獻
[1] Altera Corporation.Stratix II Device Handbook[M]. available at http://www.Altera.com.
[2] ?嵩天，湯志忠，汪東升.可重構計算相關研究綜述[G]. 2004年全國博士生學術論壇論文集,2004.
[3] ?高娜娜，王沁，李占才.基于AES和DES算法的可重構S盒硬件實現[J].小型微型計算機系統，2006,(3):446－449.
[4] ?IBM Corporation Carolynn Burwick Don Coppersmith Edward D’Avignon Rosario Gennaro Shai Halevi Charanjit Jutla StephenM. Matyas Jr. Luke O’Connor Mohammad Peyravian David Safford Nevenko Zunic, MARS-a candidate cipher for AES, Revised, September, 22, 1999
[5] ?ELBIRT A J. Reconfigurable computing for symmetric-key algorithms[D]. PhD thesis, Electrical and Computer Engineering Department University of Massachusetts Lowell, ?April 22, 2002.
[6] ?SINGH H, LEE M H, LU G, et al.An integrated recon-figurable system for data-parallel and computation-intensive applications[J]. IEEE transactuions on computers,2000,49(5)465-481.