nx_rsa2048_mod.nx source
↩ module page · 74 lines · 2548 B
1// nx_rsa2048_mod.nx -- bit-by-bit reduction mod 2048-bit modulus.
2//
3// Given a 4096-bit dividend (in a 128-limb wide buffer) and a
4// 2048-bit modulus n (in a 64-limb u2048 buffer with the top bit
5// set), compute the 2048-bit remainder.
6//
7// Algorithm (shift-and-subtract, MSB-first):
8// rem = 0 (u2048; one extra "carry" bit kept separately)
9// for i in 4095 down to 0:
10// rem = (rem << 1) | bit_i(dividend)
11// if (carry from shift) OR (rem >= n): rem -= n
12// return rem
13//
14// O(4096 * 64) limb operations ~= O(262K) per reduction. Combined
15// with 17 squarings/mul for RSA-2048 verify (e=65537), one verify
16// is ~4-5M limb ops -- a few seconds in qemu-riscv64.
17//
18// API:
19// rsa2048_mod(out_64, dividend_128, n_64) -- out_64 = dividend_128 mod n_64
20//
21// license_tier: INDEPENDENT_REDERIVE
22// genealogy_id: international-research-sources/ietf/rfc_8017
23// lineage_id: nishi_rsa2048_mod_q10
24
25// nx_safety_envelope:
26// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
27// sil_target: SIL1
28// evidence: [bulk_applied_2026-05-20, rsa2048-mod-bitwise]
29// verdict: NOT_YET_EVALUATED
30
31import "nx_syscalls.nx"
32import "nx_u2048.nx"
33import "nx_u2048_mul.nx"
34const K_MAGIC_2049: i64 = 2049
35
36func rsa2048_mod(out: *i64, dividend_128: *i64, n: *i64) -> i64 {
37 let rem: *i64 = u2048_alloc()
38 u2048_zero(rem)
39 var rem_top: i64 = 0 // extra carry bit (rem can be up to K_MAGIC_2049 bits transiently)
40
41 var i: i64 = NX_U2048_WIDE_LIMBS * NX_U2048_LIMB_BITS - 1
42 while i >= 0 {
43 // Shift rem left by 1. rem_top absorbs the carry out of bit 2047.
44 let shift_carry: i64 = u2048_shl1(rem)
45 rem_top = shift_carry
46 // Bring in bit i of dividend as new LSB.
47 let bit: i64 = u2048_wide_get_bit(dividend_128, i)
48 rem[0] = (rem[0] | bit) & NX_U2048_LIMB_MASK
49 // If rem_top is set (i.e. rem >= 2^2048 > n) OR rem >= n: subtract n.
50 if rem_top == 1 {
51 u2048_sub_with_borrow(rem, rem, n)
52 rem_top = 0
53 } else {
54 if u2048_cmp(rem, n) >= 0 {
55 u2048_sub_with_borrow(rem, rem, n)
56 }
57 }
58 i = i - 1
59 }
60 u2048_copy(out, rem)
61 return 0
62}
63
64// Multiply mod n: out = (a * b) mod n. Uses u2048_mul_wide + rsa2048_mod.
65func rsa2048_mul_mod(out: *i64, a: *i64, b: *i64, n: *i64) -> i64 {
66 let wide: *i64 = u2048_wide_alloc()
67 u2048_mul_wide(wide, a, b)
68 rsa2048_mod(out, wide, n)
69 return 0
70}
71
72func main() -> i64 {
73 return 0
74}