??? 摘 ? 要： 在分析DES、AES,、IDEA等41種分組密碼算法" title="密碼算法">密碼算法結(jié)構(gòu)的基礎(chǔ)上,，研究了常用的不同位寬及不同模數(shù)" title="模數(shù)">模數(shù)的模乘運(yùn)算,。提出了專(zhuān)用的模乘運(yùn)算指令,，通過(guò)適配" title="適配">適配兩個(gè)參數(shù)with與type,，可靈活地完成16bit" title="16bit">16bit、32bit算術(shù)乘法以及模2¹⁶＋1乘的運(yùn)算,，并且實(shí)現(xiàn)了支持其執(zhí)行的硬件單元。最后,，以專(zhuān)用模乘運(yùn)算指令為基本指令,，給出了模232-1乘、模264乘運(yùn)算的實(shí)現(xiàn)方法,。
??? 關(guān)鍵詞： 分組密碼" title="分組密碼">分組密碼? 可適配? 模乘運(yùn)算? 專(zhuān)用指令

?

??? 分組密碼具有速度快,、易于標(biāo)準(zhǔn)化和便于硬件實(shí)現(xiàn)等特點(diǎn)，通常是信息與網(wǎng)絡(luò)安全中實(shí)現(xiàn)數(shù)據(jù)加密,、數(shù)字簽名,、認(rèn)證及密鑰管理的核心體制，而且還可以用來(lái)構(gòu)造流密碼,、偽隨機(jī)數(shù)生成器,、MACs(Message Authentication Codes)、Hash函數(shù),、簽名方案等,。隨著芯片設(shè)計(jì)技術(shù)的發(fā)展，處理密碼算法的方式逐漸增多,，專(zhuān)用密碼處理器作為一個(gè)高速,、靈活的實(shí)現(xiàn)方式已被廣泛認(rèn)可，專(zhuān)用密碼處理器的指令集包含較多的運(yùn)算指令,，這些運(yùn)算指令的靈活性與執(zhí)行效率,，在一定程度上決定了系統(tǒng)處理數(shù)據(jù)的靈活性與速度。對(duì)于專(zhuān)用的分組密碼處理器來(lái)說(shuō),，模乘運(yùn)算指令使用頻率較高,，是其指令集設(shè)計(jì)的關(guān)健,。本文在分析DES、AES,、IDEA等41種分組密碼算法的基礎(chǔ)上,，對(duì)分組密碼算法中模乘運(yùn)算的操作特征進(jìn)行研究，并提出專(zhuān)用模乘運(yùn)算操作指令及其擴(kuò)展的VLIW并行指令模型,，同時(shí)給出相應(yīng)模乘運(yùn)算單元的硬件設(shè)計(jì),。
1 分組密碼算法中的模乘運(yùn)算
??? 41種分組密碼算法中有7種算法使用了模乘運(yùn)算，數(shù)據(jù)位寬分別為16bit,、32bit和64bit,，RC6、MARS,、TWOFISH,、E2四種算法使用了模2³²乘法運(yùn)算，DFC算法中使用了模264乘法運(yùn)算,，IDEA算法使用的模數(shù)為2¹⁶＋1,，MMB算法使用的模數(shù)為232－1，如圖1所示,。

?????????????????
??? 模2⁶⁴乘法和模2³²－1乘法在分組密碼處理中使用頻度較少,，可通過(guò)基本乘法指令組合實(shí)現(xiàn)，并且設(shè)計(jì)其專(zhuān)用電路硬件資源占用大,、延時(shí)長(zhǎng),。而模2¹⁶＋1乘法盡管適用面窄，但考慮到IDEA算法目前廣為應(yīng)用,，因此設(shè)計(jì)專(zhuān)用模乘指令時(shí)應(yīng)考慮到模2¹⁶＋1乘法運(yùn)算,。
2 專(zhuān)用模乘運(yùn)算指令設(shè)計(jì)
??? 通過(guò)對(duì)分組密碼算法中常用的模乘運(yùn)算的分析可知，專(zhuān)用模乘運(yùn)算指令應(yīng)能夠完成模2³²,、模2¹⁶,、模2¹⁶＋1乘操作；指令的操作數(shù)位寬為32bit,；每條指令有兩個(gè)源操作數(shù)和一個(gè)目的操作數(shù),；指令中包括兩個(gè)參數(shù)，分別為標(biāo)識(shí)位寬的with以及標(biāo)識(shí)操作類(lèi)型的type,，給兩個(gè)參數(shù)賦于不同的值,，則可完成不同的操作。其格式如下：
MUL.with.type Rd, Rs1, Rs2
2.1 32bit乘法
??? 專(zhuān)用的模乘運(yùn)算指令能夠?qū)崿F(xiàn)兩個(gè)32bit數(shù)據(jù)Rs1和Rs2的乘法運(yùn)算,，可由兩條指令分別得到其低32bit和高32bit的運(yùn)算結(jié)果,。
??? 低32bit運(yùn)算即模232乘法指令格式為：MUL32L Rd, Rs1, Rs2，參數(shù)with為32bit，參數(shù)type為L(zhǎng),，該指令將兩個(gè)32bit數(shù)據(jù)進(jìn)行乘法運(yùn)算,，取低32bit送入目標(biāo)寄存器，即執(zhí)行模232乘法運(yùn)算,。圖2(a)給出了該指令操作示意圖,。
??? 32bit乘法取其高32bit運(yùn)算結(jié)果的指令為： MUL32H Rd,Rs1,Rs2，該指令將兩個(gè)32bit數(shù)據(jù)進(jìn)行乘法運(yùn)算,，取高32bit送入目標(biāo)寄存器,。圖2(b)給出了該指令操作示意圖。

