从 1 到 7 的所有可能的可变长度 ASCII 字符串的 CRC32 冲突概率是多少

Question

我试图在长度范围从 1 到 7 的所有可能的 ASCII 字符串中找到 CRC32 冲突概率。这里 ASCII 字符的范围可以从 ASCII 32 到 ASCII 126。我尝试在我的 PC 中运行我的程序，但由于对CPU要求高，程序会崩溃并且永远无法运行完成。有没有其他方法可以找到这个问题。

我的代码如下：

import binascii
from itertools import product

def crc32_all_ascii_strings(length):
  strings = []
  for chars in product(range(32, 127), repeat=length):
    strings.append(''.join(chr(c) for c in chars))

  crc32_dict = {}
  for string in strings:
    crc32 = binascii.crc32(string.encode()) & 0xFFFFFFFF
    if crc32 not in crc32_dict:
      crc32_dict[crc32] = []
    crc32_dict[crc32].append(string)

  return crc32_dict

if __name__ == "__main__":
  for length in range(1, 8):
    crc32_dict = crc32_all_ascii_strings(length)
    for crc32, string_list in crc32_dict.items():
      if len(string_list) > 1:
        print(f"CRC32: {crc32:08X}")
        for string in string_list:
          print(f"  {string}")

Answer 1

长度为 1-4 的字符串发生冲突的概率恰好为零。 CRC-32 是 32 位到 32 位的一对一映射。