nx_p256_field_inv.nx source
↩ module page · 138 lines · 4892 B
1// nx_p256_field_inv.nx -- P-256 prime-field modular inverse via
2// Fermat's little theorem.
3//
4// Phase 0b §I.3 piece 1d of the ECDSA-P256 arc:
5// ✓ 0. u256 big-int (6ff89dd8)
6// ✓ 1. p256_field add/sub/neg (133f16a1)
7// ✓ 1b. u256 wide multiplication (ddb0994a)
8// ✓ 1c. p256_field mul + sq (d295c0a3)
9// ✓ 1d. p256_field inverse (THIS commit)
10// - 2. p256_point ops (queued)
11// - 3. p256_scalar mod n (queued)
12// - 4. ecdsa_p256 verify (queued)
13//
14// Algorithm: Fermat's little theorem. For prime p and nonzero a:
15// a^(p-1) = 1 (mod p) => a^(p-2) = a^(-1) (mod p)
16//
17// We compute a^(p-2) via straightforward left-to-right binary
18// square-and-multiply over the 256 bits of (p-2). This is the
19// most-portable form -- no addition-chain optimization, no
20// constant-time guarantee. An optimized addition-chain variant
21// (~30 mults vs ~128 here) is queued for piece 1d-fast.
22//
23// p-2 has 128 set bits in its 256-bit representation:
24// bits 255..224 set (32 bits, top of p)
25// bit 192 set (1 bit, "+ 2^192" in p)
26// bits 95..32 set (64 bits, low 96 bits of p)
27// bits 31, 30, ..., 2 set (30 bits)
28// bit 0 set (lowest bit; bit 1 clear because -2)
29//
30// So 256 squarings + 128 multiplications = ~384 field ops per
31// inverse. With our slow p256_field_mul at ~4100 limb-ops per
32// mul, that's ~1.5M limb-ops per inverse. Each ECDSA verify
33// uses ONE inverse (s^(-1) mod n -- but that's via the scalar
34// modulus n, not p; this field inverse is used during point
35// arithmetic's final-step Jacobian-to-affine conversion).
36//
37// Public API:
38// p256_field_load_p_minus_2(out)
39// p256_field_inv(out, a)
40// p256_field_bit_at(limbs, bit_pos) -> 0|1 (helper)
41//
42// Aliasing: out MAY equal a (uses scratch internally).
43//
44// Caveat for non-invertible inputs:
45// Calling p256_field_inv(out, 0) returns 0 (because 0^anything
46// = 0 for any positive exponent). Mathematically 0 has no
47// inverse mod p, so callers MUST check for zero before
48// relying on the result. We don't return a verdict here
49// because the caller (point-arithmetic Jacobian-to-affine)
50// already knows whether its denominator is nonzero by
51// construction.
52//
53// Per Cardinal 9 (single-responsibility), 22 (composition --
54// inverse composes sq + mul), and 23 (preamble explains WHY
55// the non-optimized form ships first).
56//
57// license_tier: INDEPENDENT_REDERIVE
58// genealogy_id: international-research-sources/nist/fips_186_5
59// lineage_id: nishi_p256_field_inv_q10
60
61// nx_safety_envelope:
62// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
63// sil_target: SIL1
64// evidence: [bulk_applied_2026-05-19, fermat-inverse-square-multiply]
65// verdict: NOT_YET_EVALUATED
66
67import "nx_syscalls.nx"
68import "nx_u256.nx"
69import "nx_p256_field.nx"
70import "nx_p256_field_mul.nx"
71
72// Write p-2 into out (8 limbs, LE order). Differs from p in the
73// LSB limb only: limb[0] = 0xFFFFFFFD instead of 0xFFFFFFFF.
74func p256_field_load_p_minus_2(out: *i64) -> i64 {
75 out[0] = 0xFFFFFFFD
76 out[1] = 0xFFFFFFFF
77 out[2] = 0xFFFFFFFF
78 out[3] = 0
79 out[4] = 0
80 out[5] = 0
81 out[6] = 1
82 out[7] = 0xFFFFFFFF
83 return 0
84}
85
86// Extract the bit at bit_pos (0 = LSB) from an 8-limb (32-bit-per-
87// limb LE) integer. Returns 0 or 1.
88func p256_field_bit_at(limbs: *i64, bit_pos: i64) -> i64 {
89 let limb_idx: i64 = bit_pos / 32
90 let bit_in_limb: i64 = bit_pos - limb_idx * 32
91 let limb: i64 = limbs[limb_idx] & NX_U256_LIMB_MASK
92 return (limb >> bit_in_limb) & 1
93}
94
95// out = a^(-1) mod p via Fermat: a^(p-2). Input a must be
96// canonical (< p); output canonical. out MAY alias a.
97//
98// Square-and-multiply, left-to-right (MSB-first) over the 256
99// bits of (p-2):
100//
101// result = 1
102// for bit_pos = 255, 254, ..., 0:
103// result = result^2 mod p
104// if bit_pos-th bit of (p-2) is set:
105// result = result * a mod p
106// return result
107func p256_field_inv(out: *i64, a: *i64) -> i64 {
108 let _fm: i64 = nx_scratch_save()
109 let exp: *i64 = u256_alloc()
110 p256_field_load_p_minus_2(exp)
111
112 // Keep input safe in case out aliases a.
113 let base: *i64 = u256_alloc()
114 u256_copy(base, a)
115
116 let result: *i64 = u256_alloc()
117 p256_field_one(result)
118
119 var bit_pos: i64 = 255
120 while bit_pos >= 0 {
121 // result = result * result mod p
122 p256_field_sq(result, result)
123 // If bit is set: result = result * a mod p
124 if p256_field_bit_at(exp, bit_pos) == 1 {
125 p256_field_mul(result, result, base)
126 }
127 bit_pos = bit_pos - 1
128 }
129
130 u256_copy(out, result)
131 nx_scratch_restore(_fm)
132 return 0
133}
134
135// Compile-only smoke. Real KAT in nx_p256_field_inv_test.nx.
136func main() -> i64 {
137 return 0
138}