????????????????????????
2.2 16bit乘法指令
??? 稱(chēng)16bit寬的數(shù)據(jù)為亞字,，則實(shí)現(xiàn)兩個(gè)32bit字運(yùn)算可按照亞字分別進(jìn)行乘法運(yùn)算,。
??? 低16bit乘法指令格式為：MUL16L Rd,Rs1,Rs2，該指令將兩個(gè)32bit數(shù)據(jù)的低16bit進(jìn)行乘法運(yùn)算,，結(jié)果送入目標(biāo)寄存器,。圖3(a)給出了該指令操作示意圖。

??? 高16bit乘法指令格式為：MUL16H Rd,Rs1,Rs2,，該指令將兩個(gè)32bit數(shù)據(jù)的高16bit進(jìn)行乘法運(yùn)算,，結(jié)果送入目標(biāo)寄存器。圖3(b)給出了該指令操作示意圖,。
?????????????????????????????

2.3 模2¹⁶＋1乘法指令
??? 兩個(gè)32bit字按照16bit亞字分別進(jìn)行模乘運(yùn)算,。32bit字中低16bit乘法指令格式為：MUL16I Rd,Rs1,Rs2，該指令對(duì)兩個(gè)32bit源操作數(shù)的低16bit執(zhí)行模2¹⁶＋1乘法運(yùn)算,，結(jié)果送入目標(biāo)寄存器低16位,，將兩個(gè)源操作數(shù)的高16bit進(jìn)行模2¹⁶＋1乘法運(yùn)算,，結(jié)果送入目標(biāo)寄存器高16位,。圖4給出了該指令操作示意圖,。

??????????????????????????? ???????
3 模乘運(yùn)算單元的硬件實(shí)現(xiàn)
??? 指令的執(zhí)行需要有相應(yīng)硬件功能單元的支持。由專(zhuān)用指令所完成的功能可知,，模乘運(yùn)算單元應(yīng)可配置地完成32bit乘法、16bit乘法及模2¹⁶＋1乘法,。下面在研究模2¹⁶＋1乘法實(shí)現(xiàn)算法的基礎(chǔ)上,，給出模乘運(yùn)算單元的硬件電路。
3.1 模（2ⁿ+1）乘法的實(shí)現(xiàn)算法
??? 設(shè)a和b為兩個(gè)n位二進(jìn)制數(shù),c=abmod(2ⁿ+1),， 則模(2ⁿ+1)乘法可表達(dá)為：
???

式中,，0≤c_H<2n 為高n位數(shù)據(jù),0≤c_L<2ⁿ為低n位數(shù)據(jù)。
??? 由上式可以得到：
???

??? 當(dāng)c_L-c_H≥0,，有c=c_L-c_H;
??? 當(dāng)c_L-c_H≥0,，有c=c_L-c_H+1+2ⁿ。
??? 由此，可以得到模(2ⁿ+1)乘法的算法如下：
???? ?

3.2 單元電路
??? 由于32bit的乘法運(yùn)算可以分解為16bit的乘法與16bit加法運(yùn)算,，而模2¹⁶+1乘法可以通過(guò)上述算法得以實(shí)現(xiàn),，因此乘法電路以16bit的乘法運(yùn)算電路為核心，輔助以16bit加法運(yùn)算,、數(shù)據(jù)選擇器和模修正電路實(shí)現(xiàn),，如圖5所示。

