HerraduraKEx 加密套件：FSCX 原语与后量子 Ring-LWR 密钥交换

The Herradura Cryptographic Suite implements cryptographic protocols built on the FSCX (Full Surroundings Cyclic XOR) primitive, Diffie-Hellman key exchange over GF(2^n)*, and a post-quantum Ring-LWR key exchange. In short: it gives two parties a way to agree on a shared secret over an insecure channel, then use that secret to encrypt, sign, and verify messages — with both classical (pre-quantum) and post-quantum variants of each — implemented from scratch across six languages so the same protocols can be read, taught, and cross-checked in whichever one is most familiar.

New to cryptography, or just to this repo? Start with docs/CRYPTOGRAPHY_BASICS.md (no prior background assumed), then docs/INTRODUCTION.md (plain-language walkthrough of every concept below), then docs/TUTORIAL.md (copy-pasteable API recipes per language). The rest of this file is a compact technical reference, not a tutorial.

External tools and agents integrating HerraduraKEx as a dependency should start with llms.txt — a condensed, token-efficient API reference (function signatures, CLI subcommands, protocol identifiers) with pointers to the detailed docs.

FSCX — The Core Primitive

FSCX is the mixing operation every protocol in this suite is built from: it takes two equal-size bitstrings and combines them by XOR-ing each with rotated copies of both, so that changing a single input bit flips bits throughout the output. Formally:

Let $A$, $B$, $C$ be bitstrings of size $P$, where $A_i$ is the $i$-th bit (from left to right), and $i \in {0,\ldots,P-1}$. Let $\oplus$ denote bitwise XOR and let $\circlearrowleft$, $\circlearrowright$ denote 1-bit cyclic left and right rotations respectively.

$$\text{FSCX}(A, B) = A \oplus B \oplus \circlearrowleft A \oplus \circlearrowleft B \oplus \circlearrowright A \oplus \circlearrowright B$$

Equivalently, defining the linear operator $M = I \oplus \text{ROL} \oplus \text{ROR}$:

$$\text{FSCX}(A, B) = M \cdot (A \oplus B)$$

FSCX_REVOLVE(A, B, n) iterates FSCX $n$ times with $B$ held constant:

$$\text{FSCX-REVOLVE}(A, B, n) = \text{FSCX}^{\circ n}(A, B)$$

For bitstrings of size $P = 2^k$, the orbit period is always $P$ or $P/2$, so $\text{FSCX-REVOLVE}(A, B, P) = A$ for all $A$, $B$.

HKEX-GF — Key Exchange over GF(2^n)*

HKEX-GF is a standard Diffie-Hellman key exchange over the multiplicative group $\mathbb{GF}(2^n)^{\ast}$.

1. Setup. Both parties agree on an irreducible polynomial $p(x)$ of degree $n$ and a generator $g = 3$.
2. Key generation. Alice draws a private scalar $a$; Bob draws $b$.
3. Public values. Alice publishes $C = g^a$; Bob publishes $C_2 = g^b$ (all arithmetic in $\mathbb{GF}(2^n)$).
4. Shared secret. Alice computes $\mathit{sk} = C_2^a = g^{ab}$; Bob computes $\mathit{sk} = C^b = g^{ba}$. By commutativity of field multiplication, $g^{ab} = g^{ba}$.

sequenceDiagram
    participant Alice
    participant Bob
    Note over Alice,Bob: agree on p(x), g = 3
    Alice->>Alice: pick private a
    Bob->>Bob: pick private b
    Alice->>Bob: C = g^a
    Bob->>Alice: C2 = g^b
    Alice->>Alice: sk = C2^a = g^(ab)
    Bob->>Bob: sk = C^b = g^(ba)
    Note over Alice,Bob: both now hold the same sk

Loading

