2.4 密码哈希函数

密码哈希函数将可变长度输入映射到固定长度输出。该类哈希函数输出可以被视为输入数据的指纹。密码哈希函数在许多应用中均扮演着重要的角色，例如数字签名、消息完整性、身份验证协议、密码保护和随机数生成等。在基于密码学构建的隐私计算领域，处处可见密码哈希函数的身影。

2.4.1 SHA-2算法

安全哈希算法2（Secure Hash Algorithm 2，简写为SHA-2）是一系列哈希算法，可用于取代 SHA-1算法。SHA-2具有比SHA-1高的安全级别。SHA-2由美国国家标准与技术研究院（National Institute of Standards and Technology，简写为NIST）和美国国家安全局（National Security Agency，简写为NSA）设计，共包含6个算法标准：SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256。本节以SHA-256为例，介绍SHA-2算法的原理，其计算流程如图2-18所示。

1.背景知识

如图2-19所示，SHA-256是一个确定性算法，其输入的长度需要控制在2 ⁶⁴ 比特以内，在计算之前，输入需要先进行填充，然后按512比特分组进行处理，算法计算完成后，输出一个256比特的摘要。

该算法在正式计算前，需要预备1个常量集合和1个函数集合。

1）消息填充

假设待计算的消息为 m ，其长度为Len（ m ）。在执行逻辑计算前，需要对 m 补位填充，得到 m' 。具体的填充方法如下。

步骤1： 将消息中的每个字符更换为ASCII码，例如，字符串abc 979899。

步骤2： 将其转换为二进制表示方式，如下所示。

abc 979899 01100001 01100010 01100011

步骤 3： 如图2-20所示，在最后1比特后填充1，然后重复追加0，直至Len（ m || padding）= 448 mod 512。其中，|| 是比特串连接符，padding表示填充比特。

步骤4： 将Len（ m || padding）转换为64比特的二进制值，并附加在 m' 的最后几比特。例如，abc的长度是24比特，转换为64比特的二进制值是0…011000，因此 m' 的最终结果如下。

01100001 01100010 01100011||10...0||0...011000

此时，0=Len（ m' ）mod512。

2）计算初始常量

SHA-256计算过程需要1个常量集合和1个函数集合，常量集合包含8个初始常量（ A 0 ， B 0 ， C 0 ， D 0 ， E 0 ， F 0 ， G 0 ， H 0 ）与64个轮常量 ，函数集合包含6个函数（ C h ， M a ， Σ 0 ， Σ 1 ， σ 0 ， σ 1 ）。

· 初始常量

初始常量共包含8个值，其具体数值分别如下：

0x6a09e667，0xbb67ae85，0x3c6ef372，0xa54ff53a

0x510e527f，0x9b05688c，0x1f83d9ab，0x5be0cd19

以上常量分别通过以下方式计算得到。

步骤1： 选择正整数中最小的8个素数（2，3，5，7，11，13，17，19）。

步骤2： 计算每个素数的平方根，得到 。

步骤3： 截取每个素数平方根的小数部分，例如2≈1.414213562373095048，截取小数部分，得到0.414213562373095048。

步骤4： 将每个素数平方根的小数部分转换为十六进制值，并取前8个字符。例如 ≈1.414213562373095048，截取小数部分，得到0.414213562373095048；将其转换为十六进制值，得到6a09e667f3bccc；截取前8个字符，得到6a09e667。

如图2-21所示，使用以上常量对（ A 0 ， B 0 ， C 0 ， D 0 ， E 0 ， F 0 ， G 0 ， H 0 ）进行初始化：

（ A 0 ， B 0 ， C 0 ， D 0 ， E 0 ， F 0 ， G 0 ， H 0 ）用于SHA-256的逻辑运算。

· 轮常量

轮常量 包含64个值，具体值在图2-22中给出。轮常量的计算方式与初始常量类似，具体过程如下。

步骤1： 选择正整数中最小的64个素数。

步骤2： 对以上每个素数计算立方根。

步骤3： 对每个素数立方根的小数部分，截取前32比特，得到最终的结果。

3）函数集合定义

在SHA-256的逻辑运算中，需要使用6个运算函数（ C h ， M a ， Σ 0 ， Σ 1 ， σ 0 ， σ 1 ）。其函数定义如下：

其中， x ∧ y 表示将 x 和 y 按位与， x ⊕ y 表示将 x 和 y 按位异或，¬ x 表示将 x 按位非， S ⁱ （ x ）表示将 x 逻辑右移 i 比特， R ⁱ （ x ）表示将 x 循环右移 i 比特。

