nx_p256_scalar_mul.nx source
↩ module page · 104 lines · 3738 B
1// nx_p256_scalar_mul.nx -- P-256 scalar multiplication k * P.
2//
3// Phase 0b §I.3 piece 2c of the ECDSA-P256 arc:
4// ✓ 2b. p256_point_add (190acf1f)
5// ✓ 2c. p256_scalar_mul (THIS commit)
6// - 3. p256_scalar mod n (queued)
7// - 4. ecdsa_p256 verify (queued)
8//
9// Algorithm: binary double-and-add, left-to-right (MSB-first):
10//
11// result := O (infinity)
12// for bit_pos = 255 down to 0:
13// result := double(result)
14// if bit_pos-th bit of k is set:
15// result := add(result, P)
16// return result
17//
18// Cost: 256 doublings + up to 256 adds. For a typical 256-bit
19// scalar (~128 set bits), roughly 256 doubles + 128 adds = 384
20// point ops. Each point op composes ~10-15 field ops; with our
21// slow field_mul at ~4100 limb-ops, one scalar-mult is roughly
22// ~20-25M limb-ops, or ~2-3s on qemu-riscv64-static.
23//
24// ECDSA verify needs TWO scalar mults (u1*G + u2*Q). Shamir's
25// trick (compute both via one shared doubling chain by walking
26// the bits of u1 and u2 in lockstep against a 4-element
27// precomputed point table {O, G, Q, G+Q}) is an optimization
28// queued for a follow-up. For first-cut correctness this
29// commit ships the simpler standalone scalar_mul.
30//
31// Public API:
32// p256_scalar_mul(out, k_8, p)
33// -- k_8: 8-limb 256-bit scalar (LE limb order, MUST be < n
34// in practice but no defensive check here -- caller's
35// ECDSA verify already reduces u1, u2 mod n)
36// -- p: input point (Jacobian)
37// -- out: result point (Jacobian); MAY alias p
38//
39// Edge cases handled:
40// - k == 0: returns O (infinity)
41// - p == O: returns O for any k
42// - All bits of k zero: result stays O via empty add chain
43//
44// Per Cardinals 9 (single-responsibility), 22 (composition --
45// scalar_mul is double + add iterated), 23 (preamble explains
46// variable-time vs constant-time tradeoff -- verify operates
47// on public scalars u1, u2 derived from public sig + public
48// pubkey + public msg-hash, so variable-time is safe).
49//
50// license_tier: INDEPENDENT_REDERIVE
51// genealogy_id: international-research-sources/sec_g/sec1_v2
52// lineage_id: nishi_p256_scalar_mul_q10
53
54// nx_safety_envelope:
55// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
56// sil_target: SIL1
57// evidence: [bulk_applied_2026-05-19, p256-scalar-double-and-add]
58// verdict: NOT_YET_EVALUATED
59
60import "nx_syscalls.nx"
61import "nx_u256.nx"
62import "nx_p256_field.nx"
63import "nx_p256_point.nx"
64import "nx_p256_point_add.nx"
65
66// out = k * p on the curve.
67//
68// Aliasing-safe: out may equal p (input snapshotted via copy
69// into a local).
70func p256_scalar_mul(out: *P256Point, k_8: *i64, p: *P256Point) -> i64 {
71 let _fm: i64 = nx_scratch_save()
72 // Snapshot p so out can alias p safely.
73 let base: *P256Point = p256_point_alloc()
74 p256_point_copy(base, p)
75
76 // Accumulator starts at infinity.
77 let result: *P256Point = p256_point_alloc()
78 p256_point_zero(result)
79
80 // Double-and-add, MSB-first.
81 var bit_pos: i64 = 255
82 while bit_pos >= 0 {
83 // result := 2 * result
84 p256_point_double(result, result)
85 // If k bit set: result := result + base
86 let limb_idx: i64 = bit_pos / 32
87 let bit_in_limb: i64 = bit_pos - limb_idx * 32
88 let limb: i64 = k_8[limb_idx] & 0xFFFFFFFF
89 let bit: i64 = (limb >> bit_in_limb) & 1
90 if bit == 1 {
91 p256_point_add(result, result, base)
92 }
93 bit_pos = bit_pos - 1
94 }
95
96 p256_point_copy(out, result)
97 nx_scratch_restore(_fm)
98 return 0
99}
100
101// Compile-only smoke. Real KAT in nx_p256_scalar_mul_test.nx.
102func main() -> i64 {
103 return 0
104}