Bouncy Castle Cryptography for .NET

The Org.BouncyCastle.Math.BinPoly namespace provides a high-performance, unified implementation of binary-polynomial (GF(2)[x]) arithmetic. It is designed to replace ad-hoc implementations used in various parts of the Bouncy Castle library (like F2mFieldElement, BikeRing, and Hqc.GF2x) with a single, well-tested core.

Key Capabilities

• Arithmetic Operations: Multiplication, squaring, and repeated squaring (SquareN), all producing fully reduced results.
• Modular Reduction: Supports reduction by binomial ($x^n + 1$), trinomial ($x^n + x^k + 1$), and pentanomial ($x^n + x^{k3} + x^{k2} + x^{k1} + 1$) polynomials.
• Inversion: Supports inversion in $GF(2^n)$ using the Itoh–Tsujii algorithm (for field/irreducible moduli).
• Flexibility: Supports any degree $n$ (even or odd, including multiples of 64).
• Performance: Utilizes two backends: an x86 Vector128 PCLMULQDQ backend for hardware acceleration and a portable scalar fallback.

Data Representation

Polynomials are bit-packed in ulong[] using little-endian word order. Bit $i$ of the polynomial is stored at bit ($i$ mod 64) of limb ($i$ / 64).

Multiplication performance is optimized by dispatching to specialized, sealed implementations based on the operand size (number of ulong limbs) and the available Instruction Set Architecture (ISA).

X86.V128 Backend (Hardware Accelerated)

Uses PCLMULQDQ via Vector128<ulong>. The KaratsubaCutoff is 32 limbs.

Scalar Backend (Portable Fallback)

Used on platforms without hardware support or when intrinsics are disabled. The KaratsubaCutoff is 8 limbs.

The BinPoly architecture is layered to balance high-level ease of use with low-level performance. It uses a facade pattern to hide complex implementation details behind narrow interfaces.

Architectural Layers

1. BinPolys (Static Facade): The primary entry point. It provides reducer-independent helpers (like Size, Create, Copy, Clear) and nested factory classes (Mul and Inv) to instantiate arithmetic engines.
2. IBinPolyMul & IBinPolyInv (Interfaces): Narrow, array-based interfaces that consumers interact with. IBinPolyMul provides Multiply, Square, and SquareN. IBinPolyInv provides Invert.
3. BinPolyMulBase (Abstract Base): Implements the shared logic for Square and SquareN and manages the internal state, including the reduction strategy (IReduce).
4. Sealed Implementations: Specific, highly optimized classes (e.g., V128Impls, ScalarImpls) are selected based on the operand size and the available Instruction Set Architecture (ISA). These are designed to be devirtualized and inlined by the JIT compiler.
5. Backends & Kernels: The Backend layer acts as a factory and availability gate (e.g., checking if x86 Vector128 is enabled), while Kernels provide the raw carry-less-multiply routines.

The BinPoly design follows a strict constant-time discipline to protect against side-channel attacks:

• Branching: The library only branches on non-secret parameters (such as the polynomial degree n or the tap positions k). It never branches on the actual element data.
• Hardware Path: The X86.V128 backend is designed to be constant-time.
• Scalar Fallback Warning: The Scalar fallback uses a 16-entry table indexed by 4 bits of an operand. This introduces a cache-timing side channel. For deployments requiring protection against cache-timing attackers, ensure the hardware-accelerated path (PCLMULQDQ) is available and enabled.
• Memory Wiping: Secret intermediate buffers are wiped using BinPolys.Clear, which utilizes CryptographicOperations.ZeroMemory to prevent JIT elision.
• Responsibility: When using IReduce, the caller is responsible for wiping the extended buffer tt after use, as its post-reduction contents are arbitrary.

The Org.BouncyCastle.Math.BinPoly namespace provides a high-level factory API for performing arithmetic on binary polynomials. You should interact with the BinPolys factory rather than managing backends or reducers manually.

Multiplication

Use BinPolys.Mul to obtain an IBinPolyMul instance. The factory automatically selects the most efficient backend (e.g., X86.V128 with PCLMULQDQ if available, or a portable Scalar fallback) and the appropriate reducer based on the polynomial parameters (binomial, trinomial, or pentanomial).

Inversion

Use BinPolys.Inv.ItohTsujii to obtain an IBinPolyInv instance. This implementation is backend-independent and uses the Itoh–Tsujii identity.

Note: Inversion is only mathematically correct for irreducible reduction polynomials (fields). The library enforces this by only allowing trinomial and pentanomial factories to be routed to the Inv factory; binomial rings are excluded.