An eavesdropper who sees $C$ and $C_2$ still can't compute $a$, $b$, or $\mathit{sk}$ without solving the discrete log problem in $\mathbb{GF}(2^n)^{\ast}$ — see docs/CRYPTOGRAPHY_BASICS.md for why that's believed hard.

The binding attack is Pohlig–Hellman, not the function field sieve: the order of $\mathbb{GF}(2^n)^{\ast}$ is $2^n - 1$, whose largest prime factor is only 73 bits at $n = 256$, so a discrete log costs the square root of that rather than of the field. The sub-exponential FFS $L[1/3]$ figure often quoted for these sizes (~80–90 bits at $n = 256$) is therefore not the practical bound — see SecurityProofs-3.md §9.2.4. Every protocol in the HKEX-GF family is demo-only for this reason; the post-quantum families below do not share the weakness.

Herradura Cryptographic Suite

The suite builds protocols on top of HKEX-GF, FSCX_REVOLVE, and the v1.5.0 NL-FSCX extensions. There are three families, each giving the same basic toolkit — key exchange, symmetric encryption, signature, public-key encryption — under a different hardness assumption:

Classical (v1.4.0) — the baseline quartet, secure against classical (non-quantum) attackers, all built directly on HKEX-GF and FSCX_REVOLVE above:

1. HKEX-GF — key exchange (DH over $\mathbb{GF}(2^n)^{\ast}$, as above)
2. HSKE — symmetric encryption: $E = \text{FSCX-REVOLVE}(P, \mathit{key}, i)$; decrypt with $D = \text{FSCX-REVOLVE}(E, \mathit{key}, r)$
3. HPKS — Schnorr-style public key signature: $R = g^k$; $e = \text{FSCX-REVOLVE}(R, P, i)$; $s = (k - a \cdot e) \bmod (2^n - 1)$; verify $g^s \cdot C^e = R$
4. HPKE — El Gamal public key encryption: $R = g^r$; $\text{enc-key} = C^r$; $E = \text{FSCX-REVOLVE}(P, \text{enc-key}, i)$; Alice decrypts with $\text{dec-key} = R^a$

Post-quantum / NL-hardened (v1.5.0) — same four roles, but swap the classical building blocks for the non-linear FSCX variants (NL-FSCX) and a Ring-LWR key exchange, whose hardness is conjectured to survive a quantum attacker (see docs/CRYPTOGRAPHY_BASICS.md §5.1, "Why quantum-resistant matters"):

