nx_p256_field_mul.nx source
↩ module page · 308 lines · 12743 B
1// nx_p256_field_mul.nx -- P-256 prime field multiplication.
2//
3// Phase 0b §I.3 piece 1c of the ECDSA-P256 arc. Composes:
4// - u256_mul_wide (commit ddb0994a) for the 256x256 -> 512
5// - NIST P-256 Solinas fast reduction mod p (THIS version)
6//
7// FAST REDUCTION (Solinas, FIPS 186-4 / Hankerson Alg. 2.29):
8// p = 2^256 - 2^224 + 2^192 + 2^96 - 1 has a special form that lets
9// the 512-bit product be reduced with a fixed sequence of 32-bit-word
10// permutations + a handful of 256-bit add/sub, instead of the
11// bit-serial 257-iteration long division. ~10-15x fewer limb ops.
12//
13// Given product words c0..c15 (c0 = least significant 32-bit word):
14// s1 = (c7,c6,c5,c4,c3,c2,c1,c0)
15// s2 = (c15,c14,c13,c12,c11, 0, 0, 0)
16// s3 = ( 0,c15,c14,c13,c12, 0, 0, 0)
17// s4 = (c15,c14, 0, 0, 0,c10,c9,c8)
18// s5 = (c8,c13,c15,c14,c13,c11,c10,c9)
19// s6 = (c10,c8, 0, 0, 0,c13,c12,c11)
20// s7 = (c11,c9, 0, 0,c15,c14,c13,c12)
21// s8 = (c12, 0,c10,c9,c8,c15,c14,c13)
22// s9 = (c13, 0,c11,c10,c9, 0,c15,c14)
23// r = s1 + 2*s2 + 2*s3 + s4 + s5 - s6 - s7 - s8 - s9 (mod p)
24// (tuples are (word7..word0); word7 is the most significant.)
25//
26// The previous bit-serial reducer is RETAINED as p256_field_mul_slow:
27// it is the trivially-correct gold-standard ORACLE the fast path is
28// validated against (nx_p256_field_mul_oracle_test.nx checks
29// fast == slow over many random inputs). Per Cardinals 13 + 25:
30// additive -- the reference is never stripped.
31//
32// Public API:
33// u256_wide_shr_1(buf) -- in-place 1-bit right shift
34// u256_wide_sub(out, a, b) -- 16-limb subtract w/ borrow
35// p256_field_mul(out, a, b) -- (a*b) mod p, canonical (FAST)
36// p256_field_mul_slow(out, a, b) -- (a*b) mod p, canonical (oracle)
37// p256_field_sq(out, a) -- (a*a) mod p, canonical
38//
39// Aliasing: out MAY alias a or b (computation uses fresh scratch).
40//
41// license_tier: INDEPENDENT_REDERIVE
42// genealogy_id: international-research-sources/nist/fips_186_5
43// lineage_id: nishi_p256_field_mul_q10
44
45import "nx_syscalls.nx"
46import "nx_u256.nx"
47import "nx_u256_mul.nx"
48import "nx_p256_field.nx"
49
50// In-place 1-bit right shift on a 16-limb wide buffer.
51func u256_wide_shr_1(buf: *i64) -> i64 {
52 var i: i64 = NX_U256_WIDE_LIMBS - 1
53 var carry: i64 = 0
54 while i >= 0 {
55 let v: i64 = buf[i] & NX_U256_LIMB_MASK
56 let new_carry: i64 = v & 1
57 buf[i] = ((v >> 1) | (carry << (NX_U256_LIMB_BITS - 1))) & NX_U256_LIMB_MASK
58 carry = new_carry
59 i = i - 1
60 }
61 return 0
62}
63
64// 16-limb subtract with borrow. out = a - b mod 2^512. Returns borrow.
65func u256_wide_sub(out: *i64, a: *i64, b: *i64) -> i64 {
66 var i: i64 = 0
67 var borrow: i64 = 0
68 while i < NX_U256_WIDE_LIMBS {
69 let d: i64 = (a[i] & NX_U256_LIMB_MASK) - (b[i] & NX_U256_LIMB_MASK) - borrow
70 if d < 0 {
71 out[i] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK
72 borrow = 1
73 } else {
74 out[i] = d & NX_U256_LIMB_MASK
75 borrow = 0
76 }
77 i = i + 1
78 }
79 return borrow
80}
81
82// ----- Solinas reduction helpers (9-limb signed-free accumulators) -----
83
84// Add a 32-bit value `val` into 9-limb accumulator `acc` at limb `L`,
85// propagating carry upward. acc limbs are 32-bit; acc[8] is the top.
86func _r_addw(acc: *i64, L: i64, val: i64) -> i64 {
87 var i: i64 = L
88 var carry: i64 = val & NX_U256_LIMB_MASK
89 while carry != 0 {
90 if i > 8 { carry = 0 } else {
91 let v: i64 = (acc[i] & NX_U256_LIMB_MASK) + carry
92 acc[i] = v & NX_U256_LIMB_MASK
93 carry = v >> NX_U256_LIMB_BITS
94 i = i + 1
95 }
96 }
97 return 0
98}
99
100// Compare two 8-limb values: 1 if a>b, 0 if eq, -1 if a<b.
101func _r_cmp8(a: *i64, b: *i64) -> i64 {
102 var i: i64 = NX_U256_LIMBS - 1
103 while i >= 0 {
104 let av: i64 = a[i] & NX_U256_LIMB_MASK
105 let bv: i64 = b[i] & NX_U256_LIMB_MASK
106 if av > bv { return 1 }
107 if av < bv { return 0 - 1 }
108 i = i - 1
109 }
110 return 0
111}
112
113// Reduce a 9-limb accumulator mod p in place (result in low 8 limbs,
114// acc[8] becomes 0). acc < ~7p, so a bounded subtract loop suffices.
115func _r_reduce9(acc: *i64, p: *i64) -> i64 {
116 var guard: i64 = 0
117 while guard < 20 {
118 var ge: i64 = 0
119 if (acc[8] & NX_U256_LIMB_MASK) > 0 { ge = 1 } else {
120 var c: i64 = 0
121 var i: i64 = NX_U256_LIMBS - 1
122 while i >= 0 {
123 let av: i64 = acc[i] & NX_U256_LIMB_MASK
124 let pv: i64 = p[i] & NX_U256_LIMB_MASK
125 if c == 0 {
126 if av > pv { c = 1 } else { if av < pv { c = 0 - 1 } }
127 }
128 i = i - 1
129 }
130 if c >= 0 { ge = 1 }
131 }
132 if ge == 0 { guard = 20 } else {
133 var borrow: i64 = 0
134 var j: i64 = 0
135 while j < NX_U256_LIMBS {
136 let d: i64 = (acc[j] & NX_U256_LIMB_MASK) - (p[j] & NX_U256_LIMB_MASK) - borrow
137 if d < 0 {
138 acc[j] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK
139 borrow = 1
140 } else {
141 acc[j] = d & NX_U256_LIMB_MASK
142 borrow = 0
143 }
144 j = j + 1
145 }
146 acc[8] = (acc[8] & NX_U256_LIMB_MASK) - borrow
147 guard = guard + 1
148 }
149 }
150 return 0
151}
152
153// out8 = c (16-limb product) mod p, via Solinas reduction.
154func _p256_solinas_reduce(out8: *i64, c: *i64) -> i64 {
155 let p: *i64 = u256_alloc()
156 p256_field_load_p(p)
157 // scratch: POS = sc[0..8], NEG = sc[9..17] (two 9-limb accumulators)
158 // Arena scratch (reclaimed by the enclosing p256_field_mul frame).
159 let sc: *i64 = (nx_scratch(18 * 8)) as *i64
160 var z: i64 = 0
161 while z < 18 { sc[z] = 0; z = z + 1 }
162 let POS: *i64 = sc
163 let NEG: *i64 = (sc as i64 + 9 * 8) as *i64
164
165 let c0: i64 = c[0] & NX_U256_LIMB_MASK
166 let c1: i64 = c[1] & NX_U256_LIMB_MASK
167 let c2: i64 = c[2] & NX_U256_LIMB_MASK
168 let c3: i64 = c[3] & NX_U256_LIMB_MASK
169 let c4: i64 = c[4] & NX_U256_LIMB_MASK
170 let c5: i64 = c[5] & NX_U256_LIMB_MASK
171 let c6: i64 = c[6] & NX_U256_LIMB_MASK
172 let c7: i64 = c[7] & NX_U256_LIMB_MASK
173 let c8: i64 = c[8] & NX_U256_LIMB_MASK
174 let c9: i64 = c[9] & NX_U256_LIMB_MASK
175 let c10: i64 = c[10] & NX_U256_LIMB_MASK
176 let c11: i64 = c[11] & NX_U256_LIMB_MASK
177 let c12: i64 = c[12] & NX_U256_LIMB_MASK
178 let c13: i64 = c[13] & NX_U256_LIMB_MASK
179 let c14: i64 = c[14] & NX_U256_LIMB_MASK
180 let c15: i64 = c[15] & NX_U256_LIMB_MASK
181
182 // DEFERRED-CARRY accumulation (2026-07-02): identical S-term table as the prior ~60 _r_addw
183 // calls, but each POS/NEG limb is summed WIDE (64-bit, max ~6*(2^32-1) < 2^35, no overflow) with
184 // plain array adds -- NO function calls, NO per-add carry propagation -- then normalized ONCE
185 // below. Bit-exact vs the _r_addw path (nx_p256_solinas_fast_difftest 5000/5000) + still guarded
186 // by the bit-serial oracle (nx_p256_solinas_difftest 3716/3716). ~1.7x faster reduce.
187 POS[0]=c0; POS[1]=c1; POS[2]=c2; POS[3]=c3; POS[4]=c4; POS[5]=c5; POS[6]=c6; POS[7]=c7; POS[8]=0
188 POS[3]=POS[3]+c11+c11; POS[4]=POS[4]+c12+c12; POS[5]=POS[5]+c13+c13; POS[6]=POS[6]+c14+c14; POS[7]=POS[7]+c15+c15
189 POS[3]=POS[3]+c12+c12; POS[4]=POS[4]+c13+c13; POS[5]=POS[5]+c14+c14; POS[6]=POS[6]+c15+c15
190 POS[0]=POS[0]+c8; POS[1]=POS[1]+c9; POS[2]=POS[2]+c10; POS[6]=POS[6]+c14; POS[7]=POS[7]+c15
191 POS[0]=POS[0]+c9; POS[1]=POS[1]+c10; POS[2]=POS[2]+c11; POS[3]=POS[3]+c13; POS[4]=POS[4]+c14; POS[5]=POS[5]+c15; POS[6]=POS[6]+c13; POS[7]=POS[7]+c8
192 NEG[0]=c11; NEG[1]=c12; NEG[2]=c13; NEG[3]=0; NEG[4]=0; NEG[5]=0; NEG[6]=c8; NEG[7]=c10; NEG[8]=0
193 NEG[0]=NEG[0]+c12; NEG[1]=NEG[1]+c13; NEG[2]=NEG[2]+c14; NEG[3]=NEG[3]+c15; NEG[6]=NEG[6]+c9; NEG[7]=NEG[7]+c11
194 NEG[0]=NEG[0]+c13; NEG[1]=NEG[1]+c14; NEG[2]=NEG[2]+c15; NEG[3]=NEG[3]+c8; NEG[4]=NEG[4]+c9; NEG[5]=NEG[5]+c10; NEG[7]=NEG[7]+c12
195 NEG[0]=NEG[0]+c14; NEG[1]=NEG[1]+c15; NEG[3]=NEG[3]+c9; NEG[4]=NEG[4]+c10; NEG[5]=NEG[5]+c11; NEG[7]=NEG[7]+c13
196 var _cr: i64 = 0; var _ni: i64 = 0
197 while _ni < 9 { let _t: i64 = POS[_ni] + _cr; POS[_ni] = _t & NX_U256_LIMB_MASK; _cr = _t >> NX_U256_LIMB_BITS; _ni = _ni + 1 }
198 _cr = 0; _ni = 0
199 while _ni < 9 { let _t: i64 = NEG[_ni] + _cr; NEG[_ni] = _t & NX_U256_LIMB_MASK; _cr = _t >> NX_U256_LIMB_BITS; _ni = _ni + 1 }
200
201 // Reduce POS and NEG to canonical [0,p).
202 _r_reduce9(POS, p)
203 _r_reduce9(NEG, p)
204
205 // out = (POS - NEG) mod p.
206 if _r_cmp8(POS, NEG) >= 0 {
207 var borrow: i64 = 0
208 var j: i64 = 0
209 while j < NX_U256_LIMBS {
210 let d: i64 = (POS[j] & NX_U256_LIMB_MASK) - (NEG[j] & NX_U256_LIMB_MASK) - borrow
211 if d < 0 { out8[j] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK; borrow = 1 }
212 else { out8[j] = d & NX_U256_LIMB_MASK; borrow = 0 }
213 j = j + 1
214 }
215 } else {
216 // out = POS + p - NEG (in (0,p) since POS < NEG < p)
217 let t: *i64 = (nx_scratch(9 * 8)) as *i64
218 var z2: i64 = 0
219 while z2 < 9 { t[z2] = 0; z2 = z2 + 1 }
220 var carry: i64 = 0
221 var k: i64 = 0
222 while k < NX_U256_LIMBS {
223 let v: i64 = (POS[k] & NX_U256_LIMB_MASK) + (p[k] & NX_U256_LIMB_MASK) + carry
224 t[k] = v & NX_U256_LIMB_MASK
225 carry = v >> NX_U256_LIMB_BITS
226 k = k + 1
227 }
228 t[8] = carry
229 var borrow: i64 = 0
230 var j: i64 = 0
231 while j < NX_U256_LIMBS {
232 let d: i64 = (t[j] & NX_U256_LIMB_MASK) - (NEG[j] & NX_U256_LIMB_MASK) - borrow
233 if d < 0 { t[j] = (d + (1 << NX_U256_LIMB_BITS)) & NX_U256_LIMB_MASK; borrow = 1 }
234 else { t[j] = d & NX_U256_LIMB_MASK; borrow = 0 }
235 j = j + 1
236 }
237 t[8] = (t[8] & NX_U256_LIMB_MASK) - borrow
238 _r_reduce9(t, p)
239 var m: i64 = 0
240 while m < NX_U256_LIMBS { out8[m] = t[m] & NX_U256_LIMB_MASK; m = m + 1 }
241 }
242 return 0
243}
244
245// out_8 = c (16-limb 512-bit product) mod p, via the FAST Solinas path.
246// PUBLIC entry point onto the exact _p256_solinas_reduce production code so
247// the reduction can be differentially validated against a bit-serial oracle
248// on ARBITRARY 512-bit inputs (not only a*b products) -- see
249// nx_p256_solinas_difftest.nx. Purely ADDITIVE: it changes NO existing
250// logic and does not alter p256_field_mul. Frames its own scratch (mirrors
251// p256_field_mul) so the reducer's temporaries are reclaimed on return;
252// out_8 and c_16 are caller buffers below the frame mark, never touched by
253// the restore. Aliasing: out_8 must be distinct from c_16.
254func p256_field_reduce_solinas(out_8: *i64, c_16: *i64) -> i64 {
255 let _fm: i64 = nx_scratch_save()
256 _p256_solinas_reduce(out_8, c_16)
257 nx_scratch_restore(_fm)
258 return 0
259}
260
261// out_8 = (a * b) mod p (FAST Solinas path). out may alias a or b.
262func p256_field_mul(out_8: *i64, a: *i64, b: *i64) -> i64 {
263 let _fm: i64 = nx_scratch_save()
264 let c: *i64 = u256_wide_alloc()
265 // G3 MEASURED: u256_mul_wide_4x64 (now using the native __adc_acc carry) is
266 // byte-exact (nx_u256_mul4_fuzz) but 17% SLOWER than 8x32 (interleaved 546 vs
267 // 463ms) -- __adc_acc forces the 3-word accumulator into MEMORY (6 mem ops /
268 // partial product), costing more than the native carry saves vs the software
269 // version's REGISTER accumulator. The win needs Phase-2 maax: the whole
270 // multiply as one contiguous MULX+ADCX+ADOX block keeping the accumulator in
271 // registers. Stays on 8x32. Bench: runtime/nx_p256_fieldmul_bench.nx.
272 u256_mul_wide(c, a, b)
273 _p256_solinas_reduce(out_8, c)
274 nx_scratch_restore(_fm)
275 return 0
276}
277
278// out_8 = (a * b) mod p (SLOW bit-serial path; gold-standard oracle).
279func p256_field_mul_slow(out_8: *i64, a: *i64, b: *i64) -> i64 {
280 let _fm: i64 = nx_scratch_save()
281 let c: *i64 = u256_wide_alloc()
282 let shifted_p: *i64 = u256_wide_alloc()
283 let p: *i64 = u256_alloc()
284 p256_field_load_p(p)
285 u256_mul_wide(c, a, b)
286 var i: i64 = 0
287 while i < NX_U256_WIDE_LIMBS { shifted_p[i] = 0; i = i + 1 }
288 i = 0
289 while i < NX_U256_LIMBS { shifted_p[i + 8] = p[i]; i = i + 1 }
290 var k: i64 = 0
291 while k < 257 {
292 if u256_wide_cmp(c, shifted_p) >= 0 { u256_wide_sub(c, c, shifted_p) }
293 u256_wide_shr_1(shifted_p)
294 k = k + 1
295 }
296 u256_wide_copy_low(out_8, c)
297 nx_scratch_restore(_fm)
298 return 0
299}
300
301// out = (a * a) mod p.
302func p256_field_sq(out: *i64, a: *i64) -> i64 {
303 return p256_field_mul(out, a, a)
304}
305
306func main() -> i64 {
307 return 0
308}