code wiki / _hdl_build / nx_u2048_smallops.nx
nx_u2048_smallops.nx source
↩ module page · 270 lines · 11434 B
1// nx_u2048_smallops.nx -- F103e RUNG 6: big-by-SMALL arithmetic (mul, div, mod, add).
2//
3// WHY THIS SHAPE, and not a general extended GCD: RSA needs d = e^-1 mod lambda(n). The textbook
4// route is a binary extended GCD over 2048-bit values, which needs (x + m) >> 1 -- and x + m
5// OVERFLOWS 2048 bits, while u2048_shr1 has no carry-in. That is a real trap, not a style choice.
6//
7// The route taken instead exploits the fact that **e is small** (65537). Write:
8// k*lambda + 1 = d*e with k in [1, e-1]
9// Then k = -(lambda mod e)^-1 mod e -- an inverse of a SMALL number modulo a SMALL number, solvable
10// in plain i64 -- and d = (k*lambda + 1)/e, which is a big-by-small multiply and a big-by-small
11// divide. Every intermediate fits in an i64 because the limbs are 32-bit:
12// divide: rem < m <= 2^31, so (rem << 32) | limb < 2^63 -- proven by the bound, not hoped
13// multiply: (2^32-1)*(2^31-1) + carry < 2^63
14// ★★★★★★ **THE PRIMITIVE YOU NEED IS OFTEN NARROWER THAN THE ONE THE TEXTBOOK NAMES — AND THE NARROW
15// ONE CAN BE EXACTLY THE ONE THAT FITS IN THE REGISTERS YOU HAVE.** A general u2048 modinv is a much
16// larger, more dangerous organ than this, and RSA does not need it.
17//
18// ★THE ORACLE IS PLAIN i64 ARITHMETIC. Every tooth loads a value that fits in 64 bits, runs the
19// u2048 path, and demands agreement with the `*`, `/`, `%` the compiler already gives us. Two
20// independent implementations; no recalled constants anywhere.
21//
22// Usage: nx_u2048_smallops selftest
23// Exit: 0 GREEN | 1 RED. Log -> knowledge/status/nishi_os.log, verdict= LAST.
24// license_tier: ORIGINAL
25import "nx_syscalls.nx"
26import "nx_u2048.nx"
27const SO_MAGIC_65537: i64 = 65537
28const SO_MAGIC_4294967295: i64 = 4294967295
29const SO_MAGIC_4294967296: i64 = 4294967296
30const SO_MAGIC_1099511627776: i64 = 1099511627776
31const SO_MAGIC_9007199254740993: i64 = 9007199254740993
32const SO_MAGIC_123456789012345: i64 = 123456789012345
33const SO_MAGIC_1000003: i64 = 1000003
34const SO_MAGIC_2147483647: i64 = 2147483647
35const SO_MAGIC_1000000007: i64 = 1000000007
36const SO_MAGIC_12345: i64 = 12345
37
38const SO_LIMB_MASK: i64 = 0xFFFFFFFF
39const SO_MAX_SMALL: i64 = 2147483647 // 2^31-1: the bound the overflow proofs above assume
40
41func so_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
42func so_fp(fd: i64, s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(fd, s, n); return 0 }
43func so_fn(fd: i64, v: i64) -> i64 {
44 let bb: *u8 = sys_mmap(28); var m: i64 = v
45 if m < 0 { m = 0 - m; bb[0] = 45 as u8; sys_write(fd, bb, 1) }
46 let t: *u8 = sys_mmap(28); var k: i64 = 0
47 if m == 0 { t[0] = 48 as u8; k = 1 }
48 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
49 var i: i64 = 0
50 while i < k { bb[i] = t[k - 1 - i]; i = i + 1 }
51 sys_write(fd, bb, k); return 0
52}
53
54func so_set_i64(x: *i64, v: i64) -> i64 {
55 let b: *u8 = sys_mmap(256)
56 var i: i64 = 0
57 while i < 256 { b[i] = 0 as u8; i = i + 1 }
58 var k: i64 = 0
59 while k < 8 { b[255 - k] = ((v >> (k * 8)) & 0xff) as u8; k = k + 1 }
60 u2048_load_be(x, b)
61 return 0
62}
63// read back the low 64 bits (limbs are 32-bit, limb[0] is least significant)
64func so_low64(x: *i64) -> i64 {
65 return (x[0] & SO_LIMB_MASK) | ((x[1] & SO_LIMB_MASK) << 32)
66}
67
68// out = a * k. Returns the overflow carry out of the top limb (0 when it fits).
69func u2048_mul_small(out: *i64, a: *i64, k: i64) -> i64 {
70 if k < 0 { return 0 - 1 }
71 if k > SO_MAX_SMALL { return 0 - 1 }
72 var i: i64 = 0
73 var carry: i64 = 0
74 while i < NX_U2048_LIMBS {
75 let p: i64 = (a[i] & SO_LIMB_MASK) * k + carry
76 out[i] = p & SO_LIMB_MASK
77 carry = (p >> 32) & SO_LIMB_MASK
78 i = i + 1
79 }
80 return carry
81}
82
83// out = a / m, returns a mod m. Long division from the most significant limb down.
84func u2048_div_small(out: *i64, a: *i64, m: i64) -> i64 {
85 if m <= 0 { return 0 - 1 }
86 if m > SO_MAX_SMALL { return 0 - 1 }
87 var rem: i64 = 0
88 var i: i64 = NX_U2048_LIMBS - 1
89 while i >= 0 {
90 let cur: i64 = (rem << 32) | (a[i] & SO_LIMB_MASK)
91 out[i] = cur / m
92 rem = cur % m
93 i = i - 1
94 }
95 return rem
96}
97
98// a mod m, without producing the quotient (Horner over the limbs)
99func u2048_mod_small(a: *i64, m: i64) -> i64 {
100 if m <= 0 { return 0 - 1 }
101 if m > SO_MAX_SMALL { return 0 - 1 }
102 var rem: i64 = 0
103 var i: i64 = NX_U2048_LIMBS - 1
104 while i >= 0 {
105 let cur: i64 = (rem << 32) | (a[i] & SO_LIMB_MASK)
106 rem = cur % m
107 i = i - 1
108 }
109 return rem
110}
111
112// out = a + k. Returns carry out of the top limb.
113func u2048_add_small(out: *i64, a: *i64, k: i64) -> i64 {
114 if k < 0 { return 0 - 1 }
115 if k > SO_MAX_SMALL { return 0 - 1 }
116 var i: i64 = 0
117 var carry: i64 = k
118 while i < NX_U2048_LIMBS {
119 let s: i64 = (a[i] & SO_LIMB_MASK) + carry
120 out[i] = s & SO_LIMB_MASK
121 carry = (s >> 32) & SO_LIMB_MASK
122 i = i + 1
123 }
124 return carry
125}
126
127// modular inverse of a mod m for SMALL values, by extended Euclid in i64.
128// Returns the inverse in [0, m), or -1 when gcd(a, m) != 1 (no inverse exists -- REFUSED, never 0).
129func i64_modinv_small(a: i64, m: i64) -> i64 {
130 if m <= 1 { return 0 - 1 }
131 var old_r: i64 = a % m
132 if old_r < 0 { old_r = old_r + m }
133 var r: i64 = m
134 var old_s: i64 = 1
135 var s: i64 = 0
136 while r != 0 {
137 let q: i64 = old_r / r
138 let tr: i64 = old_r - q * r
139 old_r = r; r = tr
140 let ts: i64 = old_s - q * s
141 old_s = s; s = ts
142 }
143 if old_r != 1 { return 0 - 1 } // not coprime: no inverse
144 var res: i64 = old_s % m
145 if res < 0 { res = res + m }
146 return res
147}
148
149// =================================================================================================
150func so_selftest() -> i64 {
151 var pass: i64 = 0
152 var teeth: i64 = 0
153 let x: *i64 = u2048_alloc()
154 let y: *i64 = u2048_alloc()
155
156 // T1 div/mod vs the compiler's own / and % over a spread of values and divisors.
157 // FULL cross-product of the stated fixture sets -- both sets printed, so the coverage is legible.
158 teeth = teeth + 1
159 let vals: *i64 = sys_mmap(128) as *i64
160 vals[0] = 0; vals[1] = 1; vals[2] = SO_MAGIC_65537; vals[3] = SO_MAGIC_4294967295
161 vals[4] = SO_MAGIC_4294967296; vals[5] = SO_MAGIC_1099511627776; vals[6] = SO_MAGIC_9007199254740993; vals[7] = SO_MAGIC_123456789012345
162 let mods: *i64 = sys_mmap(128) as *i64
163 mods[0] = 2; mods[1] = 3; mods[2] = SO_MAGIC_65537; mods[3] = SO_MAGIC_1000003; mods[4] = SO_MAGIC_2147483647
164 var bad: i64 = 0
165 var checked: i64 = 0
166 var vi: i64 = 0
167 while vi < 8 {
168 var mi: i64 = 0
169 while mi < 5 {
170 so_set_i64(x, vals[vi])
171 let r: i64 = u2048_div_small(y, x, mods[mi])
172 let q: i64 = so_low64(y)
173 if r != (vals[vi] % mods[mi]) { bad = bad + 1 }
174 if q != (vals[vi] / mods[mi]) { bad = bad + 1 }
175 if u2048_mod_small(x, mods[mi]) != (vals[vi] % mods[mi]) { bad = bad + 1 }
176 checked = checked + 1
177 mi = mi + 1
178 }
179 vi = vi + 1
180 }
181 if bad == 0 { if checked == 40 { pass = pass + 1
182 so_p("SO-T1 div/mod match i64 over 8x5=40 pairs GREEN\n" as *u8) }
183 else { so_p("SO-T1 RED [VACUOUS: checked " as *u8); so_fn(1, checked); so_p("]\n" as *u8) } }
184 else { so_p("SO-T1 RED bad=" as *u8); so_fn(1, bad); so_p("\n" as *u8) }
185
186 // T2 multiply vs i64, on values small enough that the product still fits in 64 bits
187 teeth = teeth + 1
188 bad = 0; checked = 0
189 let mv: *i64 = sys_mmap(64) as *i64
190 mv[0] = 0; mv[1] = 1; mv[2] = SO_MAGIC_65537; mv[3] = SO_MAGIC_4294967295; mv[4] = SO_MAGIC_1000000007
191 var ki: i64 = 0
192 while ki < 5 {
193 var kk: i64 = 0
194 while kk < 5 {
195 so_set_i64(x, mv[ki])
196 let c: i64 = u2048_mul_small(y, x, mv[kk] % SO_MAGIC_2147483647)
197 if c != 0 { bad = bad + 1 }
198 if so_low64(y) != (mv[ki] * (mv[kk] % SO_MAGIC_2147483647)) { bad = bad + 1 }
199 checked = checked + 1
200 kk = kk + 1
201 }
202 ki = ki + 1
203 }
204 if bad == 0 { if checked == 25 { pass = pass + 1; so_p("SO-T2 mul matches i64 over 25 pairs GREEN\n" as *u8) }
205 else { so_p("SO-T2 RED [VACUOUS]\n" as *u8) } }
206 else { so_p("SO-T2 RED bad=" as *u8); so_fn(1, bad); so_p("\n" as *u8) }
207
208 // T3 ROUND TRIP, the property that actually matters for d = (k*lambda + 1)/e:
209 // (v * k + 1) / k must give back v, remainder 1.
210 teeth = teeth + 1
211 bad = 0
212 so_set_i64(x, SO_MAGIC_123456789012345)
213 u2048_mul_small(y, x, SO_MAGIC_65537)
214 let cr: i64 = u2048_add_small(y, y, 1)
215 if cr != 0 { bad = bad + 1 }
216 let rr: i64 = u2048_div_small(x, y, SO_MAGIC_65537)
217 if rr != 1 { bad = bad + 1 }
218 if so_low64(x) != SO_MAGIC_123456789012345 { bad = bad + 1 }
219 if bad == 0 { pass = pass + 1; so_p("SO-T3 (v*e+1)/e round-trips with remainder 1 GREEN\n" as *u8) }
220 else { so_p("SO-T3 RED\n" as *u8) }
221
222 // T4 the small modular inverse, checked by MULTIPLYING BACK -- never by trusting the algorithm
223 teeth = teeth + 1
224 bad = 0; checked = 0
225 var ai: i64 = 1
226 while ai < 200 {
227 let inv: i64 = i64_modinv_small(ai, SO_MAGIC_65537)
228 if inv < 0 { bad = bad + 1 } else {
229 if ((ai * inv) % SO_MAGIC_65537) != 1 { bad = bad + 1 }
230 }
231 checked = checked + 1
232 ai = ai + 1
233 }
234 if bad == 0 { if checked == 199 { pass = pass + 1
235 so_p("SO-T4 modinv verified by multiplying back, 199/199 GREEN\n" as *u8) }
236 else { so_p("SO-T4 RED [VACUOUS]\n" as *u8) } }
237 else { so_p("SO-T4 RED bad=" as *u8); so_fn(1, bad); so_p("\n" as *u8) }
238
239 // T5 NEGATIVE CONTROL: a non-coprime pair has NO inverse and must be REFUSED, not answered.
240 // gcd(6, 9) = 3. An implementation that returns a plausible number here is silently wrong.
241 teeth = teeth + 1
242 if i64_modinv_small(6, 9) == (0 - 1) { if i64_modinv_small(4, 8) == (0 - 1) {
243 pass = pass + 1; so_p("SO-T5 neg-control-noncoprime-refused GREEN\n" as *u8) }
244 else { so_p("SO-T5 RED (4 mod 8)\n" as *u8) } }
245 else { so_p("SO-T5 RED (6 mod 9)\n" as *u8) }
246
247 // T6 bounds are REFUSED rather than silently overflowing the i64 proofs above
248 teeth = teeth + 1
249 so_set_i64(x, SO_MAGIC_12345)
250 if u2048_div_small(y, x, 0) == (0 - 1) { if u2048_mul_small(y, x, SO_MAGIC_4294967296) == (0 - 1) {
251 pass = pass + 1; so_p("SO-T6 out-of-range-refused GREEN\n" as *u8) }
252 else { so_p("SO-T6 RED mul accepted an over-large k\n" as *u8) } }
253 else { so_p("SO-T6 RED div accepted m=0\n" as *u8) }
254
255 so_p("SO-SELFTEST " as *u8); so_fn(1, pass); so_p("/" as *u8); so_fn(1, teeth); so_p("\n" as *u8)
256 let lf: i64 = sys_openat_append("knowledge/status/nishi_os.log" as *u8, 0x1a4)
257 if lf >= 0 {
258 so_fp(lf, "U2048SMALLOPS selftest teeth=" as *u8); so_fn(lf, pass)
259 so_fp(lf, "of" as *u8); so_fn(lf, teeth)
260 so_fp(lf, " oracle=i64-native-arithmetic verdict=" as *u8)
261 if pass == teeth { so_fp(lf, "GREEN\n" as *u8) } else { so_fp(lf, "RED\n" as *u8) }
262 sys_close(lf)
263 }
264 if pass == teeth { sys_exit(0); return 0 }
265 sys_exit(1); return 1
266}
267
268func main(argc: i64, argv: *i64) -> i64 {
269 return so_selftest()
270}