可重构哈希算法芯片的设计与实现

【前言】可重构哈希算法芯片的设计与实现由文秘帮小编整理而成，但愿对你的学习工作带来帮助。(Jiangnan Institute of Computing Technology, Wuxi 214000, China) Abstract: Based on the research of MD4, MD5, SHA1 algorithm, we unify the expression of three algorithms through transformations of the iterative expression. And then we design a reco...

摘要：该文在研究MD4、MD5和SHA1算法的基础上，通过迭代表达式的变换，统一了这三种算法的表达式，设计了一款可同时实现这三种算法的可重构哈希算法芯片。该文给出了这一实现的硬件架构，并进行了优化以获取更高的吞吐率。最后在FPGA上对芯片原型进行了实现，给出了验证结果。

关键词：MD4；MD5；SHA1；可重构哈希算法芯片

中图分类号：TP301文献标识码：A文章编号：1009-3044(2012) 05-0821-04

Design and Implementation of Reconfigurable Hash Chip

WANG Yuan

(Jiangnan Institute of Computing Technology, Wuxi 214000, China)

Abstract: Based on the research of MD4, MD5, SHA1 algorithm, we unify the expression of three algorithms through transformations of the iterative expression. And then we design a reconfigurable hash algorithm chip that can also achieve the three algorithms. This paper presents the structure of this method and optimizes the realization in order to get higher throughput rate. Finally we realize the reconfigu? rable Hash algorithm on FPGA and give the results.

Key words: MD4; MD5; SHA1; reconfigurable hash chip

1概述

哈希算法在信息安全领域应用非常广泛。目前国内外使用的大多是实现特定算法的专用芯片，例如SHA1，SHA256和MD5等。这些芯片由于只实现了单个算法，因此使用广泛程度受到限制，不能满足不同用户多层次的需求。本文在研究MD4、MD5和SHA1三种算法的基础上，提出了一种能够同时实现这三种算法的可重构实现结构，可以很好的解决上述问题。

可重构哈希算法芯片能够根据不同哈希算法的需求重新组织，构成不同的电路结构，实现不同哈希算法功能[1]。同时，经过合理的电路复用，使得该结构不仅可以灵活实现多种哈希算法，还可以更加有效地利用硬件资源以达到节约逻辑资源的目的。本文详细描述了这一实现方法，并对电路的时序进行了优化，获得了较高的吞吐率。最后笔者将这一可重构哈希算法芯片的原型在FP? GA上进行了验证，证明了思路的可行性。

2算法介绍

MD4、MD5和SHA1是操作原理类似的哈希函数，它们每次均操作512bit的分组，完成数据压缩，最大可对264bit数据进行压缩，分别生成128bit、128bit和160bit的哈希值。具体的算法原理描述见相关文档[2-4]。下面对这三个算法原理作简要介绍。

这三个哈希算法的运算可以分为三部分。1)进行数据填充，完成对消息分组进行比特填充和长度值填充，以及链接变量初始值填充。2)进行消息分组的变换，其中MD4和MD5的扩展只是将消息分组以32bit为单位进行重新排序，而SHA1则将分组内容进行了逻辑变换。3)进行若干级的基本轮运算，这是哈希算法的主要操作，基本轮运算由32位加、循环移位和逻辑运算组成，其中MD4进行48级轮运算，MD5进行64级轮运算，SHA1进行80级轮运算。下面对这三部分分别进行分析以期找出其相通或可复用之处。

2.1消息填充

消息填充分两步，首先对消息填充使得其比特长在模512下为448 (即长度488 mod 512)，即使消息长度已满足要求，仍需填充。一次填充位数在1～512之间。填充方式是固定不变的，即第一位为1，其余各位皆为0。其次是附加消息长度，在消息后附加64位，将其看作64位无符号整数，它表示了消息填充前的长度。这三种算法在填充长度方面略有区别，其中MD4和MD5是相同的，填充长度是高字节优先，而SHA1是低字节优先。因此三个算法填充方式类似，该填充单元能够直接复用。

2.2消息变换

消息变换为基本轮运算提供变换过后的32bit消息分组。三种变换方式不尽相同。令W为512bit的消息，以32bit为单位进行分组，则W512={W0,…Wi,…,W15}。前16轮三种算法均相同，顺序取输入的消息分组Wi(0≤i≤15)。16轮过后，MD4和MD5类似，取不同位置的分组Wj(j为固定小于15的数值)，而SHA1则取Wt=(Wt-3^ Wt-8^ Wt-14^ Wt-16)

