paim-creater/prng
GitHub: paim-creater/prng
基于代数度驱动方法设计的高性能伪随机数生成器，提供密码学安全与非密码学两种方案，以远超 ChaCha20 的吞吐量满足从安全加密到科学计算的随机数需求。
Stars: 1 | Forks: 0
# Bolt & Tempest：代数度驱动的 PRNG 设计
[](LICENSE)
[](src/)
[](https://github.com/paim-creater/prng/actions/workflows/benchmark.yml)
[](https://github.com/rust-cc/awesome-cryptography-rust)
两款通过**代数度驱动方法论**设计的高性能伪随机数生成器 —— 首先以 GF(2) 上的代数度 (deg) 为目标，然后反向工程出最优的原语组合。
| 平台 | 状态 |
|----------|--------|
| x86-64 (GCC/Clang/MSVC) | ✅ 完全支持 |
| ARM64 (Apple M / Cortex-A) | ✅ 完全支持 |
| RISC-V 64 | ✅ 完全支持 |
| MSVC | ✅ 通过 `src/platform.h` 支持 |
## 概览
| 算法 | 类型 | 吞吐量 | 安全性 | 测试状态 |
|-----------|------|-----------|----------|-------------|
| **ADC-Bolt** | 非密码学 PRNG | **70.3 Gbit/s** (12.1× ChaCha20) | deg=2 (非密码学) | NIST ✅ TestU01 ✅ PractRand ✅ |
| **Tempest v3** | CSPRNG | **17.7 Gbit/s** (3.0× ChaCha20) | deg≥256 (已证明), DP(1)≤2⁻³ (已证明) | NIST ✅ TestU01 ✅ PractRand 1 TiB ✅ |
| **Tempest v3 AVX-512** | CSPRNG (SIMD) | **65.4 Gbit/s** (11.3× ChaCha20) | deg≥256 | NIST ✅ TestU01 ✅ PractRand ✅ |
## 快速开始
```
git clone https://github.com/paim-creater/prng.git && cd prng
make && make bench
```
预期输出：
```
============================================
Bolt & Tempest — Throughput Benchmark
============================================
ADC-Bolt: 62753 Mbit/s (62.8 Gbit/s)
Tempest v3: 17700 Mbit/s (17.7 Gbit/s) [provable degree, DP bound]
============================================
```
### 直接使用（单头文件）
复制一个文件即可 —— 无需构建系统：
```
#include "prng_single_header.h"
// Non-crypto: games, Monte Carlo, ML
adcbolt_state rng;
adcbolt_seed(&rng, 42);
double x = adcbolt_double(&rng);
int dice = adcbolt_range(&rng, 1, 6);
// Cryptographic: keys, tokens, authentication
tempest_state csprng;
tempest_init(&csprng, key, nonce);
uint64_t token = tempest_u64(&csprng);
```
### Python
```
import prng
rng = prng.ADC_Bolt(seed=42)
print(rng.randint(1, 6))
csprng = prng.Tempest(key=bytes(32), nonce=bytes(16))
print(csprng.hex(16))
```
## 设计方法论
传统的 PRNG 设计遵循：*选择结构 → 测试 → 增加轮次*。我们反其道而行之：
**首先确定目标代数度 (deg)，然后反向工程原语。**
关键指标是 **deg-per-op** —— 每次非线性操作（AND 门、ADD 进位或 MULX）产生的代数度收益。ADC-Bolt 使用 ADD+ADD（deg-per-op = 1.0，2c 延迟）。Tempest v3 使用 AND 混合级联（每 4 阶段链 deg ×16，4c 延迟）。
### ADC-Bolt (70.3 Gbit/s)
用**进位链双加法**（ADD+ADD，2 周期延迟）替代 MULX 乘法（3 周期延迟）。具有相同的代数度 (deg=2)，更短的关键路径，吞吐量比 MULX 基准**高出 52%**。
```
// Core nonlinearity: carry-chain provides deg=2 at 2c latency
z = (z + u) + v; // majority carry = quadratic over GF(2)
```
### Tempest v3 (纯 GF(2)，可证明的度数增长)
**代数保证：** 2 轮后，输出 deg ≥ 256，XL 复杂度 ≥ 2³⁴⁵（启发式）。所有非线性均通过 AND（GF(2) 乘法）实现 —— 移除了整数 ADD/CMUL。
1. **纯 GF(2) 轮函数** —— 仅包含 XOR、ROTL、AND 操作（代数上可分析）
2. **4 阶段 AND 混合级联** —— 每个阶段使代数度翻倍（由归纳法证明）
3. **跨字 XOR-ROT 扩散** —— 基于快照，所有 4 个操作并行
4. **双输出** —— 通过状态置换每轮输出 2×64 位
## 统计测试
两种算法均已通过**所有**应用的统计测试：
| 测试套件 | 测试数 | ADC-Bolt | Tempest v3 |
|------------|-------|----------|-------------------|
| NIST SP 800-22 | 15 个系列 | ✅ 15/15 | ✅ 15/15 |
| TestU01 SmallCrush | 15 | ✅ 通过 | ✅ 通过 |
| TestU01 Rabbit | 40 | ✅ 通过 | ✅ 通过 |
| TestU01 Alphabit | 17 | ✅ 通过 | ✅ 通过 |
| TestU01 BigCrush | 160 | ✅ 通过 (1小时39分) | ✅ 通过 (3小时20分) |
| TestU01 Crush | 144 | ✅ 通过 (12小时46分) | ✅ 通过 (23分) |
| PractRand | — | ✅ 1 TiB, 354 组 | ✅ 1 TiB, 354 组, 0 异常 |
完整测试日志：[`results/`](results/)
## 性能
### 参考平台 (AMD Zen 4)
| 算法 | 轮次 | 时间 | 吞吐量 |
|-----------|--------|------|------------|
| ADC-Bolt | 2×10⁸ | 182 ms | 70.3 Gbit/s |
| Tempest v3 | 5×10⁷ | 325 ms | 17.7 Gbit/s |
| ChaCha20 (标量) | 2×10⁸ | — | 5.8 Gbit/s |
### 各架构预测性能
| CPU | ADC-Bolt | Tempest v3 | 关键因素 |
|-----|----------|------------|------------|
| **Apple M4 Pro/Max** 🥇 | 85–95 Gbit/s | 16–18 Gbit/s | UMULL=1c (=ADD 延迟) |
| AMD Zen 5 | 75–82 Gbit/s | 13–15 Gbit/s | IPC 比 Zen 4 高 15% |
| **AMD Zen 4** | **70.3** ✅ | **17.7** ✅ | 参考平台 |
| Intel Arrow Lake | 75–85 Gbit/s | 12–14 Gbit/s | 更高时钟频率 (5.7 GHz) |
| Intel Raptor Lake | 60–70 Gbit/s | 10–12 Gbit/s | 上一代 |
| ARM Cortex-X4 | 55–65 Gbit/s | 10–13 Gbit/s | 移动端散热限制 |
### 在您的硬件上复现
```
git clone https://github.com/paim-creater/prng.git && cd prng
gcc -O3 -march=native -o benchmark benchmark.c src/adcbolt.c src/tempest_v3.c -I.
./benchmark
```
然后[提交您的结果](https://github.com/paim-creater/prng/issues/new?template=benchmark_result.md)到社区数据库！
| 贡献者 | CPU | ADC-Bolt | Tempest v3 |
|-------------|-----|----------|------------|
| [提交您的结果 →](https://github.com/paim-creater/prng/issues/new?template=benchmark_result.md) | — | — | — |
| [@paim-creater](https://github.com/paim-creater) | Ryzen 9 8940HX (Zen 4) | 70.3 Gbit/s | 17.7 Gbit/s |
| [GitHub Actions CI](https://github.com/paim-creater/prng/actions) | Xeon E5 v4 | 8.6 Gbit/s | 4.6 Gbit/s |
## 仓库结构
```
.
├── README.md
├── LICENSE ← MIT
├── CONTRIBUTING.md
├── CMakeLists.txt ← CMake build (MSVC / Xcode / Make / Ninja)
├── Makefile ← One-click: make && make bench
├── prng_single_header.h ← Drop-in: copy one file, #include it
├── prng.py ← Python bindings
├── benchmark.c ← Throughput benchmark
├── test_bolt.c ← ADC-Bolt self-test
├── test_tempest.c ← Tempest v3 self-test
├── examples/
│ ├── dice_roll.c ← Game dice roller
│ ├── generate_token.c ← Secure API token
│ └── monte_carlo.c ← π via Monte Carlo
├── src/
│ ├── platform.h ← Auto-detects x86-64 / ARM64 / RISC-V / MSVC
│ ├── adcbolt.h ← ADC-Bolt API
│ ├── adcbolt.c ← ADC-Bolt implementation
│ ├── tempest_v3.h ← Tempest v3 API
│ ├── tempest_v3.c ← Tempest v3 implementation
│ ├── tempest_openssl.c ← OpenSSL 3.x Provider (EVP_RAND)
│ ├── tempest_cuda_kernel.cu ← CUDA GPU RNG kernel
│ ├── bitgen_tempest.c ← NumPy BitGenerator C extension
│ └── _tempest_numpy.c ← NumPy bulk fill acceleration
├── tempest_rng.py ← ⭐ NumPy: random/normal/integers/shuffle (11 Gbit/s)
├── tempest_cuda.py ← GPU: CUDA-accelerated Monte Carlo
├── setup_bitgen.py ← Build script for NumPy BitGenerator
├── tempest-rs/ ← ⭐ Rust crate: RngCore + CryptoRng
│ ├── Cargo.toml
│ ├── src/lib.rs
│ └── examples/pi_estimation.rs
├── results/ ← Full test logs
│ ├── nist_tempest_v3_report.txt
│ ├── smallcrush_tempest_v3.log
│ ├── rabbit_tempest_v3.log
│ ├── alphabit_tempest_v3.log
│ ├── bigcrush_tempest_v3.log
│ ├── crush_tempest_v3.log
│ ├── practrand_tempest_v3_1tb.log
│ └── (adcbolt counterparts)
└── .github/
├── workflows/benchmark.yml ← CI benchmark
└── ISSUE_TEMPLATE/
```
## 快速验证
任何人都可以在一秒钟内验证实现是否正确：
```
#include "src/kat_tempest.h"
tempest_state s;
if (tempest_kat_verify(&s) == 0) {
printf("Tempest v3: correct\n");
}
```
这会运行一个已知答案测试（key={1,2,3,4}, nonce={5,6}）并与参考输出进行核对。无需外部依赖，无需构建系统。
完整测试套件：
```
gcc -O3 -o test_self test_tempest.c src/tempest_v3.c -I.
./test_self
```
## 统计测试结果
| 套件 | 测试数 | 结果 |
|-------|-------|--------|
| NIST SP 800-22 | 15/15 | ✅ 通过 |
| TestU01 SmallCrush | 15 | ✅ 通过 |
| TestU01 Rabbit | 40 | ✅ 通过 |
| TestU01 Alphabit | 17 | ✅ 通过 |
| TestU01 Crush | 144 | ✅ 通过 |
| TestU01 BigCrush | 160 | ✅ 通过 |
| PractRand | ≥354 (1 TiB) | ✅ 通过 |
## 安全性
Tempest v3 提供了代数度保证以及经验上有界的差分/线性抗性。
安全性指标分为**已证明**（数学推导）、**启发式**（依赖于标准假设）或**经验性**（通过实验测量）三类。
### 纯 GF(2) 轮函数（代数上可分析）
- **代数度**：r 轮后 deg ≥ 16^r（AND 度数倍增归纳法）。r = 2 轮后：deg ≥ 256 → XL 复杂度 ≥ 2³⁴⁵（Courtois-Pieprzyk 启发式）
- **每比特 AND DP**：= 1/2（GF(2) 代数 —— AND 即 GF(2) 乘法）
- **单轮 DP**：DP(1) ≤ 2^{-3}（已证明下界，a₁ ≥ 3 个活跃的 AND 字操作）
- **多轮 DP**：DP(r) ≤ 2^{-3r}（在 Markov 密码假设下）
- **线性偏差**：ε^{(2)} ≤ 2^{-22}（经验值，2×10¹⁰ 个样本）
### 经验性（标准密码学实践 —— 类似于 AES S 盒 DP）
- **AND 混合扩散**：每级联覆盖 1→3→9→27→64 位（针对旋转常数 (31,53),(17,43),(7,23),(5,19) 测量）
- **迭代 DP**：经验上与 2¹²⁸ 的安全边界一致
### 设计基本原理
- **纯 GF(2) 操作**：所有非线性均通过 AND（GF(2) 乘法）实现
- **Weyl 每轮密钥**：抗滑动攻击（依赖于轮次的混合）
- **双输出**：通过状态置换每轮输出 2×64 位
完整的安全分析请参见 [DESIGN.md](DESIGN.md)。
**NIST SP 800-90A/90B**：Tempest v3 被打包为一个完整的 DRBG（实例化/生成/再种子化/取消实例化），并带有符合 SP 800-90B 的熵源（RCT/APT 健康度测试 + Tempest 调节）。12 项工程验证测试通过。
**生态系统集成**：NumPy (tempest_rng.py, 11 Gbit/s)、OpenSSL 3.x Provider (TEMPEST-DRBG)、Rust rand crate (tempest-rs, RngCore + CryptoRng)、CUDA GPU kernel (tempest_cuda_kernel.cu, 并行蒙特卡洛)。
## 构建选项
### 使用 Make (Linux / macOS / MSYS2)
```
make # compile + run self-tests
make test # build and run both test programs
make benchmark # build benchmark binary
make bench # build and run benchmark
make clean # remove binaries
```
### CMake (包含 MSVC 的所有平台)
```
mkdir build && cd build
cmake ..
cmake --build .
ctest # run test_all
./benchmark # run benchmark
```
### 手动编译
```
# ADC-Bolt
gcc -O3 -march=native -o test_bolt test_bolt.c src/adcbolt.c -I.
# Tempest v3
gcc -O3 -march=native -o test_tempest test_tempest.c src/tempest_v3.c -I.
# Benchmark
gcc -O3 -march=native -o benchmark benchmark.c src/adcbolt.c src/tempest_v3.c -I.
```
## 对比
### 标量 CSPRNG
| 算法 | 吞吐量 | 安全性 | 验证 |
|-----------|-----------|----------|-------------|
| **Tempest v3** | **17.7 Gbit/s** | deg≥256 (已证明), DP(1)≤2⁻³ (已证明) | TestU01 全部 5 个级别, PractRand 1 TiB |
| ChaCha20 | 5.8 Gbit/s | 2²⁵⁶ | 15 余年的密码分析 |
| AES-CTR DRBG (AES-NI) | 2–6 Gbit/s | 2²⁵⁶ | NIST 标准 |
### 非密码学 PRNG
| 算法 | 吞吐量 | 状态更新 | TestU01 BigCrush |
|-----------|-----------|-------------|-----------------|
| RomuTrio | ~213 Gbit/s | 线性 | ❌ 在 2¹⁹ 字节后失败 |
| wyrand | ~178 Gbit/s | 线性 | 部分通过 |
| xoroshiro128+ | ~90 Gbit/s | 线性 | ❌ 存在部分失败 |
| **ADC-Bolt** | **70.3 Gbit/s** | **非线性 (deg=2)** | ✅ 完全通过 |
## 引用
```
@misc{bolt_tempest_2026,
title = {Tempest v3 \& ADC-Bolt:
Algebraic Degree-Driven PRNG Design},
author = {Tian Yuezhou},
year = {2026},
url = {https://github.com/paim-creater/prng},
}
```
## 许可证
MIT —— 学术、商业和个人用途均免费。请参见 [LICENSE](LICENSE)。
标签：Bash脚本, C99, CSPRNG, SIMD, Vectored Exception Handling, 伪随机数生成器, 可视化界面, 客户端加密, 密码学, 手动系统调用, 逆向工具