??? 摘 ? 要： 在分析DES、AES、IDEA等41種分組密碼算法" title="密碼算法">密碼算法結(jié)構(gòu)的基礎(chǔ)上，研究了常用的不同位寬及不同模數(shù)" title="模數(shù)">模數(shù)的模乘運算。提出了專用的模乘運算指令，通過適配" title="適配">適配兩個參數(shù)with與type，可靈活地完成16bit" title="16bit">16bit、32bit算術(shù)乘法以及模216＋1乘的運算，并且實現(xiàn)了支持其執(zhí)行的硬件單元。最后，以專用模乘運算指令為基本指令，給出了模232-1乘、模264乘運算的實現(xiàn)方法。
??? 關(guān)鍵詞： 分組密碼" title="分組密碼">分組密碼? 可適配? 模乘運算? 專用指令
?
??? 分組密碼具有速度快、易于標準化和便于硬件實現(xiàn)等特點，通常是信息與網(wǎng)絡(luò)安全中實現(xiàn)數(shù)據(jù)加密、數(shù)字簽名、認證及密鑰管理的核心體制，而且還可以用來構(gòu)造流密碼、偽隨機數(shù)生成器、MACs(Message Authentication Codes)、Hash函數(shù)、簽名方案等。隨著芯片設(shè)計技術(shù)的發(fā)展，處理密碼算法的方式逐漸增多，專用密碼處理器作為一個高速、靈活的實現(xiàn)方式已被廣泛認可，專用密碼處理器的指令集包含較多的運算指令，這些運算指令的靈活性與執(zhí)行效率，在一定程度上決定了系統(tǒng)處理數(shù)據(jù)的靈活性與速度。對于專用的分組密碼處理器來說，模乘運算指令使用頻率較高，是其指令集設(shè)計的關(guān)健。本文在分析DES、AES、IDEA等41種分組密碼算法的基礎(chǔ)上，對分組密碼算法中模乘運算的操作特征進行研究，并提出專用模乘運算操作指令及其擴展的VLIW并行指令模型，同時給出相應(yīng)模乘運算單元的硬件設(shè)計。
1 分組密碼算法中的模乘運算
??? 41種分組密碼算法中有7種算法使用了模乘運算，數(shù)據(jù)位寬分別為16bit、32bit和64bit，RC6、MARS、TWOFISH、E2四種算法使用了模232乘法運算，DFC算法中使用了模264乘法運算，IDEA算法使用的模數(shù)為216＋1，MMB算法使用的模數(shù)為232－1，如圖1所示。
????????????????? 
??? 模264乘法和模232－1乘法在分組密碼處理中使用頻度較少，可通過基本乘法指令組合實現(xiàn)，并且設(shè)計其專用電路硬件資源占用大、延時長。而模216＋1乘法盡管適用面窄，但考慮到IDEA算法目前廣為應(yīng)用，因此設(shè)計專用模乘指令時應(yīng)考慮到模216＋1乘法運算。
2 專用模乘運算指令設(shè)計
??? 通過對分組密碼算法中常用的模乘運算的分析可知，專用模乘運算指令應(yīng)能夠完成模232、模216、模216＋1乘操作；指令的操作數(shù)位寬為32bit；每條指令有兩個源操作數(shù)和一個目的操作數(shù)；指令中包括兩個參數(shù)，分別為標識位寬的with以及標識操作類型的type，給兩個參數(shù)賦于不同的值，則可完成不同的操作。其格式如下：
MUL.with.type Rd, Rs1, Rs2
2.1 32bit乘法
??? 專用的模乘運算指令能夠?qū)崿F(xiàn)兩個32bit數(shù)據(jù)Rs1和Rs2的乘法運算，可由兩條指令分別得到其低32bit和高32bit的運算結(jié)果。
??? 低32bit運算即模232乘法指令格式為：MUL32L Rd, Rs1, Rs2，參數(shù)with為32bit，參數(shù)type為L，該指令將兩個32bit數(shù)據(jù)進行乘法運算，取低32bit送入目標寄存器，即執(zhí)行模232乘法運算。圖2(a)給出了該指令操作示意圖。
??? 32bit乘法取其高32bit運算結(jié)果的指令為： MUL32H Rd,Rs1,Rs2，該指令將兩個32bit數(shù)據(jù)進行乘法運算，取高32bit送入目標寄存器。圖2(b)給出了該指令操作示意圖。
???????????????????????? 
2.2 16bit乘法指令
??? 稱16bit寬的數(shù)據(jù)為亞字，則實現(xiàn)兩個32bit字運算可按照亞字分別進行乘法運算。
??? 低16bit乘法指令格式為：MUL16L Rd,Rs1,Rs2，該指令將兩個32bit數(shù)據(jù)的低16bit進行乘法運算，結(jié)果送入目標寄存器。圖3(a)給出了該指令操作示意圖。
??? 高16bit乘法指令格式為：MUL16H Rd,Rs1,Rs2，該指令將兩個32bit數(shù)據(jù)的高16bit進行乘法運算，結(jié)果送入目標寄存器。圖3(b)給出了該指令操作示意圖。
????????????????????????????? 
2.3 模216＋1乘法指令
??? 兩個32bit字按照16bit亞字分別進行模乘運算。32bit字中低16bit乘法指令格式為：MUL16I Rd,Rs1,Rs2，該指令對兩個32bit源操作數(shù)的低16bit執(zhí)行模216＋1乘法運算，結(jié)果送入目標寄存器低16位，將兩個源操作數(shù)的高16bit進行模216＋1乘法運算，結(jié)果送入目標寄存器高16位。圖4給出了該指令操作示意圖。
??????????????????????????? 
???????
3 模乘運算單元的硬件實現(xiàn)
??? 指令的執(zhí)行需要有相應(yīng)硬件功能單元的支持。由專用指令所完成的功能可知，模乘運算單元應(yīng)可配置地完成32bit乘法、16bit乘法及模216＋1乘法。下面在研究模216＋1乘法實現(xiàn)算法的基礎(chǔ)上，給出模乘運算單元的硬件電路。
3.1 模（2n+1）乘法的實現(xiàn)算法
??? 設(shè)a和b為兩個n位二進制數(shù),c=abmod(2n+1)， 則模(2n+1)乘法可表達為：
??? 
式中，0≤cH<2n 為高n位數(shù)據(jù),0≤cL<2n為低n位數(shù)據(jù)。
??? 由上式可以得到：
??? 
??? 當cL-cH≥0，有c=cL-cH;
??? 當cL-cH≥0，有c=cL-cH+1+2n。
??? 由此，可以得到模(2n+1)乘法的算法如下：
???? 
?
3.2 單元電路
??? 由于32bit的乘法運算可以分解為16bit的乘法與16bit加法運算，而模216+1乘法可以通過上述算法得以實現(xiàn)，因此乘法電路以16bit的乘法運算電路為核心，輔助以16bit加法運算、數(shù)據(jù)選擇器和模修正電路實現(xiàn)，如圖5所示。
???????????????????????????? 
4 其他模乘運算實現(xiàn)研究
4.1 模(2n-1)乘法運算
??? 設(shè)a、b為兩個n位二進制數(shù)，c=abmod(2n-1)，則模(2n-1)乘法可表達為：
??? 
式中,0≤cH<2n為高n位數(shù)據(jù),0≤cL<2n為低n位數(shù)據(jù)。
??? 由上式可得：
??? 
??? 當cL+cH>2n-1，有c=cL+cH+1-2n;
??? 當cL+cH=2n-1，有c=0;
??? 當cL+cH<2n-1，有c=cL+cH
??? 據(jù)此，可以得到模(2n-1)乘法的算法如下：
??? Input：n-bit數(shù)據(jù) a，b
??? 
??? 因此，模232-1乘法需要首先執(zhí)行一次MUL32L指令和一次MUL32H指令，然后執(zhí)行兩次32bit模加指令，另外還需要分支判斷指令，共計需要5～6條基本指令。
4.2 模264乘法運算
??? 進行模264乘法運算時，電路以32bit的乘法器為基本單元，通過組合實現(xiàn)64bit的模乘運算。實現(xiàn)基本原理如下：
??? 
?
式中, A和B均為64bit，AH為A的高32bit，AL為A的低32bit；BH為B的高32bit，BL為B的低32bit。由于兩數(shù)相乘后要進行模264操作，所以有：
??? 
??? 進一步的分析可以看出,(AH×BL+BH×AL)×232的結(jié)果要進行模264操作，只需將AH×BL和BH×AL相乘的低32位相加即，然后再與AL×BL的高32位相加，結(jié)果就是A×B mod 264的高32位。AL×BL的低32位就是A×B mod 264的低32bit。
??? 因此，模264乘法需要首先執(zhí)行三次MUL32L指令和三次MUL32H指令，然后連續(xù)執(zhí)行兩次32比特模加指令，共計需要8條基本指令。
??? 在分析DES、AES、IDEA等41種分組密碼算法結(jié)構(gòu)的基礎(chǔ)上，總結(jié)出算法用到的所有模乘操作，其中包括232、264、232－1、216＋1四種模數(shù)的運算，然后就其在分組密碼算法中的使用情況進行了分析與研究。綜合考慮資源及時延，提出了可高效、靈活完成232、216算術(shù)乘法及模216＋1乘操作的專用模乘運算指令，它能完成兩個字及兩個亞字的算術(shù)乘法操作，并且能夠并行執(zhí)行兩組模216＋1乘操作。設(shè)計、實現(xiàn)了支持專用模乘運算指令執(zhí)行的硬件單元。最后，在專用指令的基礎(chǔ)上，給出了模232-1乘、模264乘運算的具體實現(xiàn)。
參考文獻
[1]?MA Yu Tai. A simplified architecture for modulo(2n+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)計算相關(guān)研究綜述.中國:2004?年全國博士生學(xué)術(shù)論壇論文集, 2004.
[5]?多磊.分組密碼的設(shè)計與分析.國防科學(xué)技術(shù)大學(xué)研究生院，2002.
?