密码散列函数

密码学散列函数或密码散列函数是为密码学设计的散列函数。 哈希函数从输入值（例如消息或文件）生成输出值（“哈希”），该输出值通常是整数，在给定的值范围内以随机方式出现。 从今天的角度来看，如果该函数还具有以下属性，则该函数适用于密码学：

• 它可以处理任何位或字节序列，并使用它来生成固定长度（通常为 256 位）的整数散列。
• 它具有很强的抗冲突性：几乎不可能（需要不切实际的高计算量）找到产生相同散列的两个不同输入。
• 这是一种单向函数：几乎不可能找到产生给定散列的输入。

此类散列函数主要用于检查文件或消息的完整性。 为此，该函数应用于要检查的文件并与已知的先前哈希值进行比较。 如果新的哈希值与此不同，则文件已被修改。 加密散列函数还用于安全地存储密码和数字签名。 当系统验证密码或签名时，它会将其哈希值与存储的哈希值进行比较。 如果两个值匹配，则密码或签名正确。 这避免了以纯文本形式存储密码或签名，这会使它们容易受到攻击。 此外，加密散列函数可用作伪随机数生成器并构建分组密码。

有许多加密散列函数。 许多算法，例如消息摘要算法 5，不再被认为是安全的，因为针对它们的密码分析攻击是众所周知的。 SHA-2 和 SHA-3 算法系列是实践中经常使用的函数之一，仍然被认为是安全的。

哈希函数是一种映射，可以有效地将任意长度的字符串（输入值）映射到固定长度的字符串（哈希值）。 这必然意味着不同的输入值被分配了相同的哈希值，因此映射不是单射的。 所以基本上可以找到导致相同哈希值的两个输入值。

除了只接收一个输入的无密钥散列函数之外，还有需要密钥作为第二个输入的依赖于密钥的散列函数。

无密钥哈希函数又分为单向哈希函数（简称OWHF）和抗碰撞哈希函数（简称CRHF）。

单向哈希函数满足以下条件：

• 单向函数（原像阻力）：对于给定的输出值 y 实际上不可能找到散列函数映射到 y 的输入值 x : h ( x ) = y  。
• 弱抗碰撞性或第二原像抗性：对于给定值 x 几乎不可能找到产生相同哈希值的不同值 x ′： h ( x ) = h ( x ′ ) , x ≠ x ′ .

对于抗碰撞哈希函数，以下内容也适用：

• 抗碰撞性强：几乎不可能找到两个不同的输入值 x 和 x ′ 产生相同的哈希值。 与弱抗碰撞的区别在于输入值 x和 x ′ 都可以自由选择。

您还可以要求近碰撞阻力。 几乎不可能找到两个不同的输入值 x和 x ′其散列值 h ( x ) 和 h ( x ′ ) 只有几位不同。

依赖于密钥的哈希函数包括消息身份验证代码 (MAC)。 这些包括 HMAC、CBC-MAC 或 UMAC 等结构。

大多数加密散列函数将要散列的消息分成长度相等的部分 m ，这些部分依次合并到长度为 n 的数据块中。 如有必要，消息会被加长到 m 的倍数，因此原始消息的长度通常也会被编码ht 被附加。 有一个连接函数将消息部分和数据块的当前值作为输入并计算数据块的下一个值。 一些散列算法为连接函数提供进一步的输入，例如到那时为止处理的消息块或比特的数量，例如，参见 HAIFA 方法。 数据块的大小通常为 128 到 512 位，有时更多，例如 SHA-3。 B. 1600 位。 在处理完最后一个消息部分后，从数据块中获取哈希值；在某些情况下，会预先对其应用终结函数。

拼接函数是根据混淆和扩散的原理设计的，目的是为了保证输入的消息段不会有意构造出两个不同的消息，结果是相同的哈希值（碰撞安全）。

2010 年之前开发的大多数哈希函数都遵循 Merkle-Damgård 构造。 在 SHA-3 竞赛过程中，这种结构被各种其他方法补充或修改。

在 Merkle-Damgård 构造中，压缩函数用作碰撞安全的串联函数，即。 H。 很难找到提供相同输出的不同输入。 这也导致了单向函数的属性。 很难为给定的输出找到合适的输入值。 压缩函数可以用不同的方式表示，通常它是从分组密码构造的。

使用 Merkle-Damgård 构造，输入消息 M 首先被扩展，并且还附加了消息长度的编码。 然后它被分成块 M 1 到 M t 长度为 m 。 压缩函数 f : { 0 , 1 } m + n → { 0 , 1 } n 将消息块和连接块作为输入并输出下一个连接块。 IV 表示链接块的恒定初始值。 最后一个区块的值 H t就是结果，即消息 M 的哈希值：

H 0 = I V H i = f ( M i , H i − 1 ) , i = 1 , 2 , … , t h ( M ) = H t

压缩函数 f 由分组密码 E构造而成。 E K ( x ) 应表示在密钥 K下使用分组密码 E 对 x 进行加密。 ⊕ {\displaystyle \oplus } 代表按位异或。 如上， M i  是消息块， H i 是连接块的值。 一些常见的压缩函数是：

Davies-Meyer（用于 MD4、MD5 和 SHA 等）以消息部分作为密钥对连接块进行加密，然后将密文链接到连接块，通常使用 XOR：

H i = E M i ( H i − 1 ) ⊕ H i − 1 。

相反，Matyas-Meyer-Oseas 使用连接块加密消息部分。 函数 g {\displaystyle g} 用于调整块大小，通常是恒等式：

H i = E g ( H i − 1 ) ( M i ) ⊕ M i 。

Hirose 使用的串联块的宽度是块密码的明文或密文块宽度的两倍。 G i , H i 各代表连接块的一半。 这里 g是一个可以保持简单的无定点函数，例如 B. 仅反转一位。 ‖ 表示串联，i。 H。 两个位块的连接：

G i = E H i − 1 ‖ M i ( G i − 1 ) ⊕ G i − 1 哈希函数 MDC-2 本质上是基于 Matyas-Meyer-Oseas 构造的双重应用。