Module arithmetic 

Arithmetic backends

This page describes representations and invariants. It is not a substitute for the bounds in the owning crate’s tests.

Field modulo p = 2^255 - 19

Compatibility representation

FieldElement2625 contains ten 32-bit storage limbs with alternating logical widths:

limb index:  0  1  2  3  4  5  6  7  8  9
radix bits: 26 25 26 25 26 25 26 25 26 25

The representation follows Dalek’s serial 32-bit backend. Intermediate values may be loose; functions that compare or encode must first establish their documented carry/reduction bounds. Do not replace a bounded limb operation with a wrapping operation merely because both pass small vectors.

The serial engine exposes multiply, add, and subtract operations. The parallel bank supplies four field multipliers to the point controller. Inversion and square-root operations use fixed exponentiation chains, so operation count does not depend on secret data.

Fast representation

[rhdl_ed25519_fast_field::FieldElement17] contains fifteen 17-bit limbs:

x = sum(limb[i] * 2^(17*i)), i = 0..14

Because 2^(17*15) = 2^255, wrapped coefficients fold into the low limbs with factor 19. The current pipeline forms all 225 limb products, accumulates wrapped and non-wrapped terms, performs carry passes, and canonicalizes the result.

[rhdl_ed25519_fast_field::Radix17FieldMulPipe] is an RHDL black-box wrapper around SystemVerilog. Its behavioral counterpart is [rhdl_ed25519_fast_field::multiply_model]. Any RTL change must agree with an independent big-integer oracle, not only with this model.

Scalars modulo group order l

The Ed25519 group order is:

l = 2^252 + 27742317777372353535851937790883648493

The compatibility scalar engine uses nine 29-bit limbs and supports:

• reduction of a 512-bit SHA-512 digest;
• reduction of a 256-bit clamped scalar;
• r + k*a mod l;
• canonicality testing for verification.

Signature verification must reject S >= l; reducing an untrusted S would change strict verification semantics.

Scalar recoding

The compatibility scalar multiplier uses balanced radix 16. A 32-byte scalar becomes 64 signed digits in [-8, 8]. The table selector scans all eight magnitudes for every digit and applies sign by swapping y+x/y-x and negating xy2d.

For the generic variable-point path, the engine generates [P, 2P, ..., 8P] on demand. Each Projective Niels point occupies forty 32-bit words. Eight BRAM banks are read with the same public word address, and secret magnitude selects only after all candidates have been fetched.

Edwards points

Extended Edwards coordinates represent affine (x, y) as:

x = X/Z
y = Y/Z
T = X*Y/Z

with the invariant X*Y = Z*T. The extended form avoids inversion during addition and doubling. Inversion is deferred until compression.

Affine/Projective Niels forms store combinations such as y+x, y-x, and 2*d*x*y. Mixed addition then becomes a fixed DAG of field additions and products. The point controller executes that DAG through microcode and shared field engines.

Encoding and decoding

Compressed Ed25519 points store canonical affine y in little-endian form and the parity of affine x in the high bit. Decompression:

1. extracts and clears the sign bit;
2. checks that y is canonical;
3. solves the curve equation for x^2;
4. computes a square-root candidate using a fixed chain;
5. verifies/adjusts the root and applies the encoded sign;
6. reconstructs (X:Y:Z:T).

Verification additionally performs small-order checks. Compression and decompression are therefore protocol operations, not just serialization helpers.

Change checklist for arithmetic

An arithmetic optimization is incomplete until it has:

1. boundary and randomized differential tests against an independent oracle;
2. explicit input/intermediate/output bounds;
3. constant operation and table-access patterns where secrets are involved;
4. RHDL compilation or black-box RTL lint/simulation evidence;
5. fresh synthesis evidence for area and timing claims.