nx_u2048_millerrabin.nx source

1// nx_u2048_millerrabin.nx -- F103e RUNG 5: probabilistic primality over u2048. 2// 3// The gate for RSA KEYGEN, which is the gate for signing, which is the gate for enrolling our own 4// Secure Boot key (debt 1786237435: real EDK2 with MS keys refuses our unsigned .efi; the SAME 5// secboot firmware in SETUP mode runs it, so the blocker is the enrolled key set). 6// Unblocked by nx_rsa2048_mod_exp_big: Miller-Rabin needs a^d mod n with d ~1024 bits, and the 7// estate's incumbent modexp takes the exponent as an i64 -- it structurally could not do this. 8// 9// ★NO RECALLED CONSTANTS. Every fixture's primality is established IN-TEST by independent i64 trial 10// division; the u2048 Miller-Rabin path is then required to agree. Two methods, one answer. An RSA 11// modulus recited from memory would be a fabricated constant, which is exactly what the estate's 12// rules forbid -- so the key gets GENERATED (next rung), never quoted. 13// 14// ★THE ANTI-VACUITY TOOTH IS THE CARMICHAEL FAMILY. 561 = 3*11*17, 1105 = 5*13*17, 1729 = 7*13*19 -- 15// built here AS PRODUCTS, so their compositeness is proven by construction rather than remembered. 16// They satisfy the FERMAT test for every coprime base, so an implementation that computed 17// a^(n-1) mod n instead of doing the square-root descent passes every other test in this file and 18// fails only these. ★★★★★★A WEAKER ALGORITHM WEARING THE RIGHT NAME PASSES EVERY TEST EXCEPT THE 19// ONE THAT WAS DESIGNED TO SEPARATE THEM. 20// 21// ★AND ONE TOOTH PROVES THE BASE LOOP MATTERS: 23*89 = 2047 is a strong pseudoprime to base 2, so 22// MR with bases {2} must report PROBABLY-PRIME (wrong, and expected) while {2,3} reports COMPOSITE. 23// Without this, a single-base implementation would look perfect. 24// 25// Usage: nx_u2048_millerrabin selftest 26// Exit: 0 GREEN | 1 RED. Log -> knowledge/status/nishi_os.log, verdict= LAST. 27// license_tier: ORIGINAL 28import "nx_syscalls.nx" 29import "nx_u2048.nx" 30import "nx_u2048_mul.nx" 31import "nx_rsa2048_mod.nx" 32import "nx_rsa2048_mod_exp.nx" 33import "nx_rsa2048_mod_exp_big.nx" 34const MR_MAGIC_2048: i64 = 2048 35const MR_MAGIC_1105: i64 = 1105 36const MR_MAGIC_1729: i64 = 1729 37const MR_MAGIC_2465: i64 = 2465 38const MR_MAGIC_2821: i64 = 2821 39const MR_MAGIC_2147483647: i64 = 2147483647 40const MR_MAGIC_65521: i64 = 65521 41const MR_MAGIC_65519: i64 = 65519 42 43const MR_SWEEP_HI: i64 = 512 // EXHAUSTIVE over [2, MR_SWEEP_HI]; traps beyond are named 44 45func mr_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 46func mr_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 } 47func mr_fn(fd: i64, v: i64) -> i64 { 48 let bb: *u8 = sys_mmap(28); var m: i64 = v 49 if m < 0 { m = 0 - m } 50 let t: *u8 = sys_mmap(28); var k: i64 = 0 51 if m == 0 { t[0] = 48 as u8; k = 1 } 52 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 53 var i: i64 = 0 54 while i < k { bb[i] = t[k - 1 - i]; i = i + 1 } 55 sys_write(fd, bb, k); return 0 56} 57 58func mr_set_i64(x: *i64, v: i64) -> i64 { 59 let b: *u8 = sys_mmap(256) 60 var i: i64 = 0 61 while i < 256 { b[i] = 0 as u8; i = i + 1 } 62 var k: i64 = 0 63 while k < 8 { b[255 - k] = ((v >> (k * 8)) & 0xff) as u8; k = k + 1 } 64 u2048_load_be(x, b) 65 return 0 66} 67 68// THE INDEPENDENT ORACLE: plain i64 trial division. Different arithmetic, different code path. 69func mr_i64_is_prime(v: i64) -> i64 { 70 if v < 2 { return 0 } 71 var i: i64 = 2 72 while (i * i) <= v { 73 if (v % i) == 0 { return 0 } 74 i = i + 1 75 } 76 return 1 77} 78 79// Miller-Rabin. Returns 1 = probably prime, 0 = COMPOSITE (definite). 80// bases are small i64 values; nbases of them. Deterministic given the base list, which is what makes 81// the teeth reproducible -- a random-base version wraps this once keygen needs it. 82func u2048_is_probable_prime(n: *i64, bases: *i64, nbases: i64) -> i64 { 83 let two: *i64 = u2048_alloc() 84 mr_set_i64(two, 2) 85 if u2048_cmp(n, two) < 0 { return 0 } // 0 and 1 are not prime 86 if u2048_cmp(n, two) == 0 { return 1 } // 2 is 87 if u2048_get_bit(n, 0) == 0 { return 0 } // any other even number is composite 88 89 let one: *i64 = u2048_alloc() 90 u2048_one(one) 91 let n1: *i64 = u2048_alloc() 92 u2048_sub_with_borrow(n1, n, one) // n1 = n - 1 93 94 // n-1 = d * 2^r -- r = count of trailing zero bits, found by INDEX not by clobbering a cursor 95 var r: i64 = 0 96 var scanning: i64 = 1 97 while scanning == 1 { 98 if u2048_get_bit(n1, r) == 1 { scanning = 0 } else { r = r + 1 } 99 if r >= MR_MAGIC_2048 { scanning = 0 } 100 } 101 let d: *i64 = u2048_alloc() 102 u2048_copy(d, n1) 103 var s: i64 = 0 104 while s < r { u2048_shr1(d); s = s + 1 } 105 106 let a: *i64 = u2048_alloc() 107 let x: *i64 = u2048_alloc() 108 let tmp: *i64 = u2048_alloc() 109 var bi: i64 = 0 110 while bi < nbases { 111 mr_set_i64(a, bases[bi]) 112 // require 2 <= a <= n-2; if the base is too big for this n, it carries no information 113 if u2048_cmp(a, n1) < 0 { 114 if rsa2048_mod_exp_big(x, a, d, n) != 1 { return 0 } 115 var witness: i64 = 1 // assume this base witnesses compositeness 116 if u2048_eq(x, one) == 1 { witness = 0 } 117 if u2048_eq(x, n1) == 1 { witness = 0 } 118 var k: i64 = 1 119 while k < r { 120 if witness == 1 { 121 rsa2048_mul_mod(tmp, x, x, n) 122 u2048_copy(x, tmp) 123 if u2048_eq(x, n1) == 1 { witness = 0 } 124 } 125 k = k + 1 126 } 127 if witness == 1 { return 0 } // definitely composite 128 } 129 bi = bi + 1 130 } 131 return 1 132} 133 134// ================================================================================================= 135func mr_selftest() -> i64 { 136 var pass: i64 = 0 137 var teeth: i64 = 0 138 let n: *i64 = u2048_alloc() 139 let bases: *i64 = sys_mmap(64) as *i64 140 bases[0] = 2; bases[1] = 3; bases[2] = 5; bases[3] = 7; bases[4] = 11 141 142 // T1 EXHAUSTIVE over [2, MR_SWEEP_HI] against independent i64 trial division. Not a sample -- 143 // the interval is stated and every value in it is checked. 144 teeth = teeth + 1 145 var mismatches: i64 = 0 146 var first_bad: i64 = 0 - 1 147 var v: i64 = 2 148 while v <= MR_SWEEP_HI { 149 mr_set_i64(n, v) 150 let got: i64 = u2048_is_probable_prime(n, bases, 5) 151 let want: i64 = mr_i64_is_prime(v) 152 if got != want { 153 mismatches = mismatches + 1 154 if first_bad < 0 { first_bad = v } 155 } 156 v = v + 1 157 } 158 if mismatches == 0 { pass = pass + 1 159 mr_p("MR-T1 exhaustive [2," as *u8); mr_fn(1, MR_SWEEP_HI) 160 mr_p("] agrees with i64 trial division GREEN\n" as *u8) } 161 else { mr_p("MR-T1 RED mismatches=" as *u8); mr_fn(1, mismatches) 162 mr_p(" first=" as *u8); mr_fn(1, first_bad); mr_p("\n" as *u8) } 163 164 // T2 ANTI-VACUITY: Carmichael numbers, CONSTRUCTED as products so compositeness is proven here. 165 // A Fermat test passes all of these; only the square-root descent catches them. 166 teeth = teeth + 1 167 let cf: *i64 = sys_mmap(128) as *i64 168 cf[0] = 3; cf[1] = 11; cf[2] = 17 // 561 169 cf[3] = 5; cf[4] = 13; cf[5] = 17 // MR_MAGIC_1105 170 cf[6] = 7; cf[7] = 13; cf[8] = 19 // MR_MAGIC_1729 171 cf[9] = 5; cf[10] = 17; cf[11] = 29 // MR_MAGIC_2465 172 cf[12] = 7; cf[13] = 13; cf[14] = 31 // MR_MAGIC_2821 173 var ci: i64 = 0 174 var carm_ok: i64 = 1 175 var carm_checked: i64 = 0 176 while ci < 5 { 177 let prod: i64 = cf[ci * 3] * cf[ci * 3 + 1] * cf[ci * 3 + 2] 178 if mr_i64_is_prime(prod) != 0 { carm_ok = 0 } // fixture sanity: a product IS composite 179 mr_set_i64(n, prod) 180 if u2048_is_probable_prime(n, bases, 5) != 0 { carm_ok = 0 } 181 carm_checked = carm_checked + 1 182 ci = ci + 1 183 } 184 if carm_ok == 1 { if carm_checked == 5 { pass = pass + 1 185 mr_p("MR-T2 carmichael-5of5-rejected (a Fermat test would pass all) GREEN\n" as *u8) } 186 else { mr_p("MR-T2 RED [VACUOUS: checked " as *u8); mr_fn(1, carm_checked); mr_p("]\n" as *u8) } } 187 else { mr_p("MR-T2 RED\n" as *u8) } 188 189 // T3 THE BASE LOOP MUST MATTER: 23*89 = 2047 is a strong pseudoprime to base 2. 190 // {2} alone must say PROBABLY-PRIME (wrong, and that is the point); {2,3} must say COMPOSITE. 191 teeth = teeth + 1 192 let sp: i64 = 23 * 89 193 mr_set_i64(n, sp) 194 let b1: *i64 = sys_mmap(32) as *i64 195 b1[0] = 2; b1[1] = 3 196 let one_base: i64 = u2048_is_probable_prime(n, b1, 1) 197 let two_base: i64 = u2048_is_probable_prime(n, b1, 2) 198 if mr_i64_is_prime(sp) == 0 { // fixture is genuinely composite 199 if one_base == 1 { if two_base == 0 { pass = pass + 1 200 mr_p("MR-T3 base-2-fooled-by-2047, base-3-catches-it GREEN\n" as *u8) } 201 else { mr_p("MR-T3 RED two-base did not catch it\n" as *u8) } } 202 else { mr_p("MR-T3 RED [single-base did NOT report probable-prime, so this fixture proves nothing about the base loop]\n" as *u8) } 203 } else { mr_p("MR-T3 RED [VACUOUS: fixture not composite]\n" as *u8) } 204 205 // T4 a large prime the sweep cannot reach: 2^31-1, verified in-test by i64 trial division. 206 teeth = teeth + 1 207 let big: i64 = MR_MAGIC_2147483647 208 if mr_i64_is_prime(big) == 1 { 209 mr_set_i64(n, big) 210 if u2048_is_probable_prime(n, bases, 5) == 1 { pass = pass + 1 211 mr_p("MR-T4 large-prime-2^31-1 GREEN\n" as *u8) } 212 else { mr_p("MR-T4 RED said composite\n" as *u8) } 213 } else { mr_p("MR-T4 RED [fixture failed its own trial division]\n" as *u8) } 214 215 // T5 a large COMPOSITE of two primes -- the RSA shape. Built as a product. 216 teeth = teeth + 1 217 let semi: i64 = MR_MAGIC_65521 * MR_MAGIC_65519 218 mr_set_i64(n, semi) 219 if u2048_is_probable_prime(n, bases, 5) == 0 { pass = pass + 1 220 mr_p("MR-T5 semiprime-rejected GREEN\n" as *u8) } 221 else { mr_p("MR-T5 RED\n" as *u8) } 222 223 // T6 boundaries: 0, 1 not prime; 2 prime; an even number composite. 224 teeth = teeth + 1 225 var bok: i64 = 1 226 mr_set_i64(n, 0); if u2048_is_probable_prime(n, bases, 5) != 0 { bok = 0 } 227 mr_set_i64(n, 1); if u2048_is_probable_prime(n, bases, 5) != 0 { bok = 0 } 228 mr_set_i64(n, 2); if u2048_is_probable_prime(n, bases, 5) != 1 { bok = 0 } 229 mr_set_i64(n, 4); if u2048_is_probable_prime(n, bases, 5) != 0 { bok = 0 } 230 if bok == 1 { pass = pass + 1; mr_p("MR-T6 boundaries-0-1-2-4 GREEN\n" as *u8) } 231 else { mr_p("MR-T6 RED\n" as *u8) } 232 233 mr_p("MR-SELFTEST " as *u8); mr_fn(1, pass); mr_p("/" as *u8); mr_fn(1, teeth); mr_p("\n" as *u8) 234 let lf: i64 = sys_openat_append("knowledge/status/nishi_os.log" as *u8, 0x1a4) 235 if lf >= 0 { 236 mr_fp(lf, "MILLERRABIN selftest teeth=" as *u8); mr_fn(lf, pass) 237 mr_fp(lf, "of" as *u8); mr_fn(lf, teeth) 238 mr_fp(lf, " sweep=exhaustive-2-to-" as *u8); mr_fn(lf, MR_SWEEP_HI) 239 mr_fp(lf, " oracle=i64-trial-division verdict=" as *u8) 240 if pass == teeth { mr_fp(lf, "GREEN\n" as *u8) } else { mr_fp(lf, "RED\n" as *u8) } 241 sys_close(lf) 242 } 243 if pass == teeth { sys_exit(0); return 0 } 244 sys_exit(1); return 1 245} 246 247func main(argc: i64, argv: *i64) -> i64 { 248 return mr_selftest() 249}