nx_ecdsa_p256.nx source

1// nx_ecdsa_p256.nx -- ECDSA signature verification over NIST P-256. 2// 3// Phase 0b §I.3 FINAL piece of the ECDSA-P256 arc: 4// ✓ 0. u256 big-int (6ff89dd8) 5// ✓ 1. p256_field add/sub/neg (133f16a1) 6// ✓ 1b. u256 wide multiplication (ddb0994a) 7// ✓ 1c. p256_field mul + sq (d295c0a3) 8// ✓ 1d. p256_field inverse (48e8e69d) 9// ✓ 2. p256_point double + on_curve + to_affine (ecc7ad5f) 10// ✓ 2b. p256_point_add (190acf1f) 11// ✓ 2c. p256_scalar_mul (also shipped earlier) 12// ✓ 3. p256_modn (Z/nZ arithmetic) (7e836066) 13// ✓ 4. ecdsa_p256_verify (THIS commit) 14// 15// This is the primitive that x509_validate's signature dispatch 16// will call for ECDSA-signed certs -- including every modern 17// Web PKI cert chain (google.com, Cloudflare, ~80% of the Web). 18// 19// Algorithm (FIPS 186-5 §6.4.2 / SEC 1 v2.0 §4.1.4): 20// 21// Input: pubkey Q = (Qx, Qy) (affine point on curve, != O) 22// msg hash e (256-bit, already truncated/computed) 23// signature (r, s) -- both 256-bit 24// 25// 1. Verify 1 <= r < n and 1 <= s < n. Reject otherwise. 26// 2. Verify Q is on the curve. Reject otherwise. 27// 3. e_n = e mod n (truncate-and-reduce; SHA-256 output 28// has the same bit-length as n for 29// P-256 + SHA-256, so this is just a 30// conditional subtract.) 31// 4. s_inv = s^(-1) mod n 32// 5. u1 = (e_n * s_inv) mod n 33// 6. u2 = (r * s_inv) mod n 34// 7. R = u1 * G + u2 * Q 35// 8. Reject if R = O (point at infinity). 36// 9. Convert R to affine; v = x_R mod n 37// 10. Accept iff v == r. 38// 39// Public API: 40// nx_ecdsa_p256_verify(pub_x, pub_y, hash_e, sig_r, sig_s) -> verdict 41// nx_ecdsa_p256_verdict_is_valid(v) -> 0|1 42// 43// All input arrays are 8-limb LE U256 buffers. Caller responsibility: 44// - hash_e is already the message hash (caller does SHA-256) 45// - hash_e bytes are interpreted as a 256-bit BE integer per 46// FIPS 186-5 §6.4.2 step 1 (use u256_load_be). 47// 48// Sealed verdict enum: 49// 50// NX_ECDSA_OK (1) signature valid 51// NX_ECDSA_BAD_R_RANGE (2) r outside [1, n-1] 52// NX_ECDSA_BAD_S_RANGE (3) s outside [1, n-1] 53// NX_ECDSA_PUBKEY_NOT_ON_CURVE (4) Q not on the curve 54// NX_ECDSA_PUBKEY_INFINITY (5) Q is infinity (degenerate) 55// NX_ECDSA_INFINITY_RESULT (6) R = u1*G + u2*Q is infinity 56// NX_ECDSA_BAD_SIG (7) v != r (sig doesn't verify) 57// 58// Per Cardinals 9 (single-responsibility -- this primitive is JUST 59// orchestration; each step has its own primitive), 12 (defensive 60// at boundaries -- range-check r, s and on-curve-check Q first), 61// 22 (composition -- 10 substrate primitives compose into one 62// verify), and 23 (preamble explains the algorithm step-by-step). 63// 64// license_tier: INDEPENDENT_REDERIVE 65// genealogy_id: international-research-sources/nist/fips_186_5 + sec_g/sec1_v2 66// lineage_id: nishi_ecdsa_p256_verify_q10 67 68// nx_safety_envelope: 69// intended_use: AUTO_APPLIED -- primitive-specific tuning queued 70// sil_target: SIL1 71// evidence: [bulk_applied_2026-05-19, ecdsa-p256-verify-orchestrator] 72// verdict: NOT_YET_EVALUATED 73 74import "nx_syscalls.nx" 75import "nx_u256.nx" 76import "nx_p256_field.nx" 77import "nx_p256_point.nx" 78import "nx_p256_point_add.nx" 79import "nx_p256_scalar_mul.nx" 80import "nx_p256_modn.nx" 81import "nx_p256_comb.nx" // fixed-base comb k*G (4.9x faster than generic) for the u1*G half of verify 82import "nx_p256_scalar_mul_wnaf.nx" // width-4 wNAF variable-base k*Q (1.33x faster) for the u2*Q half 83 84const NX_ECDSA_OK: i64 = 1 85const NX_ECDSA_BAD_R_RANGE: i64 = 2 86const NX_ECDSA_BAD_S_RANGE: i64 = 3 87const NX_ECDSA_PUBKEY_NOT_ON_CURVE: i64 = 4 88const NX_ECDSA_PUBKEY_INFINITY: i64 = 5 89const NX_ECDSA_INFINITY_RESULT: i64 = 6 90const NX_ECDSA_BAD_SIG: i64 = 7 91const NX_ECDSA_VERDICT_N: i64 = 8 92 93func nx_ecdsa_p256_verdict_is_valid(v: i64) -> i64 { 94 if v < NX_ECDSA_OK { return 0 } 95 if v >= NX_ECDSA_VERDICT_N { return 0 } 96 return 1 97} 98 99// Cached fixed-base comb table for G (2026-07-02). Built ONCE (lazily, first verify) into 100// PERSISTENT mmap memory (NOT scratch -> survives every nx_scratch_restore), reused across all 101// verifies. p256_scalar_mul_base(...,table) is proven == generic p256_scalar_mul(k,G) 102// (nx_p256_comb_test + nx_p256_comb_bench 64 scalars) and ~4.9x faster -> the u1*G half of verify. 103// Fork-per-connection server: each process builds its own once (a benign one-time cost + no race). 104static _g_p256_comb: i64 105func _p256_comb_table() -> *i64 { 106 if _g_p256_comb == 0 { 107 let t: *i64 = (sys_mmap(NX_P256_COMB_BYTES)) as *i64 108 p256_comb_build(t) 109 _g_p256_comb = t as i64 110 } 111 return _g_p256_comb as *i64 112} 113 114// Verify an ECDSA-P256 signature. 115// 116// Returns NX_ECDSA_OK on valid signature, or one of the 117// NX_ECDSA_* non-OK verdicts on any failure. 118func _nx_ecdsa_p256_verify_impl(pub_x: *i64, pub_y: *i64, 119 hash_e: *i64, 120 sig_r: *i64, sig_s: *i64) -> i64 { 121 let n: *i64 = u256_alloc() 122 p256_modn_load_n(n) 123 let one: *i64 = u256_alloc() 124 p256_modn_one(one) 125 126 // ---- Step 1: range-check r, s ---- 127 // r >= 1 128 if u256_is_zero(sig_r) == 1 { return NX_ECDSA_BAD_R_RANGE } 129 // r < n 130 if u256_cmp(sig_r, n) >= 0 { return NX_ECDSA_BAD_R_RANGE } 131 // s >= 1 132 if u256_is_zero(sig_s) == 1 { return NX_ECDSA_BAD_S_RANGE } 133 // s < n 134 if u256_cmp(sig_s, n) >= 0 { return NX_ECDSA_BAD_S_RANGE } 135 136 // ---- Step 2: pubkey on curve + not infinity ---- 137 let Q: *P256Point = p256_point_alloc() 138 p256_point_set_affine(Q, pub_x, pub_y) 139 if p256_point_is_infinity(Q) == 1 { return NX_ECDSA_PUBKEY_INFINITY } 140 if p256_point_on_curve(Q) != 1 { return NX_ECDSA_PUBKEY_NOT_ON_CURVE } 141 142 // ---- Step 3: e_n = e mod n ---- 143 let e_n: *i64 = u256_alloc() 144 p256_modn_reduce(e_n, hash_e) 145 146 // ---- Step 4: s_inv = s^(-1) mod n ---- 147 let s_inv: *i64 = u256_alloc() 148 p256_modn_inv(s_inv, sig_s) 149 150 // ---- Step 5: u1 = (e_n * s_inv) mod n ---- 151 let u1: *i64 = u256_alloc() 152 p256_modn_mul(u1, e_n, s_inv) 153 154 // ---- Step 6: u2 = (r * s_inv) mod n ---- 155 let u2: *i64 = u256_alloc() 156 p256_modn_mul(u2, sig_r, s_inv) 157 158 // ---- Step 7: R = u1*G + u2*Q ---- 159 let G: *P256Point = p256_point_alloc() 160 p256_point_load_g(G) 161 162 let u1G: *P256Point = p256_point_alloc() 163 let u2Q: *P256Point = p256_point_alloc() 164 p256_scalar_mul_base(u1G, u1, _p256_comb_table()) // fixed-base comb (~4.9x faster than generic) 165 p256_scalar_mul_wnaf(u2Q, u2, Q) // width-4 wNAF (~1.33x faster than generic) 166 167 let R: *P256Point = p256_point_alloc() 168 p256_point_add(R, u1G, u2Q) 169 170 // ---- Step 8: reject if R is infinity ---- 171 if p256_point_is_infinity(R) == 1 { return NX_ECDSA_INFINITY_RESULT } 172 173 // ---- Step 9: v = x_R mod n ---- 174 p256_point_to_affine(R) 175 let v: *i64 = u256_alloc() 176 p256_modn_reduce(v, R.x) 177 178 // ---- Step 10: accept iff v == r ---- 179 if p256_modn_eq(v, sig_r) == 1 { return NX_ECDSA_OK } 180 return NX_ECDSA_BAD_SIG 181} 182 183// Public entry: frame the whole verify so every scratch temporary 184// (across all ~9 early-return reject paths in the impl) is reclaimed 185// in O(1) on return. The verdict is an i64 value, surviving restore. 186func nx_ecdsa_p256_verify(pub_x: *i64, pub_y: *i64, 187 hash_e: *i64, 188 sig_r: *i64, sig_s: *i64) -> i64 { 189 let _fm: i64 = nx_scratch_save() 190 let v: i64 = _nx_ecdsa_p256_verify_impl(pub_x, pub_y, hash_e, sig_r, sig_s) 191 nx_scratch_restore(_fm) 192 return v 193} 194 195// Compile-only smoke. Real KAT in nx_ecdsa_p256_test.nx. 196func main() -> i64 { 197 return 0 198}