基于FPGA的改进型MD5算法的设计与实现

田 野

(忻州师范学院计算机系，山西忻州 034000)

0 引言

MD5是在二十世纪九十年代由Rivest开发，经MD2、MD3和MD4发展而来.MD5算法在信息安全领域得到了十分普遍的运用.其具有以下特点：(1)压缩性能较好：不管明文长度多少，生成的都是长度固定的MD5值.(2)计算的简易性突出：从明文算出MD5值的方法十分简易.(3)抗篡改性强：原始的数据哪怕是发生了极细微的改动，所得到的MD5值都会改动前的原始值产生异常大的区别.(4)抗碰撞性能突出：作为加密算法，抗碰撞性能显得非常重要，假设知道明文还有MD5值均已知，但是要找出另外一个和已知MD5值一模一样的明文仍然是异常艰难的[1].

虽然MD5存在以上诸多优点，但在实际的使用中MD5算法仍暴露出了两个主要问题，第一个问题是“彩虹表”撞库的问题威胁着MD5算法的安全性，所以MD5加密的明文加“Salt”成为需要.彩虹表撞库的思想就是建立一个原明文与密文之间对应的hash表.这样在获得密文后通过比较，查询或者计算，可以快速定位出原明文.防止彩虹表撞库攻击的有效方法是将拟加密明文加“Salt”，这个“Salt”值是由系统随机生成的，这样即使在彩虹表中建立了源数据和加密数据的对应，由于拟加密明文加入了系统生成的“Salt”值，使散列值发生了改变，这样就无法通过原有对应关系推出明文，有效的降低了MD5算法被彩虹表撞库的风险.第二个问题是MD5大多数情况下由软件实现，但是随着通信领域对带宽的要求越来越高，软件实现在性能上并不能很好的满足高带宽的需求，所以MD5算法的硬件实现在高带宽背景下成为必需.因为FPGA是一种具有良好的重构性，较高的可靠性和较好的实时性的硬件实现技术，所以该设计基于FPGA技术实现[2].

1 MD5算法理论介绍

MD5的具体思想简述如下：首先以16个分组来处理输入的拟加密的明文，每个分组大小为32位，通过一系列运算处理后，可以推出所需要的信息，该信息值有4个分组级联组合而成，每组32位[3].MD5算法主要分为以下5个步骤实现：

第一步：填充信息m使其比特数b满足b≡448 mod 512，补充的内容除去第一位填充1，其他各位都用0填充，填充长度为1到512；

第二步：增加64 bit用来表示原明文m大小，假如m原来的大小多于264bit，则将多余长度删去，保存低阶64 bit即可；

第三步：使用寄存器，其中每个寄存器大小32 bit，共使用4个，寄存器空间总和为128 bit，并且用十六进制表示寄存器初始值.

第四步：用一个含有4轮“循环”的压缩函数实现数据变换，每一轮分别具有一个逻辑函数而且结构相似，NN,OO,PP,QQ分别表示了4轮“循环”压缩函数每一轮的变换，

其中符号“<<

图1 MD5算法四轮变换

第五步：输出最终结果.

以上是传统MD5的基本实现方法，但是在实际使用中生成的密文面临着被彩虹表撞库的风险，通过对拟加密明文加入伪随机数改变生成密码的散列值可以降低通过彩虹表撞库推出明文的风险.

2 基于FPGA的加“Salt”MD5算法设计和实现

根据MD5算法的原理以及FPGA的技术实现特点，整个设计大致上分成伪随机数生成模块，拟用加密明文前期处理模块、数据存储模块、算法实现模块、状态机模块、输出密文模块六部分[4]，以下简要介绍各模块设计：

(1)伪随机数生成模块：若干个异或门以及n个D触发器组成了伪随机数生成模块，如图2.

图2 伪随机数生成原理图

Kn是取值只能为0和1反馈系数，取1时表明这个反馈路径是存在的，反之为不存在.n个D触发器可以最多提供不包括全0状态下的2n-1个状态[5].为测试伪随机数发生模块，利用Verilog HDL产生一个n=8，k0k1k2k3k4k5k6k7k8=101110001的伪随机数发生器，在Modelsim上对其进行了仿真测试：首先将load信号置位，让其在255个状态中运行，得到伪随机数255、143、111、222、205、235、…….仿真波形如图3所示.

图3 伪随机数发生器波形图

