nx_rsa4096_mont_gate.nx source
↩ module page · 39 lines · 2023 B
1// nx_rsa4096_mont_gate.nx -- correctness KAT: the new Montgomery rsa4096_mod_exp_mont MUST equal the
2// trusted bit-by-bit rsa4096_mod_exp byte-for-byte on s^65537 mod n. This is what makes wiring the fast
3// path SAFE-BY-GATE (a wrong Montgomery goes RED, never a silent cert-validation bug). Mirrors
4// nx_rsa2048_mont_gate. license_tier: INDEPENDENT_REDERIVE
5import "nx_syscalls.nx"
6import "nx_u4096.nx"
7import "nx_rsa4096_mod_exp.nx"
8import "nx_rsa4096_mont.nx"
9
10func g_p(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
11
12func main() -> i64 {
13 g_p("=== RSA-4096 MONTGOMERY KAT: mont MUST equal the trusted bit-by-bit modexp ===\n" as *u8)
14 // construct a valid modulus n: odd, 4096-bit (top bit set). Any such n proves the two implementations agree.
15 let n: *i64 = u4096_alloc()
16 var i: i64 = 0
17 while i < 128 { n[i] = (0x80000000 + i * 7 + 1) & NX_U4096_LIMB_MASK; i = i + 1 }
18 n[0] = n[0] | 1 // odd
19 n[127] = n[127] | 0x80000000 // top bit set => 4096-bit
20 // s ~2048-bit (limbs 0..63 set, 64..127 zero) => s < n
21 let s: *i64 = u4096_alloc()
22 i = 0
23 while i < 64 { s[i] = (0x12345678 + i * 13) & NX_U4096_LIMB_MASK; i = i + 1 }
24 let e: i64 = 65537
25
26 let m1: *i64 = u4096_alloc()
27 let r1: i64 = rsa4096_mod_exp(m1, s, e, n) // trusted oracle (slow bit-by-bit)
28 let m2: *i64 = u4096_alloc()
29 let r2: i64 = rsa4096_mod_exp_mont(m2, s, e, n) // the new fast Montgomery
30
31 if r1 != NX_RSA4096_MOD_EXP_OK { g_p("FAIL: slow modexp errored\n" as *u8); sys_exit(1); return 1 }
32 if r2 != NX_RSA4096_MONT_OK { g_p("FAIL: mont modexp errored\n" as *u8); sys_exit(1); return 1 }
33 if u4096_cmp(m1, m2) == 0 {
34 g_p("RSA4096-MONT-GATE GREEN -- s^65537 mod n: Montgomery == bit-by-bit, byte-identical (SAFE to wire)\n" as *u8)
35 sys_exit(0); return 0
36 }
37 g_p("RSA4096-MONT-GATE RED -- MISMATCH: the Montgomery is WRONG, do NOT wire\n" as *u8)
38 sys_exit(1); return 1
39}