3哈希算法的可重构结构

根据上面的分析，我们首先给出消息变换的通用结构，然后找出可重构实现的基本轮运算结构，进而给出整个可重构哈希算法芯片的实现结构。

3.1可重构消息变换结构

通过前面的分析，MD4、MD5算法的消息变换只是进行位置变换，分组内容不变；SHA1算法是位置不变，内容进行了变换。我们将消息变换的表达式也进行了相关变换，以支持这三种变换。将W512以32bit为单位划分，形成16个变量的数组Wi(0≤i≤15)，引入变量Wsha、Wnext及S。其中，Wsha为SHA1算法变换生成的明文分组，S为t时刻明文分组在W512中的位置标识，Wt为t时刻输出给基本轮运算的明文分组。则变换表达式如下所示。

S为t时刻的明文分组位置标识

需要指出的是，W512形成了一个循环移位寄存器，每次运算时均在最右边移入变量Wnext。Wnext变量在SHA1算法运算时取Wsha，其它算法取W0。这样整个实现结构，在SHA1运算时进行SHA1消息分组内容变换，其它算法时分组内容未进行变换，只进行位置变换。输出给基本轮运算Wt则通过位置标识S，取出W512中的特定分组完成输出。因此对于特定的算法，变量S是一组固定的位置标识，数值为0~15，对于MD4和MD5而言是一组事先可知的位置标识；对于SHA1而言是固定值0。至此整个结构可以通过位置标识S的选择，实现三个算法消息变换功能。

3.2可重构基本轮运算结构

图2

轮运算模块实现上述可重构基本轮运算结构，如图3所示。图3

控制模块负责整个运算的控制，其核心是一个7位计算器，根据该计算器值控制每一步轮运算所需要的各种参数、明文分组，并

4 FPGA验证及结果

我们选用Altera公司的FPGA进行哈希算法芯片原型的验证，FPGA芯片采用Altera Cyclone系列器件。由于我们的可重构哈希算法采用流水方式实现的，因此我们也采用流水方式单独实现了MD4、MD5和SHA1算法，对这几种实现的性能进行了比较。这四种实现的结果如表1所示。

表1

从表1中可以看出，可重构哈希算法在性能上相对三种单独的哈希算法比较接近，同时在资源开销上与三种单独的哈希算法相比超出不是很多，表明可重构哈希算法在资源消耗相对不高的情况下能够高效地完成三种哈希运算，和三种单独的哈希算法相比有非常大的优势。

5结论及下一步工作

本文的创新之处在于采用可重构的设计思路，在同一芯片上实现了MD4、MD5和SHA1三种哈希算法，可以很好的解决传统哈希算法芯片适用性不好的问题。本文不仅给出了可重构实现结构，并给出了优化实现结构，提高了芯片的整体吞吐率，因而具有很好的实用价值。

最后，我们需要指出，本文给出的可重构结构，在粒度选择上是比较粗的，即将算法的加法路径作为一个可重构单元而提出来，这是基于在这三个算法研究的基础上提出的。它带来的好处是我们可以针对这三个算法，带来较好的处理速率。本文只是给出了支持三种哈希算法的可重构结构，下一步的我们的研究方向是研究支持更多哈希算法的可重构哈希算法结构，这就要研究细粒度的可重构结构，需要将哈希算法所专用的32位加、移位及逻辑运算等操作抽象为可重构基本单元。

参考文献：

[1]曲英杰.可重构密码协处理器的组成与结构[J].计算机工程与应用,2003(23):32-34.

[2] The MD4 Message Digest Algorithm[EB/OL].www.省略/rfc/rfc1186.txt.

[3] The MD5 Message-Digest Algorithm[EB/OL].www.省略/rfc/rfc1321.txt

[4] The Internet Engineering Task Force (IETF)[EB/OL]. www.省略/rgc/rfc3174.txt.

[5]杨晓辉,戴紫彬.一种基于FPGA的可重构密码芯片的设计与实现[J].电子技术应用,2006(8):102.

[6]曲英杰,刘卫东,胡嘉瑾.可重构密码协处理器简介及其特性[J].计算机工程,2004,30(13).

[7]李淼,徐金甫,戴紫彬.可重构散列函数密码芯片的设计与实现[J].计算机工程,2010(6).