nx_ed25519_signature.nx source
↩ module page · 366 lines · 12516 B
1// nx_ed25519_signature.nx -- final Ed25519 verify + sign (RFC 8032 §5.1).
2//
3// Phase 0b §I.1.D of the Ed25519 completion arc per
4// docs/NISHI_TLS13_GAP_AUDIT.md. Wires together all four shipped
5// substrate pieces (field T7 + decompress T8 + arith T9 + scalar
6// T10) into the final two callable signatures the rest of the
7// substrate consumes:
8//
9// ed25519_sign(priv32, msg, msg_len, sig_out_64)
10// ed25519_verify_full(pub32, msg, msg_len, sig_64) -> 1/0
11//
12// Plus the helper sc_muladd that sign needs.
13//
14// Sign (RFC 8032 §5.1.6):
15// 1. H = SHA-512(priv) ; 64 bytes
16// 2. s = clamp(H[0..32]) ; 32 bytes (secret scalar)
17// prefix = H[32..64] ; 32 bytes
18// 3. A = [s]B ; public key
19// A_enc = compress(A)
20// 4. r = sc_reduce(SHA-512(prefix || msg)) ; 32 bytes
21// R = [r]B
22// R_enc = compress(R) ; 32 bytes
23// 5. k = sc_reduce(SHA-512(R_enc || A_enc || msg)) ; 32 bytes
24// 6. S = (k*s + r) mod L = sc_muladd(k, s, r) ; 32 bytes
25// 7. signature = R_enc || S ; 64 bytes
26//
27// Verify (RFC 8032 §5.1.7):
28// 1. Parse sig: R_enc (32) || S (32). Reject if S >= L.
29// 2. Decompress R_enc -> R_pt; decompress pubkey -> A_pt.
30// 3. h = sc_reduce(SHA-512(R_enc || pubkey || msg))
31// 4. Check: [S]B == R_pt + [h]A_pt (compare via compressed encoding)
32//
33// What it does today: both sign and verify, KAT-verified against
34// RFC 8032 §7.1 TEST 1 (the empty-message vector).
35//
36// What it doesn't do yet:
37// - TEST 2 (1-byte) and TEST 3 (1023-byte) KATs are
38// mechanically the same; we ship TEST 1 to prove correctness
39// and queue TEST 2/3 as exhaustive interop.
40// - Constant-time signing (current sc_reduce is data-independent
41// in iteration count but the scalar mul is variable-time;
42// OK for KAT and for the sovereign-server signing path, but
43// should be hardened before client-side cert-auth use).
44//
45// Composes with:
46// - nx_sha512 (Sha512 ctx + init/update/final)
47// - nx_x25519 (fe_*)
48// - nx_ed25519_field, nx_ed25519_point, nx_ed25519_arith, nx_ed25519_scalar
49//
50// license_tier: INDEPENDENT_REDERIVE
51// genealogy_id: international-research-sources/ietf/rfc_8032
52// lineage_id: nishi_ed25519_signature_q10
53
54// nx_safety_envelope:
55// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
56// sil_target: SIL1
57// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
58// verdict: NOT_YET_EVALUATED
59
60import "nx_syscalls.nx"
61import "nx_sha512.nx"
62import "nx_x25519.nx"
63import "nx_ed25519_field.nx"
64import "nx_ed25519_point.nx"
65import "nx_ed25519_arith.nx"
66import "nx_ed25519_scalar.nx"
67
68const NX_ED25519_SIG_OK: i64 = 1
69const NX_ED25519_SIG_BAD: i64 = 0
70
71// Check S < L (RFC 8032 §5.1.7 step 1). Returns 1 if S < L, 0
72// otherwise. S is a 32-byte LE encoding. This is the malleability
73// defense -- accepting any S in [L, 2^256) lets attackers craft
74// alternative signatures for the same (msg, pubkey).
75func ed25519_s_lt_l(s_32: *u8) -> i64 {
76 let l: *u8 = sys_mmap(32)
77 l[0]=0xed; l[1]=0xd3; l[2]=0xf5; l[3]=0x5c
78 l[4]=0x1a; l[5]=0x63; l[6]=0x12; l[7]=0x58
79 l[8]=0xd6; l[9]=0x9c; l[10]=0xf7; l[11]=0xa2
80 l[12]=0xde; l[13]=0xf9; l[14]=0xde; l[15]=0x14
81 var li: i64 = 16
82 while li < 31 { l[li] = 0; li = li + 1 }
83 l[31] = 0x10
84 // Compare from MSB downward.
85 var i: i64 = 31
86 while i >= 0 {
87 let sv: i64 = s_32[i] & 0xff
88 let lv: i64 = l[i] & 0xff
89 if sv < lv { return 1 }
90 if sv > lv { return 0 }
91 i = i - 1
92 }
93 return 0 // equal -> NOT less-than
94}
95
96// Fill `out` (a GeP3) with the Ed25519 basepoint by decompressing
97// its canonical encoding (5866...66).
98func ed25519_basepoint_p3(out: *GeP3) -> i64 {
99 let b: *u8 = sys_mmap(32)
100 b[0] = 0x58
101 var i: i64 = 1
102 while i < 32 {
103 b[i] = 0x66
104 i = i + 1
105 }
106 return ge_p3_decompress(out, b)
107}
108
109// SHA-512 of n bytes into 64-byte `out`.
110func ed25519_sha512(msg: *u8, msg_len: i64, out_64: *u8) -> i64 {
111 let ctx_raw: *u8 = sys_mmap(512)
112 let ctx: *Sha512 = ctx_raw as *Sha512
113 sha512_init(ctx)
114 sha512_update(ctx, msg, msg_len)
115 sha512_final(ctx, out_64)
116 return 0
117}
118
119// SHA-512 of three concatenated buffers into 64-byte `out`.
120func ed25519_sha512_3(
121 a: *u8, a_len: i64,
122 b: *u8, b_len: i64,
123 c: *u8, c_len: i64,
124 out_64: *u8
125) -> i64 {
126 let ctx_raw: *u8 = sys_mmap(512)
127 let ctx: *Sha512 = ctx_raw as *Sha512
128 sha512_init(ctx)
129 sha512_update(ctx, a, a_len)
130 sha512_update(ctx, b, b_len)
131 sha512_update(ctx, c, c_len)
132 sha512_final(ctx, out_64)
133 return 0
134}
135
136// sc_muladd(out, a, b, c): out = (a*b + c) mod L.
137// All inputs are 32-byte little-endian scalars; output is 32 bytes.
138//
139// Algorithm: schoolbook 32×32 → 64-byte product using 8-bit limbs
140// (each partial product fits in 16 bits; accumulator + carry in
141// i64). Add c into low 32 bytes with carry propagation. Reduce
142// 64-byte result mod L via the shipped sc_reduce.
143//
144// Cost: ~1000 ops for the multiply + 32 ops for add + sc_reduce
145// (which is ~26000 ops). Per-signature cost: 1 sc_muladd + 2
146// sc_reduce + 2 ge_scalar_mul; the scalar muls dominate.
147func sc_muladd(out_32: *u8, a_32: *u8, b_32: *u8, c_32: *u8) -> i64 {
148 let prod: *u8 = sys_mmap(128)
149 var z: i64 = 0
150 while z < 64 {
151 prod[z] = 0
152 z = z + 1
153 }
154 // ---- Schoolbook multiply ----
155 var i: i64 = 0
156 while i < 32 {
157 let ai: i64 = a_32[i] & 0xff
158 if ai != 0 {
159 var carry: i64 = 0
160 var j: i64 = 0
161 while j < 32 {
162 let bj: i64 = b_32[j] & 0xff
163 let p: i64 = ai * bj + (prod[i + j] & 0xff) + carry
164 prod[i + j] = p & 0xff
165 carry = p >> 8
166 j = j + 1
167 }
168 // Propagate final carry into upper bytes (bounded to position 64).
169 var k: i64 = i + 32
170 while carry != 0 {
171 if k >= 64 { return 0 - 1 } // overflow shouldn't happen for valid inputs
172 let v: i64 = (prod[k] & 0xff) + carry
173 prod[k] = v & 0xff
174 carry = v >> 8
175 k = k + 1
176 }
177 }
178 i = i + 1
179 }
180 // ---- Add c into low 32 bytes ----
181 var c_carry: i64 = 0
182 var ci: i64 = 0
183 while ci < 32 {
184 let v: i64 = (prod[ci] & 0xff) + (c_32[ci] & 0xff) + c_carry
185 prod[ci] = v & 0xff
186 c_carry = v >> 8
187 ci = ci + 1
188 }
189 // Propagate c's carry into upper bytes (bounded).
190 var upper: i64 = 32
191 while c_carry != 0 {
192 if upper >= 64 { return 0 - 1 }
193 let v: i64 = (prod[upper] & 0xff) + c_carry
194 prod[upper] = v & 0xff
195 c_carry = v >> 8
196 upper = upper + 1
197 }
198 // ---- Reduce mod L ----
199 sc_reduce(prod, out_32)
200 return 0
201}
202
203// Compute Ed25519 signature. See file preamble for algorithm.
204//
205// priv must be exactly 32 bytes; sig_out_64 receives 64 bytes
206// (R_enc || S). Returns 0 on success.
207func ed25519_sign_full(
208 priv_32: *u8,
209 msg: *u8, msg_len: i64,
210 sig_out_64: *u8
211) -> i64 {
212 // ---- Step 1+2: H = SHA-512(priv); split + clamp ----
213 let h: *u8 = sys_mmap(64)
214 ed25519_sha512(priv_32, 32, h)
215 let s_scalar: *u8 = sys_mmap(32)
216 let prefix: *u8 = sys_mmap(32)
217 var i: i64 = 0
218 while i < 32 {
219 s_scalar[i] = h[i]
220 prefix[i] = h[32 + i]
221 i = i + 1
222 }
223 s_scalar[0] = s_scalar[0] & 0xf8
224 s_scalar[31] = (s_scalar[31] & 0x7f) | 0x40
225
226 // ---- Step 3: A = [s]B; compress ----
227 let bp: *GeP3 = ge_p3_alloc()
228 ed25519_basepoint_p3(bp)
229 let A_pt: *GeP3 = ge_p3_alloc()
230 ge_scalar_mul(A_pt, s_scalar, bp)
231 let A_enc: *u8 = sys_mmap(32)
232 ge_p3_compress(A_enc, A_pt)
233
234 // ---- Step 4: r = sc_reduce(SHA-512(prefix || msg)) ----
235 let r_h: *u8 = sys_mmap(64)
236 let empty: *u8 = sys_mmap(8)
237 ed25519_sha512_3(prefix, 32, msg, msg_len, empty, 0, r_h)
238 let r_scalar: *u8 = sys_mmap(32)
239 sc_reduce(r_h, r_scalar)
240
241 // R = [r]B; compress
242 let R_pt: *GeP3 = ge_p3_alloc()
243 ge_scalar_mul(R_pt, r_scalar, bp)
244 let R_enc: *u8 = sys_mmap(32)
245 ge_p3_compress(R_enc, R_pt)
246
247 // ---- Step 5: k = sc_reduce(SHA-512(R_enc || A_enc || msg)) ----
248 let k_h: *u8 = sys_mmap(64)
249 ed25519_sha512_3(R_enc, 32, A_enc, 32, msg, msg_len, k_h)
250 let k_scalar: *u8 = sys_mmap(32)
251 sc_reduce(k_h, k_scalar)
252
253 // ---- Step 6: S = (k * s + r) mod L ----
254 let S_scalar: *u8 = sys_mmap(32)
255 sc_muladd(S_scalar, k_scalar, s_scalar, r_scalar)
256
257 // ---- Step 7: signature = R_enc || S ----
258 var j: i64 = 0
259 while j < 32 {
260 sig_out_64[j] = R_enc[j]
261 sig_out_64[32 + j] = S_scalar[j]
262 j = j + 1
263 }
264 return 0
265}
266
267// Verify an Ed25519 signature. Returns NX_ED25519_SIG_OK (1) on
268// valid, NX_ED25519_SIG_BAD (0) on invalid. Negative on a
269// malformed signature (e.g. S >= L, non-decodable R or A).
270func ed25519_verify_full(
271 pub_32: *u8,
272 msg: *u8, msg_len: i64,
273 sig_64: *u8
274) -> i64 {
275 // ---- Step 1: parse sig + S < L check ----
276 let R_bytes: *u8 = sys_mmap(32)
277 let S_bytes: *u8 = sys_mmap(32)
278 var i: i64 = 0
279 while i < 32 {
280 R_bytes[i] = sig_64[i]
281 S_bytes[i] = sig_64[32 + i]
282 i = i + 1
283 }
284 if ed25519_s_lt_l(S_bytes) != 1 {
285 return NX_ED25519_SIG_BAD
286 }
287
288 // ---- Step 2: decompress R and A ----
289 let R_pt: *GeP3 = ge_p3_alloc()
290 let dR: i64 = ge_p3_decompress(R_pt, R_bytes)
291 if dR != NX_GE_VERDICT_OK { return NX_ED25519_SIG_BAD }
292 let A_pt: *GeP3 = ge_p3_alloc()
293 let dA: i64 = ge_p3_decompress(A_pt, pub_32)
294 if dA != NX_GE_VERDICT_OK { return NX_ED25519_SIG_BAD }
295
296 // ---- Step 3: h = sc_reduce(SHA-512(R_enc || A_enc || msg)) ----
297 let h_64: *u8 = sys_mmap(64)
298 ed25519_sha512_3(R_bytes, 32, pub_32, 32, msg, msg_len, h_64)
299 let h_32: *u8 = sys_mmap(32)
300 sc_reduce(h_64, h_32)
301
302 // ---- Step 4: [S]B == R + [h]A ? ----
303 let bp: *GeP3 = ge_p3_alloc()
304 ed25519_basepoint_p3(bp)
305 let SB: *GeP3 = ge_p3_alloc()
306 ge_scalar_mul(SB, S_bytes, bp)
307 let hA: *GeP3 = ge_p3_alloc()
308 ge_scalar_mul(hA, h_32, A_pt)
309 let R_plus_hA: *GeP3 = ge_p3_alloc()
310 ge_p3_add(R_plus_hA, R_pt, hA)
311 if ge_p3_equal(SB, R_plus_hA) == 1 {
312 return NX_ED25519_SIG_OK
313 }
314 return NX_ED25519_SIG_BAD
315}
316
317// ===== V-HOST-4c: ed25519_pub_from_priv (RFC 8032 §5.1.5) =================================================
318//
319// Derive 32-byte Ed25519 public key from 32-byte secret seed.
320// Per RFC 8032:
321// 1. H = SHA-512(priv_32) -> 64 bytes
322// 2. s = first 32 bytes of H; clamp per RFC 8032 §5.1.5:
323// s[0] &= 248 (clear low 3 bits)
324// s[31] &= 127 (clear high bit)
325// s[31] |= 64 (set bit 254)
326// 3. A = s * B (scalar mult of clamped s and base point)
327// 4. pub_32 = ge_p3_compress(A)
328//
329// Returns 0 on success; -1 on internal failure.
330
331func ed25519_pub_from_priv(priv_32: *u8, pub_32_out: *u8) -> i64 {
332 if (priv_32 as i64) == 0 { return 0 - 1 }
333 if (pub_32_out as i64) == 0 { return 0 - 1 }
334
335 // 1. H = SHA-512(priv_32)
336 let h: *u8 = sys_mmap(64)
337 ed25519_sha512(priv_32, 32, h)
338
339 // 2. Clamp first 32 bytes
340 let s_clamped: *u8 = sys_mmap(32)
341 var i: i64 = 0
342 while i < 32 { s_clamped[i] = h[i]; i = i + 1 }
343 s_clamped[0] = ((s_clamped[0] as i64) & 248) as u8
344 s_clamped[31] = ((s_clamped[31] as i64) & 127) as u8
345 s_clamped[31] = ((s_clamped[31] as i64) | 64) as u8
346
347 // 3. A = s_clamped * basepoint
348 // SITES-LIVE 2026-05-27 bug fix: ed25519_basepoint_p3 returns
349 // ge_p3_decompress's verdict which uses NX_GE_VERDICT_OK = 1
350 // (not 0!) for success. Old `!= 0` check incorrectly treated
351 // success as failure. Same bug pattern previously fixed in the
352 // verify path (lines 291 + 294). Aligned here.
353 let B: *GeP3 = ge_p3_alloc()
354 let bp_rc: i64 = ed25519_basepoint_p3(B)
355 if bp_rc != NX_GE_VERDICT_OK { return 0 - 1 }
356
357 let A: *GeP3 = ge_p3_alloc()
358 let mul_rc: i64 = ge_scalar_mul(A, s_clamped, B)
359 if mul_rc != 0 { return 0 - 1 }
360
361 // 4. pub_32 = compress(A)
362 let c_rc: i64 = ge_p3_compress(pub_32_out, A)
363 if c_rc != 0 { return 0 - 1 }
364
365 return 0
366}