Python中如何通过反向输入字节逆向SHA256哈希至初始状态？

已知字符串Hello World!的SHA256哈希值为7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069，希望从该最终哈希出发，输入反向字符串!dlroW olleH，逆向还原出空输入时的初始哈希状态（即空字节哈希值e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855）。

核心需求是实现逆向SHA256哈希流程：从最终哈希状态开始，输入原数据的反向字节，逐步逆推回初始状态，而非正向计算哈希。

需求背景是为了在O(1)空间、O(n)时间复杂度且不修改单向链表的前提下，验证值为[0..9]的单向链表是否为回文（对应LeetCode题目：验证回文链表）。

#!/usr/bin/python3

import hashlib

# 正向SHA256示例（现有功能）
m = hashlib.sha256()
print(m.hexdigest())  # 输出空输入哈希：e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
m.update(b"Hello ")
m.update(b"World!")
print(m.hexdigest())  # 输出最终哈希：7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069

m2 = hashlib.sha256()
m2.update(b"Hello World!")
print(m2.hexdigest()) # 与上面结果一致：7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069

assert m.hexdigest() == m2.hexdigest()


# 期望的逆向SHA256功能
r = hashlib.sha256rev("7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069")
r.update(b"!dlroW")
r.update(b" olleH")
print(r.hexdigest())  # 期望输出空输入哈希：e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

r2 = hashlib.sha256rev("7f83b1657ff1fc53b92dc18148a1d65dfc2d4b1fa3d677284addd200126d9069")
r2.update(b"!dlroW olleH")
print(r2.hexdigest()) # 期望输出空输入哈希：e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

assert r.hexdigest() == r2.hexdigest()

SHA256是单向哈希函数，设计目标为正向计算容易、逆向推导困难，但本次需求并非破解哈希（寻找任意原输入），而是在已知后续输入反向的前提下逆推哈希状态：

1. SHA256核心压缩函数由64轮可逆/半可逆操作（旋转、异或、模加法等）组成，理论上可通过逆运算推导出上一轮状态，但需精确处理每一步变换逻辑。
2. 需匹配SHA256的填充规则：正向计算时会自动对输入填充（添加1、补0、追加长度），逆向过程需对应处理原输入填充的反向逻辑，否则无法得到正确初始状态。
3. Python标准库hashlib未提供逆向哈希功能，需自行实现底层逻辑。

1. 掌握SHA256底层逻辑：先熟悉SHA256的消息扩展（将512位消息块生成64个32位字）、压缩函数（8个32位寄存器的64轮更新）正向流程。
2. 实现压缩函数逆运算：
   • 针对每一轮变换公式反向推导寄存器状态：例如正向中a = h0 + Σ0(a_prev) + Ch(e_prev,f_prev,g_prev) + k[i] + w[i]，逆向时需从当前a、已知w[i]和k[i]推导出a_prev，并恢复其他寄存器状态。
   • 处理模加法逆向：由于是32位无符号整数加法，逆向时需用减法结合模2^32运算。
3. 处理消息块与填充：将反向输入分割为512位消息块，按照SHA256填充规则处理（匹配原输入填充的反向），从最后一个块开始逆推状态。
4. 分步验证：先针对单个消息块的逆向进行测试，比如用空输入哈希正向计算单个块得到最终哈希，再逆向该块验证是否能回到空输入哈希，确保每一步逻辑正确。

由于逆向SHA256实现复杂度高、易出错，针对回文链表验证需求，更简单高效的O(1)空间方案如下：

• 快慢指针找中点：快指针每次走2步，慢指针每次走1步，快指针到末尾时，慢指针指向链表中点。
• 反转后半部分链表：从慢指针位置开始反转后半部分链表。
• 比较前后部分：同时遍历前半部分和反转后的后半部分，比较节点值是否一致。
• 恢复链表（可选）：若需保持链表结构，可再次反转后半部分并拼接回原链表。

内容的提问来源于stack exchange，提问作者correabuscar