nx_rsa4096_mod.nx source
↩ module page · 71 lines · 2419 B
1// nx_rsa4096_mod.nx -- bit-by-bit reduction mod 4096-bit modulus.
2//
3// Given an 8192-bit dividend (in a 256-limb wide buffer) and a
4// 4096-bit modulus n (in a 128-limb u4096 buffer with the top bit
5// set), compute the 4096-bit remainder.
6//
7// Mirrors nx_rsa2048_mod with bit-width doubled (8191 iterations
8// instead of 4095; reduction takes ~4x more limb operations).
9//
10// Algorithm (shift-and-subtract, MSB-first):
11// rem = 0 (u4096; one extra "carry" bit kept separately)
12// for i in 8191 down to 0:
13// rem = (rem << 1) | bit_i(dividend)
14// if (carry from shift) OR (rem >= n): rem -= n
15// return rem
16//
17// O(8192 * 128) limb operations ~= O(1M) per reduction. Combined
18// with 17 squarings/mul for RSA verify (e=65537), one verify is
19// ~17M limb ops -- ~10-20 seconds in qemu-riscv64.
20//
21// API:
22// rsa4096_mod(out_128, dividend_256, n_128) -- out = dividend mod n
23//
24// license_tier: INDEPENDENT_REDERIVE
25// genealogy_id: international-research-sources/ietf/rfc_8017
26// lineage_id: nishi_rsa4096_mod_q1
27
28import "nx_syscalls.nx"
29import "nx_u4096.nx"
30import "nx_u4096_mul.nx"
31const K_MAGIC_4097: i64 = 4097
32
33func rsa4096_mod(out: *i64, dividend_256: *i64, n: *i64) -> i64 {
34 let rem: *i64 = u4096_alloc()
35 u4096_zero(rem)
36 var rem_top: i64 = 0 // extra carry bit (rem can be up to K_MAGIC_4097 bits transiently)
37
38 var i: i64 = NX_U4096_WIDE_LIMBS * NX_U4096_LIMB_BITS - 1
39 while i >= 0 {
40 // Shift rem left by 1. rem_top absorbs the carry out of bit 4095.
41 let shift_carry: i64 = u4096_shl1(rem)
42 rem_top = shift_carry
43 // Bring in bit i of dividend as new LSB.
44 let bit: i64 = u4096_wide_get_bit(dividend_256, i)
45 rem[0] = (rem[0] | bit) & NX_U4096_LIMB_MASK
46 // If rem_top is set (rem >= 2^4096 > n) OR rem >= n: subtract n.
47 if rem_top == 1 {
48 u4096_sub_with_borrow(rem, rem, n)
49 rem_top = 0
50 } else {
51 if u4096_cmp(rem, n) >= 0 {
52 u4096_sub_with_borrow(rem, rem, n)
53 }
54 }
55 i = i - 1
56 }
57 u4096_copy(out, rem)
58 return 0
59}
60
61// Multiply mod n: out = (a * b) mod n. Uses u4096_mul_wide + rsa4096_mod.
62func rsa4096_mul_mod(out: *i64, a: *i64, b: *i64, n: *i64) -> i64 {
63 let wide: *i64 = u4096_wide_alloc()
64 u4096_mul_wide(wide, a, b)
65 rsa4096_mod(out, wide, n)
66 return 0
67}
68
69func main() -> i64 {
70 return 0
71}