nx_rsa2048_mod_exp_big.nx source

1// nx_rsa2048_mod_exp_big.nx -- F103e RUNG 4: modular exponentiation with a FULL-WIDTH exponent. 2// 3// THE GAP, found by reading the signature rather than the filename: the estate's 4// `rsa2048_mod_exp(out, s, e: i64, n)` takes the exponent as an **i64**, and its own header says so 5// plainly -- "e fits in i64 (true for all Web PKI: e is either 3, 17, 65537)". That is correct and 6// sufficient for VERIFICATION, where the public exponent is tiny. It is structurally unable to do 7// either of the two things F103e needs next: 8// * RSA SIGNING: s = m^d mod n, where the private exponent d is ~2048 bits. 9// * MILLER-RABIN: a^d mod n, where d = (n-1)/2^r is ~1024 bits -- i.e. RSA KEYGEN. 10// ★★★★★★A LIBRARY NAMED FOR AN OPERATION MAY IMPLEMENT ONLY THE DIRECTION ITS AUTHOR NEEDED. 11// "The estate has RSA" was true and useless; it has RSA-verify. The symbol table said i64 and the 12// filename did not. 13// 14// This is the same square-and-multiply as the incumbent, MSB-first, but walking the bits of a u2048 15// exponent instead of an i64. It deliberately does NOT re-implement the modular multiply -- it calls 16// the SAME `rsa2048_mul_mod` the incumbent calls, so there is exactly one modmul in the estate. 17// 18// ★THE ORACLE IS THE INCUMBENT: for every exponent that fits in an i64, this function must agree with 19// `rsa2048_mod_exp` BIT FOR BIT. The teeth check e = 3, 17, 65537 and 2^63-1 against it, then 20// exercise an exponent NO i64 can hold -- the case that motivated the organ and the one the 21// incumbent cannot answer, so it is reported as EXERCISED rather than cross-checked. 22// 23// Usage: nx_rsa2048_mod_exp_big selftest 24// Exit: 0 GREEN | 1 RED. Log -> knowledge/status/nishi_os.log, verdict= LAST. 25// license_tier: ORIGINAL 26import "nx_syscalls.nx" 27import "nx_u2048.nx" 28import "nx_u2048_mul.nx" 29import "nx_rsa2048_mod.nx" 30import "nx_rsa2048_mod_exp.nx" 31const MEB_MAGIC_65537: i64 = 65537 32const MEB_MAGIC_9223372036854775807: i64 = 9223372036854775807 33 34const MEB_OK: i64 = 1 35const MEB_S_OUT_OF_RANGE: i64 = 2 36const MEB_BITS: i64 = 2048 37 38func meb_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 } 39func meb_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 } 40func meb_fn(fd: i64, v: i64) -> i64 { 41 let bb: *u8 = sys_mmap(28); var m: i64 = v 42 if m < 0 { m = 0 - m } 43 let t: *u8 = sys_mmap(28); var k: i64 = 0 44 if m == 0 { t[0] = 48 as u8; k = 1 } 45 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 46 var i: i64 = 0 47 while i < k { bb[i] = t[k - 1 - i]; i = i + 1 } 48 sys_write(fd, bb, k); return 0 49} 50 51// highest set bit index of a u2048 exponent, or -1 if zero. Separate `found` flag ends the scan: 52// a loop that exits by clobbering its cursor destroys the position it was searching for. 53func meb_highbit(e: *i64) -> i64 { 54 var i: i64 = MEB_BITS - 1 55 while i >= 0 { 56 if u2048_get_bit(e, i) == 1 { return i } 57 i = i - 1 58 } 59 return 0 - 1 60} 61 62// out = s^e mod n, e full-width. Mirrors rsa2048_mod_exp exactly, over u2048 bits. 63func rsa2048_mod_exp_big(out: *i64, s: *i64, e: *i64, n: *i64) -> i64 { 64 if u2048_cmp(s, n) >= 0 { return MEB_S_OUT_OF_RANGE } 65 let hb: i64 = meb_highbit(e) 66 if hb < 0 { u2048_one(out); return MEB_OK } // e == 0 -> 1 67 68 let acc: *i64 = u2048_alloc() 69 let tmp: *i64 = u2048_alloc() 70 u2048_copy(acc, s) // the high bit of e 71 var i: i64 = hb - 1 72 while i >= 0 { 73 rsa2048_mul_mod(tmp, acc, acc, n) // square 74 u2048_copy(acc, tmp) 75 if u2048_get_bit(e, i) == 1 { 76 rsa2048_mul_mod(tmp, acc, s, n) // multiply 77 u2048_copy(acc, tmp) 78 } 79 i = i - 1 80 } 81 u2048_copy(out, acc) 82 return MEB_OK 83} 84 85// ---- teeth ------------------------------------------------------------------------------------- 86func meb_set_i64(x: *i64, v: i64) -> i64 { 87 let b: *u8 = sys_mmap(256) 88 var i: i64 = 0 89 while i < 256 { b[i] = 0 as u8; i = i + 1 } 90 var k: i64 = 0 91 while k < 8 { b[255 - k] = ((v >> (k * 8)) & 0xff) as u8; k = k + 1 } 92 u2048_load_be(x, b) 93 return 0 94} 95 96func meb_selftest() -> i64 { 97 var pass: i64 = 0 98 var teeth: i64 = 0 99 100 let n: *i64 = u2048_alloc() 101 let s: *i64 = u2048_alloc() 102 let e: *i64 = u2048_alloc() 103 let a: *i64 = u2048_alloc() 104 let b: *i64 = u2048_alloc() 105 106 // A modulus with the top bit set (the incumbent requires it) and a base below it. 107 let nb: *u8 = sys_mmap(256) 108 var i: i64 = 0 109 while i < 256 { nb[i] = 0 as u8; i = i + 1 } 110 nb[0] = 0xC7 as u8 // top bit set 111 i = 1 112 while i < 255 { nb[i] = ((i * 37 + 11) & 0xff) as u8; i = i + 1 } 113 nb[255] = 0x8D as u8 // odd 114 u2048_load_be(n, nb) 115 116 let sb: *u8 = sys_mmap(256) 117 i = 0 118 while i < 256 { sb[i] = 0 as u8; i = i + 1 } 119 i = 8 120 while i < 256 { sb[i] = ((i * 53 + 7) & 0xff) as u8; i = i + 1 } 121 u2048_load_be(s, sb) // s << n (high bytes zero) 122 123 // T1..T4 CROSS-CHECK AGAINST THE INCUMBENT for every exponent an i64 can hold. 124 // If the general path disagrees with the special-case path anywhere they overlap, it is wrong. 125 let evs: *i64 = sys_mmap(64) as *i64 126 evs[0] = 3; evs[1] = 17; evs[2] = MEB_MAGIC_65537; evs[3] = MEB_MAGIC_9223372036854775807 127 var t: i64 = 0 128 while t < 4 { 129 teeth = teeth + 1 130 let ev: i64 = evs[t] 131 let r1: i64 = rsa2048_mod_exp(a, s, ev, n) // incumbent, small-e path 132 meb_set_i64(e, ev) 133 let r2: i64 = rsa2048_mod_exp_big(b, s, e, n) // this organ, full-width path 134 var ok: i64 = 0 135 if r1 == 1 { if r2 == MEB_OK { if u2048_eq(a, b) == 1 { ok = 1 } } } 136 if ok == 1 { pass = pass + 1; meb_p("MEB-T" as *u8); meb_fn(1, t + 1) 137 meb_p(" agrees-with-incumbent e=" as *u8); meb_fn(1, ev); meb_p(" GREEN\n" as *u8) } 138 else { meb_p("MEB-T" as *u8); meb_fn(1, t + 1); meb_p(" RED e=" as *u8); meb_fn(1, ev) 139 meb_p(" rc1=" as *u8); meb_fn(1, r1); meb_p(" rc2=" as *u8); meb_fn(1, r2); meb_p("\n" as *u8) } 140 t = t + 1 141 } 142 143 // T5 e = 0 -> 1, on both paths (the boundary the loop must not enter) 144 teeth = teeth + 1 145 u2048_zero(e) 146 rsa2048_mod_exp_big(b, s, e, n) 147 let one: *i64 = u2048_alloc() 148 u2048_one(one) 149 if u2048_eq(b, one) == 1 { pass = pass + 1; meb_p("MEB-T5 e-zero-is-one GREEN\n" as *u8) } 150 else { meb_p("MEB-T5 RED\n" as *u8) } 151 152 // T6 e = 1 -> s 153 teeth = teeth + 1 154 meb_set_i64(e, 1) 155 rsa2048_mod_exp_big(b, s, e, n) 156 if u2048_eq(b, s) == 1 { pass = pass + 1; meb_p("MEB-T6 e-one-is-s GREEN\n" as *u8) } 157 else { meb_p("MEB-T6 RED\n" as *u8) } 158 159 // T7 THE CASE THAT MOTIVATED THE ORGAN: an exponent wider than any i64. The incumbent cannot be 160 // asked, so this is reported as EXERCISED, not cross-checked -- and it is bound to a property the 161 // incumbent CAN anchor: s^(2^64) must equal squaring s sixty-four times. 162 teeth = teeth + 1 163 u2048_zero(e) 164 let eb: *u8 = sys_mmap(256) 165 i = 0 166 while i < 256 { eb[i] = 0 as u8; i = i + 1 } 167 eb[247] = 0x01 as u8 // bit 64 set -> e = 2^64, NOT i64-representable 168 u2048_load_be(e, eb) 169 let r7: i64 = rsa2048_mod_exp_big(b, s, e, n) 170 // independent construction: square s 64 times 171 let acc: *i64 = u2048_alloc() 172 let tmp: *i64 = u2048_alloc() 173 u2048_copy(acc, s) 174 var k: i64 = 0 175 while k < 64 { rsa2048_mul_mod(tmp, acc, acc, n); u2048_copy(acc, tmp); k = k + 1 } 176 if r7 == MEB_OK { if u2048_eq(b, acc) == 1 { pass = pass + 1 177 meb_p("MEB-T7 exponent-beyond-i64 (2^64) matches 64 squarings GREEN\n" as *u8) } 178 else { meb_p("MEB-T7 RED [the wide-exponent path disagrees with repeated squaring]\n" as *u8) } } 179 else { meb_p("MEB-T7 RED rc=" as *u8); meb_fn(1, r7); meb_p("\n" as *u8) } 180 181 // T8 NEGATIVE CONTROL: a different exponent must give a different result. Without this, an organ 182 // that returned s unchanged (or a constant) would pass several teeth above. 183 teeth = teeth + 1 184 meb_set_i64(e, 3) 185 rsa2048_mod_exp_big(a, s, e, n) 186 meb_set_i64(e, 5) 187 rsa2048_mod_exp_big(b, s, e, n) 188 if u2048_eq(a, b) == 0 { pass = pass + 1; meb_p("MEB-T8 neg-control-different-e-differs GREEN\n" as *u8) } 189 else { meb_p("MEB-T8 RED [VACUOUS: exponent ignored]\n" as *u8) } 190 191 // T9 range guard: s >= n must be REFUSED by name, not silently reduced. 192 teeth = teeth + 1 193 meb_set_i64(e, 3) 194 if rsa2048_mod_exp_big(b, n, e, n) == MEB_S_OUT_OF_RANGE { pass = pass + 1 195 meb_p("MEB-T9 s-out-of-range-refused GREEN\n" as *u8) } 196 else { meb_p("MEB-T9 RED\n" as *u8) } 197 198 meb_p("MEB-SELFTEST " as *u8); meb_fn(1, pass); meb_p("/" as *u8); meb_fn(1, teeth); meb_p("\n" as *u8) 199 let lf: i64 = sys_openat_append("knowledge/status/nishi_os.log" as *u8, 0x1a4) 200 if lf >= 0 { 201 meb_fp(lf, "MODEXPBIG selftest teeth=" as *u8); meb_fn(lf, pass) 202 meb_fp(lf, "of" as *u8); meb_fn(lf, teeth) 203 meb_fp(lf, " oracle=rsa2048_mod_exp-incumbent-on-i64-overlap verdict=" as *u8) 204 if pass == teeth { meb_fp(lf, "GREEN\n" as *u8) } else { meb_fp(lf, "RED\n" as *u8) } 205 sys_close(lf) 206 } 207 if pass == teeth { sys_exit(0); return 0 } 208 sys_exit(1); return 1 209} 210 211func main(argc: i64, argv: *i64) -> i64 { 212 return meb_selftest() 213}