nx_rsa2048_mod_exp.nx source
↩ module page · 81 lines · 2485 B
1// nx_rsa2048_mod_exp.nx -- RSA mod-exp s^e mod n for 2048-bit modulus.
2//
3// For RSA-PKCS#1 v1.5 signature verification, the public exponent e
4// is small (commonly 65537 = 2^16 + 1). We implement square-and-
5// multiply MSB-first over the bits of e expressed as an i64 (up to
6// 64-bit exponent supported).
7//
8// For e = 65537 = 0x10001, bits 16 and 0 are set; the loop runs
9// max(bit_length(e)) iterations.
10//
11// API:
12// rsa2048_mod_exp(out, s, e: i64, n) -- out = s^e mod n
13//
14// Caller responsibilities:
15// - s < n (range-checked here; returns nonzero verdict if s >= n)
16// - n is 2048-bit with top bit set
17// - e fits in i64 (true for all Web PKI: e is either 3, 17, 65537)
18//
19// license_tier: INDEPENDENT_REDERIVE
20// genealogy_id: international-research-sources/ietf/rfc_8017
21// lineage_id: nishi_rsa2048_mod_exp_q10
22
23// nx_safety_envelope:
24// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
25// sil_target: SIL1
26// evidence: [bulk_applied_2026-05-20, rsa2048-mod-exp-small-e]
27// verdict: NOT_YET_EVALUATED
28
29import "nx_syscalls.nx"
30import "nx_u2048.nx"
31import "nx_u2048_mul.nx"
32import "nx_rsa2048_mod.nx"
33
34const NX_RSA2048_MOD_EXP_OK: i64 = 1
35const NX_RSA2048_MOD_EXP_S_OUT_OF_RANGE: i64 = 2
36
37// Find the highest set bit index of e (0..63). Returns -1 if e == 0.
38func rsa2048_highbit_i64(e: i64) -> i64 {
39 if e == 0 { return 0 - 1 }
40 var i: i64 = 63
41 while i >= 0 {
42 if ((e >> i) & 1) == 1 { return i }
43 i = i - 1
44 }
45 return 0 - 1
46}
47
48// out = s^e mod n. Square-and-multiply, MSB-first.
49func rsa2048_mod_exp(out: *i64, s: *i64, e: i64, n: *i64) -> i64 {
50 if u2048_cmp(s, n) >= 0 { return NX_RSA2048_MOD_EXP_S_OUT_OF_RANGE }
51
52 let hb: i64 = rsa2048_highbit_i64(e)
53 if hb < 0 {
54 // e == 0: s^0 = 1.
55 u2048_one(out)
56 return NX_RSA2048_MOD_EXP_OK
57 }
58
59 let acc: *i64 = u2048_alloc()
60 u2048_copy(acc, s) // start with acc = s (the high bit of e)
61
62 var i: i64 = hb - 1
63 let tmp: *i64 = u2048_alloc()
64 while i >= 0 {
65 // Square: acc = acc*acc mod n
66 rsa2048_mul_mod(tmp, acc, acc, n)
67 u2048_copy(acc, tmp)
68 // If bit i of e set: acc = acc*s mod n
69 if ((e >> i) & 1) == 1 {
70 rsa2048_mul_mod(tmp, acc, s, n)
71 u2048_copy(acc, tmp)
72 }
73 i = i - 1
74 }
75 u2048_copy(out, acc)
76 return NX_RSA2048_MOD_EXP_OK
77}
78
79func main() -> i64 {
80 return 0
81}