nx_rsa4096_mont.nx source
↩ module page · 138 lines · 5791 B
1// nx_rsa4096_mont.nx -- CIOS Montgomery modular multiplication + modexp for the 4096-bit RSA modulus.
2//
3// THE FIX (operator 2026-06-23, found by the apm->conductor->drill loop): RSA-2048 got Montgomery
4// (nx_rsa2048_mont, ~1.5s->few ms), but RSA-4096 NEVER DID -- it still used the slow bit-by-bit
5// rsa4096_mod_exp (rsa4096_mul_mod = u4096_mul + rsa4096_mod reduction, ~18x per verify). Real Web PKI
6// chains terminate at an RSA-4096 ROOT (e.g. Let's Encrypt's ISRG Root X1), so the intermediate-under-root
7// link paid ~242ms (the apm "cert link alg=3" certloop hotspot). This is the 128-limb CIOS Montgomery,
8// byte-identical to rsa4096_mod_exp (KAT-gated in nx_rsa4096_mont_gate), cutting that link to a few ms.
9// Adapts nx_rsa2048_mont 64->128 limbs verbatim (CIOS is limb-parametric). Side-channels: verifies PUBLIC
10// certs, constant-time not required. license_tier: INDEPENDENT_REDERIVE
11import "nx_syscalls.nx"
12import "nx_u4096.nx"
13import "nx_rsa4096_mod.nx"
14const NX_MAGIC_4096: i64 = 4096
15
16const NX_RSA4096_MONT_OK: i64 = 1
17const NX_RSA4096_MONT_S_OUT_OF_RANGE: i64 = 2
18
19func rsa4096_mont_highbit(e: i64) -> i64 {
20 var i: i64 = 63
21 while i >= 0 { if ((e >> i) & 1) == 1 { return i } i = i - 1 }
22 return 0 - 1
23}
24
25// n0inv = -n[0]^{-1} mod 2^32 (Hensel lift, 5 steps).
26func rsa4096_mont_n0inv(n0_full: i64) -> i64 {
27 let n0: i64 = n0_full & NX_U4096_LIMB_MASK
28 var x: i64 = n0
29 var k: i64 = 0
30 while k < 5 {
31 let t: i64 = (n0 * x) & NX_U4096_LIMB_MASK
32 let u: i64 = (2 - t) & NX_U4096_LIMB_MASK
33 x = (x * u) & NX_U4096_LIMB_MASK
34 k = k + 1
35 }
36 return (0 - x) & NX_U4096_LIMB_MASK
37}
38
39// out = (a * b * R^-1) mod n, R = 2^4096. CIOS, t has N+2 words.
40func rsa4096_mont_mul(out: *i64, a: *i64, b: *i64, n: *i64, n0inv: i64) -> i64 {
41 let N: i64 = NX_U4096_LIMBS
42 let t: *i64 = sys_mmap((N + 2) * 8) as *i64
43 var z: i64 = 0
44 while z < N + 2 { t[z] = 0; z = z + 1 }
45
46 var i: i64 = 0
47 while i < N {
48 let bi: i64 = b[i] & NX_U4096_LIMB_MASK
49 // t = t + a * b[i]
50 var c: i64 = 0
51 var j: i64 = 0
52 while j < N {
53 let s: i64 = (t[j] & NX_U4096_LIMB_MASK) + (a[j] & NX_U4096_LIMB_MASK) * bi + c
54 t[j] = s & NX_U4096_LIMB_MASK
55 c = (s >> 32) & NX_U4096_LIMB_MASK
56 j = j + 1
57 }
58 let s2: i64 = (t[N] & NX_U4096_LIMB_MASK) + c
59 t[N] = s2 & NX_U4096_LIMB_MASK
60 t[N + 1] = (t[N + 1] & NX_U4096_LIMB_MASK) + ((s2 >> 32) & NX_U4096_LIMB_MASK)
61
62 // m = t[0] * n0inv mod 2^32 ; t = (t + m*n) >> 32 (one limb)
63 let m: i64 = ((t[0] & NX_U4096_LIMB_MASK) * n0inv) & NX_U4096_LIMB_MASK
64 let s0: i64 = (t[0] & NX_U4096_LIMB_MASK) + m * (n[0] & NX_U4096_LIMB_MASK)
65 var c2: i64 = (s0 >> 32) & NX_U4096_LIMB_MASK
66 var j2: i64 = 1
67 while j2 < N {
68 let s3: i64 = (t[j2] & NX_U4096_LIMB_MASK) + m * (n[j2] & NX_U4096_LIMB_MASK) + c2
69 t[j2 - 1] = s3 & NX_U4096_LIMB_MASK
70 c2 = (s3 >> 32) & NX_U4096_LIMB_MASK
71 j2 = j2 + 1
72 }
73 let s4: i64 = (t[N] & NX_U4096_LIMB_MASK) + c2
74 t[N - 1] = s4 & NX_U4096_LIMB_MASK
75 t[N] = (t[N + 1] & NX_U4096_LIMB_MASK) + ((s4 >> 32) & NX_U4096_LIMB_MASK)
76 t[N + 1] = 0
77 i = i + 1
78 }
79
80 // final conditional subtract: result < 2n, at most one subtraction.
81 var ge: i64 = 0
82 if (t[N] & NX_U4096_LIMB_MASK) != 0 { ge = 1 } else { if u4096_cmp(t, n) >= 0 { ge = 1 } }
83 if ge == 1 { u4096_sub_with_borrow(t, t, n) }
84 u4096_copy(out, t)
85 sys_munmap(t as *u8, (N + 2) * 8) // free per-call scratch -- the leak that amplified inside a verify
86 return 0
87}
88
89// R^2 mod n (R = 2^4096) via the existing bit-by-bit reduction (one-time per modexp).
90func rsa4096_mont_r2(out: *i64, n: *i64) -> i64 {
91 let wide: *i64 = sys_mmap(256 * 8) as *i64
92 var z: i64 = 0
93 while z < 256 { wide[z] = 0; z = z + 1 }
94 wide[128] = 1 // 2^NX_MAGIC_4096 (limb 128 of 32-bit limbs)
95 let t1: *i64 = u4096_alloc()
96 rsa4096_mod(t1, wide, n) // t1 = 2^NX_MAGIC_4096 mod n = R mod n
97 rsa4096_mul_mod(out, t1, t1, n) // out = (R mod n)^2 mod n = R^2 mod n
98 sys_munmap(wide as *u8, 256 * 8) // free the one-time wide + t1 scratch
99 u4096_free(t1)
100 return 0
101}
102
103// out = s^e mod n via Montgomery. Same contract as rsa4096_mod_exp.
104func rsa4096_mod_exp_mont(out: *i64, s: *i64, e: i64, n: *i64) -> i64 {
105 if u4096_cmp(s, n) >= 0 { return NX_RSA4096_MONT_S_OUT_OF_RANGE }
106 if e == 0 { u4096_one(out); return NX_RSA4096_MONT_OK }
107
108 let n0inv: i64 = rsa4096_mont_n0inv(n[0])
109 let r2: *i64 = u4096_alloc()
110 rsa4096_mont_r2(r2, n)
111
112 let one: *i64 = u4096_alloc()
113 u4096_one(one)
114 let acc: *i64 = u4096_alloc()
115 rsa4096_mont_mul(acc, one, r2, n, n0inv) // acc = Montgomery(1) = R mod n
116 let smont: *i64 = u4096_alloc()
117 rsa4096_mont_mul(smont, s, r2, n, n0inv) // smont = Montgomery(s) = s*R mod n
118
119 let hb: i64 = rsa4096_mont_highbit(e)
120 let tmp: *i64 = u4096_alloc()
121 var i: i64 = hb
122 while i >= 0 {
123 rsa4096_mont_mul(tmp, acc, acc, n, n0inv); u4096_copy(acc, tmp) // square
124 if ((e >> i) & 1) == 1 {
125 rsa4096_mont_mul(tmp, acc, smont, n, n0inv); u4096_copy(acc, tmp) // multiply
126 }
127 i = i - 1
128 }
129 rsa4096_mont_mul(out, acc, one, n, n0inv) // convert out of Montgomery (writes caller's `out`)
130 u4096_free(r2) // free all modexp scratch -- out is the caller's buffer
131 u4096_free(one)
132 u4096_free(acc)
133 u4096_free(smont)
134 u4096_free(tmp)
135 return NX_RSA4096_MONT_OK
136}
137
138func main() -> i64 { return 0 }