摘 要：在分析DES、AES、IDEA等41种分组密码算法" title="密码算法">密码算法结构的基础上，研究了常用的不同位宽及不同模数" title="模数">模数的模乘运算。提出了专用的模乘运算指令，通过适配" title="适配">适配两个参数with与type，可灵活地完成16bit" title="16bit">16bit、32bit算术乘法以及模2¹⁶＋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四种算法使用了模2³²乘法运算，DFC算法中使用了模264乘法运算，IDEA算法使用的模数为2¹⁶＋1，MMB算法使用的模数为232－1，如图1所示。

模2⁶⁴乘法和模2³²－1乘法在分组密码处理中使用频度较少，可通过基本乘法指令组合实现，并且设计其专用电路硬件资源占用大、延时长。而模2¹⁶＋1乘法尽管适用面窄，但考虑到IDEA算法目前广为应用，因此设计专用模乘指令时应考虑到模2¹⁶＋1乘法运算。
2 专用模乘运算指令设计
通过对分组密码算法中常用的模乘运算的分析可知，专用模乘运算指令应能够完成模2³²、模2¹⁶、模2¹⁶＋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 模2¹⁶＋1乘法指令
两个32bit字按照16bit亚字分别进行模乘运算。32bit字中低16bit乘法指令格式为：MUL16I Rd,Rs1,Rs2，该指令对两个32bit源操作数的低16bit执行模2¹⁶＋1乘法运算，结果送入目标寄存器低16位，将两个源操作数的高16bit进行模2¹⁶＋1乘法运算，结果送入目标寄存器高16位。图4给出了该指令操作示意图。

3 模乘运算单元的硬件实现
指令的执行需要有相应硬件功能单元的支持。由专用指令所完成的功能可知，模乘运算单元应可配置地完成32bit乘法、16bit乘法及模2¹⁶＋1乘法。下面在研究模2¹⁶＋1乘法实现算法的基础上，给出模乘运算单元的硬件电路。
3.1 模（2ⁿ+1）乘法的实现算法
设a和b为两个n位二进制数,c=abmod(2ⁿ+1)， 则模(2ⁿ+1)乘法可表达为：

式中，0≤c_H<2n 为高n位数据,0≤c_L<2ⁿ为低n位数据。
由上式可以得到：

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

3.2 单元电路
由于32bit的乘法运算可以分解为16bit的乘法与16bit加法运算，而模2¹⁶+1乘法可以通过上述算法得以实现，因此乘法电路以16bit的乘法运算电路为核心，辅助以16bit加法运算、数据选择器和模修正电路实现，如图5所示。

4 其他模乘运算实现研究
4.1 模(2ⁿ-1)乘法运算
设a、b为两个n位二进制数，c=abmod(2ⁿ-1)，则模(2ⁿ-1)乘法可表达为：

式中,0≤cH<2n为高n位数据,0≤c_L<2ⁿ为低n位数据。
由上式可得：

当c_L+c_H>2ⁿ-1，有c=cL+cH+1-2n;
当c_L+c_H=2ⁿ-1，有c=0;
当c_L+c_H<2ⁿ-1，有c=c_L+c_H
据此，可以得到模(2ⁿ-1)乘法的算法如下：
Input：n-bit数据 a，b

因此，模2³²-1乘法需要首先执行一次MUL32L指令和一次MUL32H指令，然后执行两次32bit模加指令，另外还需要分支判断指令，共计需要5～6条基本指令。
4.2 模264乘法运算
进行模2⁶⁴乘法运算时，电路以32bit的乘法器为基本单元，通过组合实现64bit的模乘运算。实现基本原理如下：

式中, A和B均为64bit，A_H为A的高32bit，A_L为A的低32bit；BH为B的高32bit，B_L为B的低32bit。由于两数相乘后要进行模2⁶⁴操作，所以有：

进一步的分析可以看出,(A_H×B_L+B_H×A_L)×2³²的结果要进行模264操作，只需将A_H×B_L和B_H×A_L相乘的低32位相加即，然后再与AL×BL的高32位相加，结果就是A×B mod 2⁶⁴的高32位。AL×BL的低32位就是A×B mod 2⁶⁴的低32bit。
因此，模2⁶⁴乘法需要首先执行三次MUL32L指令和三次MUL32H指令，然后连续执行两次32比特模加指令，共计需要8条基本指令。
在分析DES、AES、IDEA等41种分组密码算法结构的基础上，总结出算法用到的所有模乘操作，其中包括2³²、2⁶⁴、2³²－1、2¹⁶＋1四种模数的运算，然后就其在分组密码算法中的使用情况进行了分析与研究。综合考虑资源及时延，提出了可高效、灵活完成2³²、2¹⁶算术乘法及模2¹⁶＋1乘操作的专用模乘运算指令，它能完成两个字及两个亚字的算术乘法操作，并且能够并行执行两组模2¹⁶＋1乘操作。设计、实现了支持专用模乘运算指令执行的硬件单元。最后，在专用指令的基础上，给出了模2³²-1乘、模2⁶⁴乘运算的具体实现。
参考文献
[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] 嵩天，汤志忠，汪东升.可重构计算相关研究综述.中国:2004 年全国博士生学术论坛论文集, 2004.
[5] 多磊.分组密码的设计与分析.国防科学技术大学研究生院，2002.