nx_p256_comb.nx source
↩ module page · 115 lines · 3955 B
1// nx_p256_comb.nx -- fixed-base windowed scalar multiplication for the
2// NIST P-256 generator G. Replaces the 256-doubling double-and-add for
3// k*G (the dominant ECDSA-sign cost) with a precomputed table:
4//
5// table[win][d] = d * 2^(4*win) * G for win in 0..63, d in 0..15
6//
7// k*G = sum over the 64 hex digits of k of table[win][digit_win].
8// ~64 point additions, ZERO doublings at sign time. The table is built
9// ONCE (deterministic -- multiples of the fixed G) and stored Jacobian
10// (X,Y,Z = 24 i64 = 192 bytes/entry; 1024 entries = 192 KiB) so the
11// build needs no per-entry inversion.
12//
13// Sharing model (NishiLang has no module-level mutable state): a tiny
14// generator tool writes the table to a file once; the signer reads it
15// (sys_read_file) and falls back to the generic double-and-add when the
16// file is absent (e.g. ACME/JOSE callers outside the sites daemon).
17//
18// Verified vs p256_scalar_mul over random scalars in nx_p256_comb_test.
19//
20// license_tier: INDEPENDENT_REDERIVE
21
22import "nx_syscalls.nx"
23import "nx_u256.nx"
24import "nx_p256_field.nx"
25import "nx_p256_point.nx"
26import "nx_p256_point_add.nx"
27
28// 64 windows * 16 digits * 24 i64 (X,Y,Z) = 24576 i64 = 196608 bytes.
29const NX_P256_COMB_ENTRIES: i64 = 1024
30const NX_P256_COMB_I64S: i64 = 24576
31const NX_P256_COMB_BYTES: i64 = 196608
32const NX_P256_COMB_PATH: *u8 = "/volume1/homes/elderwesto/nishihost/certs/p256_comb.bin" as *u8
33
34// Store a Jacobian point's 24 limbs (X,Y,Z) at table i64-offset off.
35func p256_comb_store(table: *i64, off: i64, p: *P256Point) -> i64 {
36 var t: i64 = 0
37 while t < 8 {
38 table[off + t] = p.x[t]
39 table[off + 8 + t] = p.y[t]
40 table[off + 16 + t] = p.z[t]
41 t = t + 1
42 }
43 return 0
44}
45
46// Load a Jacobian point's 24 limbs (X,Y,Z) from table i64-offset off.
47func p256_comb_load(p: *P256Point, table: *i64, off: i64) -> i64 {
48 var t: i64 = 0
49 while t < 8 {
50 p.x[t] = table[off + t]
51 p.y[t] = table[off + 8 + t]
52 p.z[t] = table[off + 16 + t]
53 t = t + 1
54 }
55 return 0
56}
57
58// Build the full comb table into `table` (must be NX_P256_COMB_I64S i64).
59func p256_comb_build(table: *i64) -> i64 {
60 let _fm: i64 = nx_scratch_save()
61 let g: *P256Point = p256_point_alloc()
62 p256_point_load_g(g)
63 let basew: *P256Point = p256_point_alloc() // 2^(4*win) * G
64 p256_point_copy(basew, g)
65 let acc: *P256Point = p256_point_alloc()
66
67 var win: i64 = 0
68 while win < 64 {
69 // d = 1..15 : acc = d * basew
70 p256_point_copy(acc, basew)
71 var d: i64 = 1
72 while d <= 15 {
73 let off: i64 = (win * 16 + d) * 24
74 p256_comb_store(table, off, acc)
75 if d < 15 { p256_point_add(acc, acc, basew) }
76 d = d + 1
77 }
78 // basew *= 2^4 for the next window
79 p256_point_double(basew, basew)
80 p256_point_double(basew, basew)
81 p256_point_double(basew, basew)
82 p256_point_double(basew, basew)
83 win = win + 1
84 }
85 nx_scratch_restore(_fm)
86 return 0
87}
88
89// out = k * G using the precomputed comb `table`. Returns Jacobian
90// (caller normalises via p256_point_to_affine), matching p256_scalar_mul
91// so it is a drop-in replacement. Aliasing: out must be distinct.
92func p256_scalar_mul_base(out: *P256Point, k: *i64, table: *i64) -> i64 {
93 p256_point_zero(out)
94 let _fm: i64 = nx_scratch_save()
95 let pt: *P256Point = p256_point_alloc()
96 var win: i64 = 0
97 while win < 64 {
98 let bitpos: i64 = win * 4
99 let limb_idx: i64 = bitpos / 32
100 let bit_in_limb: i64 = bitpos - limb_idx * 32
101 let digit: i64 = (k[limb_idx] >> bit_in_limb) & 0xF
102 if digit != 0 {
103 p256_comb_load(pt, table, (win * 16 + digit) * 24)
104 p256_point_add(out, out, pt)
105 }
106 win = win + 1
107 }
108 nx_scratch_restore(_fm)
109 return 0
110}
111
112// Compile-only smoke.
113func main() -> i64 {
114 return 0
115}