【SHA-1算法及其在FPGA加密认证系统中的应用】 非对称加密算法系统

　　摘要：本文对安全散列算法以及安全散列值的计算方法进行了深入的分析，给出了安全散列值的计算步骤，论证了安全散列算法的安全性和可靠性，最后提出了一种sHA-1(Secure Hash Algorithm安全哈希算法)算法在加密认证系统的应用。整个认证系统通过1-wire总线，使FPGA完成与DS28E01-OO加密芯片的通信，主机内核采用了Xilinx公司设计开发的8位微控制器软核Pico B1aze。实验证明该设计能够完成加密认证系统的过程。
　　关键词：SHA-1;哈希函数;FPGA;加密认证系统键设备的设计中，有必要采取加密的技术来保护设计者的知识产权。
　　数字签名作为一种重要的加密技术如今已被广泛地应用于网络信息交换领域，它的根本作用是保证网络中传输的数据的真实性和完整性。数字签名的应用过程是数据源发送方使用自己的私钥对数据校验和或其他与数据内容有关的变量进行加密处理，完成对数据的合法“签名”，数据接收方则利用对方的公钥来读收到的“数字签名”，并将解读结果用于对数据完整性的检验，以确认签名的合法性。而在种类众多的数字签名技术中通常都会用到一类特殊的数学算法一哈希算法，它在数字签名技术中占有极其重要的地位。目前常见的哈希算法有MD5、SHA-1和RIPEMD-160，而国内更倾向于MD5和SHA-1。就当前的情况来看，SHA-1由于其安全强度及运算效率方面的优势目前已经成为使用最为广泛的哈希算法。
　　认证系统工作过程中，FPGA读取由安全存储器件所计算出的Hash结果，与期望Hash结果做比较。如果相匹配，微控制器认为该电路是“友方”电路，因为它拥有正确的密钥，此时FPGA进入正常工作状态，开启／执行其配置数据中的所有功能。如果不匹配，则该电路被认为是一个“敌方”电路，此时禁用整个FPGA中的设计，因此，即使捕获到配置数据比特流，设计也是安全的。整个认证系统主要由SHA-1引擎、随机数发生器、1-wire接口和指令译码三个模块组成，其核心模块SHA-1引擎采用了Xilinx公司的Pieo Blaze微处理器。
　　
　　2、HaSh函数
　　
　　Hash函数也叫哈希函数、散列函数。它是一种单向密码体制，是一种从明文到密文的不可逆函数，也就是说，是无法解密的。同时，Hash函数是将任意长度的消息M变换为定长码h，一般将Hash函数定义如下：
　　h=Hash(M)或h=H(M)
　　生成的Hash码也叫消息摘要MAC(MessageAuthentication Code)或散列值。Hash函数的单向性和生成固定长度消息的特征使得它在数据完整性认证、数字签名等领域有广泛的应用。
　　
　　2.1、Hash函数的攻击方法
　　
　　评价Hash方案的一个最好方法是看一个敌手找到一对碰撞消息所花的代价有多高。一般地，假设敌手知道Hash算法，敌手的主要攻击目标是找到一对或更多对碰撞消息。现有的一些攻击Hash方案和计算碰撞消息的方法主要可以分为两类，一类是可用于任何类型的Hash方案，如生日攻击，另一类是用于攻击某些特殊类型的Hash方案，如用于攻击具有分组链结构的Hash方案的中间相遇攻击。
　　
　　2.2、Hash函数的要求
　　
　　Hash函数的目的就是为了产生固定长度的消息，因此，Hash函数需满足下列要求：
　　
　　(1)基本要求
　　①能够应用于任何大小的数据块；
　　②有数据压缩功能，能产生固定长度的输出；
　　③对于任何给定的数据块M，H能够相对容易地计算出H(M)，这样就使得硬件和软件变得切实可行。
　　
　　(2)安全性要求
　　SHA-I算法的特性是哈希码的每一位是输入的每一位的函数。简单函数ft的复杂重复产生了混合性很好的结果信息。也就是说，不同于信息的随机挑选。即使两个信息显示出很近的规律，也不可能产生同样的哈希码，除非SHA有至今尚未公布的隐含的脆弱性。产生两个信息有同样的哈希码的难度体现在需要完成数量达280次的操作，找一个给定摘要的信息的难度体现在需完成数量大2160次的操作。
　　好的哈希函数也是无冲突的：难于产生两个预设的值，使他们的哈希码相同。哈希函数是公开的，对处理过程不用保密。单向哈希函数的安全性是它的单向性。无论怎么看，输出不依赖于输入。如果预映射的值发生改变，平均而言，将引起哈希码值中一半的位改变。已知一个哈希码，要找到预映射的值，使它的哈希码等于已知的哈希码在计算上是不可行的。
　　①单向性。对于任意给定的值h来说，寻找满足H(M)=h的数据块M在计算上是不可行的。
　　②抗弱碰撞性。对任意给定的M1，求出满足H(M1)=H(M2)的M2(M1≠M2)在计算上是不可行的。
　　③抗强碰撞性。找到任意满足H(M1):H(M2)的对(M1，M2)在计算上是不可行的。
　　④雪崩性。h的任一比特都与M的所以比特相关，即Hash函数任一比特都影响Hash值h。
　　
　　2.3、Hash函数的一般结构
　　
　　Hash函数通常是建立在压缩函数原理的基础之上的，它通过对消息分组的反复迭代压缩，生成一个长度固定的散列值，一般在迭代的最后一个分组中，还包含有消息的长度值，从而在散列值中引入消息的影响。在实际中，Hash函数一般具有如下的形式：
　　给定输入M，Hash函数首先将M分成若干个分组(M0，M1，M2，…，ML-1)，每个分组长度为r比特。如果最后一个分组长度不足r比特，可以强制将其填充为长为r比特；并且包含消息的总长度值，添加消息的总长度值可以提高散列函数的安全强度。并以迭代的方式，从第一个分组开始，每次处理一个分组。
　　在处理第i个分组时，将分组i与处理分组i-1时得到的散列值作为压缩函数f的输入，即
　　Hi=f(Mi，Hi-1)
　　这时压缩函数的输出将作为直到分组i的输入的散列值。最后，在处理最后一个分组时得到的散列值，将作为整个消息的散列值输出。如图1是Hash函数的整体结构，HL即是最终输出的散列值。
　　
　　根据以上描述，Hash函数可用数学表达式表示为：
　　H0=IV
　　Hi=f(Mi，Hi-1)
　　H(M)=HL
　　Hash函数的核心是压缩函数f，如果压缩函数具有抗碰撞能力，那么Hash函数也就具有抗碰撞能力。因此，要设计安全的Hash函数，首先要设计具有以固定长度为输入的抗碰撞压缩函数。
　　
　　3、安全散列算法(SHA-1)
　　
　　安全散列算法(SHA：Secure Hash Algorithm)是美国NIST和NSA共同设计的一个标准，于1993年作为联邦信息处理标准发表(FIPS PUB 180)。1995年又公布了一个修订版FIPS PUB 180-1，称为 SHA-1。月前SHA-1作为最常用的Hash函数已被广泛应用。
　　
　　3.1、SHA-1的计算步骤
　　SHA-1的要求是消息长度小于264bit，输出的散列值长度为160bit，输入按每组512bit进行处理。如图2给出了由信息产生摘要的过程。处理过程由以下几步完成：
　　
　　第一步：附加填充位。
　　对消息填充使它的长度模512后所得的值为448。也就是说，填充后的消息长度比512位的倍数少64位。
　　
　　填充方法是在消息的比特流后面附加一个1，后接所要求的多个O。即使消息的长度在填充之前已经满足条件，附加填充比特总是需要进行的，因此，填充位数的范围是1到512。例如，如果消息的长度为448bit，那么将填充512bit形成960bit的消息。
　　
　　第二步：附加消息长度值。
　　将用64bit表示的初始消息(填充前)的长度(比特值)附加在第一步的结果后，因此要求消息长度小于264比特。
　　经过前面两步的处理，消息的长度已经是512的整数倍了。在图2中，把扩展后的消息表示成512位数据块序列：Y0、Y1、…、YL-1，这样扩展后消息的总长度就是L×512位。相等地，扩展消息的总长度也是16个32位字的整数倍，用w[0…N-1]表示结果消息字，其中N是16的整数倍，因此N=L×16。
　　
　　第三步：初始化消息摘要的缓冲区。
　　用一个160位消息摘要缓冲区存放中间和最终散列函数的结果。这160bit被分成5个32bit字H0、H1、H2、H3、H4，初始化为如下的16进制值：
　　H0=67452301h；
　　Hl=EFCDAB89h；
　　H2=98BADCFEh；
　　H3=10325476h；
　　H4=C3D2E1F0h。
　　
　　第四步：以512bit(16个字)分组处理消息。
　　处理5 12bit分组是SHA-1算法的主循环，它以512bit作为分组，从消息开头循环地处理消息序列直至消息的结尾。如图3所示，因此，主循环的循环次数将是消息中512bit消息分组的数目。其中，每一次循环都是以当前处理的512bit分组和消息摘要缓存H0、H1、H2、H3、H4作为输入，并在本次循环结束时更新缓存区的内容，然后进行下一个分组的处理或者输出。
　　每次循环都分为三个阶段：
　　
　　阶段1：拷贝中间变量。
　　把H0、H1、H2、H3、H4分别拷贝到A、B、c、D、E中，阶段2的所有操作都在中间变量A、B、c、D、E上进行。
　　
　　阶段2：散列压缩。
　　
　　
　　SHA-1主循环包括80个操作，每个操作中都使用了一个非线性函数。按照所使用的非线性函数的不同，这些操作可以分为4轮，每轮20个操作(第1轮为第0至第19个操作，第2轮为第20至第39个操作，第3轮为第40至第59个操作，第4轮为第60至第79个操作)，每一轮的所有操作都使用了相同的非线性函数；而轮与轮之间则使用了不同的非线性函数。
　　所有的80个操作都具有相同的基本算法过程，如图4所示。具体来说，它们的算法过程如下：
　　TEMP=S5
　　(A)+ft(B,C,D)+Wt+Kt+E;E=D;D=C；C=S30(B)；A=TEMP。
　　其中，A，B，C，D，E即为中间变量；TEMP为临时变量，它是保存中间结果；t为操作的序列，0≤t≤79；Sn(X)表示将)X向左循环移n位；ft(B,C,D)为非线性函数，它的输入为中间变量B、C、D；Wt是由当前的512bit输入分组所导出的32bit字；Kt是由算法指定的常数，它是按一定规律得到的伪随机数字。
　　
　　1)非线性函数A(B,C,D)
　　SHA-1的四轮操作分别使用了不同的非线性函数：
　　
　　即将第80步操作后的输出结果加到循环前的消息摘要缓存中，缓存区更新完毕后，SHA-1算法将处理下一个分组，直至处理完所有的消息分组。
　　
　　第五步：输出。
　　在所有的消息分组处理完毕后，最后产生的缓存区内容(H0，H1，H2，H3，H4)即为所需的160bit的消息摘要。
　　
　　3.2、SHA-1算法的应用
　　对于长度在一定范围内的二进制输入码流，SHA-1算法可以生成一个固定长度的二进制输出码流。从计算复杂度而言，要从SHA-1给出的输出码流中推算出输入码流是不可行的。对于不同的输入码流，得到的输出码流也是不同的。因此，数字信号在传输过程中发生的任何变化，不可避免地将导致SHA-1计算结果的变化。由此便可以检测到秘密信息传输过程中是否有未经授权的使用者。
　　
　　4、加密认证系统的总体框图
　　
　　整个认证模块主要由四部分组成，如图5所示。其中1-wire模块主要工作在主模式，负责同加密芯片之间的通信；指令译码模块主要负责加密芯片和认证模块之间通信的指令译码工作，译码前指令存储在ROM块中；SHA-1引擎的核心处理器为Xilinx公司的PicoBlaze8位微处理器，主要功能是计SHA-1算法，进行安全认证，它接收外部加密芯片通过1-wire总线接口传送来的信息，将其和MAC结果进行对比，只有当哈希计算结果和加密芯片中SHA-1引擎的哈希计算结果匹配时，才能使FPGA用户设计正常工作；随机数发生器(RNG)是当复位信号置位SHA-1引擎模块时，RNG为该模块产生一串随机数，SHA-1引擎模块处理这一串随机数，转换成40位随机数据，并用来进行哈希计算。
　　本文提出一种安全散列SHA-1算法，并对安全散列值的计算方法进行了深入的分析，给出了安全散列值的计算步骤，论证了安全散列算法的安全性和可靠性。给出了一种SHA-1(Secure HashAlgorithm安全哈希算法)算法在加密认证系统的应用，整个认证系统通过1-wire总线，使FPGA完成与DS28E01-100加密芯片的通信，主机内核采用了Xilinx公司设计开发的8位微控制器软核PicoBlaze。将加密芯片和FPGA在电路板上进行了实验验证，加密芯片所烧录的密码不正确，FPGA就不能正常工作，证明该设计能够完成加密认证系统的全过程，起到了很好的保护知识产权的目的。