1. HSKE-NL-A1 — counter-mode with NL-FSCX v1: $\mathit{ks} = \text{NL-FSCX-revolve-v1}(K, K \oplus \mathit{ctr}, i)$; $E = P \oplus \mathit{ks}$
2. HSKE-NL-A2 — revolve-mode with NL-FSCX v2: $E = \text{NL-FSCX-revolve-v2}(P, K, r)$; $D = \text{NL-FSCX-revolve-v2-inv}(E, K, r)$
3. HKEX-RNL — Ring-LWR key exchange (conjectured quantum-resistant; ring dimension $n=1024$ since v2.7.19 — older $n=256$ keys are insecure, see MIGRATING.md): shared $m_\text{blind}$ in $\mathcal R_q = (\mathbb{Z}/q\mathbb{Z})[x]/(x^n+1)$; parties derive $C = \lfloor m_\text{blind} \cdot s \rceil_p$; agreement $K = \lfloor s \cdot \text{lift}(C_2) \rceil_{p'}$
4. HPKS-NL — NL-hardened Schnorr: $e = \text{NL-FSCX-revolve-v1}(R, P, i)$
5. HPKE-NL — NL-hardened El Gamal: $E = \text{NL-FSCX-revolve-v2}(P, \text{enc-key}, i)$; $D = \text{NL-FSCX-revolve-v2-inv}(E, \text{dec-key}, i)$

Code-based PQC (v1.5.18) — the signature and KEM here rest on a different post-quantum hardness assumption, syndrome decoding (SD), via the Stern zero-knowledge identification protocol made non-interactive (Fiat-Shamir):

1. HPKS-Stern-F — Fiat-Shamir Stern ZKP signature. Security reduces to EUF-CMA ≤ SD($n$, $t$) + NL-FSCX v1 PRF — i.e. forging a signature ("EUF-CMA", existential unforgeability under chosen-message attack) would require either breaking syndrome decoding or the NL-FSCX v1 pseudorandom function ("PRF", an output indistinguishable from random without the key). Protocol: commit $(c_0, c_1, c_2)$; challenge $b \in {0,1,2}$ via NL-FSCX hash; response reveals permuted $r$, $y = e \oplus r$, or permutation $\pi$. Parameters (C/Go/Python): $N = n = 256$, $t = 16$, rounds $= 32$ (demo default; production needs 219, see the caveats section below — herradura.h emits a build warning at any count below SDF_PRODUCTION_ROUNDS; benchmarks use 4–8 rounds for throughput measurement). Assembly/Arduino: $N = 32$, $t = 2$, rounds $= 4$.
2. HPKE-Stern-F — Niederreiter KEM: $\mathit{ct} = H \cdot e'^T$; $K = \text{hash}(\mathit{seed}, e')$. The CLI's hpke-stern algo tag is a demo that decaps from a known $e'$; the separate hpke-stern-kem algo tag uses a real Black-Gray-Flip (BGF) QC-MDPC syndrome decoder (qcmdpc_keygen/qcmdpc_encap/qcmdpc_decap_bgf in all three suites) and does not need the plaintext error vector at decap.

Implementations are provided in C, Go, Python, ARM Thumb-2 assembly, NASM i386 assembly, and Arduino (all six targets at v1.5.19).

FFI Bindings (C-backed, opt-in)

bindings/ffi/ provides a ctypes-based Python wrapper and a cgo-based Go wrapper around herradura.h's classical v1.4.0 quartet (HKEX-GF, HSKE, HPKS, HPKE), for performance-sensitive callers who want C's speed without hand-porting. The native Python and Go suites are untouched and remain the pedagogical reference implementations; the bindings are opt-in and packaged separately (herradura_ffi.py is independent of HerraduraCli/primitives.py; the Go package lives at bindings/ffi/go, separate from the root herradura package).

Build the shared library once, then use either wrapper:

bash bindings/ffi/build.sh          # builds bindings/ffi/libherradura_ffi.so

python3 bindings/ffi/python/test_ffi_correctness.py   # FFI vs. native Python, byte-for-byte
cd bindings/ffi/go && CGO_ENABLED=1 go test ./...      # FFI vs. native Go, byte-for-byte

Measured on this repo's dev hardware (aarch64), hske_encrypt (a single FscxRevolve call, 64 FSCX rounds):

The gap narrows for Go because native Go is already compiled; the FFI number there mostly reflects saved big-integer/allocation overhead plus cgo call cost. Prefer the bindings when running many operations in Python or when Go's math/big-based BitArray arithmetic is a bottleneck; prefer the native implementations for portability (no C toolchain/cgo dependency), for reading/teaching the algorithms, or when only the assembly/Arduino targets are relevant. Scope: only the classical quartet is bound — NL/PQC and Stern-F protocols are not exposed through this FFI layer (TODO #137).

Build & Run Instructions

Docker quickstart

Building by hand needs a gcc, a Go toolchain, an ARM Thumb-2 cross-compiler, a NASM/i386-capable linker, and qemu — a real barrier for a first look. The included Dockerfile installs exactly what build_c.sh/build_go.sh/build_arm.sh/ build_asm_i386.sh's own header comments document, builds five of the suite's seven language targets (C, Go, Python, ARM Thumb-2, NASM i386) and runs their test suites plus one CLI integration test as a smoke test. Two targets are excluded on purpose: Arduino needs a physical or simulated board target, and Java is omitted because the image installs no JDK — bindings/java is a complete port with its own required CI job, so run it locally rather than from this image. Both exclusions are checked by tools/check_docker_mirror.py:

