求长度1-7的可打印ASCII字符串的CRC32碰撞概率

问题背景 #

需要计算长度1至7、字符范围为ASCII 32-126的可打印字符串的CRC32碰撞概率，但原代码因CPU占用过高、内存溢出导致崩溃。

原代码的核心问题 #

1. 内存爆炸：预先生成所有字符串并存入列表，比如长度7时，总共有95^7≈6.98×10¹³个字符串，完全无法存入内存。
2. 冗余计算：先生成所有字符串再遍历计算CRC，额外增加了内存开销和遍历成本。

优化方案 #

1. 数学公式估算碰撞概率（无需暴力枚举） #

根据生日悖论，当样本数量N远大于哈希空间大小M（CRC32的M=2³²≈4.29×10⁹）时，碰撞概率可通过公式近似计算：
碰撞概率 ≈ 1 - e^(-N²/(2M))

各长度对应的N（总字符串数）和近似碰撞概率：

• 长度1：N=95 → 概率≈0（可忽略）
• 长度2：N=95²=9025 → 概率≈0（可忽略）
• 长度3：N=95³=857375 → 概率≈0（可忽略）
• 长度4：N=95⁴≈8.14×10⁷ → 概率≈0.74%
• 长度5：N=95⁵≈7.73×10⁹ → 概率≈99.9999%
• 长度6、7：N远大于2³²，碰撞概率接近100%

2. 优化暴力枚举代码（仅适用于长度1-5） #

对于长度1-5，可通过以下方式减少内存占用，避免崩溃：

• 使用生成器直接遍历字符组合，不存储所有字符串
• 边遍历边计算CRC，实时更新哈希表

优化后的代码：

import binascii
from itertools import product

def calculate_crc32_collisions(length):
    crc_map = {}
    # 直接遍历字符组合，不存储所有字符串
    for chars in product(range(32, 127), repeat=length):
        s = ''.join(chr(c) for c in chars)
        crc = binascii.crc32(s.encode()) & 0xFFFFFFFF
        if crc in crc_map:
            crc_map[crc].append(s)
        else:
            crc_map[crc] = [s]
    # 筛选出有碰撞的条目
    collisions = {k: v for k, v in crc_map.items() if len(v) > 1}
    return collisions

if __name__ == "__main__":
    for length in range(1, 6):  # 长度6、7无需暴力枚举，概率接近100%
        print(f"=== 长度{length}的CRC32碰撞结果 ===")
        collisions = calculate_crc32_collisions(length)
        print(f"碰撞组数: {len(collisions)}")
        # 可选择性打印部分碰撞示例
        for crc, strings in list(collisions.items())[:5]:
            print(f"CRC32: {crc:08X}")
            for s in strings[:3]:
                print(f"  {repr(s)}")
            if len(strings) > 3:
                print(f"  ...共{len(strings)}个字符串")

3. 长度6、7的处理建议 #

由于长度6的字符串总数（95⁶≈7.34×10¹¹）已经是CRC32哈希空间的171倍，碰撞必然大量存在，无需暴力枚举。若需验证，可随机采样部分字符串计算CRC，几乎能立即找到碰撞对。

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