????????????????????????????
4 其他模乘運(yùn)算實(shí)現(xiàn)研究
4.1 模(2ⁿ-1)乘法運(yùn)算
??? 設(shè)a,、b為兩個(gè)n位二進(jìn)制數(shù),，c=abmod(2ⁿ-1)，則模(2ⁿ-1)乘法可表達(dá)為：
???

式中,0≤cH<2n為高n位數(shù)據(jù),0≤c_L<2ⁿ為低n位數(shù)據(jù),。
??? 由上式可得：
???

??? 當(dāng)c_L+c_H>2ⁿ-1,，有c=cL+cH+1-2n;
??? 當(dāng)c_L+c_H=2ⁿ-1，有c=0;
??? 當(dāng)c_L+c_H<2ⁿ-1,，有c=c_L+c_H
??? 據(jù)此,，可以得到模(2ⁿ-1)乘法的算法如下：
??? Input：n-bit數(shù)據(jù) a，b
???

??? 因此,，模2³²-1乘法需要首先執(zhí)行一次MUL32L指令和一次MUL32H指令,，然后執(zhí)行兩次32bit模加指令，另外還需要分支判斷指令,，共計(jì)需要5～6條基本指令,。
4.2 模264乘法運(yùn)算
??? 進(jìn)行模2⁶⁴乘法運(yùn)算時(shí)，電路以32bit的乘法器為基本單元,，通過(guò)組合實(shí)現(xiàn)64bit的模乘運(yùn)算,。實(shí)現(xiàn)基本原理如下：
??? ?

式中, A和B均為64bit，A_H為A的高32bit,，A_L為A的低32bit,；BH為B的高32bit，B_L為B的低32bit,。由于兩數(shù)相乘后要進(jìn)行模2⁶⁴操作,，所以有：
???

??? 進(jìn)一步的分析可以看出,(A_H×B_L+B_H×A_L)×2³²的結(jié)果要進(jìn)行模264操作，只需將A_H×B_L和B_H×A_L相乘的低32位相加即,，然后再與AL×BL的高32位相加,，結(jié)果就是A×B mod 2⁶⁴的高32位。AL×BL的低32位就是A×B mod 2⁶⁴的低32bit,。
??? 因此,，模2⁶⁴乘法需要首先執(zhí)行三次MUL32L指令和三次MUL32H指令，然后連續(xù)執(zhí)行兩次32比特模加指令,，共計(jì)需要8條基本指令,。
??? 在分析DES、AES、IDEA等41種分組密碼算法結(jié)構(gòu)的基礎(chǔ)上,，總結(jié)出算法用到的所有模乘操作,，其中包括2³²、2⁶⁴,、2³²－1,、2¹⁶＋1四種模數(shù)的運(yùn)算，然后就其在分組密碼算法中的使用情況進(jìn)行了分析與研究,。綜合考慮資源及時(shí)延,，提出了可高效、靈活完成2³²,、2¹⁶算術(shù)乘法及模2¹⁶＋1乘操作的專(zhuān)用模乘運(yùn)算指令,，它能完成兩個(gè)字及兩個(gè)亞字的算術(shù)乘法操作，并且能夠并行執(zhí)行兩組模2¹⁶＋1乘操作,。設(shè)計(jì),、實(shí)現(xiàn)了支持專(zhuān)用模乘運(yùn)算指令執(zhí)行的硬件單元。最后,，在專(zhuān)用指令的基礎(chǔ)上,，給出了模2³²-1乘、模2⁶⁴乘運(yùn)算的具體實(shí)現(xiàn),。
參考文獻(xiàn)
[1]?MA Yu Tai. A simplified architecture for modulo(2ⁿ+1)?multiplication. IEEE TRANSACTIONS ON COMPUTERS,
?1998,47(3).
[2]?ELBIRT A J. Reconfigurable computing for symmetrickey?algorithms. PhD thesis, Electrical and Computer Engineering Department University of Massachusetts Lowell, April?22, 2002.
[3]?SINGH H, LEE M H, LU Guamig Ming, et al. MorphoSys:An integrated reconfigurable system for data-parallel and?Computation-Intensive Applications[J]. IEEE Transactions?on Computers,2000,49(5):465-481.
[4]?嵩天,，湯志忠，汪東升.可重構(gòu)計(jì)算相關(guān)研究綜述.中國(guó):2004?年全國(guó)博士生學(xué)術(shù)論壇論文集, 2004.
[5]?多磊.分組密碼的設(shè)計(jì)與分析.國(guó)防科學(xué)技術(shù)大學(xué)研究生院,，2002.

?