可適配多路并行移位操作指令及其硬件實(shí)現(xiàn)研究

分組密碼具有速度快、易于標(biāo)準(zhǔn)化和便于軟硬件實(shí)現(xiàn)等特點(diǎn),已成為信息與網(wǎng)絡(luò)安全中實(shí)現(xiàn)數(shù)據(jù)加密、數(shù)字簽名、認(rèn)證及密鑰管理的核心體制之一。隨著密碼學(xué)和芯片設(shè)計(jì)技術(shù)的發(fā)展,專用密碼處理器作為一個(gè)高速、靈活的實(shí)現(xiàn)方式已被廣泛認(rèn)可。專用分組密碼處理器的指令集包含了較多運(yùn)算指令,這些運(yùn)算指令的靈活性與執(zhí)行效率在一定程度上決定了系統(tǒng)處理數(shù)據(jù)的靈活性與速度。移位操作具有較好的擾亂與擴(kuò)散作用,又易于軟硬件實(shí)現(xiàn),所以其使用頻率非常高,因而移位操作指令的設(shè)計(jì)成為專用分組密碼處理器指令集設(shè)計(jì)的關(guān)鍵之一。本設(shè)計(jì)基于32位RISC微處理器,提出了可適配的、支持多路并行執(zhí)行的移位操作指令RPSI(Reconfigurable and Parallel Shift Instruction),能夠?qū)崿F(xiàn)字節(jié)移位、亞字移位、字移位以及雙字的級(jí)聯(lián)移位,并通過(guò)指令組合實(shí)現(xiàn)長(zhǎng)字移位。文章給出了相應(yīng)移位運(yùn)算單元的硬件設(shè)計(jì),最后給出了移位運(yùn)算單元的性能分析。

1 分組密碼算法中的移位操作

分組密碼算法中用到了大量的移位操作,但其執(zhí)行模式各不相同。

移位操作按照所移位數(shù)是否可變,分為固定移位和不定移位?；诔Ａ康墓潭ㄒ莆皇欠纸M密碼處理中一種最主要的移位模式,它使數(shù)據(jù)比特到達(dá)指定的位置,且算法不易遭受定時(shí)攻擊,包含移位位數(shù)及其補(bǔ)碼的寄存器內(nèi)容也可抵抗能量攻擊[6],在Rijndael、DES、RC6等41種分組密碼算法中有25種算法使用了固定移位[1]。依賴于分組運(yùn)算中間數(shù)據(jù)或子密鑰的不定移位模式,使不同子數(shù)據(jù)路徑上的分組之間有了較好的擾亂與擴(kuò)散效果,因此具有較強(qiáng)的抵抗線性密碼分析的能力,目前已經(jīng)得到廣泛應(yīng)用。所在分析的41種分組密碼算法中有10種算法使用了不定移位。表1給出了移位操作在常用分組密碼算法中的應(yīng)用。

移位操作按照其移位方式,可分為循環(huán)移位方式和邏輯移位方式,其中,循環(huán)移位方式應(yīng)用較多,如Serpent[2]、Twofish[3]、MARS[4]等算法均使用了循環(huán)移位。

移位操作按照移位方向,可分為左向移位和右向移位方式。

按照移位的操作位寬,可分為字節(jié)(8bit)移位、亞字(16bit)移位、字(32bit)移位、雙字(64bit)移位及長(zhǎng)字(128bit)移位。除DES算法移位操作的操作位寬為28bit外,其他算法的操作位寬均為2n bit(n=34567)?？紤]到一些專用領(lǐng)域,像軍事應(yīng)用,有些專用密碼算法所使用的移位操作位寬已達(dá)到256bit, 但因當(dāng)前分組密碼算法的處理位寬多為32bit,所以字移位操作的使用頻率相對(duì)較高。

2 RPSI的設(shè)計(jì)及其可擴(kuò)展、可級(jí)聯(lián)特性研究

2.1 RPSI的設(shè)計(jì)

經(jīng)對(duì)分組密碼算法中移位操作特征的分析可知,完成一個(gè)指定的移位操作,需要確定其移位位數(shù)是否可變,采用何種移位方式、移位方向及移位操作位寬,所以移位操作指令的func域要包含的四個(gè)參數(shù)為:source、com、width、mode,加上標(biāo)識(shí)移位位數(shù)是立即數(shù)的shift域,以及指令本身的操作數(shù)域rd、rs1及rs2,其指令格式如表2。

對(duì)func域上的source、come、width、mode適配不同的值后,此指令就可以完成不同的移位操作。由于當(dāng)前常用密碼算法的處理位寬多為32bit,且本設(shè)計(jì)是基于32位RISC微處理器,所以設(shè)定其操作數(shù)rd、rs1,rs2的位寬為32bit的寄存器數(shù),imm為5bit的立即數(shù),它根據(jù)參數(shù)source而定。

