??? 摘? 要: 在分析Rijndael、Serpent、MARS等41種分組密碼算法" title="密碼算法">密碼算法的基礎上,對分組密碼算法中移位的操作特征進行了研究,提出了可適配" title="適配">適配、支持多路并行執行的移位操作指令" title="操作指令">操作指令,通過適配參數,可完成固定或不定、循環或邏輯、左向或右向、不同位寬的移位操作,不同位寬的操作支持不同組數的并行執行,并給出了其級聯" title="級聯">級聯及組合的指令模型,研究了移位操作的硬件實現算法,設計并實現了硬件單元,給出了其性能分析。?
??? 關鍵詞: 分組密碼; 可適配; 并行; 移位操作指令?
?
??? 分組密碼具有速度快、易于標準化和便于軟硬件實現等特點,已成為信息與網絡安全中實現數據加密、數字簽名、認證及密鑰管理的核心體制之一。隨著密碼學和芯片設計技術的發展,專用密碼處理器作為一個高速、靈活的實現方式已被廣泛認可。專用分組密碼處理器的指令集包含了較多運算指令,這些運算指令的靈活性與執行效率在一定程度上決定了系統處理數據的靈活性與速度。移位操作具有較好的擾亂與擴散作用,又易于軟硬件實現,所以其使用頻率非常高,因而移位操作指令的設計成為專用分組密碼處理器指令集設計的關鍵之一。本設計基于32位RISC微處理器,提出了可適配的、支持多路并行執行的移位操作指令RPSI(Reconfigurable and Parallel Shift Instruction),能夠實現字節移位、亞字移位、字移位以及雙字的級聯移位,并通過指令組合實現長字移位。文章給出了相應移位運算單元的硬件設計,最后給出了移位運算單元的性能分析。?
1 分組密碼算法中的移位操作
??? 分組密碼算法中用到了大量的移位操作,但其執行模式各不相同。?
??? 移位操作按照所移位數是否可變,分為固定移位和不定移位。基于常量的固定移位是分組密碼處理中一種最主要的移位模式,它使數據比特到達指定的位置,且算法不易遭受定時攻擊,包含移位位數及其補碼的寄存器內容也可抵抗能量攻擊[6],在Rijndael、DES、RC6等41種分組密碼算法中有25種算法使用了固定移位[1]。依賴于分組運算中間數據或子密鑰的不定移位模式,使不同子數據路徑上的分組之間有了較好的擾亂與擴散效果,因此具有較強的抵抗線性密碼分析的能力,目前已經得到廣泛應用。所在分析的41種分組密碼算法中有10種算法使用了不定移位。表1給出了移位操作在常用分組密碼算法中的應用。?
?
?
??? 移位操作按照其移位方式,可分為循環移位方式和邏輯移位方式,其中,循環移位方式應用較多,如Serpent[2]、Twofish[3]、MARS[4]等算法均使用了循環移位。?
??? 移位操作按照移位方向,可分為左向移位和右向移位方式。?
??? 按照移位的操作位寬,可分為字節(8bit)移位、亞字(16bit)移位、字(32bit)移位、雙字(64bit)移位及長字(128bit)移位。除DES算法移位操作的操作位寬為28bit外,其他算法的操作位寬均為2n bit(n=34567)。考慮到一些專用領域,像軍事應用,有些專用密碼算法所使用的移位操作位寬已達到256bit, 但因當前分組密碼算法的處理位寬多為32bit,所以字移位操作的使用頻率相對較高。?
2 RPSI的設計及其可擴展、可級聯特性研究?
2.1 RPSI的設計?
??? 經對分組密碼算法中移位操作特征的分析可知,完成一個指定的移位操作,需要確定其移位位數是否可變,采用何種移位方式、移位方向及移位操作位寬,所以移位操作指令的func域要包含的四個參數為:source、com、width、mode,加上標識移位位數是立即數的shift域,以及指令本身的操作數域rd、rs1及rs2,其指令格式如表2。
?
?
??? 對func域上的source、come、width、mode適配不同的值后,此指令就可以完成不同的移位操作。由于當前常用密碼算法的處理位寬多為32bit,且本設計是基于32位RISC微處理器,所以設定其操作數rd、rs1,rs2的位寬為32bit的寄存器數,imm為5bit的立即數,它根據參數source而定。?
??? sourse的值可適配為1或0。適配為0時,代表所進行的操作為固定移位,imm為5bit的立即數;適配為1時,代表所進行的操作為不定移位,移位位數存放在rs2中,rs2為32bit的寄存器數(取后5位);mode為移位模式,00時為邏輯左移,01時為邏輯右移,10時為循環左移,11時為循環右移。width是8bit、16bit或32bit移位位寬的選擇。width為00時,表示執行字節移位,一條指令可并行完成四組字節移位;width為01時,執行亞字移位,一條指令可并行完成兩組;為10時,執行字移位。例如:指令IROLm Rd, Rs1, #3,它所完成的操作為:將寄存器Rs1中的32bit數按8bit分四組,分別進行固定的循環左移,移位位數為3;同理,進行相應的不定移位操作時,其指令為ROLm Rd, Rs1, Rs2,其移位位數由Rs2寄存器數的低5bit指定。圖1(a)、圖1(b)給出了當width為8時,執行四種字節移位操作指令的功能示意圖,指令將輸入的32bit數據分為4個字節,每個字節自身獨立地進行指定模式的移位操作。圖1(c)、圖1(d)給出了當width為32bit時的字移位操作功能示意圖。
?
?
2.2 RPSI的級聯執行?
??? 隨著分組密碼算法主流分組寬度的增加,僅在32bit數據路徑上的移位操作已不能滿足要求,但由于RISC處理器32位位寬的局限性,不能改變其32bit的數據路徑,因此在進一步研究移位操作的基礎上,提出了移位操作指令的級聯執行模式,即64bit級聯移位。?
??? 假設要執行的操作為64bit循環左移,移位位數為m,其指令為CROL? Rd, Rs1, Rs2, #imm,這時指令格式中func域的com值是1,表示級聯。Rs1、Rs2是64bit源操作數,Rs1中存放的是64bit中高32bit,Rs2中存放的是64bit中低32bit,Rd為目的操作數,運算后存放的是64bit移位的高32bit結果。下一個時鐘(第二步),交換64bit的高低32bit,運算后Rd存放64bit移位的低32bit結果。?
??? 這樣就在32bit的數據路徑上實現了64bit的移位操作。其功能示意圖如圖2所示。?
?
?
??? 同理可執行循環右移操作。但在執行級聯的邏輯移位操作時有所不同,進行邏輯左移時,第一步與循環移位相同,在第二步時,Rs1中存放的是64bit中低32bit,Rs2中存放的操作數是全零;進行邏輯右移時,在第一步時,Rs1中存放的是64bit中高32bit,Rs2中存放的操作數全為零,第二步與循環移位相同。?
2.3 RPSI的組合執行?
??? 某些密碼算法的移位操作位寬是128bit,例如IDEA算法的子密鑰生成中,就用到了長字移位操作。在級聯移位指令的基礎上,通過指令的組合實現128bit移位操作,或者更長位寬的移位操作,例如:要完成128bit的移位,需要執行四條級聯移位指令。?
??? 以128bit邏輯左移5位為例,假設R4&R3&R2&R1表示128bit待移位的數據,則執行指令CSHL? Rd, R1, Rs, #5(Rs中的數是全零),得到移位后最終結果的31~0位;執行指令CSHL? Rd, R2, R1, #5,得到移位后最終結果的63～32位,執行指令CSHL? Rd, R3, R2, #5,得到移位后最終結果的95~64位;執行指令CSHL Rd, R4, R3, #5,得到移位后最終結果的127～96位。?
??? 再以128bit循環左移5位為例,假設R4&R3&R2&R1表示128bit待移位的數據,則執行指令CROL Rd, R1,R4,#5,得到移位后最終結果的31～0位,執行指令CROL Rd,R2,R1,#5,得到移位后最終結果的63～32位;執行指令CROL Rd,R3,R2,#5,得到移位后最終結果的95～64位;執行指令CROL Rd,R4,R2,#5,得到移位后最終結果的127～96位。?
??? 同理,可以用這種多條指令組合的方式實現256bit的移位。128bit移位操作功能示意圖如圖3所示。
?
?
3 RPSI的硬件實現及其性能分析?
3.1 移位操作硬件實現算法研究?
??? 傳統的實現方法中,基于線性反饋移位寄存器LFSR是實現移位操作的一種主要方式,LFSR通常以移1位運算為基礎,循環移k位通過k次調用移1位基本運算實現,占用k個時鐘周期,移位速度受移位位數的影響。因此對于移位位數較大的操作,采用LFSR進行循環移位運算很難滿足高速數據處理的需求。?
??? 循環移位操作還可以看作是一類特殊的置換,采用基于BENES網絡的實現方法。但是,由于移位位數k的不確定性,導致配置信息生成電路較為復雜,不利于軟硬件實現。下面在對循環移位及邏輯移位分別研究的基礎上,給出了基于數據選擇器" title="數據選擇器">數據選擇器的實現方法。?
??? (1) 循環移位的實現?
??? 令移位位數k=kn-12n-1+kn-22n-2+…+…k12+k0,則循環移位可以表示為: y=RSH(a,k),y的第j位y(j)可以表示為: y(j)=a((j±k)modN)?
其中,執行左移操作時操作符為“-”,執行右移操作時操作符為“+”,N為操作數a的位寬。由此可得:?
??? 
即:任意位的循環移位操作分解為若干加減2i置換操作的級聯。對于循環左移而言,循環移位操作可以分解為減2i置換操作。?
??? 循環左移操作算法描述:?
Input:操作數a, k=kn-12n-1+ kn-22n-2+…+k12+k0?? Output:y ?
??? (1) y←a?
??? (2) For i=n-1 downto 0 do?
??? (3) For j= 0 to N-1 do?
??????? ?If ki=1 then ?
??????????? ?If j≤k then b(j)=y((j-2i)modN) ?
???????????? else b(j)=0?
?????????????else b(j)=y(j)?
??? (4) y=b Return (y)?
??? 當N=2n時,循環左移操作可以采用n級數據選擇器實現,每一級使用N個二選一數據選擇器,共計需要nN個二選一數據選擇器,系統的延遲相當于n級二選一數據選擇器的延遲。循環右移操作可以看作循環移位位數為N-k的循環左移操作,由此可以構造如圖4所示的循環移位結構。
?
?
??? (2) 邏輯移位的實現?
??? 對于邏輯左移,上述算法可以修改如下:?
Input:操作數 a,移位位數?k=kn-12n-1+ kn-22n-2+…+k12+k0? Output:y ?
???? ① y←a?
???? ② For i=n-1 downto 0 do?
???? ③?For j= 0 to N-1 do?
???????????If ki=1 then ?
??????????????If j≤k then b(j)=y((j-2i)modN) ?
???????????else? b(j)=0?
????????else? b(j)=y(j)?
?? ? ④ y=b Return (y)?
??? 可以采用類似的方法對邏輯右移操作算法進行修改,本文不再贅述。在硬件實現時,可以通過將上述循環移位電路的每一個數據選擇器擴展為四選一實現支持循環移位和邏輯移位的電路。?
3.2 移位操作硬件單元的實現及性能分析?
??? 根據基于數據選擇器的實現原理,用verilog語言實現了32bit數據路徑上的移位操作硬件單元,用modelsim SE 6.0仿真軟件進行了功能仿真,對于RPSI所指定的功能,均能正確完成。使用Design Compiler綜合工具進行了綜合,在0.18μm工藝下綜合結果如表3。?
?
?
??? 由前面分析可知,要完成32bit數據路徑上RPSI不同模式的移位操作,只需在圖4的每個選擇輸入上加一個四選一的數據選擇器,其關鍵路徑即為一級四選一數據選擇器和六級二選一數據選擇器的路徑延遲。?
??? 移位操作是密碼算法中常用的運算,特別是在密鑰調度中用于子密鑰的生成。本文在分析Rijndael、DES、RC6等41種分組密碼算法的基礎上,首先對分組密碼算法中移位運算的操作特征進行了研究,結合移位操作特征,提出了可適配的、支持多路并行執行的RPSI;通過適配操作特征域上的source、com、width、mode四個參數,可完成固定或不定、循環或邏輯、左向或右向、不同位寬下的移位操作,能夠支持字節移位、亞字移位、字移位以及雙字的級聯移位,并通過指令組合實現長字移位;設計并實現了其硬件單元,給出了硬件單元的性能分析。?
參考文獻?
[1] ELBIRT A J. Reconfigurable computing for symmetric-key?algorithms. PhD thesis, Electrical and Computer Engineering?Department University of Massachusetts Lowell,2002,(4): 22.
[2] Ross Anderson Eli Biham Lars Knudsen Serpent: A Proposal?for the Advanced Encryption Standard http://www.ii.uib.no/~larsr/?
[3] Bruce Schneier John Kelsey Doug Whiting Twofish: A?128-Bit Block Cipher http://www.counterpane.com/twofish.html?
[4] IBM Corporation Carolynn Burwick Don Coppersmith Edward?D’Avignon, MARS-a candidate cipher for AES, Revised,?1999,(9):22.?
[5] FISKIRAN A M, LEE R B. Fast parallel table lookups to ? accelerate symmetric-key cryptography, Proceedings of the?International Conference on Information Technology Coding??and Computing (ITCC), Embedded Cryptographic Systems?Track, 2005,(4):4-6.? Las Vegas, Nevada, USA?
[6] 彭巍.一種分組密碼算法測試平臺設計.電子科技大學碩士學位論文,2004,12.?