如何从零开始编写一个sha1哈希函数?

从零开始实现一个基本的SHA1哈希函数的逐步指南,包括输入处理、初始化、计算轮次和输出。
On this page

如何从零开始编写一个sha1哈希函数?

摘录

学习如何从零开始编写 SHA1 哈希函数,并了解背后的过程。本博文详细解释了每个步骤,并提供了示例以便更好地理解。

介绍

SHA1或 SHA-1 是一种广泛应用于安全应用程序中的流行的单向加密散列函数。尽管该算法很复杂,但从头开始了解实现基本的 SHA1 散列函数所涉及的核心步骤是很有教育性和洞察力的。在本文中,我们将以简化的方式讲解开发 SHA1 散列程序的关键阶段。

理解 SHA1

SHA1 接受任意长度的输入消息并生成一个 160 位的哈希值。关键特性:

  • 输入的微小变化导致输出的显著变化
  • 无法从哈希中生成原始输入
  • 不同的输入之间发生碰撞的几率很低

SHA1 算法对二进制数据进行操作,包括 6 个主要步骤:

  1. 将输入转换为二进制
  2. 对输入进行填充
  3. 将消息分为 512 位的块
  4. 初始化变量
  5. 执行哈希计算
  6. 输出最终的 160 位哈希值

让我们来看看每个步骤:

步骤 1:将输入转换为二进制

首先将输入字符串转换为二进制位串。可以通过以下方式完成:

  • ASCII 编码 - 将字符转换为 8 位 ASCII 值
  • Unicode 编码 - 将字符转换为 16 位 Unicode 代码点

例如,字符串"Hello"在 ASCII 二进制形式下变为

10100100001100101011011000110110001101111

步骤 2:填充消息

将二进制消息填充以确保其长度是 512 位的倍数。填充包括:

  • 在消息末尾附加一个单独的 1 位
  • 添加 0 位,直到消息距下一个 512 倍数还有 64 位
  • 在末尾附加一个 64 位消息长度值

因此,具有其 ASCII 二进制的"Hello"被填充为

101001000011001010110110001101100011011110000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010000001010100100000011001010

步骤 3:将消息分为块

然后将填充的消息分为 512 位的块。如果填充后的长度为 1048 位,我们将得到两个 512 位的块:

1Block 1: 0100100001100101011011000110110001101111000000100000000000000000000000000000000000000000000000000000000
2
3Block 2: 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001010000001010100100000011001010

步骤 4:初始化变量和常数

SHA1 使用五个 32 位变量作为初始化:

1var h0 := 0x67452301
2var h1 := 0xEFCDAB89
3var h2 := 0x98BADCFE
4var h3 := 0x10325476
5var h4 := 0xC3D2E1F0

它还使用了从 2 到 79 的质数的立方根的小数部分生成的常数。

步骤 5:哈希计算

这包括四轮处理消息块:

  1. 消息调度 - 创建 80 个扩展消息单词
  2. 压缩函数 - 使用扩展消息、常数和哈希值进行逻辑操作。
  3. 更新哈希值 - 将压缩函数的输出添加到初始哈希值中。
  4. 输出 - 将最终哈希值转换为十六进制以生成 160 位哈希值。

压缩和更新步骤将针对每个 512 位块重复执行。

步骤 6:生成最终哈希值

在处理完所有块之后,通过连接 5 个更新的 32 位哈希变量 h0 到 h4 来生成最终的 160 位哈希值。

对于"Hello",最终的 SHA1 哈希值为

1f7ff9e8b7bb2e09b70935a5d785e0cc5d9d0abf0

一个免费的在线工具,可以快速验证您的答案

结论

从头开始实现 SHA1 算法可以提供对其内部工作原理的有价值的见解。通过遵循预处理、初始化、哈希计算和输出生成的基本步骤,我们可以为任何输入生成最终的 SHA1 摘要。学习这些密码学概念和方法将为我们解决更高级的哈希函数问题做好准备。