新一代哈希算法

国家无线电监测中心 霍 甲 刘 蓉 任培明

一、引言

哈希算法是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。不同的输入通过散列变换成相同的输出，并且从输出得到的散列值是惟一的。换言之就是一种将任意长度的消息压缩到某一固定长度的消息摘要的算法。如果得到的散列值不同，那么散列值的原始输入也是不相同的。利用哈希算法的良好特性，哈希算法在数字认证，数字签名领域有着广泛的应用。

二、新一代算法的产生

SHA-算法是属于哈希算法的一种，其他如 MD4，MD5，SHA-0，SHA-1，RIPENMD 等也都属于哈希算法。

1993年第一代SHA-算法颁布，被称为SHA-0。它在发布之后很快就被NSA撤回，并且由1995年发布的修订版本FIPS PUB 180-1(通常称为SHA-1)取代。SHA-1和SHA-0的算法只在压缩算法的信息转换部份差了一个比特的循环位移。SHA-0和SHA-1可将一个最大264比特的信息，转换成一串160位的信息摘要。但是很快SHA-0就遭到了破解。

2001年，NIST即宣布他们将逐渐减少使用SHA-1，改以SHA-2取而代之。NIST发布了共计4款不同的SHA-算法，分别为 SHA-256/224 ，SHA-512/384。但是随着第二代SHA-算法的应用越来越广泛，第二代SHA-也面临着诸多的问题，虽然第二代SHA-算法目前没有找到破解的可能性，但是由于MD5的成功破解，使得NIST不得不再推出一个更加安全更加效率的新算法。

美国国家标准技术研究所（NIST）在2005年、2006年分别举行了2届密码Hash 研讨会；同时于2007年正式宣布在全球范围内征集新的下一代密码Hash算法，举行SHA-3竞赛。新的Hash算法将被称为SHA-3，并且作为新的安全Hash标准。算法提交已于2008年10月结束，NIST通过2轮的筛选选出进入最终轮（final round）的算法。公开竞赛的整个进程仿照高级加密标准AES的征集过程。2012年10月2日，Keccak被选为NIST竞赛的胜利者，成为SHA-3.。

三、新一代哈希算法SHA-3技术对比

Keccak算法是由ST微电子公司的BERTONI等和NXP半导体公司的PEETERS等共同设计提交的Hash算法。它基于sponge结构，其中的压缩算法是作用在一个三维数组上的5步置换操作。对于输出为256位Hash算法应用，r取1088位，c取512位，全部输入为1600位，组成一个25×8字节的三维矩阵。Keccak算法的消息填充方式比较复杂，首先将消息填充值8位的整数倍，填充方式为最低位为1，其他位为0；然后添加上8位无符号整数d。

表1是三代SHA-算法基本参数对比，从表中我们看到，新一代SHA-算法支持更长的信息输入长度，循环次数要少于SHA-1和SHA-2。SHA-3使用的是海绵算法，在最大的版本，算法使用的内存状态是使用一个5×5的二维阵列，资料型态是64位元的字节，总计1600位元。缩版的算法使用比较小的，以2为幂次的字节大小w为1位元，总计使用25位元。除了使用较小的版本来研究加密分析攻击，比较适中的大小（例如从w=4使用100位元，到w=32使用800位元）则提供了比较实际且轻量的替代方案。

表1 三代SHA算法基本参数

对于硬件实现的效率问题，我们选取了在同等硬件消耗下进行对三代算法的对比。我们基于Xilinx公司出品的Virtex-5xc5vlx220芯片，使用ISE硬件仿真工具对电路进行FPGA硬件评估。由于不同硬件实现的硬件消耗不同，目前主流的有两种方向，一种是用最少的器件完成效率最高的吞吐量，另外一种是以器件消耗为代价完成最大的吞吐量。我们这里是以硬件器件消耗大体一致的前提下，对三代SHA-算法做了对比。表2给出了在同等硬件消耗下的吞吐量对比。可以看到，新一代SHA-3算法在同等硬件消耗的前提下完成了最大的吞吐量。

表2 吞吐量对比

四、结束语

我们在比较三代SHA-算法中发现，SHA-3算法结构有利用并行化设计，并且消息块大，消息处理能力强，因此有着非常高的数据吞吐率。同时，SHA-3算法运算单元仅为Xor，AND，Not运算，逻辑单元硬件消耗不大，因此SHA-3算法在速度导向设计中性能更加突出。再加上SHA-3算法迭代次数都远小于SHA-1和SHA-2，因此在运算复杂度上，SHA-3算法远小于SHA-1和SHA-2，这说明三种算法在同等硬件消耗情况下，SHA-3有着绝对的优势。