sourse的值可適配為1或0。適配為0時(shí),代表所進(jìn)行的操作為固定移位,imm為5bit的立即數(shù);適配為1時(shí),代表所進(jìn)行的操作為不定移位,移位位數(shù)存放在rs2中,rs2為32bit的寄存器數(shù)(取后5位);mode為移位模式,00時(shí)為邏輯左移,01時(shí)為邏輯右移,10時(shí)為循環(huán)左移,11時(shí)為循環(huán)右移。width是8bit、16bit或32bit移位位寬的選擇。width為00時(shí),表示執(zhí)行字節(jié)移位,一條指令可并行完成四組字節(jié)移位;width為01時(shí),執(zhí)行亞字移位,一條指令可并行完成兩組;為10時(shí),執(zhí)行字移位。例如:指令I(lǐng)ROLm Rd, Rs1, #3,它所完成的操作為:將寄存器Rs1中的32bit數(shù)按8bit分四組,分別進(jìn)行固定的循環(huán)左移,移位位數(shù)為3;同理,進(jìn)行相應(yīng)的不定移位操作時(shí),其指令為ROLm Rd, Rs1, Rs2,其移位位數(shù)由Rs2寄存器數(shù)的低5bit指定。圖1(a)、圖1(b)給出了當(dāng)width為8時(shí),執(zhí)行四種字節(jié)移位操作指令的功能示意圖,指令將輸入的32bit數(shù)據(jù)分為4個(gè)字節(jié),每個(gè)字節(jié)自身獨(dú)立地進(jìn)行指定模式的移位操作。圖1(c)、圖1(d)給出了當(dāng)width為32bit時(shí)的字移位操作功能示意圖。

2.2 RPSI的級(jí)聯(lián)執(zhí)行

隨著分組密碼算法主流分組寬度的增加,僅在32bit數(shù)據(jù)路徑上的移位操作已不能滿足要求,但由于RISC處理器32位位寬的局限性,不能改變其32bit的數(shù)據(jù)路徑,因此在進(jìn)一步研究移位操作的基礎(chǔ)上,提出了移位操作指令的級(jí)聯(lián)執(zhí)行模式,即64bit級(jí)聯(lián)移位。

假設(shè)要執(zhí)行的操作為64bit循環(huán)左移,移位位數(shù)為m,其指令為CROL Rd, Rs1, Rs2, #imm,這時(shí)指令格式中func域的com值是1,表示級(jí)聯(lián)。Rs1、Rs2是64bit源操作數(shù),Rs1中存放的是64bit中高32bit,Rs2中存放的是64bit中低32bit,Rd為目的操作數(shù),運(yùn)算后存放的是64bit移位的高32bit結(jié)果。下一個(gè)時(shí)鐘(第二步),交換64bit的高低32bit,運(yùn)算后Rd存放64bit移位的低32bit結(jié)果。

這樣就在32bit的數(shù)據(jù)路徑上實(shí)現(xiàn)了64bit的移位操作。其功能示意圖如圖2所示。

同理可執(zhí)行循環(huán)右移操作。但在執(zhí)行級(jí)聯(lián)的邏輯移位操作時(shí)有所不同,進(jìn)行邏輯左移時(shí),第一步與循環(huán)移位相同,在第二步時(shí),Rs1中存放的是64bit中低32bit,Rs2中存放的操作數(shù)是全零;進(jìn)行邏輯右移時(shí),在第一步時(shí),Rs1中存放的是64bit中高32bit,Rs2中存放的操作數(shù)全為零,第二步與循環(huán)移位相同。

2.3 RPSI的組合執(zhí)行

某些密碼算法的移位操作位寬是128bit,例如IDEA算法的子密鑰生成中,就用到了長(zhǎng)字移位操作。在級(jí)聯(lián)移位指令的基礎(chǔ)上,通過(guò)指令的組合實(shí)現(xiàn)128bit移位操作,或者更長(zhǎng)位寬的移位操作,例如:要完成128bit的移位,需要執(zhí)行四條級(jí)聯(lián)移位指令。

以128bit邏輯左移5位為例,假設(shè)R4R3R2R1表示128bit待移位的數(shù)據(jù),則執(zhí)行指令CSHL Rd, R1, Rs, #5(Rs中的數(shù)是全零),得到移位后最終結(jié)果的31~0位;執(zhí)行指令CSHL Rd, R2, R1, #5,得到移位后最終結(jié)果的63～32位,執(zhí)行指令CSHL Rd, R3, R2, #5,得到移位后最終結(jié)果的95~64位;執(zhí)行指令CSHL Rd, R4, R3, #5,得到移位后最終結(jié)果的127～96位。

再以128bit循環(huán)左移5位為例,假設(shè)R4R3R2R1表示128bit待移位的數(shù)據(jù),則執(zhí)行指令CROL Rd, R1,R4,#5,得到移位后最終結(jié)果的31～0位,執(zhí)行指令CROL Rd,R2,R1,#5,得到移位后最終結(jié)果的63～32位;執(zhí)行指令CROL Rd,R3,R2,#5,得到移位后最終結(jié)果的95～64位;執(zhí)行指令CROL Rd,R4,R2,#5,得到移位后最終結(jié)果的127～96位。

同理,可以用這種多條指令組合的方式實(shí)現(xiàn)256bit的移位。128bit移位操作功能示意圖如圖3所示。

