nx_p384_modn.nx source
↩ module page · 227 lines · 6343 B
1// nx_p384_modn.nx -- NIST P-384 scalar arithmetic mod n.
2//
3// n = 0xffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
4// c7634d81 f4372ddf 581a0db2 48b0a77a ecec196a ccc52973
5//
6// (FIPS 186-5 D.1.2.4 -- order of the P-384 base point G).
7//
8// Mirror of nx_p256_modn.nx on the 12-limb / 384-bit path.
9// Same shape -- add / sub / neg / reduce / mul / sq / inv, all
10// mod n. Bit-by-bit shift-and-subtract reduction for mul (mirror
11// of p384_field_mul approach -- portable, no Solinas).
12//
13// API:
14// p384_modn_load_n(out)
15// p384_modn_load_n_minus_2(out)
16// p384_modn_zero / one / copy / eq (wrappers over u384_*)
17// p384_modn_add(r, a, b) r = (a + b) mod n
18// p384_modn_sub(r, a, b) r = (a - b) mod n
19// p384_modn_neg(r, a) r = (-a) mod n
20// p384_modn_reduce(r, a) r = a mod n (single-subtract)
21// p384_modn_mul(out_12, a, b) out = (a * b) mod n
22// p384_modn_sq(out, a) out = (a * a) mod n
23// p384_modn_inv(out, a) out = a^(-1) mod n (Fermat)
24//
25// license_tier: INDEPENDENT_REDERIVE
26// genealogy_id: international-research-sources/nist/fips_186_5
27// lineage_id: nishi_p384_modn_q10
28
29// nx_safety_envelope:
30// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
31// sil_target: SIL1
32// evidence: [bulk_applied_2026-05-20, p384-modn-arithmetic]
33// verdict: NOT_YET_EVALUATED
34
35import "nx_syscalls.nx"
36import "nx_u384.nx"
37import "nx_u384_mul.nx"
38
39// Write n into out (12 limbs, LE order).
40func p384_modn_load_n(out: *i64) -> i64 {
41 out[0] = 0xCCC52973
42 out[1] = 0xECEC196A
43 out[2] = 0x48B0A77A
44 out[3] = 0x581A0DB2
45 out[4] = 0xF4372DDF
46 out[5] = 0xC7634D81
47 out[6] = 0xFFFFFFFF
48 out[7] = 0xFFFFFFFF
49 out[8] = 0xFFFFFFFF
50 out[9] = 0xFFFFFFFF
51 out[10] = 0xFFFFFFFF
52 out[11] = 0xFFFFFFFF
53 return 0
54}
55
56// Write n-2 into out. Differs from n only in LSB limb.
57func p384_modn_load_n_minus_2(out: *i64) -> i64 {
58 out[0] = 0xCCC52971
59 out[1] = 0xECEC196A
60 out[2] = 0x48B0A77A
61 out[3] = 0x581A0DB2
62 out[4] = 0xF4372DDF
63 out[5] = 0xC7634D81
64 out[6] = 0xFFFFFFFF
65 out[7] = 0xFFFFFFFF
66 out[8] = 0xFFFFFFFF
67 out[9] = 0xFFFFFFFF
68 out[10] = 0xFFFFFFFF
69 out[11] = 0xFFFFFFFF
70 return 0
71}
72
73func p384_modn_zero(out: *i64) -> i64 { return u384_zero(out) }
74func p384_modn_one(out: *i64) -> i64 { return u384_one(out) }
75func p384_modn_copy(out: *i64, src: *i64) -> i64 { return u384_copy(out, src) }
76func p384_modn_eq(a: *i64, b: *i64) -> i64 { return u384_eq(a, b) }
77
78// (a + b) mod n. Inputs canonical (< n); output canonical.
79func p384_modn_add(r: *i64, a: *i64, b: *i64) -> i64 {
80 let t: *i64 = u384_alloc()
81 let n: *i64 = u384_alloc()
82 p384_modn_load_n(n)
83 let carry: i64 = u384_add_with_carry(r, a, b)
84 let borrow: i64 = u384_sub_with_borrow(t, r, n)
85 if carry == 1 {
86 u384_copy(r, t)
87 } else {
88 if borrow == 0 {
89 u384_copy(r, t)
90 }
91 }
92 return 0
93}
94
95func p384_modn_sub(r: *i64, a: *i64, b: *i64) -> i64 {
96 let n: *i64 = u384_alloc()
97 p384_modn_load_n(n)
98 let borrow: i64 = u384_sub_with_borrow(r, a, b)
99 if borrow == 1 {
100 u384_add_with_carry(r, r, n)
101 }
102 return 0
103}
104
105func p384_modn_neg(r: *i64, a: *i64) -> i64 {
106 if u384_is_zero(a) == 1 {
107 u384_zero(r)
108 return 0
109 }
110 let n: *i64 = u384_alloc()
111 p384_modn_load_n(n)
112 u384_sub_with_borrow(r, n, a)
113 return 0
114}
115
116// Reduce a 384-bit value mod n. Since n > 2^383, single subtract
117// suffices.
118func p384_modn_reduce(r: *i64, a: *i64) -> i64 {
119 let n: *i64 = u384_alloc()
120 p384_modn_load_n(n)
121 u384_copy(r, a)
122 if u384_cmp(r, n) >= 0 {
123 u384_sub_with_borrow(r, r, n)
124 }
125 return 0
126}
127
128// Wide helpers for the bit-shift reduction in mul.
129func u384_wide_shr_1_inplace(buf: *i64) -> i64 {
130 var i: i64 = NX_U384_WIDE_LIMBS - 1
131 var carry: i64 = 0
132 while i >= 0 {
133 let v: i64 = buf[i] & NX_U384_LIMB_MASK
134 let new_carry: i64 = v & 1
135 buf[i] = ((v >> 1) | (carry << (NX_U384_LIMB_BITS - 1))) & NX_U384_LIMB_MASK
136 carry = new_carry
137 i = i - 1
138 }
139 return 0
140}
141
142func u384_wide_sub_inplace(a: *i64, b: *i64) -> i64 {
143 var i: i64 = 0
144 var borrow: i64 = 0
145 while i < NX_U384_WIDE_LIMBS {
146 let d: i64 = (a[i] & NX_U384_LIMB_MASK) - (b[i] & NX_U384_LIMB_MASK) - borrow
147 if d < 0 {
148 a[i] = (d + (1 << NX_U384_LIMB_BITS)) & NX_U384_LIMB_MASK
149 borrow = 1
150 } else {
151 a[i] = d & NX_U384_LIMB_MASK
152 borrow = 0
153 }
154 i = i + 1
155 }
156 return borrow
157}
158
159// (a * b) mod n via wide mul + bit-shift reduction (385 iters).
160func p384_modn_mul(out_12: *i64, a: *i64, b: *i64) -> i64 {
161 let c: *i64 = u384_wide_alloc()
162 let shifted_n: *i64 = u384_wide_alloc()
163 let n: *i64 = u384_alloc()
164 p384_modn_load_n(n)
165
166 u384_mul_wide(c, a, b)
167
168 var i: i64 = 0
169 while i < NX_U384_WIDE_LIMBS {
170 shifted_n[i] = 0
171 i = i + 1
172 }
173 i = 0
174 while i < NX_U384_LIMBS {
175 shifted_n[i + 12] = n[i]
176 i = i + 1
177 }
178
179 var k: i64 = 0
180 while k < 385 {
181 if u384_wide_cmp(c, shifted_n) >= 0 {
182 u384_wide_sub_inplace(c, shifted_n)
183 }
184 u384_wide_shr_1_inplace(shifted_n)
185 k = k + 1
186 }
187 u384_wide_copy_low(out_12, c)
188 return 0
189}
190
191func p384_modn_sq(out: *i64, a: *i64) -> i64 {
192 return p384_modn_mul(out, a, a)
193}
194
195func p384_modn_bit_at(limbs: *i64, bit_pos: i64) -> i64 {
196 let limb_idx: i64 = bit_pos / 32
197 let bit_in_limb: i64 = bit_pos - limb_idx * 32
198 let limb: i64 = limbs[limb_idx] & NX_U384_LIMB_MASK
199 return (limb >> bit_in_limb) & 1
200}
201
202// a^(-1) mod n via Fermat: a^(n-2) mod n.
203func p384_modn_inv(out: *i64, a: *i64) -> i64 {
204 let exp: *i64 = u384_alloc()
205 p384_modn_load_n_minus_2(exp)
206
207 let base: *i64 = u384_alloc()
208 u384_copy(base, a)
209
210 let result: *i64 = u384_alloc()
211 p384_modn_one(result)
212
213 var bit_pos: i64 = 383
214 while bit_pos >= 0 {
215 p384_modn_sq(result, result)
216 if p384_modn_bit_at(exp, bit_pos) == 1 {
217 p384_modn_mul(result, result, base)
218 }
219 bit_pos = bit_pos - 1
220 }
221 u384_copy(out, result)
222 return 0
223}
224
225func main() -> i64 {
226 return 0
227}