nx_bigint_modexp.nx source
↩ module page · 96 lines · 5820 B
1// nx_bigint_modexp.nx -- modular reduction + modular exponentiation on nx_bigint (the missing keystone).
2//
3// nx_bigint has add/sub/mul/shift/cmp but NO reduction, so it couldn't do a^e mod m -- the primitive under
4// Diffie-Hellman (hence BitTorrent MSE/PE anti-throttle encryption), RSA, and any modular crypto. This adds:
5// bi_mod -- rem = a mod m via bit-by-bit long division (shift-subtract), using only bi_shl1/cmp/sub.
6// bi_modexp -- result = base^exp mod m via square-and-multiply, reducing after every multiply.
7// Little-endian u32 limbs, same representation as nx_bigint. Caller owns all limb buffers (BI3). Correctness
8// first (not constant-time yet -- a DH/RSA hardening note; fine for the KAT + the anti-throttle handshake bring-up).
9//
10// nx_bigint_modexp -- no-arg = the GATE (classic + Fermat + multi-limb-reduction vectors)
11// license_tier: ORIGINAL module: nishi-core.crypto.bigint_modexp depends: nishi-core.bigint
12import "nx_bigint.nx"
13const K_MAGIC_4294967281: i64 = 4294967281
14
15func me_p(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
16func me_n(v: i64) -> i64 { let t: *u8=sys_mmap(28); var m: i64=v; 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} let o: *u8=sys_mmap(28); var i: i64=0; while i<k {o[i]=t[k-1-i];i=i+1} sys_write(1,o,k); return 0 }
17
18// rem (w limbs) = a (a_len limbs) mod m, where m is supplied ALREADY zero-extended to w limbs and m < 2^((w-1)*32)
19// (i.e. the top limb of m is 0 -> one limb of headroom for the shift). Standard binary long division, MSB-first.
20func bi_mod(rem: *i64, a: *i64, a_len: i64, m_w: *i64, w: i64) -> i64 {
21 bi_zero(rem, w)
22 var i: i64 = a_len*32 - 1
23 while i >= 0 {
24 bi_shl1(rem, w) // rem <<= 1 (rem < m < 2^((w-1)*32) => no overflow)
25 let bit: i64 = (a[i>>5] >> (i&31)) & 1
26 rem[0] = rem[0] | bit
27 if bi_cmp(rem, m_w, w) >= 0 { bi_sub(rem, rem, m_w, w) }
28 i = i - 1
29 }
30 return 0
31}
32
33// result (n limbs) = base^exp mod m. base/exp/m are n limbs each. m must be < 2^(n*32) (n-limb modulus).
34func bi_modexp(result: *i64, base: *i64, exp: *i64, m: *i64, n: i64) -> i64 {
35 let w: i64 = n + 1
36 let mw: *i64 = sys_mmap((w+2)*8) as *i64; bi_zero(mw, w); bi_copy(mw, m, n) // m zero-extended to w
37 let remw: *i64 = sys_mmap((w+2)*8) as *i64
38 let b: *i64 = sys_mmap((n+2)*8) as *i64
39 let prod: *i64 = sys_mmap((2*n+4)*8) as *i64
40 bi_mod(remw, base, n, mw, w); bi_copy(b, remw, n) // b = base mod m
41 bi_zero(result, n); result[0] = 1 // result = 1
42 var i: i64 = 0
43 let ebits: i64 = n*32
44 while i < ebits {
45 let bit: i64 = (exp[i>>5] >> (i&31)) & 1
46 if bit == 1 {
47 bi_mul(prod, result, n, b, n); bi_mod(remw, prod, 2*n, mw, w); bi_copy(result, remw, n)
48 }
49 bi_mul(prod, b, n, b, n); bi_mod(remw, prod, 2*n, mw, w); bi_copy(b, remw, n)
50 i = i + 1
51 }
52 return 0
53}
54
55// ---- helpers for the gate: set an n-limb bignum from a 64-bit value ----
56func me_set(dst: *i64, n: i64, lo: i64, hi: i64) -> i64 { bi_zero(dst, n); dst[0]=lo & 0xFFFFFFFF; dst[1]=hi & 0xFFFFFFFF; return 0 }
57func me_eq2(r: *i64, n: i64, lo: i64, hi: i64) -> i64 {
58 if (r[0] & 0xFFFFFFFF) != (lo & 0xFFFFFFFF) { return 0 }
59 if (r[1] & 0xFFFFFFFF) != (hi & 0xFFFFFFFF) { return 0 }
60 var i: i64=2; while i<n { if (r[i] & 0xFFFFFFFF) != 0 { return 0 } i=i+1 } return 1
61}
62
63func me_case(label: *u8, base_lo: i64, base_hi: i64, exp_lo: i64, exp_hi: i64, m_lo: i64, m_hi: i64, want_lo: i64, want_hi: i64, pass: *i64, tot: *i64) -> i64 {
64 let n: i64 = 4
65 let base: *i64 = sys_mmap((n+2)*8) as *i64; let exp: *i64 = sys_mmap((n+2)*8) as *i64
66 let m: *i64 = sys_mmap((n+2)*8) as *i64; let res: *i64 = sys_mmap((n+2)*8) as *i64
67 me_set(base, n, base_lo, base_hi); me_set(exp, n, exp_lo, exp_hi); me_set(m, n, m_lo, m_hi)
68 bi_modexp(res, base, exp, m, n)
69 let ok: i64 = me_eq2(res, n, want_lo, want_hi)
70 tot[0]=tot[0]+1; if ok==1 { pass[0]=pass[0]+1 }
71 me_p(" [" as *u8); if ok==1 { me_p("PASS" as *u8) } else { me_p("FAIL" as *u8) } me_p("] " as *u8); me_p(label)
72 me_p(" got=" as *u8); me_n(res[1]&0xFFFFFFFF); me_p(":" as *u8); me_n(res[0]&0xFFFFFFFF)
73 me_p(" want=" as *u8); me_n(want_hi&0xFFFFFFFF); me_p(":" as *u8); me_n(want_lo&0xFFFFFFFF); me_p("\n" as *u8)
74 return 0
75}
76
77func main() -> i64 {
78 let pass: *i64 = sys_mmap(8) as *i64; let tot: *i64 = sys_mmap(8) as *i64; pass[0]=0; tot[0]=0
79 me_p("BIGINT-MODEXP-GATE authored=organ\n" as *u8)
80 // 1. classic: 4^13 mod 497 = 445
81 me_case("4^13 mod 497 == 445" as *u8, 4,0, 13,0, 497,0, 445,0, pass, tot)
82 // 2. 2^10 mod 1000 = 24
83 me_case("2^10 mod 1000 == 24" as *u8, 2,0, 10,0, 1000,0, 24,0, pass, tot)
84 // 3. Fermat: 2^96 mod 97 == 1 (97 prime)
85 me_case("2^96 mod 97 == 1 (Fermat)" as *u8, 2,0, 96,0, 97,0, 1,0, pass, tot)
86 // 4. Carmichael: 2^560 mod 561 == 1 (561 = 3*11*17)
87 me_case("2^560 mod 561 == 1 (Carmichael)" as *u8, 2,0, 560,0, 561,0, 1,0, pass, tot)
88 // 5. MULTI-LIMB reduction: 2^41 mod (256*2^32+15=1099511627791) == 255*2^32+4294967281 = 1099511627761
89 // m: lo=15, hi=256 want: lo=4294967281 (0xFFFFFFF1), hi=255
90 me_case("2^41 mod 1099511627791 == 1099511627761 (2-limb)" as *u8, 2,0, 41,0, 15,256, K_MAGIC_4294967281,255, pass, tot)
91 // 6. MULTI-LIMB no-reduction: 2^40 mod 1099511627791 == 2^40 (lo=0, hi=256)
92 me_case("2^40 mod 1099511627791 == 2^40 (2-limb)" as *u8, 2,0, 40,0, 15,256, 0,256, pass, tot)
93 me_p("BIGINT-MODEXP-GATE pass=" as *u8); me_n(pass[0]); me_p("/" as *u8); me_n(tot[0])
94 if pass[0]==tot[0] { me_p(" verdict=GREEN\n" as *u8); sys_exit(0); return 0 }
95 me_p(" verdict=RED\n" as *u8); sys_exit(1); return 1
96}