2.算法细节

假设填充后的消息为 m '= m +padding，其长度为Len（ m '）= n ·512比特，其中 n 为大于或等于1的正整数。由于SHA-256的单次处理长度为512比特，因此需要将消息 m' 分成 n 个消息块，即 。对于每个消息块执行以下计算。

步骤1： 将每个消息块划分为16个32比特字，例如， = w 0 || w 2 ||···|| w 15 ，通过（ w 0 ， w 1 ，···， w 15 ）计算出（ w 16 ， w 17 ，···， w 63 ），其计算方法如下。

w t = σ 1 （ w t -2 ）+ w t -7 + σ 0 （ w t -15 ）+ w t -16

步骤2： 迭代64轮计算，得到（ A 63 ， B 63 ， C 63 ， D 63 ， E 63 ， F 63 ， G 63 ， H 63 ）。第 t 轮的计算过程如图2-23所示。其中， t ∈［1，63］。

步骤 3： 将以上步骤计算得到的摘要值（ A 63 ， B 63 ， C 63 ， D 63 ， E 63 ， F 63 ， G 63 ， H 63 ）赋值给（ A 0 ， B 0 ， C 0 ， D 0 ， E 0 ， F 0 ， G 0 ， H 0 ），输入 m' i ，并重复执行步骤1～3，直至 i = n 。其中， m' i 表示第 i 个数据块。

步骤4： 最终输出（ A 63 ， B 63 ， C 63 ， D 63 ， E 63 ， F 63 ， G 63 ， H 63 ），作为 m 的摘要。

2.4.2 SM3算法

SM3是中国国家密码管理局在2010年12月发布的一种类似于SHA系列的我国自主设计的密码哈希函数 ^［59］ 。该算法的计算流程如图2-24所示。

1.背景知识

1）初始常量

在SM3算法中，初始常量被用作填充初始IV值，即IV 0 ，IV值在每次迭代压缩函数的计算中会被用到。初始常量包含：

2）消息填充

在执行SM3逻辑计算之前，需要先对消息进行填充。对于消息填充，其过程与SHA-256算法的消息填充相同；因此，本节不再赘述。

2.算法细节

假设填充后的消息为 m' = m +padding，其长度为Len（ m' ）= n ·512比特，其中 n 为大于或等于1的正整数。由于SHA-256的单次处理长度为512比特，因此我们需要将消息 m' 分成 n 个消息块，即 。对于每个消息块，执行以下计算。

步骤 1： 按照以下方法将每个消息块扩展为132个字｛｛ w 0 ，…， w 67 ｝，｛ ，…， ｝｝。

· 首先将512比特的 m 划分为16个32比特字的消息块，即｛ w 0 ，…， w 15 ｝ m 。

· 通过逻辑函数 w j = P 1 （ w j -16 ⊕ w j -9 ⊕RL ¹⁵ （ w j -3 ））⊕RL ⁷ （ w j -13 ）⊕ w j -6 ，计算｛ w 16 ，…， w 67 ｝。其中， j ∈［16，67］，RL ⁱ （ x ）表示将 x 循环左移 i 比特， P 1 （ x ）= x ⊕RL ¹⁵ （ x ）⊕RL ²³ （ x ）。

· 通过逻辑函数 = w j ⊕ w j +4 计算｛ ，…， ｝。其中， j ∈［0，63］。

步骤2： 定义初始常量 T j ，同时定义两个函数FF j 与GG j 。

其中， X 、 Y 、 Z 是字，∧、∨、¬、⊕分别表示按位与、按位或、按位非和按位异或运算。

步骤3： 迭代64轮计算，得到（ A 63 ， B 63 ， C 63 ， D 63 ， E 63 ， F 63 ， G 63 ， H 63 ）。每轮计算过程如图2-25所示，其中 j ∈［0，63］。

步骤4： 将以上步骤计算得到的摘要值（ A 63 ， B 63 ， C 63 ， D 63 ， E 63 ， F 63 ， G 63 ， H 63 ）赋值给（ A 0 ， B 0 ， C 0 ， D 0 ， E 0 ， F 0 ， G 0 ， H 0 ），输入 m ' i ，并重复执行步骤1～4，直至 i = n 。

步骤5： 最终输出（ A 63 ， B 63 ， C 63 ， D 63 ， E 63 ， F 63 ， G 63 ， H 63 ），作为 m 的摘要。 F8fZVaLwYGWaE5wqMUzvklsdGjgfQwRcE5nEpLXqLStoJra1/m2lqWUwBU/3bQwC