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