哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　第24卷第2期 成都信息工程学院学报 Vd．24No．2 2009年4月 J()l瓜NAI．OFCHENGDUUNIVERSlltYoFINHJRMA，noNTEI曙D盯)LDGY Apr．2()09 文章编号：167l—174212009)I)2．1)129．04 HASH算法MD5的高速实现 ． 曾 旭1，一， 高献伟3， 路而红3， 陈 运1 电子科技学院电子系，北京100070) 摘要：在分析HAsH算法M【)5的基础上详细介绍了目前主流的4种硬件实现方式，给出了其中迭代方式和基 于缩短关键路径的循环展开方式的FP(认实现。基于缩短父键路径的循环展开方式有效的压缩了一半的工作时 钟数，并提高了吞吐量，是目前所给出的国内外方案中占用硬件资源较小而工作效率较高的硬件实现方式。 关键词：MD5；展开；迭代；FP(认；V“109 中图分类号：TP309 文献标识码：A l 引言 HASH函数在密码学中扮演着极其重要的角色。一个典型的应用就是从数字消息、IP信息包、磁盘文件等 数据抽取HAsH值(或者称为消息摘要)，并与对称或非对称加密技术一起来完成对原始数据的认证和完整性检 查。 HASH函数能够将任意长度的信息，通过算法变换成固定长度的输出，这个变换过程是不可逆的。H峪H函 数的不可逆特性使得攻击者不可能通过HASH值推出任何部分的原始信息，即便原始信息中的一位数据发生改 息。正是由于这些特性，所以HASH值可以用来验证信息是否被修改。 2 MD5简介 啪D5【l-2J算法由美国教授Ronald 英文“Message 的HASH值。 MD5算法包括预处理和计算HASH值两个部分。预处理部分又包括消息填充和消息分组，首先将接收到的 mod 数据填充成为满足kngth(Message)=448512比特的数据长度，然后附上64比特的消息长度，最后将数据 分成长度为512比特的子块开始HASH运算(图1)。 MD5的HASH运算共包括4轮；每轮包括16步运算， 共64步。各步运算大致相同，只是在压缩函数(即非线 子块玎 函数)和计算参数上有所区别。图2是MD5算法的步运算 流程，其中0～15步、16～3l步、32～47步和48～63步分 ，． ” 别采用F、G、H和J作为压缩函数。 (1)A、B、C和D：初始值由算法设计者提供(即Ho)， 图l MD6总流程 后续值由步运算更新。 (2)压缩函数：将输入的96比特长度数据压缩成为32比特长度输出。 (3)Mi：将本次操作的子块M依次分成32比特长度的数据共16块。 (4)t：算法设计者提供的常量。 (5)s：算法设计者提供的循环移位常量。 收稿日期：2()08．10一06；修订日期：20()8．10．23 万方数据 工 130 成都信息 程学 院 学报 第24卷 (6)田：模32佗加法。 3 HASH算法的硬件实现结构 随着网络通信速度的快速提升，用软件方式来进行HASH值计算已经显得越来越力不从心；而安全高效的 M1)5的硬件实现方法。 在FI，(认编程过程中，提高吞吐量以及减少硬件资源利用成为了衡量算法优劣的重要指标，特别是在移动 设备的设计上，高效率低功耗以及低资源都是FI，(认设计中最受关注的方面。目前为止，卜L吣H算法的Fl，(擒 J(图3)。 实现策略上大致有以下4种方式【3 (1)迭代方式：该方式将每步运算的结果重新反馈到本级作为输入，节约硬件资源的同时造成了较大的时 延。 (2)循环展开方式：该方式是在分析算法的特性后将相邻的多步运算合并在一起，从缩短关键路径的方式来 提高步运算的效率。 (3)流水线方式：该方式将所有步运算全部给出，每个时钟均有输出。全流水时吞吐量达到最高，但是占用 相当大的硬件资源。 (4)混合方式：该方式在可并行执行的算法上比较有优势。 三画 (1)迭代方式 (2)循环展开方式 ，，．，．———[if!；；ii；i：恫一一一．一一一日Hash (3)流水线种实现方式 4 MD5的FPGA实现 MD5算法的预处理阶段无论是软件实现还是硬件实现，其效率相差不大，所以着重讨论该算法的计算阶段 在硬件FPGA上的两种实现方式。 4．1迭代方式 由于MD5算法的64步运算大致相同，所以可以采用迭代方式来实现。实现过程中，将存放常数L和Ho 的常量矩阵利用R()M结构实现，待处理的子块M存放于RAM中。4个压缩函数分别是： F(X，y，Z)=(X^y)V(X八Z) G(X，y，Z)=(X八Z)V(y^Z) 万方数据 第2期 曾旭等：IIAsH算法MI)5的高速实现 13I H(x，y，z)=xoy①z J(x，y，Z)=yo(xV2) 各步A、B、C和D分别是： Ai}l=Dj Bj+I=Bj+(A+Mj+t+F(Bi，Ci，Di)s) Ci+I=Bi Di十l=Cj 4．2循环展开方式 注部分)。该关键路径上包括一个压缩函数运算(主要涉及按位的逻辑与、或、非运算)、4个模32加法运算、一个 移位运算。由于模32加法所占用的时延比重较大，所以试验中着重考虑模32加法所带来的时延。 由于单步运算有4个模32加法时延，两个单步运算则有8个模32加法时延。但是，如果把两个单步运算展 开合并后，引入预计算机制将某些可以提前运算的点独立到关键路径以外就可以缩短关键路径，从而达到提高计 立到关键路径外与第一个加法运算并行；户群2的计算独立到关键路径外与前半部分的3个加法运算并行。由 此，将关键路径上的8个加法运算减少到了5个，从理论上说效率提高了0．4。 图4缩短关键路径 图5设置预汁算点 合并后： 户rPl=T，Mf 户理2=L十l+Mf+l+Dj Ai+2=G Bf+2=(户贸2+F(Ci+2，Bi，G)s)十G+2 G+2=(户理l+Ai+F(Bi，G，Di)5)+B Df+2。Bf 4．3 FpGA实现 was Ron 述语言Ver订og进行MD5算法的FP(认实现。并利用MD5标准测试向量“M【)5prop0髓dby Rivestin 循环展开方式的吞吐量是迭代方式的1．43倍，即工作效率提高了43％。 万方数据 132 成都信息工程学院学报 第24卷 咖嘲岫蛐帅蛐哪m川咖m川山Ⅲ帅岫圳删Ⅱ邮岫圳岫ⅢIIIlI枷m咖m川mⅢ岫圳岫岫呐ⅢmⅢ岫Ⅲ咖m圳m川岫 1：：=’：五：：：：。：：：i：}j血i』：，煎 乏一生：：．毯2：重：：：：：：：奠!：!：￡：：盖玉。：：：!一：』=．：：：：：：b：：：3：±-：!：：：：：：盘：l：!i型’：：上!∑；量。2 阁6迭代方式仿真截图 -■ 殛蔓皇!盎童鲨皇汹畦亟叠生逮美釜盛莲壹二b羹￡壶盖量二量必逸』二丑』二立三：二i尘．主量兰三』盘』■玉童』上丛』』立●—二●量0三型』五二』』薹』盏堂量釜二坚妄型堡二趱邀疆!照箍!￡滏≥逊盘!zt盎：迭盘：五蛀文盎五，≥越三二二i三童=j奠!!■ii夏量羔：：逸亟i：：盆!i。也：!』。：五釜。≤耋薹幺主童 图7循环展开方式仿线 结论 的循环展开方式与迭代方式相比较，虽然工作主频降低了25％，但是吞吐量却提高了43％。与文献[5]中4级流 水线的实现方式相比，实现方式占用了较少的硬件资源，在单级上的吞吐量却明显高于其提供的数据。实验数据 表明，文中所应用到的循环展开方式比现有其他方式效率更高，并保持了较少的资源耗费，达到了在移动设备上 追求高效率和低资源耗费的目的。 ． 参考文献： RLRivest．TheMD5 UnitedStatesYearof [1]