nx_rsa4096_mod_exp.nx source
↩ module page · 70 lines · 2076 B
1// nx_rsa4096_mod_exp.nx -- RSA mod-exp s^e mod n for 4096-bit modulus.
2//
3// Mirrors nx_rsa2048_mod_exp scaled to u4096. For RSA-PKCS#1 v1.5
4// signature verification, the public exponent e is small (commonly
5// 65537 = 2^16 + 1). Square-and-multiply MSB-first over bits of e.
6//
7// API:
8// rsa4096_mod_exp(out, s, e: i64, n) -- out = s^e mod n
9//
10// Caller responsibilities:
11// - s < n (range-checked here; returns nonzero verdict if s >= n)
12// - n is 4096-bit with top bit set
13// - e fits in i64 (true for all Web PKI: e is either 3, 17, 65537)
14//
15// license_tier: INDEPENDENT_REDERIVE
16// genealogy_id: international-research-sources/ietf/rfc_8017
17// lineage_id: nishi_rsa4096_mod_exp_q1
18
19import "nx_syscalls.nx"
20import "nx_u4096.nx"
21import "nx_u4096_mul.nx"
22import "nx_rsa4096_mod.nx"
23
24const NX_RSA4096_MOD_EXP_OK: i64 = 1
25const NX_RSA4096_MOD_EXP_S_OUT_OF_RANGE: i64 = 2
26
27// Find the highest set bit index of e (0..63). Returns -1 if e == 0.
28func rsa4096_highbit_i64(e: i64) -> i64 {
29 if e == 0 { return 0 - 1 }
30 var i: i64 = 63
31 while i >= 0 {
32 if ((e >> i) & 1) == 1 { return i }
33 i = i - 1
34 }
35 return 0 - 1
36}
37
38// out = s^e mod n. Square-and-multiply, MSB-first.
39func rsa4096_mod_exp(out: *i64, s: *i64, e: i64, n: *i64) -> i64 {
40 if u4096_cmp(s, n) >= 0 { return NX_RSA4096_MOD_EXP_S_OUT_OF_RANGE }
41
42 let hb: i64 = rsa4096_highbit_i64(e)
43 if hb < 0 {
44 u4096_one(out)
45 return NX_RSA4096_MOD_EXP_OK
46 }
47
48 let acc: *i64 = u4096_alloc()
49 u4096_copy(acc, s) // acc starts at s (the high bit of e)
50
51 var i: i64 = hb - 1
52 let tmp: *i64 = u4096_alloc()
53 while i >= 0 {
54 // Square: acc = acc*acc mod n
55 rsa4096_mul_mod(tmp, acc, acc, n)
56 u4096_copy(acc, tmp)
57 // If bit i of e set: acc = acc*s mod n
58 if ((e >> i) & 1) == 1 {
59 rsa4096_mul_mod(tmp, acc, s, n)
60 u4096_copy(acc, tmp)
61 }
62 i = i - 1
63 }
64 u4096_copy(out, acc)
65 return NX_RSA4096_MOD_EXP_OK
66}
67
68func main() -> i64 {
69 return 0
70}