code wiki / _hdl_build / nx_rsa_keygen.nx
`nx_rsa_keygen.nx` source

↩ module page · 362 lines · 15879 B
1// nx_rsa_keygen.nx -- F103e RUNG 7: RSA key generation.
2//
3// The credential F103e has been walking toward. Real EDK2 with MS keys refuses our unsigned .efi
4// (Access Denied) while the SAME secboot firmware in SETUP mode runs it, so the blocker is the
5// enrolled key set (debt 1786237435). Enrolling OUR key requires HAVING one -- and it must be
6// GENERATED, never recited: an RSA modulus quoted from memory is a fabricated constant.
7//
8// Dependencies, both built earlier in this same arc because neither existed:
9//   nx_u2048_millerrabin  -- primality (needs a^d mod n with d ~1024 bits)
10//   nx_rsa2048_mod_exp_big -- that modexp (the incumbent takes the exponent as an i64)
11//   nx_u2048_smallops     -- d = (k*phi + 1)/e without a general extended GCD
12//
13// ⚠THE WIDTH TRAP, found by arithmetic and not by testing: for 1024-bit primes phi is ~2048 bits, so
14//  phi*k with k < e = 65537 is ~2065 bits and OVERFLOWS the u2048 width. The d-recovery therefore
15//  runs in the WIDE (128-limb) form. ★★★★★**AN INTERMEDIATE THAT OVERFLOWS ONLY AT PRODUCTION SIZE
16//  IS INVISIBLE TO EVERY SMALL-PARAMETER TEST** -- so the wide helpers are cross-checked against the
17//  shipped 64-limb smallops on 64-limb inputs (T2), making them the same ruler at two widths.
18//
19// ★THE CORRECTNESS PROOF NEEDS NO EXTERNAL ORACLE: a keypair is valid iff (m^e)^d == m mod n for
20//  messages we choose. That is checked for several m, INCLUDING m=1 and m=n-1 which any broken key
21//  still satisfies -- so a non-trivial m is required for the tooth to mean anything.
22//
23// Usage: nx_rsa_keygen selftest            (fast, small parameters -- proves the algorithm)
24//        nx_rsa_keygen gen <bits>          (real key from the CSPRNG, printed as hex)
25// ⚠the selftest uses a DETERMINISTIC generator so the teeth are reproducible. That path prints
26//  TEST-KEY-DO-NOT-USE and is unreachable from `gen`. ★A DETERMINISTIC KEY IS A TEST FIXTURE AND A
27//  SECURITY DEFECT WEARING THE SAME BYTES -- the two paths must never share an exit.
28// Exit: 0 GREEN | 1 RED.  Log -> knowledge/status/nishi_os.log, verdict= LAST.
29// license_tier: ORIGINAL
30import "nx_syscalls.nx"
31import "nx_u2048.nx"
32import "nx_u2048_mul.nx"
33import "nx_rsa2048_mod.nx"
34import "nx_rsa2048_mod_exp.nx"
35import "nx_rsa2048_mod_exp_big.nx"
36import "nx_u2048_millerrabin.nx"
37import "nx_u2048_smallops.nx"
38import "nx_csprng.nx"
39const KG_MAGIC_88172645463325252: i64 = 88172645463325252
40const KG_MAGIC_20260808: i64 = 20260808
41const KG_MAGIC_123456789012345: i64 = 123456789012345
42const KG_MAGIC_65537: i64 = 65537
43const KG_MAGIC_1024: i64 = 1024
44
45const KG_E:        i64 = 65537
46const KG_WIDE:     i64 = 128
47const KG_MAXTRY:   i64 = 20000
48
49func kg_p(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
50func kg_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 }
51func kg_fn(fd: i64, v: i64) -> i64 {
  let bb: *u8 = sys_mmap(28); var m: i64 = v
  if m < 0 { m = 0 - m; bb[0] = 45 as u8; sys_write(fd, bb, 1) }
  let t: *u8 = sys_mmap(28); var k: i64 = 0
  if m == 0 { t[0] = 48 as u8; k = 1 }
  while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
  var i: i64 = 0
  while i < k { bb[i] = t[k - 1 - i]; i = i + 1 }
  sys_write(fd, bb, k); return 0
60}
61func kg_hex(x: *i64) -> i64 {
  let hx: *u8 = "0123456789abcdef" as *u8
  let b: *u8 = sys_mmap(256)
  u2048_store_be(b, x)
  let o: *u8 = sys_mmap(600)
  var i: i64 = 0
  while i < 256 {
      o[i * 2]     = hx[(b[i] as i64) >> 4]
      o[i * 2 + 1] = hx[(b[i] as i64) & 0xf]
      i = i + 1
  }
  sys_write(1, o, 512); return 0
73}
74func kg_eq_str(a: *u8, b: *u8) -> i64 {
  var i: i64 = 0
  while a[i] != (0 as u8) { if a[i] != b[i] { return 0 } i = i + 1 }
  if b[i] != (0 as u8) { return 0 }
  return 1
79}
80
81// ---- generic big-by-small over N limbs. Same arithmetic as nx_u2048_smallops, parameterised by
82// ---- width because the d-recovery needs 128 limbs. T2 pins the two widths to each other.
83func kg_mul_small_n(out: *i64, a: *i64, k: i64, nl: i64) -> i64 {
  var i: i64 = 0
  var carry: i64 = 0
  while i < nl {
      let p: i64 = (a[i] & NX_U2048_LIMB_MASK) * k + carry
      out[i] = p & NX_U2048_LIMB_MASK
      carry = (p >> 32) & NX_U2048_LIMB_MASK
      i = i + 1
  }
  return carry
93}
94func kg_div_small_n(out: *i64, a: *i64, m: i64, nl: i64) -> i64 {
  if m <= 0 { return 0 - 1 }
  var rem: i64 = 0
  var i: i64 = nl - 1
  while i >= 0 {
      let cur: i64 = (rem << 32) | (a[i] & NX_U2048_LIMB_MASK)
      out[i] = cur / m
      rem = cur % m
      i = i - 1
  }
  return rem
105}
106func kg_mod_small_n(a: *i64, m: i64, nl: i64) -> i64 {
  if m <= 0 { return 0 - 1 }
  var rem: i64 = 0
  var i: i64 = nl - 1
  while i >= 0 {
      let cur: i64 = (rem << 32) | (a[i] & NX_U2048_LIMB_MASK)
      rem = cur % m
      i = i - 1
  }
  return rem
116}
117func kg_add_small_n(out: *i64, a: *i64, k: i64, nl: i64) -> i64 {
  var i: i64 = 0
  var carry: i64 = k
  while i < nl {
      let s: i64 = (a[i] & NX_U2048_LIMB_MASK) + carry
      out[i] = s & NX_U2048_LIMB_MASK
      carry = (s >> 32) & NX_U2048_LIMB_MASK
      i = i + 1
  }
  return carry
127}
128func kg_wide_zero(x: *i64) -> i64 { var i: i64 = 0; while i < KG_WIDE { x[i] = 0; i = i + 1 } return 0 }
129
130// ---- deterministic byte source for the TEST path (xorshift64*), and the CSPRNG for real keys.
131func kg_rng_next(st: *i64) -> i64 {
  var x: i64 = st[0]
  x = x ^ ((x << 13) & 0xFFFFFFFFFFFFFF)
  x = x ^ (x >> 7)
  x = x ^ ((x << 17) & 0xFFFFFFFFFFFFFF)
  if x == 0 { x = KG_MAGIC_88172645463325252 }
  st[0] = x
  return x & 0xFFFFFFFF
139}
140func kg_fill(dst: *u8, n: i64, st: *i64, deterministic: i64) -> i64 {
  if deterministic == 0 { return nx_csprng_fill(dst, n) }
  var i: i64 = 0
  while i < n { dst[i] = (kg_rng_next(st) & 0xff) as u8; i = i + 1 }
  return 0
145}
146
147// small-prime trial division: rejects ~80% of odd candidates far cheaper than Miller-Rabin
148func kg_trial_reject(c: *i64) -> i64 {
  let sp: *i64 = sys_mmap(512) as *i64
  sp[0]=3; sp[1]=5; sp[2]=7; sp[3]=11; sp[4]=13; sp[5]=17; sp[6]=19; sp[7]=23
  sp[8]=29; sp[9]=31; sp[10]=37; sp[11]=41; sp[12]=43; sp[13]=47; sp[14]=53; sp[15]=59
  sp[16]=61; sp[17]=67; sp[18]=71; sp[19]=73; sp[20]=79; sp[21]=83; sp[22]=89; sp[23]=97
  var i: i64 = 0
  while i < 24 {
      if u2048_mod_small(c, sp[i]) == 0 { return 1 }
      i = i + 1
  }
  return 0
159}
160
161// generate a probable prime of exactly `bits` bits (top two bits set, odd).
162// Returns the number of candidates examined, or -1 on exhaustion (REFUSED, never a weak key).
163func kg_gen_prime(out: *i64, bits: i64, st: *i64, deterministic: i64, bases: *i64, nb: i64) -> i64 {
  let nbytes: i64 = bits / 8
  let buf: *u8 = sys_mmap(256)
  var tries: i64 = 0
  while tries < KG_MAXTRY {
      tries = tries + 1
      var i: i64 = 0
      while i < 256 { buf[i] = 0 as u8; i = i + 1 }
      kg_fill(buf + (256 - nbytes), nbytes, st, deterministic)
      buf[256 - nbytes] = ((buf[256 - nbytes] as i64) | 0xC0) as u8   // top two bits -> exact size
      buf[255] = ((buf[255] as i64) | 1) as u8                        // odd
      u2048_load_be(out, buf)
      if kg_trial_reject(out) == 0 {
          if u2048_is_probable_prime(out, bases, nb) == 1 { return tries }
      }
  }
  return 0 - 1
180}
181
182// full keypair. Returns 1 on success, 0 on failure (never a partial key).
183func kg_keygen(bits: i64, p: *i64, q: *i64, n: *i64, d: *i64, st: *i64, deterministic: i64) -> i64 {
  let bases: *i64 = sys_mmap(64) as *i64
  bases[0]=2; bases[1]=3; bases[2]=5; bases[3]=7; bases[4]=11
  let one: *i64 = u2048_alloc(); u2048_one(one)
  let p1: *i64 = u2048_alloc()
  let q1: *i64 = u2048_alloc()
  let wide: *i64 = u2048_wide_alloc()
  let w2: *i64 = u2048_wide_alloc()
  let w3: *i64 = u2048_wide_alloc()
192
  var attempts: i64 = 0
  while attempts < 40 {
      attempts = attempts + 1
      if kg_gen_prime(p, bits, st, deterministic, bases, 5) < 0 { return 0 }
      if kg_gen_prime(q, bits, st, deterministic, bases, 5) < 0 { return 0 }
      if u2048_eq(p, q) == 1 { attempts = attempts } else {
          u2048_mul_wide(wide, p, q)
          u2048_wide_copy_low(n, wide)
          u2048_sub_with_borrow(p1, p, one)
          u2048_sub_with_borrow(q1, q, one)
          // phi = (p-1)(q-1), kept WIDE: at production size phi*k exceeds 2048 bits
          u2048_mul_wide(w2, p1, q1)
          let L: i64 = kg_mod_small_n(w2, KG_E, KG_WIDE)
          if L != 0 {
              let inv: i64 = i64_modinv_small(L, KG_E)
              if inv > 0 {
                  var k: i64 = (KG_E - inv) % KG_E
                  if k == 0 { k = KG_E }
                  // d = (phi*k + 1) / e   -- all wide, because phi*k is ~2065 bits
                  kg_mul_small_n(w3, w2, k, KG_WIDE)
                  kg_add_small_n(w3, w3, 1, KG_WIDE)
                  let r: i64 = kg_div_small_n(wide, w3, KG_E, KG_WIDE)
                  if r == 0 {                       // exact division is REQUIRED; otherwise retry
                      u2048_wide_copy_low(d, wide)
                      return 1
                  }
              }
          }
      }
  }
  return 0
224}
225
226// the only correctness statement that matters: (m^e)^d == m mod n
227func kg_roundtrip_ok(n: *i64, d: *i64, m: *i64) -> i64 {
  let c: *i64 = u2048_alloc()
  let back: *i64 = u2048_alloc()
  if rsa2048_mod_exp(c, m, KG_E, n) != 1 { return 0 }
  if rsa2048_mod_exp_big(back, c, d, n) != 1 { return 0 }
  return u2048_eq(back, m)
233}
234
235// =================================================================================================
236func kg_selftest() -> i64 {
  var pass: i64 = 0
  var teeth: i64 = 0
  let st: *i64 = sys_mmap(16) as *i64
  st[0] = KG_MAGIC_20260808
241
  kg_p("TEST-KEY-DO-NOT-USE: the selftest generator is DETERMINISTIC by design\n" as *u8)
243
  let p: *i64 = u2048_alloc()
  let q: *i64 = u2048_alloc()
  let n: *i64 = u2048_alloc()
  let d: *i64 = u2048_alloc()
248
  // T1 generate a keypair at a small-but-real size and prove it round-trips on a NON-TRIVIAL m.
  teeth = teeth + 1
  let got: i64 = kg_keygen(128, p, q, n, d, st, 1)
  var ok: i64 = 0
  if got == 1 {
      let m: *i64 = u2048_alloc()
      let b: *u8 = sys_mmap(256)
      var i: i64 = 0
      while i < 256 { b[i] = 0 as u8; i = i + 1 }
      b[240] = 0x2A as u8; b[250] = 0x99 as u8; b[255] = 0x07 as u8   // non-trivial, << n
      u2048_load_be(m, b)
      if kg_roundtrip_ok(n, d, m) == 1 { ok = 1 }
  }
  if ok == 1 { pass = pass + 1; kg_p("KG-T1 keygen-128 round-trips (m^e)^d==m GREEN\n" as *u8) }
  else { kg_p("KG-T1 RED keygen_rc=" as *u8); kg_fn(1, got); kg_p("\n" as *u8) }
264
  // T2 the WIDE helpers must agree with the shipped 64-limb smallops on 64-limb inputs.
  // Without this the production-only width is a second, unverified ruler.
  teeth = teeth + 1
  let a64: *i64 = u2048_alloc()
  let r1: *i64 = u2048_alloc()
  let r2: *i64 = u2048_alloc()
  so_set_i64(a64, KG_MAGIC_123456789012345)
  let m1: i64 = u2048_mod_small(a64, KG_MAGIC_65537)
  let m2: i64 = kg_mod_small_n(a64, KG_MAGIC_65537, NX_U2048_LIMBS)
  let d1: i64 = u2048_div_small(r1, a64, KG_MAGIC_65537)
  let d2: i64 = kg_div_small_n(r2, a64, KG_MAGIC_65537, NX_U2048_LIMBS)
  if m1 == m2 { if d1 == d2 { if u2048_eq(r1, r2) == 1 { pass = pass + 1
              kg_p("KG-T2 wide-helpers agree with shipped smallops GREEN\n" as *u8) }
          else { kg_p("KG-T2 RED quotient differs\n" as *u8) } }
      else { kg_p("KG-T2 RED remainder differs\n" as *u8) } }
  else { kg_p("KG-T2 RED mod differs\n" as *u8) }
281
  // T3 the generated primes must actually BE prime by the independent Miller-Rabin, and distinct.
  teeth = teeth + 1
  let bs: *i64 = sys_mmap(64) as *i64
  bs[0]=2; bs[1]=3; bs[2]=5; bs[3]=7; bs[4]=11; bs[5]=13; bs[6]=17
  var t3: i64 = 1
  if u2048_is_probable_prime(p, bs, 7) != 1 { t3 = 0 }
  if u2048_is_probable_prime(q, bs, 7) != 1 { t3 = 0 }
  if u2048_eq(p, q) == 1 { t3 = 0 }
  if t3 == 1 { pass = pass + 1; kg_p("KG-T3 p,q prime under 7 bases and distinct GREEN\n" as *u8) }
  else { kg_p("KG-T3 RED\n" as *u8) }
292
  // T4 ANTI-VACUITY / NEGATIVE CONTROL: a WRONG private exponent must FAIL the round trip.
  // Without this, a round-trip check that always returned 1 would pass T1.
  teeth = teeth + 1
  let dbad: *i64 = u2048_alloc()
  u2048_copy(dbad, d)
  dbad[0] = (dbad[0] ^ 1) & NX_U2048_LIMB_MASK          // flip one bit of d
  let m2b: *i64 = u2048_alloc()
  let bb2: *u8 = sys_mmap(256)
  var j: i64 = 0
  while j < 256 { bb2[j] = 0 as u8; j = j + 1 }
  bb2[248] = 0x11 as u8; bb2[255] = 0x0D as u8
  u2048_load_be(m2b, bb2)
  if kg_roundtrip_ok(n, dbad, m2b) == 0 { pass = pass + 1
      kg_p("KG-T4 neg-control-wrong-d-fails GREEN\n" as *u8) }
  else { kg_p("KG-T4 RED [VACUOUS: the round trip accepts a corrupted d]\n" as *u8) }
308
  // T5 n must have exactly 2*bits bits (top bit of the product set), i.e. the size is what we asked
  teeth = teeth + 1
  if u2048_get_bit(n, 2 * 128 - 1) == 1 { pass = pass + 1
      kg_p("KG-T5 modulus is the requested width GREEN\n" as *u8) }
  else { kg_p("KG-T5 RED modulus short\n" as *u8) }
314
  // T6 a second, independent m -- one round trip could coincide; two on different values is a claim
  teeth = teeth + 1
  let m3: *i64 = u2048_alloc()
  let b3: *u8 = sys_mmap(256)
  var z: i64 = 0
  while z < 256 { b3[z] = 0 as u8; z = z + 1 }
  b3[235] = 0x5C as u8; b3[244] = 0xA1 as u8; b3[255] = 0x3B as u8
  u2048_load_be(m3, b3)
  if kg_roundtrip_ok(n, d, m3) == 1 { pass = pass + 1; kg_p("KG-T6 second-message round-trips GREEN\n" as *u8) }
  else { kg_p("KG-T6 RED\n" as *u8) }
325
  kg_p("KG-SELFTEST " as *u8); kg_fn(1, pass); kg_p("/" as *u8); kg_fn(1, teeth); kg_p("\n" as *u8)
  let lf: i64 = sys_openat_append("knowledge/status/nishi_os.log" as *u8, 0x1a4)
  if lf >= 0 {
      kg_fp(lf, "RSAKEYGEN selftest teeth=" as *u8); kg_fn(lf, pass)
      kg_fp(lf, "of" as *u8); kg_fn(lf, teeth)
      kg_fp(lf, " gen=deterministic-TEST-ONLY verdict=" as *u8)
      if pass == teeth { kg_fp(lf, "GREEN\n" as *u8) } else { kg_fp(lf, "RED\n" as *u8) }
      sys_close(lf)
  }
  if pass == teeth { sys_exit(0); return 0 }
  sys_exit(1); return 1
337}
338
339func main(argc: i64, argv: *i64) -> i64 {
  if argc >= 2 { if kg_eq_str(argv[1] as *u8, "selftest" as *u8) == 1 { return kg_selftest() } }
  if argc >= 3 { if kg_eq_str(argv[1] as *u8, "gen" as *u8) == 1 {
      var bits: i64 = 0
      let a: *u8 = argv[2] as *u8
      var i: i64 = 0
      while a[i] != (0 as u8) { bits = bits * 10 + ((a[i] as i64) - 48); i = i + 1 }
      if bits < 64 { kg_p("REFUSED: bits too small to be a key\n" as *u8); sys_exit(2); return 2 }
      if bits > KG_MAGIC_1024 { kg_p("REFUSED: bits exceeds the u2048 modulus width\n" as *u8); sys_exit(2); return 2 }
      let p: *i64 = u2048_alloc(); let q: *i64 = u2048_alloc()
      let n: *i64 = u2048_alloc(); let d: *i64 = u2048_alloc()
      let st: *i64 = sys_mmap(16) as *i64
      st[0] = 1
      if kg_keygen(bits, p, q, n, d, st, 0) != 1 {      // deterministic=0 -> CSPRNG
          kg_p("KEYGEN FAILED\n" as *u8); sys_exit(1); return 1
      }
      kg_p("n="  as *u8); kg_hex(n); kg_p("\n" as *u8)
      kg_p("d="  as *u8); kg_hex(d); kg_p("\n" as *u8)
      kg_p("e=65537 bits="  as *u8); kg_fn(1, bits); kg_p("\n" as *u8)
      sys_exit(0); return 0
  } }
  kg_p("usage: nx_rsa_keygen selftest | nx_rsa_keygen gen <bits>\n" as *u8)
  sys_exit(2); return 2
362}
nx_rsa_keygen.nx source

`nx_rsa_keygen.nx` source
