在FPGA上快速实现MD5算法的新方法论文
摘 要 文章介绍了一种在FPGA上快速实现MD5算法的新方法，给出了优化设计的原理、实现的具体方法及其重要模块的设计实现方案。
关键词 MD5；FPGA；Verilog语言；集成电路；关键路径
1 引言
随着电子商务和网络通信的发展，网络信息安全的重要性越来越显著，信息加密、数字签名、数据的完整性认证、身份验证等成为信息安全领域的重要内容。MD5算法本身是为数字签名应用而设计的，随后也应用在信息验证技术当中。作为应用最广泛的安全散列算法，MD5算法的高效实现就成为研究的需要，MD5算法本身可以采用软件实现，但其性能受到处理器件性能的制约不能满足网络通信带宽日益增长的要求，因而通过硬件实现高速MD5 运算就成为需要。
2 MD5算法介绍
MD5 算法可以对任何长度不超过 264二进制位的消息产生128 位的单向散列消息摘要输出， RFC1321 标准中的MD5 算法主要步骤如下：
在一些初始化处理后，MD5以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由四个32位分组组成，将它们级联形成一个128位散列值。
（1）附加填充比特：填充消息使其长度恰好为一个比512位的倍数仅小64位的数。即对报文进行填充使报文的长度(比特数)与448模512同余。填充方法是附一个１在消息后面接所要求的多个比特０。
（2）附加长度值：在其后附上64位的消息长度（填充前）。如果消息长度大于 264，仅使用该长度的低64比特。这样，该域包含的长度值为初始长度模264 的值。
这两步的作用是使消息长度恰好是512位的整数倍（算法的其余部分要求如此），同时确保不同的消息在填充后不相同。
（3）初始化寄存器：四个32位初始化变量为：
它们也被称为链接变量（chaining variable）
（4）进行算法的主循环：这一步是算法的核心，它是一个包含四个大循环的64步函数，四个大循环结构相同，但每次使用的逻辑函数不同，每一个大循环由对512比特的16步操作组成，即每16步为一轮大循环。
每次操作如下(设 Ai+1、Bi+1 、Ci+1 、Di+1 为第 +1个时钟周期时打入寄存器的值)：
以一下是每轮中用到的四个非线性函数（每轮一个）。
常数ti可以如下选择：在第i步中，ti是4294967296*abs(sin(i))的整数部分，i的单位是弧度。Wi是512位消息分组中的一个，Si是每次循环移位的次数。对每次而言也是固定的常数。
（5）结果输出：所有64步完成之后，将第64步的输出加到四个初始化变量上作为新的初始化变量，进行下一个512比特分组的运算，直到所有分组处理完毕，单次操作图如下：
图1. MD5算法单步操作图
3 算法优化
由上图可以看到，硬件实现时，MD5算法每一步操作中的关键路径在于B的求取（其他三个变量都是直接传递），这个关键路径包括了四个模 232加法运算、三输入变量的逻辑运算、"两个查找表运算及一个循环左移运算，而在FPGA设计中，加法运算最为耗时，四个加法运算至少需要三个加法器级联完成，加法运算严重制约了整个操作的速度，可见要加快算法运行速度就必须在简化这一关键路径上下工夫，经过观察我们发现，在
中 对每个周期都是已知的常数，是输入的512比特的一个32位分组，这样，在512比特输入初始化完成后，也可看作固定常数，
Ai是第ｉ时钟周期里寄存器D 的值，而 Di的值又是第i-1周期里的Ci-1 ，即Ai 的`值是第i-1周期里Ci-1的值。
若在第ｉ周期设中间寄存器变量 ，并令
那么在第i+1周期，
就可以表示为
操作就可以用下面几个式子代替：
其中， Ai+1没有参与任何运算，因此上式可以接着化简为
这样一来，原来一个周期内需要完成三级加法和相应的组合逻辑，现在只需要完成两级加法和部分组合逻辑就行了，大大提高了算法速度，只要在运算开始时加－个周期的初始化即可，简化后的系统框图如下：
图2. 改进后的单步操作图
4 结果比较
由上文中的算法分析部分不难看出，传统的实现方式关键路径是3级32比特加法器延迟和组合逻辑的延迟，而改进的实现方式减少了一级加法器的延迟，并把组合逻辑的延迟分散到不同路径上，因此，采用改进的实现方式大约可以将速度提高到原来的1.5倍左右。同时，为了实现数据的初始化，需要提前一个周期计算出寄存器A的值，因此整个算法的实现需要65个周期。我们采用 VerilogHDL 描述，选择Altera Stratix II EP2S15F672C5 FBGA芯片，在QuartusII6.0上验证通过。由于在FPGA中，连线延时也很关键，而这部分延时不能像加法延时那样通过预先计算并存储在寄存器中来消除一部分，所以实际的MD5改进算法与传统型相比较，速度的提高约为1.3，资源方面由于只是增加了一个时钟节拍，寄存器数量和组合逻辑并没有增加，所以改进型在资源方面和传统型相当。下表为算法改进前后在资源、频率、流量上的比较。
表1. 改进前后资源比较
5 结束语
由表1可见，改进型MD5算法实现，使用的资源并没有明显增加，但速度的改善十分明显，基本实现了用较少的资源得到较高速率的目标，证明了结构的正确性和合理性。实验结果也说明，这种利用寄存器来减少加法器级联从而减少关键路径的实现方法也可用于一般的FPGA硬件设计中。
参考文献
[1] R.Rivest. The MD5 Message-Digest Algorithm，RFC1321 1992。
[2] Jarvinen K， Tommiska M，Skytta J.Hardware implementation analysis of the MD5 hash algorithm.System Sciences，2005.HICSS’05.Proceedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:298
[3] Bruce Schneier. 应用密码学.北京：机械工业出版社，2000：188～194
[4] William Stallings. 密码编码学与网络安全：原理与实践.北京：电子工业出版社，2001: 216～222。
[5] 夏宇闻.Verilog 数字系统设计教程.航空航天大学出版社，2005