nx_u256.nx source
↩ module page · 355 lines · 13460 B
1// nx_u256.nx -- 256-bit unsigned big-integer primitives.
2//
3// Phase 0b §I.3 of the Nishi TLS 1.3 stack -- foundation for the
4// ECDSA-P256 arc (which is the biggest single remaining blocker
5// for public-HTTPS-fetch per task #21). Web PKI cert chains for
6// google.com + Cloudflare + every modern CDN sign with ECDSA over
7// NIST P-256, and verifying those sigs requires:
8// 1. 256-bit big-int arithmetic (THIS primitive)
9// 2. P-256 prime-field math (queued: nx_p256_field.nx)
10// 3. P-256 curve-point math (queued: nx_p256_point.nx)
11// 4. P-256 scalar math mod n (queued: nx_p256_scalar.nx)
12// 5. ECDSA verify orchestrator (queued: nx_ecdsa_p256.nx)
13//
14// This module ships ONLY the raw unsigned 256-bit arithmetic +
15// byte-order helpers. No field reduction, no curve, no signature.
16//
17// Representation: U256 is an 8-element i64 array where each
18// element holds a 32-bit limb in its low bits and zeros in its
19// high bits. Little-endian limb order: limb[0] is the least-
20// significant 32 bits, limb[7] is the most-significant 32 bits.
21//
22// Why 8 x 32-bit limbs (not 4 x 64-bit):
23// - Avoids signed-vs-unsigned i64 comparison hell that 4-limb
24// would require for carry detection on (i64+i64) overflow.
25// - 32-bit add/sub fits in i64 without overflow, so carry can
26// be extracted with a clean (sum >> 32) & 1 instead of an
27// unsigned-compare workaround.
28// - 32-bit mul also fits in i64 (32 + 32 = 64 < 63 bits), so
29// the upcoming p256_field_mul can use standard schoolbook
30// limb-by-limb multiplication without 128-bit intermediates.
31// - Matches BoringSSL's u32-limb P-256 implementation, which is
32// the modern reference for non-vector platforms.
33//
34// Byte-order: X.509 / TLS / DER carry integers BIG-ENDIAN. All
35// load/store helpers convert between BE byte buffers and our
36// little-endian limb layout.
37//
38// What this primitive does:
39// - u256_zero / u256_one / u256_copy / u256_alloc
40// - u256_load_be (32-byte BE -> 8-limb LE)
41// - u256_store_be (8-limb LE -> 32-byte BE)
42// - u256_add_with_carry (returns carry-out 0|1)
43// - u256_sub_with_borrow (returns borrow-out 0|1)
44// - u256_cmp (returns -1, 0, +1)
45// - u256_is_zero (returns 0|1)
46// - u256_eq (returns 0|1)
47//
48// What it does NOT do (queued for subsequent commits):
49// - Multiplication (composes ADD via schoolbook; ships with
50// nx_p256_field.nx since multiplication-with-reduction is the
51// only practical mode for P-256)
52// - Modular inverse, modular squaring (field-specific)
53// - Variable-time vs constant-time differentiation -- this
54// module ships constant-time PRIMITIVES (no early returns
55// from cmp / no input-dependent branches in add/sub), but
56// the downstream verify is naturally variable-time since
57// ECDSA verify takes only public inputs.
58//
59// Per Cardinal 9 (single-responsibility), each function does ONE
60// thing. Per Cardinal 12 (defensive at boundaries), every store
61// validates the destination size; loads assume 32 bytes since
62// that's the contract (caller responsibility).
63//
64// license_tier: INDEPENDENT_REDERIVE
65// genealogy_id: international-research-sources/nist/fips_186_5 + ietf/rfc_5480
66// lineage_id: nishi_u256_primitives_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, u256-foundation-for-p256]
72// verdict: NOT_YET_EVALUATED
73
74import "nx_syscalls.nx"
75
76const NX_U256_LIMBS: i64 = 8
77const NX_U256_BYTES: i64 = 32
78const NX_U256_LIMB_BITS: i64 = 32
79const NX_U256_LIMB_MASK: i64 = 0xFFFFFFFF
80
81// --- u256 scratch arena (bump allocator) ---------------------------
82//
83// Crypto temporaries used to sys_mmap one page PER allocation
84// (u256_alloc, u256_wide_alloc, the Solinas reduce scratch, point
85// structs). A single P-256 scalar-mult composes ~384 point ops x
86// ~10-15 field ops x ~3-4 allocations = tens of thousands of mmap
87// syscalls, which both dominated the runtime AND crashed at high
88// iteration counts (vm.max_map_count). We replace per-op mmap with
89// ONE arena + a bump pointer; a caller reclaims a whole frame of
90// temporaries in O(1) via nx_scratch_save / nx_scratch_restore.
91//
92// Safety invariant (already honoured throughout the P-256 code):
93// every routine writes its result ONLY into caller-provided pointers
94// (which live below its own frame mark) and allocates temporaries
95// from this arena, so restoring the mark on exit reclaims the
96// temporaries without ever touching a live output. The only
97// functions that return a pointer (u256_alloc / u256_wide_alloc /
98// p256_point_alloc) are NOT framed -- their results persist in the
99// caller's frame. See NX_PITWALL_MEASURED_BOARD lever #1.
100// CHAINED-BLOCK arena: grows by mmap'ing fixed 1 MiB blocks on demand
101// rather than capping at one block. This matters because not every
102// u256 consumer is framed -- an un-framed routine (e.g. x509 validate
103// paths that accumulate scratch without a save/restore) must DEGRADE
104// like the old per-op-mmap leak (grow as needed), NOT hard-fail at a
105// fixed cap. Framed callers stay bounded: restore rewinds the virtual
106// cursor and the already-mmap'd blocks are reused (re-zeroed on reuse),
107// so the high-water block count is the deepest framed footprint, while
108// un-framed accumulation just mmaps more 1 MiB blocks (MiB-chunked, ~no
109// syscalls after warmup) -- strictly safer than both the old per-op
110// mmap and a fixed cap. The virtual cursor (contiguous byte address
111// over the block sequence) is the single-i64 frame mark.
112const NX_SCRATCH_BLOCK: i64 = 1048576 // 1 MiB per block
113const NX_SCRATCH_MAXBLOCKS: i64 = 8192 // 8 GiB ceiling (pathological-leak backstop only)
114
115static NX_SCRATCH_BLOCKS: i64 // addr of i64[NX_SCRATCH_MAXBLOCKS] (block base addrs); 0 = uninit
116static NX_SCRATCH_NBLOCKS: i64 // blocks mmap'd so far
117static NX_SCRATCH_CUR: i64 // virtual cursor (bytes): block = CUR/BLOCK, in-block = CUR%BLOCK
118
119func nx_scratch_init() -> i64 {
120 if NX_SCRATCH_BLOCKS == 0 {
121 let arr: *u8 = sys_mmap(NX_SCRATCH_MAXBLOCKS * 8)
122 NX_SCRATCH_BLOCKS = arr as i64
123 let blocks: *i64 = NX_SCRATCH_BLOCKS as *i64
124 let b0: *u8 = sys_mmap(NX_SCRATCH_BLOCK)
125 blocks[0] = b0 as i64
126 NX_SCRATCH_NBLOCKS = 1
127 NX_SCRATCH_CUR = 0
128 }
129 return 0
130}
131
132// Loud-fail ONLY on a pathological condition (single alloc bigger than a
133// whole block, or the 8 GiB block-table ceiling = a genuine runaway
134// leak) -- NEVER on ordinary growth. No silent-wrong.
135func nx_scratch_oom(msg: *u8, mlen: i64) -> i64 {
136 sys_write(2, msg, mlen)
137 sys_exit(231)
138 return 0
139}
140
141// Allocate n bytes (rounded up to 8) from the chained arena, zeroed.
142func nx_scratch(n: i64) -> *u8 {
143 nx_scratch_init()
144 let aligned: i64 = ((n + 7) / 8) * 8
145 if aligned > NX_SCRATCH_BLOCK {
146 nx_scratch_oom("FATAL: u256 scratch alloc exceeds block size\n" as *u8, 45)
147 }
148 var bi: i64 = NX_SCRATCH_CUR / NX_SCRATCH_BLOCK
149 var off: i64 = NX_SCRATCH_CUR - bi * NX_SCRATCH_BLOCK
150 if off + aligned > NX_SCRATCH_BLOCK { // won't fit this block -> next block
151 bi = bi + 1
152 off = 0
153 NX_SCRATCH_CUR = bi * NX_SCRATCH_BLOCK
154 }
155 let blocks: *i64 = NX_SCRATCH_BLOCKS as *i64
156 while NX_SCRATCH_NBLOCKS <= bi { // grow: mmap blocks up to bi (reuses after restore)
157 if NX_SCRATCH_NBLOCKS >= NX_SCRATCH_MAXBLOCKS {
158 nx_scratch_oom("FATAL: u256 scratch arena hit block ceiling (leak?)\n" as *u8, 52)
159 }
160 let nb: *u8 = sys_mmap(NX_SCRATCH_BLOCK)
161 blocks[NX_SCRATCH_NBLOCKS] = nb as i64
162 NX_SCRATCH_NBLOCKS = NX_SCRATCH_NBLOCKS + 1
163 }
164 let addr: i64 = blocks[bi] + off
165 NX_SCRATCH_CUR = bi * NX_SCRATCH_BLOCK + off + aligned
166 let pw: *i64 = addr as *i64
167 let words: i64 = aligned / 8
168 var i: i64 = 0
169 while i < words {
170 pw[i] = 0
171 i = i + 1
172 }
173 return addr as *u8
174}
175
176// LIFO frame: save returns the current virtual cursor; restore rewinds
177// to it, reclaiming every allocation since (blocks stay mmap'd + reused).
178func nx_scratch_save() -> i64 {
179 nx_scratch_init()
180 return NX_SCRATCH_CUR
181}
182
183func nx_scratch_restore(mark: i64) -> i64 {
184 NX_SCRATCH_CUR = mark
185 return 0
186}
187
188// Allocate an 8-limb buffer. Caller treats as *i64; each i64
189// holds a 32-bit limb in its low bits. All allocations zeroed.
190func u256_alloc() -> *i64 {
191 return (nx_scratch(NX_U256_LIMBS * 8)) as *i64
192}
193
194// out = 0
195func u256_zero(out: *i64) -> i64 {
196 var i: i64 = 0
197 while i < NX_U256_LIMBS {
198 out[i] = 0
199 i = i + 1
200 }
201 return 0
202}
203
204// out = 1
205func u256_one(out: *i64) -> i64 {
206 u256_zero(out)
207 out[0] = 1
208 return 0
209}
210
211// out = src (element-wise copy)
212func u256_copy(out: *i64, src: *i64) -> i64 {
213 var i: i64 = 0
214 while i < NX_U256_LIMBS {
215 out[i] = src[i]
216 i = i + 1
217 }
218 return 0
219}
220
221// Load a 32-byte BIG-ENDIAN integer into our little-endian limb
222// layout. bytes[0] is the most-significant byte (per DER); our
223// limb[7] is the most-significant limb.
224//
225// Layout mapping: bytes[i*4 .. i*4+3] map BE to limb[7-i] for
226// i in 0..8. Inside each 4-byte group: bytes[i*4] is the high
227// byte of the limb (BE), bytes[i*4+3] is the low byte.
228func u256_load_be(out: *i64, bytes: *u8) -> i64 {
229 var i: i64 = 0
230 while i < NX_U256_LIMBS {
231 let off: i64 = i * 4
232 let limb_idx: i64 = NX_U256_LIMBS - 1 - i
233 let b0: i64 = bytes[off] & 0xff
234 let b1: i64 = bytes[off + 1] & 0xff
235 let b2: i64 = bytes[off + 2] & 0xff
236 let b3: i64 = bytes[off + 3] & 0xff
237 out[limb_idx] = (b0 << 24) | (b1 << 16) | (b2 << 8) | b3
238 i = i + 1
239 }
240 return 0
241}
242
243// Store our little-endian limb layout to 32-byte BIG-ENDIAN bytes.
244// Inverse of u256_load_be.
245func u256_store_be(bytes: *u8, src: *i64) -> i64 {
246 var i: i64 = 0
247 while i < NX_U256_LIMBS {
248 let off: i64 = i * 4
249 let limb_idx: i64 = NX_U256_LIMBS - 1 - i
250 let limb: i64 = src[limb_idx]
251 bytes[off] = ((limb >> 24) & 0xff) as u8
252 bytes[off + 1] = ((limb >> 16) & 0xff) as u8
253 bytes[off + 2] = ((limb >> 8) & 0xff) as u8
254 bytes[off + 3] = (limb & 0xff) as u8
255 i = i + 1
256 }
257 return 0
258}
259
260// Schoolbook add with carry propagation across the 8 limbs.
261// Returns the final carry-out (0 or 1). Aliasing safe:
262// (out, a, b) may share buffers (the read of a[i]+b[i] happens
263// before the write of out[i]).
264func u256_add_with_carry(out: *i64, a: *i64, b: *i64) -> i64 {
265 var i: i64 = 0
266 var carry: i64 = 0
267 while i < NX_U256_LIMBS {
268 let s: i64 = (a[i] & NX_U256_LIMB_MASK) + (b[i] & NX_U256_LIMB_MASK) + carry
269 out[i] = s & NX_U256_LIMB_MASK
270 carry = (s >> NX_U256_LIMB_BITS) & 1
271 i = i + 1
272 }
273 return carry
274}
275
276// Schoolbook subtract with borrow propagation. out = a - b.
277// Returns the final borrow-out (0 if a >= b, 1 if a < b in u256).
278// Two's-complement-style on each 32-bit limb: borrow is the high
279// bit of the 33-bit intermediate (a - b - prev_borrow).
280func u256_sub_with_borrow(out: *i64, a: *i64, b: *i64) -> i64 {
281 var i: i64 = 0
282 var borrow: i64 = 0
283 while i < NX_U256_LIMBS {
284 // Compute as 33-bit signed: (a[i] - b[i] - borrow) lies in
285 // [-(2^32 + 1), 2^32 - 1]. If negative, add 2^32 to wrap
286 // into a 32-bit limb and propagate borrow=1.
287 let d: i64 = (a[i] & NX_U256_LIMB_MASK) - (b[i] & NX_U256_LIMB_MASK) - borrow
288 if d < 0 {
289 out[i] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK
290 borrow = 1
291 } else {
292 out[i] = d & NX_U256_LIMB_MASK
293 borrow = 0
294 }
295 i = i + 1
296 }
297 return borrow
298}
299
300// Unsigned compare. Returns -1 if a < b, 0 if a == b, +1 if a > b.
301// Walks limbs MSB-first; data-dependent return is intentional for
302// this primitive (every U256 use site is on public-input data).
303func u256_cmp(a: *i64, b: *i64) -> i64 {
304 var i: i64 = NX_U256_LIMBS - 1
305 while i >= 0 {
306 let av: i64 = a[i] & NX_U256_LIMB_MASK
307 let bv: i64 = b[i] & NX_U256_LIMB_MASK
308 if av < bv { return 0 - 1 }
309 if av > bv { return 1 }
310 i = i - 1
311 }
312 return 0
313}
314
315// Returns 1 if a == 0, 0 otherwise.
316func u256_is_zero(a: *i64) -> i64 {
317 var i: i64 = 0
318 var acc: i64 = 0
319 while i < NX_U256_LIMBS {
320 acc = acc | (a[i] & NX_U256_LIMB_MASK)
321 i = i + 1
322 }
323 if acc == 0 { return 1 }
324 return 0
325}
326
327// Constant-time conditional MOVE: dst = (flag==1) ? src : dst. Branchless (mask = 0-flag),
328// the u256 twin of fe_cmov -- the foundation primitive for constant-time P-256 field reductions
329// (SEC-CT-001). src is never mutated. flag MUST be 0 or 1.
330func u256_cmov(dst: *i64, src: *i64, flag: i64) -> i64 {
331 let mask: i64 = 0 - flag
332 var i: i64 = 0
333 while i < NX_U256_LIMBS {
334 dst[i] = dst[i] ^ (mask & (dst[i] ^ src[i]))
335 i = i + 1
336 }
337 return 0
338}
339
340// Returns 1 if a == b, 0 otherwise.
341func u256_eq(a: *i64, b: *i64) -> i64 {
342 var i: i64 = 0
343 var diff: i64 = 0
344 while i < NX_U256_LIMBS {
345 diff = diff | ((a[i] ^ b[i]) & NX_U256_LIMB_MASK)
346 i = i + 1
347 }
348 if diff == 0 { return 1 }
349 return 0
350}
351
352// Compile-only smoke. Real KAT in nx_u256_test.nx.
353func main() -> i64 {
354 return 0
355}