安全散列算法的FPGA实现与仿真.pdf

2010第12要：安全散列算法是一种常用的加密算法，在信息安全领域得到了广泛应用。该文通过设计硬件电路，建立SHA-算法时采取并行处理的方法，对算法的实现流程进行了优化，通过模块化设计，缩短了算法实现的周期，减少了存储资源的占用。最后进行综合和仿真，验证了算法实现的正确性。关键词：现场可编程逻辑门阵列；安全散列算法；硬件描述语言中图分类号：TP393文献标识码：A文章编号：1003-0107(2010)12-0019-04Abstract:SecureHashAlgorithmmostcommonencryptionalgorithms,itwidelyusedinformationsecurityfield.Inarticle,webuildSHA-algorithmmodelimplementthroughhardwaredesign.UsingparallelprocessingmethodFPGA,itshortensimplementtime,reducesstorageresource.Andwesimulateimplementation.Keywords:FPGA;SHAAlgorithm;VerilogHDLCLCnumber:TP393Documentcode:AArticleID：1003-0107(2010)12-0019-04安全散列算法的FPGA实现与仿真ImplementationFPGA崔东岳,龙兵,曾浩,向川云（电子科技大学自动化工程学院,四川成都611731）CuiDong-yue,LongBing,ZengHao,XiangChuan-yun(SchoolAutomationEngineering,UESTC,SichuanChengdu611731）引言SHA-算法是SHA(SecureHashAlgorithm，安全散列算法)系列算法中的一种。

SHA算法是由美国国家安全局(NSA)设计，并由美国国家标准与技术研究院(NIST)发布的一系列密码散列函数。SHA-算法具有不可逆、防冲突、高雪崩效应的特点，在信息安全领域有着十分广泛的应用。通过FPGA实现SHA-算法，可以利用FPGA实现加密的功能，也可以对FPGA的设计进行保护，且成本较低，在嵌入式系统中具有良好的应用前景。本文介绍了一种通过FPGA实现SHA-的方案设计，并通过仿真加以验证。算法原理2.1SHA-算法简介SHA-算法是一种特殊的压缩算法，它可以将任意长度的原始消息压缩成一个固定长度的代码串，即消息摘要。SHA-算法具有单向性、唯一性、高雪崩效应的特点。(1)单向性通过原始消息能够得出消息摘要，而因为算法包含非线性计算，通过消息摘要无法反推与之对应的原始消息。(2)唯一性一个原始消息对应唯一的消息摘要，任意两个不同的原始消息通过算法不能得到相同的消息摘要。(3)高雪崩效应原始消息中的每一个字符都与压缩结果相关联，改变原始消息中的任何一个字符都会造成消息摘要有一半以上的位发生变化。2.2SHA-算法流程SHA-算法的流程可以分为原始消息补位、消息分组及扩展、核心操作和消息摘要输出四个基本步骤。

2.2.1原始消息补位

补位是要将原始消息填充成一个位数是512位的整数倍的消息。补位方法是：先在原始消息末尾添加一个"1"，再添加若干个"0"，直到长度达到(512n-64)位，最后64位原始消息的长度。本文以将原始消息补位到512位为例说明，如果补位后的消息是512n位，将消息划分为n个512位消息即可。

2.2.2消息分组及扩展

先将512位的消息进行分组，共分成16组消息，每组消息的长度为32位。这16组消息分别为W消息分组完成后，利用已经存在的16组消息W19据式(1)，计算出64组新的消息，将整个消息扩展到8079。其中，S14xorW2.2.3核心操作利用已经准备好的80组消息，进入算法的核心操作部分，核心操作的一次运算过程如图1所示。核心操作是通过式(2)~(7)对消息进行压缩计算，这种运算是非线性的，包括移位运算和加运算，共循环80次，不断更均为32位变量，其初始值分别为：A=0x67452301，B=0xEFCDAB89，C=0x98BADCFE，D=0x10325476，E=0xC3D2E1F0。式(2)中，Ft(B,C,D)按照式(8)进行计算，KtFt(B,C,D)=(BandC)or(BandD),0t19BxorCxorD,20t39(BandC)or(BandD)or(CandD),40t59BxorCxorD,60t7Kt=5A827999,0t196ED9EBA1,20t398F1BBCDC,40t59CA62C1D6,60t72.2.4消息摘要输出在执行80次循环后，核心操作完成，将最终得到的A、B、H0=H0+AH1=H1+BH2=H2+CH3=H3+DH4=H4+(10)其中，H0，H1，H2，H3，H4均为32位，其初始值分别为：H0=0x67452301，H1=0xEFCDAB89，H2=0x98BADCFE，H3=0x10325476，H4=0xC3D2E1F0。

将最终得到的H0，H1，H2，H3，H4按照H0H1H2H3H4格式进行输出，就得到了160位的消息摘要。算法的FPGA实现通过对SHA-算法的描述，我们不难看出，整个算法可以通过顺序执行的方式实现。即先进行对原始消息的补位和分组，然后将16组消息按照公式扩充到80组，再进行核心操作部分的80次压缩计算，最后进行160位消息摘要输出。然而，如果在FPGA中采用顺序执行的方式，虽然能够实现算法，但整个算法实现的时间较长，效率较低。而且需要准备一个存放80组32位消息的存储器，并且要对特定的消息进行读取，这样，就需要一个0.625K的RAM进行存储，这样会消耗FPGA较大的存储资源。在通过FPGA实现SHA-算法时可以利用FPGA并行操作的特点，将消息分组扩展过程与核心操作过程同时进行，并考虑减少FPGA存储资源的占用。3.1算法所需存储单元的重新划分我们注意到在式(2)中，在每执行一次压缩计算时，每一个只使用一次便不再使用，因此，如果将80组消息都保存起来，占用的存储资源较大。本设计中，使用W0~W15共1632位的寄存器，用于存储16个消息。在每次压缩计算时，将W0的数据代入式(2)中。

根据式(1)计算出新的Wn的值，因为16个寄存器是固定的，因此只需每次固定提取W0、W2、W8、W13用于生成新的Wn值。在执行一次压缩计算后，将新的Wn送入存储单元15，原来存储单元15的值送入存储单元14，原存储单元14的值送入存储单元13，依此类推，存储单元的值送入存储单元0，每一次都把存储单元0的值代入式 (2)，即每输出一个Wn 就进行一次核心操作，Wn 使用后便丢 掉，不再占用存储单元。这样循环进行，16 个存储单元从整体 来看，就类似一个先进先出的FIFO。表1 所示给出了存储单 元的存储内容及变化情况，0~15 代表16 个存储单元，1~80 表进行的80轮移位操作。 通过对比，并行实现算法仅需要16 个存储单元，仅为顺 序执行算法需要的80 个存储单元的五分之一，这大大减少了 FPGA逻辑资源的占用率，同时还保证了必要数据的存储。 3.2 算法的硬件结构设计 整个SHA- 算法的硬件结构设计示意图如图2所示。 专业测试 ro Testing 算法核心操作的一次运算20 2010 第12 测试测量技术3.3 算法的流程 根据并行实现算法的需要，将消息扩展和核心操作部分 同时进行，以缩短算法实现的时间。

整个SHA- 算法的流程如图3 所示。 3.4 算法模块说明 3.4.1 功能模块 结合SHA- 算法的硬件结构设计及实现的流程，对各功能模块进行简单说明。 (1)初始化模块(INIT) 此模块用于对W0~W15，H0、H1、H2、H3、H4，A、B、C、D、E 赋初始值，并将计数器CNT清零。 (2)预处理模块(PREPROC) 此模块首先将W0~W15 的值送入新的寄存器保存，以备 后期移位更新W0~W15 值使用。同时，先通过公式计算Wn 值，但先不进行循环左移操作。相关代码如下：W0REG= W0； W15REG=W15； WPRE (W0^W2 ^W8 ^W13) (3)循环左移模块(ROL) 此模块对A、B和上一步未进行移位的Wn 进行循环左移 操作，并通过式(8)计算FT的值。相关代码如下： WPRESHIFT= {WPRE[30:0]，WPRE[31]}； ASHIFT= {A[26:0]，A[31:27]}； BSHIFT= {B[1:0]，B[31:2]} 值模块(NEW)此模块用于在经过压缩计算后生成新的 值，相关代码如下：AREG= ASHIFT+ FT+ W0REG+KT； BREG= CREG=BSHIFT； DREG= （5）移位更新W0~W15值模块(SHIFT) 此模块用于更新W0~W15 的值，并更新计数器的值，相关 代码如下： W0 W15REG；W15 WPRESHIFT；CNT= CNT+ 1'b1 （6）输出模块(OUTPUT) 在进行80 次压缩计算后，输出最终的H0H1H2H3H4，即 160 位的输出消息。 相关代码如下： H0 E_REG3.4.2 状态机模块 为了保证各模块之间的正常转换，通过状态机控制较为 理想，相应的状态转移图如图4 所示。 15 14 W15W14 W2W1 W0 W16W15 W3W2 W1 W17W16 W4W3 W2 65W79 W78 W66W65 W64 66 W79 W67W66 W65 79W79 W78 80 W79 算法流程下转28 仿真与结果分析下面通过对上文所设计的算法进行仿真分析，以验证结