如何使用Python内置模块对超大整数执行位运算并修复SHA-1实现中的超大整数处理问题

我来帮你解决这个SHA-1实现的问题！你的核心问题出在错误地用字符串拼接来计算整数，这直接导致了超大整数，完全违背了SHA-1的32位无符号整数运算规则。下面我一步步给你修复，全程只用Python内置模块：

核心问题分析 #

SHA-1的所有中间运算都是基于32位无符号整数定义的，而你用字符串拼接生成整数的操作，完全偏离了这个规则，直接制造了超出预期的超大整数。我们不需要用数组来处理，只要用Python的整数配合32位掩码，就能完美模拟32位无符号整数的运算行为。

1. 修复循环左移函数 #

你的leftrotate_util用字符串处理完全没必要，Python可以直接用位运算实现符合SHA-1要求的32位循环左移：

def leftrotate(x: int, n: int) -> int:
    # 循环左移n位后，用掩码保留32位，模拟无符号整数溢出
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF

2. 修复generate_temp函数 #

你之前用字符串拼接计算temp是完全错误的，SHA-1的temp计算应该是32位整数的加法和位运算：

def generate_temp(a: int, f: int, e: int, k: int, current_word: int) -> int:
    rotated_a = leftrotate(a, 5)
    # 所有运算后用掩码截断为32位
    temp = (rotated_a + f + e + k + current_word) & 0xFFFFFFFF
    return temp

注意：current_word必须是32位整数，你的digest()函数要确保返回的每个words[i]都是符合要求的32位消息字。

3. 简化位运算代码 #

你用operator模块的写法太繁琐，Python本身有更简洁的内置位运算符，替换后代码更易读：

• operator.and_(b,c) → b & c
• operator.or_(x,y) → x | y
• operator.not_(b) → (~b) & 0xFFFFFFFF（加掩码转成32位无符号取反）
• operator.xor_(b,c) → b ^ c

比如i≤19时的f计算，可以简化为：

f = (b & c) | ((~b) & 0xFFFFFFFF & d)
# 或者更简洁的SHA-1等价写法：f = d ^ (b & (c ^ d))

4. 修复哈希值更新逻辑 #

你之前用字符串拼接更新h0-h4的操作完全错误，正确的逻辑是循环结束后，用32位模加法更新初始哈希值：

# 80轮循环结束后更新哈希值
h0 = (h0 + a) & 0xFFFFFFFF
h1 = (h1 + b) & 0xFFFFFFFF
h2 = (h2 + c) & 0xFFFFFFFF
h3 = (h3 + d) & 0xFFFFFFFF
h4 = (h4 + e) & 0xFFFFFFFF

完整修复后代码示例 #

from typing import Final

def leftrotate(x: int, n: int) -> int:
    """32位无符号整数的循环左移实现"""
    return ((x << n) | (x >> (32 - n))) & 0xFFFFFFFF

def generate_temp(a: int, f: int, e: int, k: int, current_word: int) -> int:
    """按SHA-1规则计算temp值，全程保持32位运算"""
    rotated_a = leftrotate(a, 5)
    return (rotated_a + f + e + k + current_word) & 0xFFFFFFFF

def digest():
    """
    这里替换成你自己的消息填充与扩展实现：
    1. 对输入消息进行SHA-1标准填充
    2. 分割为16个32位字，再扩展为80个32位字
    """
    # 示例返回空的80个32位字，实际要替换为你的逻辑
    return [0] * 80

def hashing():
    words = digest()
    # SHA-1初始哈希值
    h0, h1, h2, h3, h4 = (0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0)
    
    a, b, c, d, e = h0, h1, h2, h3, h4
    for i in range(80):
        if 0 <= i <= 19:
            f = (b & c) | ((~b) & 0xFFFFFFFF & d)
            k: Final[int] = 0x5A827999
        elif 20 <= i <= 39:
            f = b ^ c ^ d
            k: Final[int] = 0x6ED9EBA1
        elif 40 <= i <= 59:
            f = (b & c) | (b & d) | (c & d)
            k: Final[int] = 0x8F1BBCDC
        elif 60 <= i <= 79:
            f = b ^ c ^ d
            k: Final[int] = 0xCA62C1D1
        
        temp = generate_temp(a, f, e, k, words[i])
        e = d
        d = c
        c = leftrotate(b, 30)
        b = a
        a = temp
    
    # 更新并保留32位哈希值
    h0 = (h0 + a) & 0xFFFFFFFF
    h1 = (h1 + b) & 0xFFFFFFFF
    h2 = (h2 + c) & 0xFFFFFFFF
    h3 = (h3 + d) & 0xFFFFFFFF
    h4 = (h4 + e) & 0xFFFFFFFF
    
    # 转换为16进制哈希字符串
    return f"{h0:08x}{h1:08x}{h2:08x}{h3:08x}{h4:08x}"

关于数组处理的疑问 #

你提到考虑用数组表示整数，其实完全没必要！Python的int支持任意精度，但我们可以通过& 0xFFFFFFFF这个掩码，手动模拟32位无符号整数的溢出行为，这样所有运算都严格符合SHA-1的定义，比用数组处理位运算简单得多。

最后注意事项 #

• 你的digest()函数是关键，必须正确实现SHA-1的消息填充和消息扩展逻辑，否则整个哈希结果都会错误。
• 所有涉及32位整数的运算后，一定要加上& 0xFFFFFFFF掩码，确保截断为32位无符号整数，模拟硬件级别的溢出行为。

内容来源于stack exchange