(2)明文前期处理模块：该模块具体实现包括：①为了使添加后明文的长度达到512位的倍数，明文前期处理模块加入了数据填充子模块负责填充位的添加和长度的添加；②为了方便计算和存储原始明文的长度，前期处理模块内加入了明文长度计数器.当valid信号输入为有效时，每当1个字节的数据被输入后，相应计数器执行加8的操作，反之valid信号输入为无效状态时，计数中止工作；③为了统计一共有多少个512位的明文分组，前期处理模块加入了明文分组计数器[6].

(3)数据存储模块：该模块有两个存储器构成，包括一个用于保存512位明文分组的地址宽度为16的双端口随机存取存储器和一个用于保存常数组T值查找表的数据宽度为32，地址宽度为64的只读存储器[7].

(4)算法实现模块：该模块主要有三个基本功能，即加法运算操作、循环移位操作和非线性函数运算.Quartus II 8.0中集成了可以调用的，可用于加法运算操作以及循环移位的模块，在非线性函数N/O/P/Q的实现中，先假设输出函数为w，则其输出：

whenround=2'b10,w=P(b,c,d)=b⊕c⊕d,

(5)状态机模块：该模块借鉴分层思想，自上而下分三层分别用状态机嵌套实现了各类状态关系.其中，控制完成明文(伪伪随机数+输入明文)的处理由上层状态机实现；中层状态机负责完成每一个512位明文分组的处理；下层状态机负责每一步的处理控制[8].具体功能设计如下：

①上层状态机存在有4种不同的状态：空闲状态(reset=1)；start=1时处理明文，转入等待状态；ack=1时转入工作状态；当状态机离开工作状态时就表示完成了一个明文分组的操作，若检查发现不是最后一个分组则等待，否则输出；等输出状态输出结果后，状态机自主转入空闲状态为下一段拟加密明文的操作做好准备[9]；

②中层状态机有5个状态：开始状态、就绪状态(等待输入)、前期处理状态、循环处理状态(完成每轮16步共4轮处理)、最后处理状态(完成处理后的A，B，C，D与初始摘要值的相加)；

③下层状态机包含有2个状态机.其中一个状态机表示4轮操作，另外一个状态机表示16步处理为一轮.两个状态机均在中层状态机执行循环处理时开始工作.

(6)输出密文模块：该模块由摘要寄存器和4个加法器组成，前者用于保存每个分组的初始摘要，后者用于完成操作后的A、B、C、D与初始摘要的相加.

综上所述：总体设计如图4所示，其中，伪随机数模块主要完成伪随机数的生成.预处理模块主要负责完成将伪随机数模块生成的数字放在明文之前以及填充位的填充和长度的填充.因为添加了伪随机数后的拟加密明文以及常量数组的查找表均需要保存，所以增加了存储模块.在状态机模块发出信号后，进行了每轮16步共计4轮的循环处理.输出密文模块将算法实现模块循环处理后的A、B、C、D与初始摘要值相加，输出最后的结果.控制整个系统运行的控制信号由状态机模块通过其他模块反馈信号和输入信号产生[10].

图4 总体设计示意图

如图5所示，用Verilog HDL语言进行优化设计，由QuartusII编译生成的MD5密文生成模块图，包括伪随机数生成、预处理、存储、状态机、算法操作和输出各子模块功能[11].

图5 MD5密文生成模块图

3 系统仿真测试

系统采用Verilog HDL编写实现.目标原器件是FPGA EP2C35F672C6芯片为基础的DE2系统板.该芯片由Altera公司开发.图6为改进后MD5算法的仿真图.

图6 改进MD5加密算法仿真图

由图6可知，明文为“123”，生成伪随机数为“255”，加密明文为“255123”，处理后得到的32位散列值为“cb881061c30f2d49c3817b03f2e731b0”，和MD5软件求得的32位散列值一致.证明了本设计是正确的，合理的.

从结果分析来看，该设计理论最大时钟频率可以达到50 MHz，使用了4 895个逻辑单元，占总逻辑单元的12%.从以上仿真结果可知，每经过52个时钟频率的延时可以处理一个512 bit的消息分组，于是可以计算出理论处理速度为：50×512÷52≈492.3(Mbit/s).

4 总结

本设计基于FPGA技术，利用Verilog语言完成编程设计，通过加入伪随机数生成模块降低了传统MD5在实际使用中被“彩虹表”撞库的风险，在提高MD5加密速度的同时提高了MD5算法的安全性.因为MD5算法与很多现在比较流行的数据摘要算法相比有许多类似之处,同时FPGA灵活可编程特点使其可以适用于不同的系统，因此本文提出的设计可以根据其他摘要算法的特点进行重构以便运用于其他摘要算法的硬件实现，经过实验验证，该设计具有一定的理论和实用价值.