Caume/HerraduraKEx
GitHub: Caume/HerraduraKEx
基于 FSCX 按位运算原语构建的实验性密码套件，涵盖经典 Diffie-Hellman 密钥交换、El Gamal 加密、Schnorr 签名以及后量子 Ring-LWR 和基于编码的 Stern 签名方案，支持从 Arduino 到桌面端的六种平台实现。
Stars: 6 | Forks: 1
# Herradura 密码套件 (v1.5.20)
Herradura 密码套件实现了基于 FSCX (Full Surroundings Cyclic XOR) 原语、GF(2^n)* 上的 Diffie-Hellman 密钥交换以及后量子 Ring-LWR 密钥交换构建的密码协议。
# FSCX — 核心原语
设 $A$, $B$, $C$ 为大小为 $P$ 的比特串，其中 $A_i$ 是第 $i$ 位（从左到右），且 $i \in \{0,\ldots,P-1\}$。设 $\oplus$ 表示按位异或，设 $\circlearrowleft$, $\circlearrowright$ 分别表示 1 位的循环左移和循环右移。
$$\text{FSCX}(A, B) = A \oplus B \oplus \circlearrowleft\!A \oplus \circlearrowleft\!B \oplus \circlearrowright\!A \oplus \circlearrowright\!B$$
等价地，定义线性算子 $M = I \oplus \text{ROL} \oplus \text{ROR}$：
$$\text{FSCX}(A, B) = M \cdot (A \oplus B)$$
**FSCX_REVOLVE(A, B, n)** 保持 $B$ 不变并迭代 FSCX $n$ 次：
$$\text{FSCX}\textunderscore\text{REVOLVE}(A, B, n) = \text{FSCX}^{\circ n}(A, B)$$
对于大小为 $P = 2^k$ 的比特串，轨道周期始终为 $P$ 或 $P/2$，因此对于所有 $A$, $B$ 都有 $\text{FSCX}\textunderscore\text{REVOLVE}(A, B, P) = A$。
# HKEX-GF — GF(2^n)* 上的密钥交换
HKEX-GF 是基于乘法群 $\mathbb{GF}(2^n)^*$ 的标准 Diffie-Hellman 密钥交换。
1. **设置。** 双方约定一个 $n$ 次不可约多项式 $p(x)$ 和生成元 $g = 3$。
2. **密钥生成。** Alice 生成一个私有标量 $a$；Bob 生成 $b$。
3. **公开值。** Alice 公布 $C = g^a$；Bob 公布 $C_2 = g^b$（所有算术运算均在 $\mathbb{GF}(2^n)$ 中进行）。
4. **共享密钥。** Alice 计算 $\mathit{sk} = C_2^a = g^{ab}$；Bob 计算 $\mathit{sk} = C^b = g^{ba}$。根据域乘法的交换律，$g^{ab} = g^{ba}$。
| $n$ | 本原多项式 | 经典安全性 |
|-----|---------------------|-------------------|
| 32 | $x^{32}+x^{22}+x^2+x+1$ (`0x00400007`) | 仅用于演示 |
| 64 | $x^{64}+x^4+x^3+x+1$ (`0x1B`) | ~40 位 |
| 128 | $x^{128}+x^7+x^2+x+1$ (`0x87`) | ~60–80 位 |
| 256 | $x^{256}+x^{10}+x^5+x^2+1$ (`0x425`) | ~128 位（推荐） |
# Herradura 密码套件
该套件在 HKEX-GF、FSCX_REVOLVE 和 v1.5.0 NL-FSCX 扩展的基础上构建协议：
**经典协议 (v1.4.0)：**
1. **HKEX-GF** — 密钥交换（$\mathbb{GF}(2^n)^*$ 上的 DH，如上所述）
2. **HSKE** — 对称加密：$E = \text{FSCX}\textunderscore\text{REVOLVE}(P, \mathit{key}, i)$；使用 $D = \text{FSCX}\textunderscore\text{REVOLVE}(E, \mathit{key}, r)$ 解密
3. **HPKS** — Schnorr 风格的公钥签名：$R = g^k$；$e = \text{FSCX}\textunderscore\text{REVOLVE}(R, P, i)$；$s = (k - a \cdot e) \bmod (2^n - 1)$；验证 $g^s \cdot C^e = R$
4. **HPKE** — El Gamal 公钥加密：$R = g^r$；$\mathit{enc}\textunderscore\mathit{key} = C^r$；$E = \text{FSCX}\textunderscore\text{REVOLVE}(P, \mathit{enc}\textunderscore\mathit{key}, i)$；Alice 使用 $\mathit{dec}\textunderscore\mathit{key} = R^a$ 解密
**后量子 / NL 强化 (v1.5.0)：**
5. **HSKE-NL-A1** — 使用 NL-FSCX v1 的计数器模式：$\mathit{ks} = \text{NL-FSCX-revolve-v1}(K, K \oplus \mathit{ctr}, i)$；$E = P \oplus \mathit{ks}$
6. **HSKE-NL-A2** — 使用 NL-FSCX v2 的 revolve 模式：$E = \text{NL-FSCX-revolve-v2}(P, K, r)$；$D = \text{NL-FSCX-revolve-v2-inv}(E, K, r)$
7. **HKEX-RNL** — Ring-LWR 密钥交换（推测具有抗量子性）：在 $\mathbb{Z}_q[x]/(x^n+1)$ 中共享 $m_\text{blind}$；双方推导出 $C = \text{round}_p(m_\text{blind} \cdot s)$；协商 $K = \text{round}_{pp}(s \cdot \text{lift}(C_\text{other}))$
8. **HPKS-NL** — NL 强化的 Schnorr：$e = \text{NL-FSCX-revolve-v1}(R, P, i)$
9. **HPKE-NL** — NL 强化的 El Gamal：$E = \text{NL-FSCX-revolve-v2}(P, \mathit{enc}\textunderscore\mathit{key}, i)$；$D = \text{NL-FSCX-revolve-v2-inv}(E, \mathit{dec}\textunderscore\mathit{key}, i)$
**基于编码的 PQC (v1.5.18)：**
10. **HPKS-Stern-F** — Fiat-Shamir Stern ZKP 签名（EUF-CMA ≤ SD($n$,$t$) + NL-FSCX v1 PRF）：提交 $(c_0, c_1, c_2)$；通过 NL-FSCX 哈希生成挑战 $b \in \{0,1,2\}$；响应公开置换后的 $r$，$y = e \oplus r$ 或置换 $\pi$。参数 (C/Go/Python)：$N = n = 256$，$t = 16$，轮数 $= 32$。Assembly/Arduino：$N = 32$，$t = 2$，轮数 $= 4$。
11. **HPKE-Stern-F** — Niederreiter KEM：$\mathit{ct} = H \cdot e'^T$；$K = \text{hash}(\mathit{seed}, e')$。生产环境的解封装需要 QC-MDPC 伴随式解码器；演示使用已知的 $e'$。
实现提供了 C、Go、Python、ARM Thumb-2 汇编、NASM i386 汇编和 Arduino 版本（所有六个目标平台均为 v1.5.19 版本）。
# 构建与运行说明
## C
```
# 完整加密套件 (所有协议：classical、NL/PQC、Stern-F code-based)
gcc -O2 -o "Herradura cryptographic suite_c" "Herradura cryptographic suite.c"
./"Herradura cryptographic suite_c"
# 安全性与性能测试 (位于 CryptosuiteTests/ 目录)
gcc -O2 -o CryptosuiteTests/Herradura_tests_c CryptosuiteTests/Herradura_tests.c
./CryptosuiteTests/Herradura_tests_c
```
## Go
```
# 完整加密套件
go run "Herradura cryptographic suite.go"
# 安全性与性能测试 (位于 CryptosuiteTests/ 目录)
cd CryptosuiteTests && go run Herradura_tests.go
```
## Python
```
# 完整加密套件
python3 "Herradura cryptographic suite.py"
# 安全性与性能测试 (位于 CryptosuiteTests/ 目录)
python3 CryptosuiteTests/Herradura_tests.py
```
## Assembly
```
# ARM Linux — 完整套件 + 测试 (32-bit Thumb；classical + NL/PQC + Stern-F 协议)
arm-linux-gnueabi-gcc -o "Herradura cryptographic suite_arm" "Herradura cryptographic suite.s"
arm-linux-gnueabi-gcc -o CryptosuiteTests/Herradura_tests_arm CryptosuiteTests/Herradura_tests.s
qemu-arm -L /usr/arm-linux-gnueabi "./Herradura cryptographic suite_arm"
qemu-arm -L /usr/arm-linux-gnueabi ./CryptosuiteTests/Herradura_tests_arm
# NASM i386 — 完整套件 + 测试 (纯 Linux syscalls，无 libc)
# 依赖: nasm, x86_64-linux-gnu-ld (或支持 elf_i386 的 ld), qemu-i386
nasm -f elf32 "Herradura cryptographic suite.asm" -o suite32.o
nasm -f elf32 CryptosuiteTests/Herradura_tests.asm -o tests32.o
x86_64-linux-gnu-ld -m elf_i386 -o "Herradura cryptographic suite_i386" suite32.o
x86_64-linux-gnu-ld -m elf_i386 -o CryptosuiteTests/Herradura_tests_i386 tests32.o
qemu-i386 "./Herradura cryptographic suite_i386"
qemu-i386 ./CryptosuiteTests/Herradura_tests_i386
# 在原生 x86/x86_64 Linux 主机上，二进制文件无需 qemu-i386 即可直接运行
```
## Arduino
`.ino` 文件需要安装了 AVR 开发板包的 Arduino IDE 或 `arduino-cli`。在 IDE 中打开并上传至带有 9600 波特率串口监视器的开发板，或者：
```
# 仅编译检查 (需要 arduino-cli 及 arduino:avr 开发板包)
arduino-cli compile --fqbn arduino:avr:uno "Herradura cryptographic suite.ino"
arduino-cli compile --fqbn arduino:avr:uno CryptosuiteTests/Herradura_tests.ino
```
# 性能 (v1.5.18, Orange Pi 5 — RK3588, Cortex-A76 @ 2.4 GHz)
来自 `CryptosuiteTests/Herradura_tests.{c,go,py}` 且带有 `-t 3.0` 参数的基准测试。
GF/NL/Stern 基准测试使用 32 位参数；FSCX/HSKE 基准测试使用 256 位参数。
## C (gcc -O2)
| 基准测试 | 吞吐量 |
|-----------|-----------|
| FSCX 单步 (256-bit) | 10.4 M ops/sec |
| gf_pow 吞吐量 (32-bit) | 19,841 M ops/sec |
| HKEX-GF 完整握手 (32-bit) | 1,968 M ops/sec |
| HSKE 往返 (256-bit) | 40.9 K ops/sec |
| HPKE El Gamal 往返 (32-bit) | 2,004 M ops/sec |
| NL-FSCX v1 revolve (32-bit, n/4 步) | 1,968 M ops/sec |
| NL-FSCX v2 enc+dec (32-bit) | 1,941 M ops/sec |
| HSKE-NL-A1 计数器模式 (32-bit) | 10.2 M ops/sec |
| HSKE-NL-A2 revolve 模式 (32-bit) | 15.2 M ops/sec |
| HKEX-RNL 完整握手 (n=32) | 77.3 K ops/sec |
| HPKS-Stern-F sign+verify (N=256, t=16, rounds=4) | 113 ops/sec |
## Go (go run)
| 基准测试 | 64-bit | 128-bit | 256-bit |
|-----------|--------|---------|---------|
| FSCX 单步 | 146 K | 121 K | 110 K ops/sec |
| HKEX-GF 完整握手 (32-bit) | 270 ops/sec | — | — |
| HSKE 往返 | 2.15 K | 1.03 K | 413 ops/sec |
| NL-FSCX v1 revolve (n/4 步) | 6.34 K | 2.62 K | 1.21 K ops/sec |
| NL-FSCX v2 enc+dec | 213 ops/sec | — | — |
| HSKE-NL-A1 计数器模式 | 5.65 K | 2.66 K | 1.18 K ops/sec |
| HSKE-NL-A2 revolve 模式 (64-bit) | 220 ops/sec | — | — |
| HKEX-RNL 完整握手 | 10.0 K (n=32) | 4.79 K (n=64) | — |
| HPKS-Stern-F sign+verify (N=256, rounds=4) | 1.3 ops/sec | — | — |
## Python 3
| 基准测试 | 64-bit | 128-bit | 256-bit |
|-----------|--------|---------|---------|
| FSCX 单步 | 157 K | 152 K | 155 K ops/sec |
| HKEX-GF 完整握手 (32-bit) | 491 ops/sec | — | — |
| HSKE 往返 | 2.36 K | 1.18 K | 601 ops/sec |
| NL-FSCX v1 revolve (n/4 步) | 7.29 K | 3.63 K | 1.85 K ops/sec |
| NL-FSCX v2 enc+dec | 296 ops/sec | — | — |
| HSKE-NL-A1 计数器模式 | 7.01 K | 3.63 K | 1.82 K ops/sec |
| HSKE-NL-A2 revolve 模式 (64-bit) | 295 ops/sec | — | — |
| HKEX-RNL 完整握手 | 1.05 K (n=32) | 510 (n=64) | — |
| HPKS-Stern-F sign+verify (N=32, rounds=4) | 75.7 ops/sec | — | — |
# 仓库结构
```
Herradura cryptographic suite.{c,go,py,s,asm,ino} — protocol suite implementations
CryptosuiteTests/
Herradura_tests.{c,go,py,s,asm,ino} — security tests & benchmarks
go.mod
SecurityProofsCode/ — formal break proofs (Python)
SecurityProofs.md — algebraic analysis (incl. §11 NL/PQC, §12 quantum, §11.8.4 Stern-F)
```
# 许可证
基于 GPL v3.0 和 MIT 双重许可。用户可选择其中一种。
OAHR
标签：Cryptography, Crypto Suite, Diffie-Hellman, DNS 反向解析, FSCX, GF(2^n), Herradura, Key Exchange, meg, Ring-LWR, XOR, 位运算, 信息安全, 加密套件, 加密算法, 后量子密码学, 密码学, 密码学原语, 密钥交换, 手动系统调用, 抗量子加密, 数学算法, 日志审计, 有限域, 环形纠错学习问题, 网络安全, 网络安全, 软件库, 逆向工具, 隐私保护, 隐私保护