oritwoen/kangaroo

# Kangaroo [](https://crates.io/crates/kangaroo) [](https://crates.io/crates/kangaroo) [](LICENSE) [](https://deepwiki.com/oritwoen/kangaroo) GPU 加速的 Pollard's Kangaroo 算法，用于求解 secp256k1 上的椭圆曲线离散对数问题 (ECDLP)。 ## 功能 - 🖥️ **跨平台 GPU** — 通过 wgpu 支持 Vulkan (AMD, NVIDIA, Intel)、Metal (Apple Silicon)、DX12 (Windows) - 🦀 **纯 Rust + WGSL** — 无 CUDA 依赖，计算着色器在运行时编译 - ⚡ **Distinguished Points** — 带有自动调整 DP 位数的高效碰撞检测 - 🔄 **Negation map** — 通过带有环检测的 Y 奇偶校验定向漫步实现约 1.29 倍加速 - 🦘 **多组 Kangaroo** — tame、wild1、wild2 群组以提高碰撞概率 - 🎯 **模约束** — 如果 k ≡ R (mod M)，则可将搜索空间缩小 M 倍 - ⚙️ **自动校准** — GPU 调度时间和工作组大小在启动时进行调整 - 📊 **内置基准测试** — 使用 `--benchmark` 测试硬件，使用 `--save-benchmarks` 记录结果 - 📦 **数据提供器** — 可插拔的谜题源（集成 boha 用于 Bitcoin 谜题） - 💻 **CPU 后备方案** — 纯 CPU 求解器，用于测试和对比 ## 为什么做这个项目？ 大多数现有的 Kangaroo 实现（JeanLucPons/Kangaroo、RCKangaroo 等）仅通过 CUDA 支持 NVIDIA GPU。本实现使用 WebGPU/wgpu，可通过 Vulkan、Metal 和 DX12 提供跨平台的 GPU 计算。 ## 安装 ### Arch Linux (AUR) ``` paru -S kangaroo ``` ### Cargo ``` cargo install kangaroo ``` ### 从源码构建 ``` git clone https://github.com/oritwoen/kangaroo cd kangaroo cargo build --release ``` ### 包含 boha 提供器 ``` cargo build --release --features boha ``` ## 使用方法 ``` kangaroo --pubkey --start --range ``` ### 参数 | 参数 | 默认值 | 描述 | |----------|---------|-------------| | `-t, --target` | - | 数据提供器目标 (例如, `boha:b1000/135`) | | `-p, --pubkey` | - | 目标公钥 (压缩十六进制格式, 33 字节) | | `-s, --start` | 0 | 搜索范围的起点 (十六进制, 不含 0x 前缀) | | `-r, --range` | 32 | 以比特为单位的搜索范围 (密钥位于 [start, start + 2^range - 1] 范围内) | | `-d, --dp-bits` | auto | Distinguished point 比特数 | | `-k, --kangaroos` | auto | 并行 Kangaroo 数量 | | `--gpu` | 0 | GPU 设备索引 | | `--backend` | auto | GPU 后端: `auto`, `vulkan`, `dx12`, `metal`, `gl` | | `-o, --output` | - | 结果输出文件 | | `-q, --quiet` | false | 最少输出，仅打印找到的密钥 | | `--max-ops` | 0 | 最大操作次数 (0 = 无限制) | | `--cpu` | false | 使用 CPU 求解器代替 GPU | | `--json` | false | 以 JSON 格式输出基准测试结果 | | `--benchmark` | false | 运行基准测试套件 | | `--save-benchmarks` | false | 在使用 `--benchmark` 时将基准测试结果保存到 `BENCHMARKS.md` | | `--mod-step` | 1 | 模步长 M (十六进制): 仅搜索 k ≡ R (mod M) | | `--mod-start` | 0 | 模余数 R (十六进制): 0 ≤ R < M | | `--list-providers` | false | 列出提供器可用的谜题 | 必须提供 `--target` 或 `--pubkey` 参数。 ### 示例 **使用数据提供器 (boha):** ``` # 使用 boha 数据解题（自动：pubkey、起始值、范围） kangaroo --target boha:b1000/66 # 覆盖范围（搜索较小子集） kangaroo --target boha:b1000/66 --range 60 # 列出可用谜题 kangaroo --list-providers ``` **手动设置参数:** ``` kangaroo \ --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \ --start 8000000000 \ --range 40 ``` **带模约束 (k ≡ 37 mod 60):** ``` kangaroo \ --pubkey 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 \ --start 8000000000 \ --range 40 \ --mod-step 3c \ --mod-start 25 ``` 这会将搜索空间缩小约 60 倍。当已知部分密钥结构时（例如，使用可预测步长模式生成的密钥），此功能非常有用。 ## 工作原理 Pollard's Kangaroo 算法可以在 O(√n) 的时间内求解离散对数问题，其中 n 是搜索范围。其工作原理如下： 1. **Tame kangaroo（驯袋鼠）** 从一个已知点出发并进行随机跳跃 2. **Wild kangaroo（野袋鼠）** 从目标公钥出发并进行相同类型的跳跃 3. 当 wild kangaroo 和 tame kangaroo 落在同一个点上（发生碰撞）时，我们就可以计算出私钥 **Distinguished Points (DP) 优化：** 并非存储所有访问过的点，我们只存储那些 x 坐标具有特定位数的前导零的点。这在仍然允许碰撞检测的同时，极大地减少了内存使用。 ## 性能 预期操作数：约 2^(range_bits/2) 运行 `kangaroo --benchmark` 可在不触碰文件的情况下测试你的硬件。使用 `kangaroo --benchmark --save-benchmarks` 来更新 [BENCHMARKS.md](BENCHMARKS.md)。 ## 使用场景 | 使用场景 | 示例 | |----------|---------| | 已解码部分密钥 | 谜题给出了约 240 位，需要找到剩余的约 16 位 | | 密钥在已知范围内 | 已知密钥在 X 和 Y 之间 | | 验证近似解 | 有了候选答案，在其周围 ±N 位范围内搜索 | **不适用于：** - 完整的 256 位密钥搜索（数学上不可能实现） - BIP39 助记词暴力破解（请改用字典攻击） - 没有部分密钥信息的谜题 ## 库的用法 ``` use kangaroo::{KangarooSolver, GpuContext, GpuBackend, parse_pubkey, parse_hex_u256, verify_key}; fn main() -> anyhow::Result<()> { let pubkey = parse_pubkey("03...")?; let start = parse_hex_u256("8000000000")?; let ctx = pollster::block_on(GpuContext::new(0, GpuBackend::Auto))?; let mut solver = KangarooSolver::new( ctx, pubkey.clone(), start, 40, // range_bits 12, // dp_bits 1024, // num_kangaroos )?; loop { if let Some(key) = solver.step()? { if verify_key(&key, &pubkey) { println!("Found: {}", hex::encode(&key)); break; } } } Ok(()) } ``` ## 数据提供器 Kangaroo 支持用于谜题源的外部数据提供器。提供器负责提供 pubkey、密钥范围以及其他谜题元数据。 ### boha (可选特性) [boha](https://github.com/oritwoen/boha) 提供加密谜题数据，包括 Bitcoin Puzzle Transaction (b1000)。 构建时启用 boha 支持： ``` cargo build --release --features boha ``` 用法： ``` # 解答特定谜题 kangaroo --target boha:b1000/66 # 列出可解谜题（未解答且已知 pubkey） kangaroo --list-providers ``` 提供器会验证范围的覆盖——你不能在谜题的密钥范围之外进行搜索。 ## 架构 ``` src/ ├── main.rs # CLI entry point ├── lib.rs # Library entry + Args + run() ├── solver.rs # GPU solver coordination ├── cli.rs # CLI utilities (tracing, progress bar) ├── benchmark.rs # Built-in benchmark suite ├── modular.rs # Modular constraint transformation ├── math.rs # 256-bit arithmetic, DP mask generation ├── convert.rs # Limb/byte conversions for GPU↔CPU ├── provider/ │ ├── mod.rs # Provider system interface │ └── boha.rs # boha provider (feature-gated) ├── cpu/ │ ├── cpu_solver.rs # Pure CPU solver (testing/comparison) │ ├── dp_table.rs # Distinguished Points collision detection │ └── init.rs # Kangaroo initialization + jump tables ├── crypto/ │ └── mod.rs # k256/secp256k1 wrappers ├── gpu/ │ ├── pipeline.rs # Compute pipeline setup │ └── buffers.rs # GPU buffer management ├── gpu_crypto/ │ ├── context.rs # GPU context + backend selection │ └── shaders/ # WGSL shader library │ ├── field.wgsl # secp256k1 field arithmetic │ └── curve.wgsl # Jacobian point operations └── shaders/ └── kangaroo_affine.wgsl # Main Kangaroo compute shader ``` ## 环境要求 - Rust 1.70+ - 支持 Vulkan 的 GPU (AMD, NVIDIA, Intel) 或 Metal (macOS) - 在使用 AMD RADV 的 Linux 系统上，需要 Mesa 25.x 或更高版本（旧版 Mesa 可能会在着色器循环中的 WGSL 动态索引时崩溃） - 已安装 GPU 驱动程序 ## 许可证 MIT 许可证 - 详见 [LICENSE](LICENSE)。 ## 相关项目 - [JeanLucPons/Kangaroo](https://github.com/JeanLucPons/Kangaroo) - CUDA 实现 (仅限 NVIDIA) - [RCKangaroo](https://github.com/RetiredC/RCKangaroo) - CUDA 实现 (仅限 NVIDIA) - [boha](https://github.com/oritwoen/boha) - 加密谜题和悬赏数据库

标签：CPU回退, CUDA替代方案, DirectX 12, Distinguished Points, DX12, ECDLP求解器, Metal, Pollard's Kangaroo算法, Rust, secp256k1, Vulkan, WebGPU, wgpu, WGSL, 信息收集, 加密货币安全, 区块链安全, 可视化界面, 安全审计工具, 密码学, 并行计算, 异构计算, 性能基准测试, 手动系统调用, 数值计算, 杰出点检测, 椭圆曲线密码学, 椭圆曲线离散对数问题, 比特币谜题, 求反映射, 网络流量审计, 计算着色器, 跨平台GPU计算, 通知系统