3 RPSI的硬件實(shí)現(xiàn)及其性能分析

3.1 移位操作硬件實(shí)現(xiàn)算法研究

傳統(tǒng)的實(shí)現(xiàn)方法中,基于線性反饋移位寄存器LFSR是實(shí)現(xiàn)移位操作的一種主要方式,LFSR通常以移1位運(yùn)算為基礎(chǔ),循環(huán)移k位通過(guò)k次調(diào)用移1位基本運(yùn)算實(shí)現(xiàn),占用k個(gè)時(shí)鐘周期,移位速度受移位位數(shù)的影響。因此對(duì)于移位位數(shù)較大的操作,采用LFSR進(jìn)行循環(huán)移位運(yùn)算很難滿足高速數(shù)據(jù)處理的需求。

循環(huán)移位操作還可以看作是一類(lèi)特殊的置換,采用基于BENES網(wǎng)絡(luò)的實(shí)現(xiàn)方法。但是,由于移位位數(shù)k的不確定性,導(dǎo)致配置信息生成電路較為復(fù)雜,不利于軟硬件實(shí)現(xiàn)。下面在對(duì)循環(huán)移位及邏輯移位分別研究的基礎(chǔ)上,給出了基于數(shù)據(jù)選擇器的實(shí)現(xiàn)方法。

(1) 循環(huán)移位的實(shí)現(xiàn)

令移位位數(shù)k=kn-12n-1+kn-22n-2+…+…k12+k0,則循環(huán)移位可以表示為: y=RSH(a,k),y的第j位y(j)可以表示為: y(j)=a((j±k)modN)

其中,執(zhí)行左移操作時(shí)操作符為“-”,執(zhí)行右移操作時(shí)操作符為“+”,N為操作數(shù)a的位寬。由此可得:

即:任意位的循環(huán)移位操作分解為若干加減2i置換操作的級(jí)聯(lián)。對(duì)于循環(huán)左移而言,循環(huán)移位操作可以分解為減2i置換操作。

循環(huán)左移操作算法描述:

Input:操作數(shù)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)

當(dāng)N=2n時(shí),循環(huán)左移操作可以采用n級(jí)數(shù)據(jù)選擇器實(shí)現(xiàn),每一級(jí)使用N個(gè)二選一數(shù)據(jù)選擇器,共計(jì)需要nN個(gè)二選一數(shù)據(jù)選擇器,系統(tǒng)的延遲相當(dāng)于n級(jí)二選一數(shù)據(jù)選擇器的延遲。循環(huán)右移操作可以看作循環(huán)移位位數(shù)為N-k的循環(huán)左移操作,由此可以構(gòu)造如圖4所示的循環(huán)移位結(jié)構(gòu)。

(2) 邏輯移位的實(shí)現(xiàn)

對(duì)于邏輯左移,上述算法可以修改如下:

Input:操作數(shù) a,移位位數(shù) 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)

可以采用類(lèi)似的方法對(duì)邏輯右移操作算法進(jìn)行修改,本文不再贅述。在硬件實(shí)現(xiàn)時(shí),可以通過(guò)將上述循環(huán)移位電路的每一個(gè)數(shù)據(jù)選擇器擴(kuò)展為四選一實(shí)現(xiàn)支持循環(huán)移位和邏輯移位的電路。

3.2 移位操作硬件單元的實(shí)現(xiàn)及性能分析

根據(jù)基于數(shù)據(jù)選擇器的實(shí)現(xiàn)原理,用verilog語(yǔ)言實(shí)現(xiàn)了32bit數(shù)據(jù)路徑上的移位操作硬件單元,用modelsim SE 6.0仿真軟件進(jìn)行了功能仿真,對(duì)于RPSI所指定的功能,均能正確完成。使用Design Compiler綜合工具進(jìn)行了綜合,在0.18μm工藝下綜合結(jié)果如表3。

由前面分析可知,要完成32bit數(shù)據(jù)路徑上RPSI不同模式的移位操作,只需在圖4的每個(gè)選擇輸入上加一個(gè)四選一的數(shù)據(jù)選擇器,其關(guān)鍵路徑即為一級(jí)四選一數(shù)據(jù)選擇器和六級(jí)二選一數(shù)據(jù)選擇器的路徑延遲。

移位操作是密碼算法中常用的運(yùn)算,特別是在密鑰調(diào)度中用于子密鑰的生成。本文在分析Rijndael、DES、RC6等41種分組密碼算法的基礎(chǔ)上,首先對(duì)分組密碼算法中移位運(yùn)算的操作特征進(jìn)行了研究,結(jié)合移位操作特征,提出了可適配的、支持多路并行執(zhí)行的RPSI;通過(guò)適配操作特征域上的source、com、width、mode四個(gè)參數(shù),可完成固定或不定、循環(huán)或邏輯、左向或右向、不同位寬下的移位操作,能夠支持字節(jié)移位、亞字移位、字移位以及雙字的級(jí)聯(lián)移位,并通過(guò)指令組合實(shí)現(xiàn)長(zhǎng)字移位;設(shè)計(jì)并實(shí)現(xiàn)了其硬件單元,給出了硬件單元的性能分析。