nx_rsa2048_mont.nx source
↩ module page · 150 lines · 5950 B
1// nx_rsa2048_mont.nx -- Montgomery modular multiplication + modexp for the
2// 2048-bit RSA modulus. Replaces the O(bits*n) bit-by-bit reduction
3// (nx_rsa2048_mod.nx, "a few seconds per verify") with CIOS Montgomery
4// multiplication (O(n^2) limb ops), measured to cut TLS cert-verify from
5// ~1.5s to a few ms (sovereign native perf timers in nx_https_get / _session_run).
6//
7// 32-bit limbs in 64-bit words make CIOS overflow-safe: the inner
8// accumulate t[j] + a[j]*b[i] + carry has max value (2^32-1)^2 + 2*(2^32-1)
9// = 2^64 - 1, which fits one unsigned 64-bit word exactly. Carry/low are
10// extracted with (x>>32)&MASK / x&MASK (correct under arithmetic shift+mask).
11//
12// Side channels: this verifies PUBLIC server certificates (modulus, signature,
13// and exponent are all public), so constant-time is not required here.
14//
15// Correctness is pinned by KAT equality against the bit-by-bit rsa2048_mod_exp
16// in nx_rsa2048_mont_gate.nx -- both must produce identical s^e mod n.
17//
18// license_tier: INDEPENDENT_REDERIVE
19// genealogy_id: international-research-sources/ietf/rfc_8017 (Montgomery 1985; Koc CIOS)
20// lineage_id: nishi_rsa2048_mont_q10
21
22import "nx_syscalls.nx"
23import "nx_u2048.nx"
24import "nx_u2048_mul.nx"
25import "nx_rsa2048_mod.nx"
26const NX_MAGIC_2048: i64 = 2048
27
28const NX_RSA2048_MONT_OK: i64 = 1
29const NX_RSA2048_MONT_S_OUT_OF_RANGE: i64 = 2
30
31// highest set bit index of e (0..63), or -1 if e == 0.
32func rsa2048_mont_highbit(e: i64) -> i64 {
33 var i: i64 = 63
34 while i >= 0 {
35 if ((e >> i) & 1) == 1 { return i }
36 i = i - 1
37 }
38 return 0 - 1
39}
40
41// n0inv = -n[0]^{-1} mod 2^32. n[0] is odd (RSA n is odd), so x=n0 is correct
42// mod 8 (odd^2 == 1 mod 8); Hensel/Newton x <- x*(2 - n0*x) doubles the correct
43// low bits each step: 3 -> 6 -> 12 -> 24 -> 48 (>=32) in 4 steps; 5 for margin.
44func rsa2048_mont_n0inv(n0_full: i64) -> i64 {
45 let n0: i64 = n0_full & NX_U2048_LIMB_MASK
46 var x: i64 = n0
47 var k: i64 = 0
48 while k < 5 {
49 let t: i64 = (n0 * x) & NX_U2048_LIMB_MASK
50 let u: i64 = (2 - t) & NX_U2048_LIMB_MASK
51 x = (x * u) & NX_U2048_LIMB_MASK
52 k = k + 1
53 }
54 return (0 - x) & NX_U2048_LIMB_MASK
55}
56
57// out = (a * b * R^-1) mod n, R = 2^2048. CIOS, t has N+2 words.
58func rsa2048_mont_mul(out: *i64, a: *i64, b: *i64, n: *i64, n0inv: i64) -> i64 {
59 let N: i64 = NX_U2048_LIMBS
60 let t: *i64 = sys_mmap((N + 2) * 8) as *i64
61 var z: i64 = 0
62 while z < N + 2 { t[z] = 0; z = z + 1 }
63
64 var i: i64 = 0
65 while i < N {
66 let bi: i64 = b[i] & NX_U2048_LIMB_MASK
67 // t = t + a * b[i]
68 var c: i64 = 0
69 var j: i64 = 0
70 while j < N {
71 let s: i64 = (t[j] & NX_U2048_LIMB_MASK) + (a[j] & NX_U2048_LIMB_MASK) * bi + c
72 t[j] = s & NX_U2048_LIMB_MASK
73 c = (s >> 32) & NX_U2048_LIMB_MASK
74 j = j + 1
75 }
76 let s2: i64 = (t[N] & NX_U2048_LIMB_MASK) + c
77 t[N] = s2 & NX_U2048_LIMB_MASK
78 t[N + 1] = (t[N + 1] & NX_U2048_LIMB_MASK) + ((s2 >> 32) & NX_U2048_LIMB_MASK)
79
80 // m = t[0] * n0inv mod 2^32 ; t = (t + m*n) >> 32 (one limb)
81 let m: i64 = ((t[0] & NX_U2048_LIMB_MASK) * n0inv) & NX_U2048_LIMB_MASK
82 let s0: i64 = (t[0] & NX_U2048_LIMB_MASK) + m * (n[0] & NX_U2048_LIMB_MASK)
83 var c2: i64 = (s0 >> 32) & NX_U2048_LIMB_MASK // low limb of s0 is 0 by construction
84 var j2: i64 = 1
85 while j2 < N {
86 let s3: i64 = (t[j2] & NX_U2048_LIMB_MASK) + m * (n[j2] & NX_U2048_LIMB_MASK) + c2
87 t[j2 - 1] = s3 & NX_U2048_LIMB_MASK
88 c2 = (s3 >> 32) & NX_U2048_LIMB_MASK
89 j2 = j2 + 1
90 }
91 let s4: i64 = (t[N] & NX_U2048_LIMB_MASK) + c2
92 t[N - 1] = s4 & NX_U2048_LIMB_MASK
93 t[N] = (t[N + 1] & NX_U2048_LIMB_MASK) + ((s4 >> 32) & NX_U2048_LIMB_MASK)
94 t[N + 1] = 0
95 i = i + 1
96 }
97
98 // final conditional subtract: result < 2n, so at most one subtraction.
99 var ge: i64 = 0
100 if (t[N] & NX_U2048_LIMB_MASK) != 0 { ge = 1 } else { if u2048_cmp(t, n) >= 0 { ge = 1 } }
101 if ge == 1 { u2048_sub_with_borrow(t, t, n) }
102 u2048_copy(out, t)
103 return 0
104}
105
106// Compute R^2 mod n (R = 2^2048) using the existing bit-by-bit reduction.
107// One-time per modexp (the 17 mont_muls that follow are the fast part).
108func rsa2048_mont_r2(out: *i64, n: *i64) -> i64 {
109 let wide: *i64 = u2048_wide_alloc()
110 wide[64] = 1 // 2^NX_MAGIC_2048 (limb 64 of 32-bit limbs)
111 let t1: *i64 = u2048_alloc()
112 rsa2048_mod(t1, wide, n) // t1 = 2^NX_MAGIC_2048 mod n
113 rsa2048_mul_mod(out, t1, t1, n) // out = (2^NX_MAGIC_2048)^2 mod n = R^2 mod n
114 return 0
115}
116
117// out = s^e mod n via Montgomery. Same contract as rsa2048_mod_exp.
118func rsa2048_mod_exp_mont(out: *i64, s: *i64, e: i64, n: *i64) -> i64 {
119 if u2048_cmp(s, n) >= 0 { return NX_RSA2048_MONT_S_OUT_OF_RANGE }
120 if e == 0 { u2048_one(out); return NX_RSA2048_MONT_OK }
121
122 let n0inv: i64 = rsa2048_mont_n0inv(n[0])
123 let r2: *i64 = u2048_alloc()
124 rsa2048_mont_r2(r2, n)
125
126 let one: *i64 = u2048_alloc()
127 u2048_one(one)
128 let acc: *i64 = u2048_alloc()
129 rsa2048_mont_mul(acc, one, r2, n, n0inv) // acc = Montgomery(1) = R mod n
130 let smont: *i64 = u2048_alloc()
131 rsa2048_mont_mul(smont, s, r2, n, n0inv) // smont = Montgomery(s) = s*R mod n
132
133 let hb: i64 = rsa2048_mont_highbit(e)
134
135 let tmp: *i64 = u2048_alloc()
136 var i: i64 = hb
137 while i >= 0 {
138 rsa2048_mont_mul(tmp, acc, acc, n, n0inv); u2048_copy(acc, tmp) // square
139 if ((e >> i) & 1) == 1 {
140 rsa2048_mont_mul(tmp, acc, smont, n, n0inv); u2048_copy(acc, tmp) // multiply
141 }
142 i = i - 1
143 }
144 rsa2048_mont_mul(out, acc, one, n, n0inv) // convert out of Montgomery (acc * R^-1)
145 return NX_RSA2048_MONT_OK
146}
147
148func main() -> i64 {
149 return 0
150}