SHA256-CDP：循环数字和投影（Cyclic Digit-sum Projection）

基于CDP结构分析框架的SHA-256 GPU加速彩虹表实现。

基于CDP论文（DOI：10.5281/zenodo.20627240）的研究成果，本仓库提供了CDP彩虹链表的完整、可工作实现，包含OpenCL构建内核和针对AMD RDNA4硬件的Vulkan计算查询/验证管线。

什么是CDP？

CDP（循环数字和投影）是SHA-256的一种结构分析框架，揭示了哈希函数输出分布中先前未记录过的数学性质。

核心发现：任何SHA-256输出的十六进制数字和 W(H)，当通过 f(w) = W(SHA256(str(w))) 迭代再哈希时，确定性地收敛到恰好 两个闭循环：

C1: 476 ↔ 438          (2-循环)
C2: 471 → 472 → 525 → 537 → 414 → 417 → 546 → 518 → 471  (8-循环)

这种循环结构，结合多分量指纹 F(H) = (W, Wvec₁₆, cycle_entry, W₂–W₅, max_nibble, min_nibble)，在受限输入空间上产生了 双射映射 —— 使得通过彩虹表实现O(1)原像查找成为可能，且缩减函数零碰撞。

已证明的关键性质：

• 定理5.1 —— 半字节补和不变性：对所有256个补码对，Σnibble(W₀) = 38
• 定理5.4 —— 遍历马尔可夫性质：π_B = 17.00%，与 K[i]、H₀ 及输入类别无关
• W(H₀) = 502 —— NIST初始化常数的可检测结构签名（高于平衡值22.2）
• 在所有测试输入空间上，1.67M输入范围内无碰撞双射

CDP 并未破解SHA-256。原像和碰撞抵抗力不受影响。参见论文第12节。

仓库结构

SHA256-CDP/
├── cdp_chain_builder.py   # 主入口 —— 构建、破解、查询CLI
├── cdp_query.comp         # Vulkan GLSL计算着色器（查询内核）
├── cdp_verify.comp        # Vulkan GLSL计算着色器（验证内核）
├── vulkan_query.py        # Vulkan Python引擎（ACO后端）
└── paper/
    └── cdp_v3.pdf         # CDP论文v3

要求

• Python 3.10+
• PyOpenCL：pip install pyopencl
• NumPy：pip install numpy
• Vulkan（推荐）：pip install vulkan + Vulkan SDK
• AMD RDNA2+ GPU（在RX 9070 XT / gfx1201上测试通过）

注意： Vulkan是获得正确查询性能所必需的。如果没有Vulkan，系统将回退到CPU多进程处理（速度显著降低）。OpenCL查询内核在gfx1201上存在已知的AMD PAL-LLVM优化器错误，使用-cl-fast-relaxed-math时会产生错误结果；Vulkan ACO后端没有此问题。

Windows用户： 将python.exe、clinfo.exe和explorer.exe添加到Windows Defender受控文件夹访问白名单，以防止表操作期间GPU内存访问被阻止。

安装

git clone https://github.com/JM00NJ/SHA256-CDP
cd SHA256-CDP
pip install pyopencl numpy vulkan

验证GPU检测：

python cdp_chain_builder.py --validate

用法

构建彩虹表

# 单表（小写8字符，chain_len=300,000）
python cdp_chain_builder.py --build --charset lower --length 8 --chain-len 300000 --output cdp_8.bin

# 多表（更高覆盖率）
# n=1: 66.7%  n=2: 88.9%  n=3: 96.3%  n=5: 99.3%
python cdp_chain_builder.py --build-multi 3 --prefix cdp_8_bin --length 8 --chain-len 300000

破解哈希

# 单个哈希
python cdp_chain_builder.py --crack <sha256_hash> \
  --tables cdp_8_bin_1.bin,cdp_8_bin_2.bin,cdp_8_bin_3.bin \
  --length 8 --chain-len 300000

# 哈希列表（批处理模式 —— 表只加载一次）
python cdp_chain_builder.py --crack-list hashes.txt \
  --tables cdp_8_bin_1.bin,cdp_8_bin_2.bin,cdp_8_bin_3.bin \
  --length 8 --chain-len 300000

端到端自测

python cdp_chain_builder.py --self-test --length 7

验证GPU输出

python cdp_chain_builder.py --validate
python cdp_chain_builder.py --validate-query <sha256_hash>

性能

在 AMD Radeon RX 9070 XT（gfx1201，32个CU）、Windows 11、驱动3679.0（PAL,LC）上测试：

7字符小写，3张表（96.3%覆盖率）：

• 表大小：3 × 0.7 MB
• 构建时间：约3 × 12秒
• 破解时间：每个哈希约43秒

内核模式：

• --mode ilp2 —— 每线程2条链，交错SHA256以实现ILP（默认，AMD RDNA上最快）
• --mode vec4 —— 每线程4条链，使用uint4算术
• --mode scalar —— 每线程1条链（基线）

技术说明

为什么查询用Vulkan？

Windows上OpenCL（gfx1201）使用的AMD PAL-LLVM编译器后端存在已知的优化器错误：可变起始循环（for step=pos; step<N）在启用-cl-fast-relaxed-math时会产生错误结果。变通方法（-O0）可恢复正确性，但吞吐量降低约3-4倍。Vulkan ACO后端是完全独立的编译器管线，没有此问题。查询和验证内核使用Vulkan；构建内核使用OpenCL（不受该错误影响）。

CDP双射缩减

标准PCG种子缩减函数使用来自 digest[0:2] 的64位熵。CDP单射缩减则基于完整指纹 (W, Wvec₁₆, max_nibble, min_nibble) 构建种子 —— 这些正是CDP双射定理中证明在 SHA256(X) 上具有单射性的相同分量。这保证了缩减函数本身不会产生链合并；剩余合并是生日悖论端点碰撞（每张表约33%，符合预期的66.7%覆盖率）。

二进制表格式

表使用紧凑的二进制格式（CDP1魔数，每条目39字节）—— 大约是JSON的3.4倍小。使用 --convert 转换现有的JSON表：

python cdp_chain_builder.py --convert table.json --output table.bin

字符集

许可协议

© 2026 Erenay Özkan (JM00NJ / Vesqer)

本项目采用 GNU Affero General Public License v3.0 (AGPL-v3) 协议，并附带 Commons Clause 条款。

根据Commons Clause条款，未经作者明确书面许可，您不得出售本软件或将其用作商业产品或服务的一部分。

开源使用、研究和非商业应用在AGPL-v3条款下允许 —— 修改版必须在相同许可下发布。

如需商业许可咨询：请访问 netacoding.com

完整条款见 LICENSE 文件。

参考资料

• 博客文章：https://netacoding.com/posts/cdp-sha256-structural-analysis/
• Erenay Özkan. CDP: 循环数字和投影 —— SHA-256输出分布、遍历池压力及输入类别指纹的结构分析. v3, 2026. DOI: 10.5281/zenodo.20627240
• P. Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off. CRYPTO 2003.
• M. Hellman. A Cryptanalytic Time-Memory Trade-Off. IEEE Trans. Inf. Theory, 1980.

由 JM00NJ 构建 —— netacoding.com