nx_u256_mul.nx source

1// nx_u256_mul.nx -- 256 x 256 -> 512-bit unsigned multiplication. 2// 3// Phase 0b §I.3 piece 1b of the ECDSA-P256 arc. Extends the 4// nx_u256 limb primitives (commit 6ff89dd8) with the schoolbook 5// 8 x 8 limb multiplication that produces a 16-limb (512-bit) 6// wide product. This is the foundation for both: 7// - p256_field_mul (composes wide_mul + NIST P-256 Solinas 8// reduction; queued for piece 1c) 9// - p256_scalar_mul mod n (composes wide_mul + Barrett or 10// trial-subtract reduction mod the group order; queued) 11// 12// Split rationale: wide multiplication is a primitive in its own 13// right. Splitting it from reduce-mod-p means scalar arithmetic 14// (which needs reduce-mod-n, NOT reduce-mod-p) gets to reuse the 15// same wide_mul. Per Cardinal 9 (single-responsibility), this 16// primitive does ONE thing -- big-int multiply -- and the two 17// reduction primitives compose on top. 18// 19// Algorithm: schoolbook with carry propagation. 20// 21// For each i in 0..8: 22// carry = 0 23// For each j in 0..8: 24// s = out[i+j] + a[i] * b[j] + carry 25// out[i+j] = low_32(s) 26// carry = high_32(s) 27// out[i+8] = carry 28// 29// Each (a[i] * b[j] + out[i+j] + carry) intermediate fits in 30// u64 (max = (2^32 - 1)^2 + 2 * (2^32 - 1) = 2^64 - 1), so the 31// expression is computed in a single i64 register without 32// 128-bit emulation. Sign-extension concerns are handled by 33// AND-mask after right-shift -- arithmetic shift of a negative- 34// looking i64 still produces the correct high 32 bits when 35// masked with 0xFFFFFFFF. 36// 37// Wide-output layout: out_16[0] = LSB of product, out_16[15] = MSB. 38// Same little-endian limb order as the 8-limb inputs. 39// 40// Aliasing: out_16 MUST NOT overlap a or b (the algorithm reads 41// a[i], b[j] for every (i, j) while it streams writes into 42// out_16). Caller responsibility (no defensive check). 43// 44// What this primitive does NOT do: 45// - Reduction mod any specific prime (queued: p256_field_mul, 46// p256_scalar_mul). 47// - Squaring fast-path (~25% speedup; queued as 48// u256_sq_wide once needed). 49// - Constant-time guarantee against timing side channels. 50// ECDSA verify operates on PUBLIC inputs (cert pubkey + sig + 51// msg hash), so variable-time multiplication is acceptable 52// here. A constant-time variant would be required for ECDSA 53// SIGNING (which we don't ship: substrate is verify-only). 54// 55// Per Cardinal 9 (single-responsibility) and Cardinal 22 56// (composition over configuration). 57// 58// license_tier: INDEPENDENT_REDERIVE 59// genealogy_id: international-research-sources/nist/fips_186_5 60// lineage_id: nishi_u256_mul_q10 61 62// nx_safety_envelope: 63// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 64// sil_target: SIL1 65// evidence: [bulk_applied_2026-05-19, u256-wide-mul-foundation] 66// verdict: NOT_YET_EVALUATED 67 68import "nx_syscalls.nx" 69import "nx_u256.nx" 70 71const NX_U256_WIDE_LIMBS: i64 = 16 72const NX_U256_WIDE_BYTES: i64 = 64 73 74// Allocate a 16-limb (512-bit) wide buffer, zeroed. 75// Served from the u256 scratch arena (see nx_u256.nx) -- no per-op 76// mmap; reclaimed by the enclosing routine's nx_scratch frame. 77func u256_wide_alloc() -> *i64 { 78 return (nx_scratch(NX_U256_WIDE_LIMBS * 8)) as *i64 79} 80 81// out_16 = a * b (256x256 -> 512). No reduction. 82// 83// Aliasing: out_16 MUST be a distinct buffer from a and b. 84// Returns 0. 85func u256_mul_wide(out_16: *i64, a: *i64, b: *i64) -> i64 { 86 var k: i64 = 0 87 while k < NX_U256_WIDE_LIMBS { 88 out_16[k] = 0 89 k = k + 1 90 } 91 var i: i64 = 0 92 while i < NX_U256_LIMBS { 93 let ai: i64 = a[i] & NX_U256_LIMB_MASK 94 var carry: i64 = 0 95 var j: i64 = 0 96 while j < NX_U256_LIMBS { 97 let bj: i64 = b[j] & NX_U256_LIMB_MASK 98 let prev: i64 = out_16[i + j] & NX_U256_LIMB_MASK 99 let s: i64 = prev + ai * bj + carry 100 out_16[i + j] = s & NX_U256_LIMB_MASK 101 carry = (s >> NX_U256_LIMB_BITS) & NX_U256_LIMB_MASK 102 j = j + 1 103 } 104 out_16[i + 8] = carry 105 i = i + 1 106 } 107 return 0 108} 109 110// Unsigned 64-bit less-than (NishiLang `<` is signed): flip both sign bits so 111// signed order matches unsigned order. Returns 1 if a <u b, else 0. The carry 112// primitive for software add-with-carry in the 4x64 multiply (native ADC = G3). 113func u64_lt(a: i64, b: i64) -> i64 { 114 let fa: i64 = a ^ (1 << 63) 115 let fb: i64 = b ^ (1 << 63) 116 if fa < fb { return 1 } 117 return 0 118} 119 120// FAST-COMPILER PATH (2026-06-06): the intrinsic-optimized 4x64 multiply used __umulhi64 / __adc_acc, 121// which the FAST known-good compiler cannot parse -- and @ifdef is NOT honored on nx_build_run's 122// direct-compile path (it bypasses the macro preprocessor), so a guard could not exclude it. Since the 123// crypto callers (p256_field_mul / p256_modn) already use the pure 8x32 u256_mul_wide, and that IS the 124// verified byte-exact oracle, this twin now DELEGATES to it. Result: the whole crypto stack builds with 125// the fast compiler in SECONDS (no intrinsics anywhere), results bit-identical. The intrinsic fast-path 126// can be restored later behind a real macro-preprocessor build target if crypto runtime ever dominates. 127func u256_mul_wide_4x64(out_16: *i64, a: *i64, b: *i64) -> i64 { 128 return u256_mul_wide(out_16, a, b) 129} 130 131// Compare two wide (16-limb) values. Returns -1, 0, +1. 132func u256_wide_cmp(a_16: *i64, b_16: *i64) -> i64 { 133 var i: i64 = NX_U256_WIDE_LIMBS - 1 134 while i >= 0 { 135 let av: i64 = a_16[i] & NX_U256_LIMB_MASK 136 let bv: i64 = b_16[i] & NX_U256_LIMB_MASK 137 if av < bv { return 0 - 1 } 138 if av > bv { return 1 } 139 i = i - 1 140 } 141 return 0 142} 143 144// Returns 1 if the upper 8 limbs are all zero (wide value fits in 145// 256 bits), else 0. 146func u256_wide_fits_in_256(a_16: *i64) -> i64 { 147 var i: i64 = 8 148 var acc: i64 = 0 149 while i < NX_U256_WIDE_LIMBS { 150 acc = acc | (a_16[i] & NX_U256_LIMB_MASK) 151 i = i + 1 152 } 153 if acc == 0 { return 1 } 154 return 0 155} 156 157// Copy the low 8 limbs of a 16-limb wide value into an 8-limb 158// narrow buffer. Used by reducers after they've folded the high 159// limbs into the low ones. 160func u256_wide_copy_low(out_8: *i64, src_16: *i64) -> i64 { 161 var i: i64 = 0 162 while i < NX_U256_LIMBS { 163 out_8[i] = src_16[i] 164 i = i + 1 165 } 166 return 0 167} 168 169// Compile-only smoke. Real KAT in nx_u256_mul_test.nx. 170func main() -> i64 { 171 return 0 172}