✓ PractRand 128 TB · NIST 15/15 · BigCrush 160/160 · SMT Resistant
Rational Quadratic CSPRNG

BARZAKH-521

Cryptographic Key Generation
Through Rational Quadratic Nonlinearity

Barzakh-521 is a cryptographically secure pseudorandom number generator based on a rational quadratic function with modular inversion over the Mersenne prime field GF(2521−1). Designed for high-security key generation with a 2,604-bit internal state.

⬇ View on GitHub 📄 Read the Paper
"A cryptographic system should be secure even if everything about the system, except the key, is public knowledge."
Auguste Kerckhoffs — La cryptographie militaire, 1883
K(x) ≡ (a·x² + b) · (x − a)−1 + w  (mod M521)

The Barzakh Function — Rational quadratic map with modular inversion over GF(2521−1)

Empirical Certifications

Validated Against the Most Demanding Test Suites

Statistical and algebraic testing confirms that Barzakh-521 output is indistinguishable from a truly random source across all known tests.

🧪
PractRand
128 TB — 0 anomalies
14 consecutive milestones (16 GB → 128 TB), over 3,600 individual test evaluations. Zero statistical anomalies detected.
🏛️
NIST SP 800-22
15/15 tests passed
All 15 fundamental tests passed on 100 bitstreams of 106 bits each. 148 NonOverlapping Template variants validated.
📊
TestU01 BigCrush
160/160 statistics passed
All 160 statistics of the most demanding battery in TestU01 passed with zero suspect p-values (< 10−4 or > 1−10−4). SmallCrush: 15/15.
🔐
Z3 SMT Solver
TIMEOUT — all configurations
Microsoft Research Z3 v4.13 failed to recover internal state across all configurations, even with known parameters.
🔐
Bitwuzla SMT
TIMEOUT — all configurations
SMT-COMP 2023 bitvector winner. Failed to recover state on 1-round and 2-round models at all time budgets (48h).
🎯
Strict Avalanche Criterion
50.00% ± 0.36%
Measured across 218 sample pairs. Each input bit flip causes each output bit to flip with near-ideal probability. Comparable to ChaCha20 and SHAKE-256.

Architecture at a Glance

A 2,604-bit Internal State

Powered by three orthogonal sources of nonlinearity: quadratic (x²), inversive ((x−a)−1), and bitwise XOR state mixing.

2,604
Internal State (bits)
5 × 521-bit field elements (x, a, b, w, W).
w constrained to odd: 520 effective bits.
M521
Field
GF(2521−1) — Mersenne prime field
256
Output per Step (bits)
Top 256 MSBs of 521-bit intermediate K(x)
265
Hidden Residue (bits)
Exceeds Coppersmith bound: 2265 > p1/2 ≈ 2260.5
49.1%
Exposure Ratio
256/521 < 50% — below the Shparlinski–Blackburn threshold
7.54 MB/s
Batch Throughput
Per core (Apple M2) via Montgomery batch inversion, 8 lanes
234K/s
Iterations per Second
256-bit blocks per second per core
(≈ 7.54 MB/s in batch mode)
Zeroize
Memory Safety
All secret state automatically zeroed on drop

Compared to Existing Generators

Barzakh-521 in the CSPRNG Landscape

Number-theoretic comparison with classical inversive and quadratic generators.

Property ICG (Classical) BBS Barzakh-521
Algebraic Degree 1 (linear) 2 (x²) 2 (rational quadratic)
Field GF(p) ℤ/Nℤ GF(M521)
Modular Inversion Yes No Yes
XOR State Mixing No No Yes
Internal State log₂(p) bits log₂(N) bits 2,604 bits
Output / Step Full 1 bit 256 bits (MSB)
Throughput ~0.5 MB/s ~0.001 MB/s 7.54 MB/s
PractRand N/A N/A 128 TB (0 anomalies)
BigCrush N/A N/A 160/160
NIST SP 800-22 N/A N/A 15/15

Quantum Resistance

Shor-Resistant Architecture

Barzakh-521 is not based on factoring or discrete logarithm. Shor's algorithm does not directly apply. Grover halves the search space, but the resulting work factor remains intractable.

2265
Hidden bits per output (classical)
~132 bits
Estimated post-Grover security
Immune
Shor's algorithm
2,604
Full state (bits)
⚠ Note: The post-Grover security estimate (~132 bits) is based on Grover halving the 265 hidden bits per output. A formal post-quantum security analysis is an open research problem. These figures should not be interpreted as a certified post-quantum security level.

Formal Security Analysis

Five Concrete Security Propositions

Each major attack family has been analyzed and shown to be ineffective against Barzakh-521.

1️⃣
Coppersmith Resistance
2265 > p1/2 ≈ 2260.5
The hidden residue (265 bits) exceeds the Coppersmith root bound for degree-2 polynomials. Both univariate and bivariate variants fail.
2️⃣
Lattice Resistance (LLL/BKZ)
256/521 = 49.1% < 50%
The exposure ratio falls below the Shparlinski–Blackburn threshold for inversive generators. The system of equations is underdetermined for any number of outputs.
3️⃣
Algebraic Immunity (XOR Barrier)
Degree Θ(p) over 𝔽p
The XOR state update x ← W ⊕ K(x) has algebraic degree p−1 = 2521−2 over 𝔽p, preventing any polynomial system formulation.
4️⃣
Circuit Complexity
> 1.77 × 108 gates
A single iteration requires >105 Boolean gates (dominated by Fermat inversion: 520 squarings + 13 multiplications = 533 modular operations).
5️⃣
RHNP Assumption
New hardness problem
We introduce the Rational Hidden Number Problem (RHNP), a new hardness assumption generalizing the classical HNP of Boneh–Venkatesan to rational quadratic functions with XOR recurrence.

White Paper

Read the Full Technical Paper

Complete construction, security proofs, and empirical validation.

📄
Barzakh-521: A Rational Quadratic CSPRNG over GF(2521−1) with Resistance to Lattice and Algebraic Attacks
Abdelghaffour Khettany — EdiwareLab, Morocco — April 2026
⬇ Download PDF

Contact

Get In Touch

Interested in enterprise or research collaboration? Let's talk.