本节书摘来自华章计算机《区块链开发指南》一书中的第3章，第3.1节,作者：申屠青春 主编 宋 波 张 鹏 汪晓明 季宙栋 左川民 编著更多章节内容可以访问云栖社区“华章计算机”公众号查看。
第3章 密码学基础 3.1 Hash函数
Hash函数是密码学的一个重要分支，它是一种将任意长度的输入变换为固定长度的输出且不可逆的单向密码体制。Hash函数在数字签名和消息完整性检测等方面有着广泛的应用。
3.1.1 技术原理
Hash函数又称为哈希函数、散列函数、杂凑函数。它是一种单向密码体制，即一个从明文到密文的不可逆映射，只有加密过程，没有解密过程。
Hash函数可以将满足要求的任意长度的输入进行转换，从而得到固定长度的输出。这个固定长度的输出称为原消息的散列值（Hash Value）或消息摘要（Message Digest）。Hash函数的数学表述为：
其中，H是Hash函数，没m是任意长度明文，h是固定长度的Hash值。
理想的Hash函数对于不同的输入可以获得不同的Hash值。如果是两个不同的消息，存在，则称x和x′是Hash函数的一个碰撞。
由于Hash函数这种单向的特征及长度固定的特征使得它可以生成消息或数据块的消息摘要（也称为散列值、哈希值），因此在数据完整性和数字签名领域有着广泛的应用。
典型的Hash函数有两类：消息摘要算法（MD5）和安全散列算法（SHA）。
Hash函数具有如下特点。
易压缩：对于任意大小的输入x，Hash值的长度很小，在实际应用中，函数H产生的Hash值其长度是固定的。
易计算：对于任意给定的消息，计算其Hash值比较容易。
单向性：对于给定的Hash值，要找到使得在计算上是不可行的，即求Hash的逆很困难。
抗碰撞性：理想的Hash函数是无碰撞的，但在实际算法的设计中很难做到这一点。有两种抗碰撞性：一种是弱抗碰撞性，即对于给定的消息，要发现另一个消息，满足在计算上是不可行的；另一种是强抗碰撞性，即对于任意一对不同的消息，使得在计算上也是不可行的。
高灵敏性：这是从比特位角度出发的，指的是1比特位的输入变化会造成1/2的比特位发生变化。
3.1.2 SHA-1算法
1993年美国国家标准技术研究所NIST公布了安全散列算法SHA-0标准，1995年4月17日公布的修改版本称之为SHA-1。SHA-1在设计方面很大程度上是模仿MD5进行设计的，但它对任意长度的消息均是生成160位的消息摘要（MD5仅仅生成128位的摘要），因此抗穷举搜索能力更强。它有5个参与运算的32位寄存器字，消息分组和填充方式与MD5相同，主循环也同样是四轮，但每轮要进行20次操作，包含非线性运算、移位和加法运算等，但非线性函数、加法常数和循环左移操作的设计与MD5有一些区别。
SHA-1的输入是最大长度小于264位的消息，输入消息以512位的分组为单位进行处理，输出是160位的消息摘要。SHA-1具有实现速度高、容易实现、应用范围广等优点，其算法描述如下。
1）对输入的消息进行填充：经过填充后，消息的长度模512应与448同余。填充的方式为第一位是1，余下各位都为0。再将消息被填充前的长度以big-endian的方式附加在上一步留下的最后64位中。该步骤是必须的，即使消息的长度已经是所希望的长度。填充的长度范围是1到512。
2）初始化缓冲区：可以用160位来存放Hash函数的初始变量、中间摘要及最终摘要，但首先必须进行初始化，对每个32位的初始变量赋值，即：
3）进入消息处理主循环，处理消息块：一次处理512位的消息块，总共进行4轮处理，每轮进行20次操作，如图3-1所示。这4轮处理具有类似的结构，但每轮所使用的辅助函数和常数都各不相同。每轮的输入均为当前处理的消息分组和缓冲区的当前值A、B、C、D、E，输出仍放在缓冲区以替代旧的A、B、C、D、E的值。第四轮的输出再与第一轮的输入相加，以产生，其中加法是缓冲区5个字中的每个字与中相应的字模相加。
4）输出：所有的消息分组都被处理完之后，最后一个分组的输出即为得到的消息摘要值。
SHA-1的步函数如图3-2所示，它是SHA-1最为重要的函数，也是SHA-1中最关键的部件。
图3-1 单个512位消息块的处理流程 图3-2 SHA-1的步函数SHA-1每运行一次步函数，A、B、C、D的值就会依次赋值给B、C、D、E这几个寄存器。同时，A、B、C、D、E的输入值、常数和子消息块在经过步函数运算后就会赋值给。
其中，是步数，，是由当前512位长的分组导出的一个32位的字，Kt是加法常量。
基本逻辑函数f的输入是3个32位的字，输出是一个32位的字，其函数表示如下。
其中∧、∨、-、⊕分别是与、或、非、异或4个逻辑运算符。
对于每个输入分组导出的消息分组，前16个消息字即为消息输入分组对应的16个32位字，其余可按如下公式得到：
其中，表示左循环移位s位，如图3-3所示。
此外，每轮中使用的不同消息常量，其具体数值为：
。
图3-3 SHA-1的80个消息字的产生过程
3.1.3 SHA-2算法
2002年，NIST推出SHA-2系列Hash算法，其输出长度可取224位、256位、384位、512位，分别对应SHA-224、SHA-256、SHA-384、SHA-512。它还包含另外两个算法：SHA-512/224、SHA-512/256。SHA-2系列Hash算法比之前的Hash算法具有更强的安全强度和更灵活的输出长度，其中SHA-256是常用的算法。下面将对前四种算法进行简单描述。
1.?SHA-256算法
SHA-256算法的输入是最大长度小于264位的消息，输出是256位的消息摘要，输入消息以512位的分组为单位进行处理。算法描述如下。
（1）消息的填充
添加一个“1”和若干个“0”使其长度模512与448同余。在消息后附加64位的长度块，其值为填充前消息的长度。从而产生长度为512整数倍的消息分组，填充后消息的长度最多为位。
（2）初始化链接变量
链接变量的中间结果和最终结果存储于256位的缓冲区中，缓冲区用8个32位的寄存器A、B、C、D、E、F、G和H表示，输出仍放在缓冲区以代替旧的A、B、C、D、E、F、G、H。首先要对链接变量进行初始化，初始链接变量存储于8个寄存器A、B、C、D、E、F、G和H中：
初始链接变量是取自前8个素数（2、3、5、7、11、13、17、19）的平方根的小数部分其二进制表示的前32位。
（3）处理主循环模块
消息块是以512位分组为单位进行处理的，要进行64步循环操作（如图3-4所示）。每一轮的输入均为当前处理的消息分组和得到的上一轮输出的256位缓冲区A、B、C、D、E、
F、G、H的值。每一步中均采用了不同的消息字和常数，下面将给出它们的获取方法。
图3-4 SHA-256的压缩函数
（4）得出最终的Hash值
所有512位的消息块分组都处理完以后，最后一个分组处理后得到的结果即为最终输出的256位的消息摘要。
步函数是SHA-256中最为重要的函数，也是SHA-256中最关键的部件。其运算过程如图3-5所示。
且表示对32位的变量循环右移位。
的获取方法是取前64个素数（2，3，5，7，……）立方根的小数部分，将其转换为二进制，然后取这64个数的前64位作为。其作用是提供了64位随机串集合以消除输入数据里的任何规则性。
对于每个输入分组导出的消息分组，前16个消息字直接按照消息输入分组对应的16个32位字，其他的则按照如下公式来计算得出：
，
式中，表示对32位的变量右移位，其导出方法如图3-6所示。
图3-6 SHA-256的64个消息字的生成过程
2.?SHA-512算法
SHA-512是SHA-2中安全性能较高的算法，主要由明文填充、消息扩展函数变换和随机数变换等部分组成，初始值和中间计算结果由8个64位的移位寄存器组成。该算法允许输入的最大长度是位，并产生一个512位的消息摘要，输入消息被分成若干个1024位的块进行处理，具体参数为：消息摘要长度为512位；消息长度小于位；消息块大小为1024位；消息字大小为64位；步骤数为80步。图3-7显示了处理消息、输出消息摘要的整个过程，该过程的具体步骤如下。
1）消息填充：填充一个“1”和若干个“0”，使其长度模1024与896同余，填充位数为0-1023，填充前消息的长度以一个128位的字段附加到填充消息的后面，其值为填充前消息的长度。
2）链接变量初始化：链接变量的中间结果和最终结果都存储于512位的缓冲区中，缓冲区用8个64位的寄存器A、B、C、D、E、F、G、H表示。初始链接变量也存储于8个寄存器A、B、C、D、E、F、G、H中，其值为：
图3-7 SHA-512的整体结构
。
初始链接变量采用big-endian方式存储，即字的最高有效字节存储于低地址位置。初始链接变量取自前8个素数的平方根的小数部分其二进制表示的前64位。
3）主循环操作：以1024位的分组为单位对消息进行处理，要进行80步循环操作。每一次迭代都把512位缓冲区的值A、B、C、D、E、F、G、H作为输入，其值取自上一次迭代压缩的计算结果，每一步计算中均采用了不同的消息字和常数。
4）计算最终的Hash值：消息的所有个1024位的分组都处理完毕之后，第次迭代压缩输出的512位链接变量即为最终的Hash值。
步函数是SHA-512中最关键的部件，其运算过程类似SHA-256。每一步的计算方程如下所示，B、C、D、F、G、H的更新值分别是A、B、C、E、F、G的输入状态值，同时生成两个临时变量用于更新A、E寄存器。
对于80步操作中的每一步t，使用一个64位的消息字，其值由当前被处理的1024位消息分组导出，导出方法如图3-8所示。前16个消息字分别对应消息输入分组之后的16个32位字，其他的则按照如下公式来计算得出：
，
图3-8 SHA-512的80个消息字生成的过程
其中，
式中，表示对64位的变量循环右移n位，表示对64位的变量右移位。
从图3-8可以看出，在前16步处理中，的值等于消息分组中相对应的64位字，而余下的64步操作中，其值是由前面的4个值计算得到的，4个值中的两个要进行移位和循环移位操作。
的获取方法是取前80个素数（2，3，5，7，……）立方根的小数部分，将其转换为二进制，然后取这80个数的前64位作为，其作用是提供了64位随机串集合以消除输入数据里的任何规则性。
3.?SHA-224与SHA-384
1995年，美国国家标准与技术研究所（NIST）公布了新的安全散列算法SHA-1，该算法替代了1993年颁布的Hash函数标准算法SHA；2001年，为了满足更高的安全等级，NIST又颁布了3个新的Hash函数，即SHA-256、SHA-384和SHA-512，Hash值的长度分别为256位、384位和512位；2004年，又增加了SHA-224。5种Hash函数一起作为安全散列标准。
SHA-256和SHA-512是很新的Hash函数，前者定义一个字为32位，后者则定义一个字为64位。实际上二者的结构是相同的，只是在循环运行的次数、使用常数上有所差异。SHA-224及SHA-384则是前述两种Hash函数的截短型，它们利用不同的初始值做计算。
SHA-224的输入消息长度跟SHA-256的也相同，也是小于264位，其分组的大小也是512位，其处理流程跟SHA-256也基本一致，但是存在如下两个不同的地方。
SHA-224的消息摘要取自A、B、C、D、E、F、G共7个寄存器的比特字，而SHA-256的消息摘要取自A、B、C、D、E、F、G、H共8个寄存器的32比特字。
SHA-224的初始链接变量与SHA-256的初始链接变量不同，它采用高端格式存储，但其初始链接变量的获取方法是取前第9至16个素数（23、29、31、37、41、43、47、53）的平方根的小数部分其二进制表示的第二个32位，SHA-224的初始链接变量如下：
SHA-224的详细计算步骤与SHA-256一致。
SHA-384的输入消息长度跟SHA-512相同，也是小于位，而且其分组的大小也是1024位，处理流程跟SHA-512也基本一致，但是也有如下两处不同的地方。
SHA-384的384位的消息摘要取自A、B、C、D、E、F共6个64比特字，而SHA-512的消息摘要取自A、B、C、D、E、F、G、H共8个64比特字。
SHA-384的初始链接变量与SHA-512的初始链接变量不同，它也采用高端格式存储，但其初始链接变量的获取方法是取前9至16个素数（23、29、31、37、41、43、47、53）的平方根的小数部分其二进制表示的前64位，SHA-384的初始链接变量如下：
SHA-384的详细计算步骤与SHA-512的相同。
3.1.4 SHA-3算法
由于MD5、SHA系列的Hash函数遭受到了碰撞攻击，NIST在2005年10月31日到11月1日和2006年8月24日至25日举办了两次Hash函数研讨会，评估了Hash函数当前的使用状况，征求了公众对Hash函数的新准则。经过讨论之后，在2007年11月，NIST决定通过公开竞赛，以高级加密标准AES的开发过程为范例开发新的Hash函数，新的Hash算法被称为SHA-3，用于扩充包含SHA-2算法在内的FIPS 180-3中的安全Hash标准。截止到2008年10月31日，有64个算法提交到NIST。2008年12月10日，NIST宣布在这64个算法中有51个算法满足对候选算法提出的可接受的最低标准，确定为第一轮的候选，并开始进行SHA-3的第一轮竞选。提交的第一轮候选算法公布在www.nist.gov/hash-competition上以用于公众的评审。到2009年7月24日，第一轮的候选算法中剩下14个候选算法进入到第二轮的竞选中，这14个第二轮的候选算法为BLAKE、BLUE MIDNIGHT WISH、CubeHash、ECHO、Fugue、Gr?stl、Hamsi、JH、Keccak、Luffa、Shabal、SHAvite-3、SIMD和Skein。
NIST于2010年8月23日至24日在加州大学圣塔芭芭拉分校举行第二次SHA-3候选会议。在2010年12月9日，NIST宣布5个候选算法进入到第三轮，也是最后一轮的竞选，这5个候选分别是：BLAKE、Gr?stl、JH、Keccak和Skein。其中，BLACK使用HAIFA迭代框架，在压缩函数中加入盐和计数器，内部结构是局部宽管道结构；Gr?stl和JH采用宽管道MD结构，能抵抗一般的通用攻击；Keccak使用Sponge函数；Skein既可以使用迭代结构，也可以使用树结构。NIST在2012年评选出最终算法并产生了新的Hash标准。Keccak算法由于其较强的安全性和软硬件实现性能，最终被选为新一代的标准Hash算法，并被命名为SHA-3。
SHA-3算法整体采用Sponge结构，分为吸收和榨取两个阶段。SHA-3的核心置换f作用在5×5×64的三维矩阵上。整个f共有24轮，每轮包括5个环节θ、ρ、π、χ、τ。算法的5个环节分别作用于三维矩阵的不同维度之上。环节是作用在列上的线性运算；环节是作用在每一道上的线性运算，将每一道上的64比特进行循环移位操作；环节是将每道上的元素整体移到另一道上的线性运算；环节是作用在每一行上的非线性运算，相当于将每一行上的5比特替换为另一个5比特；环节是加常数环节。
目前，公开文献对SHA-3算法的安全性分析主要是从以下几个方面来展开的。
对SHA-3算法的碰撞攻击、原像攻击和第二原像攻击。
对SHA-3算法核心置换的分析，这类分析主要针对算法置换与随机置换的区分来展开。
对SHA-3算法的差分特性进行展开，主要研究的是SHA-3置换的高概率差分链，并构筑差分区分器。
Keccak算法的立体加密思想和海绵结构，使SHA-3优于SHA-2，甚至AES。Sponge函数可建立从任意长度输入到任意长度输出的映射。
3.1.5 RIPEMD160算法
RIPEMD（RACE Integrity Primitives Evaluation Message Digest），即RACE原始完整性校验消息摘要，是比利时鲁汶大学COSIC研究小组开发的Hash函数算法。RIPEMD使用MD4的设计原理，并针对MD4的算法缺陷进行改进，1996年首次发布RIPEMD-128版本，它在性能上与SHA-1相类似。
RIPEMD-160是对RIPEMD-128的改进，并且是RIPEMD中最常见的版本。RIPEMD-160输出160位的Hash值，对160位Hash函数的暴力碰撞搜索攻击需要次计算，其计算强度大大提高。RIPEMD-160的设计充分吸取了MD4、MD5、RIPEMD-128的一些性能，使其具有更好的抗强碰撞能力。它旨在替代128位Hash函数MD4、MD5和RIPEMD。
RIPEMD-160使用160位的缓存区来存放算法的中间结果和最终的Hash值。这个缓存区由5个32位的寄存器A、B、C、D、E构成。寄存器的初始值如下所示：
数据存储时采用低位字节存放在低地址上的形式。
处理算法的核心是一个有10个循环的压缩函数模块，其中每个循环由16个处理步骤组成。在每个循环中使用不同的原始逻辑函数，算法的处理分为两种不同的情况，在这两种情况下，分别以相反的顺序使用5个原始逻辑函数。每一个循环都以当前分组的消息字和160位的缓存值A、B、C、D、E为输入得到新的值。每个循环使用一个额外的常数，在最后一个循环结束后，两种情况的计算结果A、B、C、D、E和A′、B′、C′、D′、E′及链接变量的初始值经过一次相加运算产生最终的输出。对所有的512位的分组处理完成之后，最终产生的160位输出即为消息摘要。
除了128位和160位的版本之外，RIPEMD算法也存在256位和320位的版本，它们共同构成RIPEMD家族的四个成员：RIPEMD-128、RIPEMD-160、RIPEMD-256、RIPEMD-320。其中128位版本的安全性已经受到质疑，256位和320位版本减少了意外碰撞的可能性，但是相比于RIPEMD-128和RIPEMD-160，它们不具有较高水平的安全性，因为他们只是在128位和160位的基础上，修改了初始参数和s-box来达到输出为256位和320位的目的。
