nx_p384_field_mul.nx source
↩ module page · 116 lines · 3528 B
1// nx_p384_field_mul.nx -- P-384 field multiplication + squaring
2// mod p. Bit-by-bit shift-and-subtract reduction (mirror of the
3// P-256 approach in nx_p256_field_mul.nx). Portable, works for
4// any prime; Solinas optimization can be a future drop-in.
5//
6// Algorithm (385 iterations -- one per possible high-bit of the
7// 768-bit wide product, plus one final at shifted_p == p):
8// 1. c = a * b (24-limb wide)
9// 2. shifted_p = p << 384 (high 12 = p, low 12 = 0)
10// 3. for k in 0..385:
11// if c >= shifted_p: c -= shifted_p
12// shifted_p >>= 1
13// 4. c's low 12 limbs == (a * b) mod p
14//
15// API:
16// p384_field_mul(out_12, a, b) out = (a * b) mod p
17// p384_field_sq(out, a) out = (a * a) mod p
18//
19// license_tier: INDEPENDENT_REDERIVE
20// genealogy_id: international-research-sources/nist/fips_186_5
21// lineage_id: nishi_p384_field_mul_q10
22
23// nx_safety_envelope:
24// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
25// sil_target: SIL1
26// evidence: [bulk_applied_2026-05-20, p384-field-mul]
27// verdict: NOT_YET_EVALUATED
28
29import "nx_syscalls.nx"
30import "nx_u384.nx"
31import "nx_u384_mul.nx"
32import "nx_p384_field.nx"
33import "nx_p384_field_mul_fast.nx"
34
35// In-place 1-bit right shift on a 24-limb wide buffer.
36func u384_wide_shr_1(buf: *i64) -> i64 {
37 var i: i64 = NX_U384_WIDE_LIMBS - 1
38 var carry: i64 = 0
39 while i >= 0 {
40 let v: i64 = buf[i] & NX_U384_LIMB_MASK
41 let new_carry: i64 = v & 1
42 buf[i] = ((v >> 1) | (carry << (NX_U384_LIMB_BITS - 1))) & NX_U384_LIMB_MASK
43 carry = new_carry
44 i = i - 1
45 }
46 return 0
47}
48
49// 24-limb subtract with borrow. out = a - b mod 2^768.
50func u384_wide_sub(out: *i64, a: *i64, b: *i64) -> i64 {
51 var i: i64 = 0
52 var borrow: i64 = 0
53 while i < NX_U384_WIDE_LIMBS {
54 let d: i64 = (a[i] & NX_U384_LIMB_MASK) - (b[i] & NX_U384_LIMB_MASK) - borrow
55 if d < 0 {
56 out[i] = (d + (1 << NX_U384_LIMB_BITS)) & NX_U384_LIMB_MASK
57 borrow = 1
58 } else {
59 out[i] = d & NX_U384_LIMB_MASK
60 borrow = 0
61 }
62 i = i + 1
63 }
64 return borrow
65}
66
67// Bit-by-bit reference (kept as the correctness oracle for the fast path's gate).
68func p384_field_mul_bitwise(out_12: *i64, a: *i64, b: *i64) -> i64 {
69 let c: *i64 = u384_wide_alloc()
70 let shifted_p: *i64 = u384_wide_alloc()
71 let p: *i64 = u384_alloc()
72 p384_field_load_p(p)
73
74 // c = a * b (24 limbs)
75 u384_mul_wide(c, a, b)
76
77 // shifted_p = p << 384 (high 12 limbs = p, low 12 = 0)
78 var i: i64 = 0
79 while i < NX_U384_WIDE_LIMBS {
80 shifted_p[i] = 0
81 i = i + 1
82 }
83 i = 0
84 while i < NX_U384_LIMBS {
85 shifted_p[i + 12] = p[i]
86 i = i + 1
87 }
88
89 // Bit-by-bit reduction: 385 iterations.
90 var k: i64 = 0
91 while k < 385 {
92 if u384_wide_cmp(c, shifted_p) >= 0 {
93 u384_wide_sub(c, c, shifted_p)
94 }
95 u384_wide_shr_1(shifted_p)
96 k = k + 1
97 }
98
99 u384_wide_copy_low(out_12, c)
100 return 0
101}
102
103// Production path: fast prime-complement reduction (KAT-equal to the bitwise
104// reference; nx_p384_field_mul_fast_gate.nx pins it). All P-384 point ops
105// (and p384_field_sq) route through here.
106func p384_field_mul(out_12: *i64, a: *i64, b: *i64) -> i64 {
107 return p384_field_mul_fast(out_12, a, b)
108}
109
110func p384_field_sq(out: *i64, a: *i64) -> i64 {
111 return p384_field_mul(out, a, a)
112}
113
114func main() -> i64 {
115 return 0
116}