docker build -t herradurakex .
docker run --rm -it herradurakex

No local cross-toolchain installation required; everything happens inside the container. See docker-entrypoint.sh for exactly what runs. A full run takes roughly 75–90 minutes on an ARM SBC and rather less on a modern x86_64 host; HERRADURA_SMOKE_ROUNDS and HERRADURA_SMOKE_TIME trade coverage for time without changing the defaults.

C

# Full cryptographic suite (all protocols: classical, NL/PQC, Stern-F code-based)
gcc -O2 -o "Herradura cryptographic suite_c" "Herradura cryptographic suite.c"
./"Herradura cryptographic suite_c"

# Security & performance tests (in CryptosuiteTests/)
gcc -O2 -o CryptosuiteTests/Herradura_tests_c CryptosuiteTests/Herradura_tests.c
./CryptosuiteTests/Herradura_tests_c

Go

# Full cryptographic suite
go run "Herradura cryptographic suite.go"

# Security & performance tests (in CryptosuiteTests/)
cd CryptosuiteTests && go run Herradura_tests.go

Python

# Full cryptographic suite
python3 "Herradura cryptographic suite.py"

# Security & performance tests (in CryptosuiteTests/)
python3 CryptosuiteTests/Herradura_tests.py

Package managers

The herradurakex package (pyproject.toml, TODO #191) wraps the suite and HerraduraCli for distribution without duplicating either — it loads the same source files via herradurakex/_vendor/ (symlinks into the checkout, bundled as package data in the wheel/sdist), so pip install herradurakex runs byte-identical code to a source checkout:

pip install herradurakex        # once published to PyPI
python3 -c "import herradurakex as h; print(h.KEYBITS)"
herradurakex genpkey --algo hkex-gf --out alice.pem   # console script

The Go module (module herradurakex, root go.mod) resolves via go get from any commit on master, but has no versioned releases yet — go get without a tag pulls the latest commit as a pseudo-version. To cut a real release: tag the commit (git tag -s v2.1.3 -m "v2.1.3", GPG-signed; git push origin v2.1.3), then go get herradurakex@v2.1.3 resolves it via the Go module proxy. The HerraduraCli and herradura (FFI) Go modules can be tagged independently with their own vX.Y.Z prefix per Go's multi-module-repo convention (e.g. HerraduraCli/vX.Y.Z) once they have external consumers.

Assembly

# ARM Linux — full suite + tests (32-bit Thumb; classical + NL/PQC + Stern-F protocols)
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 — full suite + tests (pure Linux syscalls, no libc)
# Requires: nasm, x86_64-linux-gnu-ld (or ld with elf_i386 support), 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
# On a native x86/x86_64 Linux host the binaries run directly without qemu-i386

Arduino

The .ino files require the Arduino IDE or arduino-cli with the AVR board package installed. Open in the IDE and upload to a board with a serial monitor at 9600 baud, or:

# Compile-check only (requires arduino-cli with arduino:avr board package)
arduino-cli compile --fqbn arduino:avr:uno "Herradura cryptographic suite.ino"
arduino-cli compile --fqbn arduino:avr:uno CryptosuiteTests/Herradura_tests.ino

Performance (v1.8.9, Orange Pi 5 — RK3588, Cortex-A76 @ 2.4 GHz)

Benchmarks from CryptosuiteTests/Herradura_tests.{c,go,py} with -t 1.5. Columns correspond to operand bit-width; for HKEX-RNL the column header is the ring degree $n$.

C (gcc -O2)

C benchmarks use native types per size: uint32_t / uint64_t / __uint128_t / BitArray.

Go (go run)

Python 3

Repository Structure

Herradura cryptographic suite.{c,go,py,s,asm,ino}  — protocol suite (all six language targets)
herradura.h                                         — header-only C library (Protocol Layer wrappers)
CryptosuiteTests/
  Herradura_tests.{c,go,py,s,asm,ino}              — security tests & benchmarks
  go.mod
HerraduraCli/                                       — Python CLI (genpkey/pkey/kex/enc/dec/sign/verify)
Mcp/                                                 — MCP server exposing the CLI as agent-callable
                                                      tools (stdlib-only, no external dependency);
                                                      see Mcp/README.md for the trust model
spec/                                                — machine-readable protocol spec (JSON Schema):
                                                      parameters, PEM wire-format labels, CLI --algo
                                                      tags, and security-level classification per
                                                      protocol — the canonical source for tooling/LLMs
SecurityProofsCode/                                 — standalone Python proof and analysis scripts
SecurityProofs-1.md                                 — formal analysis §1 (algebraic foundations)
SecurityProofs-2.md                                 — formal analysis §2–§8 (protocol security,
                                                      quantum attack analysis, experimental
                                                      code index)
SecurityProofs-3.md                                 — formal analysis §9–§10 (non-linear proposals,
                                                      v1.4.0 migration)
SecurityProofs-4.md                                 — formal analysis §11–§11.8.2 (non-linearity and
                                                      post-quantum extensions, NL-FSCX v1/v2, HKEX-RNL)
SecurityProofs-5.md                                 — formal analysis §11.8.3–§11.8.10 (PQ signature
                                                      options, HPKE-Stern-KEM)
SecurityProofs-6.md                                 — formal analysis §11.9 (HFSCX-256-DM hash)
SecurityProofs-7.md                                 — formal analysis §11.10–§11.13, §11.15–§11.33
                                                      (ZKP extensions, research-review sections)
SecurityProofs-8.md                                 — formal analysis §11.34–§11.36 (NL-FSCX v3
                                                      exact row analysis, weak keys; the
                                                      asymptotic differential and linear
                                                      slopes, measured exactly)
SecurityProofs-9.md                                 — formal analysis §11.37–§11.42 (the width
                                                      residue #252 and #254 shared; the
                                                      annealed threshold evaluated exactly
                                                      at n = 256; the pair correlation; the
                                                      quenched check against exact mu; the
                                                      certified ladder to n = 20; the
                                                      exact slope to n = 23)
SecurityProofs-10.md                                — formal analysis §11.43–§11.49 (the
                                                      local certificate: a sound lower
                                                      bound on mu at any width, why its
                                                      window must grow with n, and the
                                                      certificate solved at n = 256; the
                                                      linear hull, measured exactly to
                                                      n = 16; where the optimal cycles
                                                      pay, at delta's run boundaries; no
                                                      upper bound by search and no
                                                      monotone lift between widths;
                                                      the coupled ladder, where E[mu]
                                                      rises at every step to n = 17;
                                                      the period exponent, which
                                                      separates the n = 256 readings)
SecurityProofs.md                                   — split index (redirects to the ten files above)
MIGRATING.md                                        — consolidated breaking-change history and
                                                      upgrade notes
docs/
  CRYPTOGRAPHY_BASICS.md                            — cryptography fundamentals primer (no prior background required)
  INTRODUCTION.md                                   — plain-language cryptographic concepts primer
  TUTORIAL.md                                       — integration tutorial (C/Go/Python API recipes)
  examples/                                         — minimal runnable examples (C, Go, Python)

Known Limitations

These are accepted, currently-shipping limitations — not bugs, and not blocking issues. Each is tracked and documented at the citation given; this section exists so they're visible without having to search TODO_DONE.md.

• HPKS-NL / HPKE-NL are not quantum-resistant. They harden the classical Schnorr/El Gamal constructions with the non-linear FSCX primitive, but remain built on the DLP over GF(2^n)* — Shor's algorithm still breaks them. No lattice-based replacement is planned for these two specifically; use HPKS-Stern-F/HPKE-Stern-F or the HKEX-RNL quartet for genuine post-quantum security (TODO #5, TODO_DONE.md — deprecated by design, not an open item).
• HPKS-Stern-F / HPKE-Stern-F ship at demo scale. The default parameters (N = n = 256, t = 16, 32 Fiat-Shamir rounds) are a low-soundness demonstration configuration. Production-grade parameters require N on the order of 17,000+ for 128-bit security — a substantially larger, unimplemented configuration. Treat both protocols as reference implementations of the Stern ZKP construction, not as production-ready code signing or KEM at their current defaults. This caveat covers the hpke-stern CLI algo tag specifically (its decap needs the plaintext error vector); the separate hpke-stern-kem tag uses a real BGF QC-MDPC decoder instead and doesn't share that particular limitation, but is demo-only for its own reasons: since v7.0.0 (TODO #276) it runs at BIKE-128's parameters (r = 12323, d = 71, t = 134), adopted verbatim together with BIKE's decoder, replacing a toy set (r = 523, d = 15, t = 18) whose measured decoding-failure rate was 0.264% = 2^-8.6 where IND-CCA2 needs 2^-128 and whose underlying QC syndrome-decoding instance was worth about 2^21 classical operations. What keeps it demo-only is a reason that changed rather than went away: the DFR at these parameters is not measurable here — that is exactly what the change bought — so 2^-128 is inherited from BIKE's published analysis, while what ships is a reimplementation of BIKE's decoder whose equivalence rests on testing rather than proof, drawing from a suite-specific FSCX-based PRF rather than BIKE's. Since v3.3.0 (TODO #235) decapsulation applies an FO transform with implicit rejection and key generation screens the weak-key classes, so the GJS reaction attack no longer has an oracle; an imported private key is still unscreened. One consequence to know: a decoding failure is now silent, surfacing as a shared secret the peer disagrees with rather than an error. See SECURITY.md and SecurityProofs-5.md §11.8.7. The round count is a separate, independent axis from N: sign --algo hpks-stern/hpks-ring accepts --rounds in all four CLIs (219 reaches 128-bit Fiat-Shamir soundness); the count is a per-signature PEM field, not a compile-time constant, so any build reads any round count (TODO #236). Raising rounds alone does not fix the N = 256 SD-hardness shortfall above.
• No test is FAIL-by-design; every [FAIL] fails the build (TODO #233, v3.0.8). This bullet used to say the opposite — that test [4] (bit-frequency bias) and C test [18] (HPKE-Stern-F brute-force decap) were expected to report FAIL and should not be treated as a build gate. Both were fixed in v3.0.8 and the harnesses were given an aggregate exit status at the same time: all six targets now aggregate their own [FAIL] markers and exit non-zero, with no allow-list. [4] scales its tolerance with the sample size (6 × 50/sqrt(N)) and [18] distinguishes an ambiguous syndrome from a decoder failure, so both assert what they measure. A [FAIL] in any language is a regression.
• Arduino/AVR CI is a required, blocking job (TODO #185, v2.0.6). It ran continue-on-error: true from its introduction (TODO #153, v1.9.120) until the ATmega2560 SRAM overflow behind its only failures was fixed (TODO #155, v1.9.122); it has passed 100% of runs since (0 failures across 74 runs as of this review) and now blocks merges like the native and ARM/i386 jobs.
• The QC-MDPC BGF decoder and Ligero-lite IOP prototypes are research code, not wired into any CLI subcommand or production path (SecurityProofsCode/ qc_mdpc_bgf_prototype.py, nl_fscx_ligero.py).

See MIGRATING.md if you're upgrading from a version predating v1.9.36 — three breaking changes in the suite's history are consolidated there.

License

Dual-licensed under GPL v3.0 and MIT. Users may choose either.