介绍
哈希函数通常用于验证数据完整性和加密目的。在本文中，我将实现广泛使用的SHA-256哈希函数，并探讨为什么它是不可逆的（即，为什么无法还原原始值）。结论是，哈希函数的不可逆性是通过信息丢失实现的。
SHA-256的流程
通过分析SHA-256的流程，我们可以理解其不可逆性。让我们以字符串"msg"为例进行哈希。
首先，将字符串"msg"转换为其字符编码（十六进制表示）。
接下来，将消息格式化为一个64字节的块。在原始消息后添加0x80，并在块的最后8个字节附加原始消息的二进制长度。由于"msg"是3字节，其二进制长度为24位，十六进制表示为0x18。在0x80和消息长度之间的空隙用零填充。
将64字节的块分割为4字节的段。例如，第一个段6d 73 67 80变为6d736780（十进制：1836279680）。
计算值W，其中包含不可逆的处理。以下是部分Rust代码片段：
fn calc_w(msg: [u32; 16]) -> [u32; 64] {
letmut w = vec![0; 64];
for i in0..16 {
w[i] = msg[i];
}
for i in16..64 {
w[i] = lower_sigma_1(w[i - 2])
.wrapping_add(w[i - 7])
.wrapping_add(lower_sigma_0(w[i - 15]))
.wrapping_add(w[i - 16]);
}
w
}
fn lower_sigma_1(x: u32) -> u32 {
rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)
}
fn rotr(x: u32, n: u32) -> u32 {
(x >> n) | (x << (32 - n))
}
fn shr(x: u32, n: u32) -> u32 {
x >> n
}
calc_w函数调用lower_sigma_1函数，而lower_sigma_1又调用rotr。让我们来看看这是如何工作的。
例如，设x = 31，n = 3。在二进制中，31是11111。由于x和n是无符号32位整数，x表示为000...000011111（前面有27个零）。
操作x >> n将x向右移动n位，在左侧添加000并移除最后的111。同样，x << (32 - n)将x向左移动32 - 3 = 29位。前三位变为111，后面跟随零。最后，步骤6和7的按位或结果是一个类似111000...0011的值。
信息丢失发生在shr操作中。在步骤6中，向右移出的位无法恢复。此外，在lower_sigma_1中，操作rotr(x, 17) ^ rotr(x, 19)导致信息丢失。简化来说，这个过程涉及将10000右移1位与10000右移2位进行异或，得到01000 ^ 00100 = 00000。这个结果也可能源自原始值00000，使得原始值无法恢复。通过重复这样的操作，恢复原始值变得不可能。
