nx_p384_field_mul_fast.nx source
↩ module page · 127 lines · 4664 B
1// nx_p384_field_mul_fast.nx -- fast P-384 field multiply (mod p) via the prime's
2// own complement, replacing the 385-iteration bit-by-bit reduction in
3// nx_p384_field_mul.nx (the measured ~640ms-per-ECDSA-verify bottleneck).
4//
5// P-384 prime: p = 2^384 - 2^128 - 2^96 + 2^32 - 1, so
6// 2^384 == 2^128 + 2^96 - 2^32 + 1 (mod p).
7// For a 768-bit product C = Hi*2^384 + Lo,
8// C == Lo + Hi*(2^128 + 2^96 - 2^32 + 1) (mod p).
9// All multipliers are word-aligned (128/96/32 are multiples of the 32-bit limb),
10// so the fold is just shifted adds/subs (offsets 4/3/1/0). Two folds bring a
11// 768-bit product below ~2p; a short final reduce finishes it. Normal domain
12// in/out -> true drop-in for p384_field_mul (no Montgomery conversions).
13//
14// Correctness is pinned by KAT equality vs the bit-by-bit p384_field_mul in
15// nx_p384_field_mul_fast_gate.nx (same a*b mod p for random a,b).
16//
17// license_tier: INDEPENDENT_REDERIVE
18// genealogy_id: international-research-sources/nist/fips_186_5 (P-384 generalized-Mersenne)
19// lineage_id: nishi_p384_field_mul_fast_q10
20
21import "nx_syscalls.nx"
22import "nx_u384.nx"
23import "nx_u384_mul.nx"
24import "nx_p384_field.nx"
25
26// acc[off+k] += hi[k] (k=0..11), carry propagated up through acc (24 words).
27func p384_acc_add_shifted(acc: *i64, hi: *i64, off: i64) -> i64 {
28 var carry: i64 = 0
29 var k: i64 = 0
30 while k < NX_U384_LIMBS {
31 let s: i64 = (acc[off + k] & NX_U384_LIMB_MASK) + (hi[k] & NX_U384_LIMB_MASK) + carry
32 acc[off + k] = s & NX_U384_LIMB_MASK
33 carry = (s >> NX_U384_LIMB_BITS) & NX_U384_LIMB_MASK
34 k = k + 1
35 }
36 var j: i64 = off + NX_U384_LIMBS
37 var go: i64 = 1
38 while go == 1 {
39 if carry == 0 { go = 0 } else {
40 if j >= NX_U384_WIDE_LIMBS { go = 0 } else {
41 let s2: i64 = (acc[j] & NX_U384_LIMB_MASK) + carry
42 acc[j] = s2 & NX_U384_LIMB_MASK
43 carry = (s2 >> NX_U384_LIMB_BITS) & NX_U384_LIMB_MASK
44 j = j + 1
45 }
46 }
47 }
48 return 0
49}
50
51// acc[off+k] -= hi[k] (k=0..11), borrow propagated up. Caller guarantees acc >= shifted hi.
52func p384_acc_sub_shifted(acc: *i64, hi: *i64, off: i64) -> i64 {
53 var borrow: i64 = 0
54 var k: i64 = 0
55 while k < NX_U384_LIMBS {
56 let d: i64 = (acc[off + k] & NX_U384_LIMB_MASK) - (hi[k] & NX_U384_LIMB_MASK) - borrow
57 if d < 0 { acc[off + k] = (d + (1 << NX_U384_LIMB_BITS)) & NX_U384_LIMB_MASK; borrow = 1 }
58 else { acc[off + k] = d & NX_U384_LIMB_MASK; borrow = 0 }
59 k = k + 1
60 }
61 var j: i64 = off + NX_U384_LIMBS
62 var go: i64 = 1
63 while go == 1 {
64 if borrow == 0 { go = 0 } else {
65 if j >= NX_U384_WIDE_LIMBS { go = 0 } else {
66 let d2: i64 = (acc[j] & NX_U384_LIMB_MASK) - borrow
67 if d2 < 0 { acc[j] = (d2 + (1 << NX_U384_LIMB_BITS)) & NX_U384_LIMB_MASK; borrow = 1 }
68 else { acc[j] = d2 & NX_U384_LIMB_MASK; borrow = 0 }
69 j = j + 1
70 }
71 }
72 }
73 return 0
74}
75
76// One fold: c <- Lo + Hi*(2^128 + 2^96 + 1) - Hi*2^32, where c = Hi*2^384 + Lo.
77// Adds first (so the running value stays >= the subtrahend, no underflow).
78func p384_fold_once(c: *i64) -> i64 {
79 let hi: *i64 = u384_alloc()
80 var k: i64 = 0
81 while k < NX_U384_LIMBS {
82 hi[k] = c[NX_U384_LIMBS + k] & NX_U384_LIMB_MASK
83 c[NX_U384_LIMBS + k] = 0
84 k = k + 1
85 }
86 p384_acc_add_shifted(c, hi, 0) // + Hi
87 p384_acc_add_shifted(c, hi, 3) // + Hi*2^96
88 p384_acc_add_shifted(c, hi, 4) // + Hi*2^128
89 p384_acc_sub_shifted(c, hi, 1) // - Hi*2^32
90 return 0
91}
92
93// Final reduce: after two folds c < ~2p (with at most word 12 set); subtract p
94// across 13 words until c < p.
95func p384_fast_reduce_final(c: *i64, p: *i64) -> i64 {
96 var done: i64 = 0
97 while done == 0 {
98 let hi12: i64 = c[NX_U384_LIMBS] & NX_U384_LIMB_MASK
99 if hi12 != 0 {
100 let borrow: i64 = u384_sub_with_borrow(c, c, p)
101 c[NX_U384_LIMBS] = (c[NX_U384_LIMBS] - borrow) & NX_U384_LIMB_MASK
102 } else {
103 if u384_cmp(c, p) >= 0 { u384_sub_with_borrow(c, c, p) } else { done = 1 }
104 }
105 }
106 return 0
107}
108
109func p384_field_mul_fast(out: *i64, a: *i64, b: *i64) -> i64 {
110 let c: *i64 = u384_wide_alloc()
111 u384_mul_wide(c, a, b)
112 let p: *i64 = u384_alloc()
113 p384_field_load_p(p)
114 p384_fold_once(c)
115 p384_fold_once(c)
116 p384_fast_reduce_final(c, p)
117 u384_wide_copy_low(out, c)
118 return 0
119}
120
121func p384_field_sq_fast(out: *i64, a: *i64) -> i64 {
122 return p384_field_mul_fast(out, a, a)
123}
124
125func main() -> i64 {
126 return 0
127}