nx_h2c_p256.nx source
↩ module page · 743 lines · 28490 B
1// nx_h2c_p256.nx -- RFC 9380 hash-to-curve for P-256.
2//
3// Ciphersuite: P256_XMD:SHA-256_SSWU_RO_ (RFC 9380 §8.2)
4//
5// Provides deterministic random-oracle mapping from arbitrary bytes
6// to a point on the NIST P-256 curve. Used by V-MODAUTH-1b OPRF
7// (RFC 9497) which is the registration primitive of OPAQUE PAKE.
8//
9// CARDINAL TRACEABILITY: composes existing substrate primitives per
10// "avoid duplicate primitives" cardinal:
11// nx_u256 (8-limb LE u256 big-int)
12// nx_p256_field (F_p add/sub/neg)
13// nx_p256_field_mul (F_p mul + sq)
14// nx_p256_field_inv (F_p Fermat inverse)
15// nx_p256_point (P-256 affine + projective)
16// nx_p256_point_add (point add for final summation)
17// sha256 (SHA-256 one-shot digest)
18//
19// COMPOSED BY:
20// hub/nx_voprf.nx (V-MODAUTH-1b OPRF protocol)
21// hub/nx_opaque_pake.nx (V-MODAUTH-2; indirectly via voprf)
22//
23// SPEC REFERENCES (every implementation choice cites a section):
24// RFC 9380 §3 hash_to_curve composition
25// RFC 9380 §5.3 hash_to_field
26// RFC 9380 §5.4.1 expand_message_xmd
27// RFC 9380 §8.2 P256_XMD:SHA-256_SSWU_RO_ ciphersuite params
28// RFC 9380 §F.2 Simplified SWU for AB == 0 (NOT applicable here)
29// RFC 9380 §F.2.1.2 Simplified SWU for AB != 0 (THIS one for P-256)
30// RFC 9380 §I.1 P-256 SSWU constants Z, A, B, c1, c2
31// RFC 9380 §J.1.1 P-256 hash-to-curve TEST VECTORS
32//
33// WINNER-TIER: BASELINE-A provisional pending RFC 9380 §J.1.1 test
34// vector verification by bench/nx_h2c_p256_smoke.sh.
35// INCUMBENTS: voprf-rs (Rust; rustcrypto), filippo.io/edwards25519
36// (Go; primarily Ed25519 but their P-256 is similar),
37// hash_to_curve.py (RFC reference impl in Python)
38// NUMBERS: measured client-side cost per hash_to_curve call:
39// pending bench post-smoke
40// GAP: no clear_cofactor (P-256 cofactor = 1; identity);
41// VOPRF/POPRF DLEQ proof variant (RFC 9380 doesn't cover;
42// RFC 9497 does and lives in nx_voprf)
43// EXEMPTION REASON: n/a; provisional pending vector verification
44//
45// V1 HONEST SCOPE LIMIT (per NISHI_CODE_HYGIENE_STANDARD M6):
46// - The SSWU constant c2 (= sqrt(-Z) mod p, where Z = -10) is
47// hard-coded from RFC 9380 §I.1. Substrate cannot YET compute
48// sqrt in F_p (Tonelli-Shanks or p^((p+1)/4) Fermat would be
49// ~80 lines added; queued V+1). The RFC 9380 §J.1.1 test vector
50// run by bench/nx_h2c_p256_smoke.sh validates the hard-coded
51// value indirectly — if c2 is wrong, the test vector fails.
52// - This is NOT a pretend stub: the constant IS the spec-defined
53// value; the test vector is the verification.
54
55import "nx_syscalls.nx"
56import "nx_u256.nx"
57import "nx_p256_field.nx"
58import "nx_p256_field_mul.nx"
59import "nx_p256_field_inv.nx"
60import "nx_p256_point.nx"
61import "nx_p256_point_add.nx"
62import "sha256.nx"
63
64// ===== Sealed verdict surface (codes 1300-1319) =================================================
65const NX_H2C_OK: i64 = 0
66const NX_H2C_BAD_INPUT: i64 = 1300
67const NX_H2C_BUF_OVERFLOW: i64 = 1301
68const NX_H2C_DST_TOO_LONG: i64 = 1302
69const NX_H2C_LEN_TOO_LONG: i64 = 1303
70const NX_H2C_SQRT_NOT_QR: i64 = 1304 // unreachable for RO mode; defensive
71const NX_H2C_POINT_NOT_ON_CURVE: i64 = 1305 // post-condition violation
72
73// ===== Named constants (per Cardinal M7: no magic numbers) =================================================
74//
75// RFC 9380 §8.2: P256_XMD:SHA-256_SSWU_RO_
76// hash = SHA-256
77// b_in_bytes = 32 (SHA-256 output)
78// s_in_bytes = 64 (SHA-256 input block size)
79// L = 48 (per §5.3: ceil((ceil(log2(p)) + k) / 8) = ceil((256+128)/8))
80// k = 128 (security level in bits)
81// m = 1 (P-256 extension degree = 1)
82// expand = XMD (eXpand Message XOF using a hash; §5.4.1)
83// map = SSWU (Simplified Shallue-van de Woestijne-Ulas; §F.2.1.2)
84
85const NX_H2C_B_IN_BYTES: i64 = 32
86const NX_H2C_S_IN_BYTES: i64 = 64
87const NX_H2C_L: i64 = 48
88const NX_H2C_FIELD_BYTES: i64 = 32 // P-256 field element = 32 bytes
89const NX_H2C_MAX_DST_LEN: i64 = 255 // RFC 9380 §5.4.3 hard limit
90const NX_H2C_MAX_MSG_LEN: i64 = 8192 // sanity cap; OPRF inputs are short
91const NX_H2C_MAX_OUT_BYTES: i64 = 8160 // 255 * 32 (XMD upper bound)
92
93// ===== I2OSP helpers per RFC 8017 §4.1 =================================================
94//
95// I2OSP(x, k): Integer-to-Octet-String Primitive; encodes a
96// nonnegative integer x as a k-byte big-endian octet string.
97//
98// We only need k=1, k=2, and k=4 variants. Per Cardinal 22:
99// compose small focused functions, not one over-general.
100
101func _h2c_i2osp_1(x: i64, out: *u8) -> i64 {
102 if x < 0 { return 0 - NX_H2C_BAD_INPUT }
103 if x > 255 { return 0 - NX_H2C_BAD_INPUT }
104 out[0] = x as u8
105 return NX_H2C_OK
106}
107
108func _h2c_i2osp_2(x: i64, out: *u8) -> i64 {
109 if x < 0 { return 0 - NX_H2C_BAD_INPUT }
110 if x > 65535 { return 0 - NX_H2C_BAD_INPUT }
111 out[0] = ((x >> 8) & 0xFF) as u8
112 out[1] = (x & 0xFF) as u8
113 return NX_H2C_OK
114}
115
116// ===== expand_message_xmd_sha256 per RFC 9380 §5.4.1 =================================================
117//
118// Inputs:
119// msg arbitrary-length input bytes
120// msg_len length of msg
121// dst domain separation tag (≤ 255 bytes per §5.4.3)
122// dst_len length of dst
123// len_in_bytes how many bytes to produce (≤ 8160 = 255 * 32)
124// out output buffer (len_in_bytes capacity)
125//
126// Algorithm (verbatim from RFC 9380 §5.4.1; pseudocode below):
127// 1. ell = ceil(len_in_bytes / b_in_bytes)
128// 2. ABORT if ell > 255 or len_in_bytes > 65535 or len(DST) > 255
129// 3. DST_prime = DST || I2OSP(len(DST), 1)
130// 4. Z_pad = I2OSP(0, s_in_bytes)
131// 5. l_i_b_str = I2OSP(len_in_bytes, 2)
132// 6. msg_prime = Z_pad || msg || l_i_b_str || I2OSP(0, 1) || DST_prime
133// 7. b_0 = H(msg_prime)
134// 8. b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
135// 9. for i in 2..ell:
136// b_i = H(strxor(b_0, b_{i-1}) || I2OSP(i, 1) || DST_prime)
137// 10. uniform_bytes = b_1 || b_2 || ... || b_ell
138// 11. return uniform_bytes[0 : len_in_bytes]
139
140func nx_h2c_expand_message_xmd_sha256(
141 msg: *u8, msg_len: i64,
142 dst: *u8, dst_len: i64,
143 len_in_bytes: i64,
144 out: *u8
145) -> i64 {
146 if (msg as i64) == 0 { return 0 - NX_H2C_BAD_INPUT }
147 if msg_len < 0 { return 0 - NX_H2C_BAD_INPUT }
148 if msg_len > NX_H2C_MAX_MSG_LEN { return 0 - NX_H2C_BAD_INPUT }
149 if (dst as i64) == 0 { return 0 - NX_H2C_BAD_INPUT }
150 if dst_len < 1 { return 0 - NX_H2C_BAD_INPUT }
151 if dst_len > NX_H2C_MAX_DST_LEN { return 0 - NX_H2C_DST_TOO_LONG }
152 if len_in_bytes < 1 { return 0 - NX_H2C_BAD_INPUT }
153 if len_in_bytes > NX_H2C_MAX_OUT_BYTES { return 0 - NX_H2C_LEN_TOO_LONG }
154 if (out as i64) == 0 { return 0 - NX_H2C_BAD_INPUT }
155
156 // Step 1.
157 let ell: i64 = (len_in_bytes + NX_H2C_B_IN_BYTES - 1) / NX_H2C_B_IN_BYTES
158
159 // Step 2: covered above + ell <= 255
160 if ell > 255 { return 0 - NX_H2C_LEN_TOO_LONG }
161
162 // Step 3: DST_prime = DST || I2OSP(len(DST), 1)
163 let dst_prime_len: i64 = dst_len + 1
164 let dst_prime: *u8 = sys_mmap(dst_prime_len)
165 var i: i64 = 0
166 while i < dst_len {
167 dst_prime[i] = dst[i]
168 i = i + 1
169 }
170 let rc_dp: i64 = _h2c_i2osp_1(dst_len, (dst_prime as i64 + dst_len) as *u8)
171 if rc_dp != NX_H2C_OK { return rc_dp }
172
173 // Step 4-6: msg_prime = Z_pad || msg || l_i_b_str || 0x00 || DST_prime
174 // Z_pad = s_in_bytes (64) zero bytes
175 // l_i_b = I2OSP(len_in_bytes, 2) (2 bytes)
176 // zero_one = I2OSP(0, 1) = single 0x00 byte
177 let msg_prime_len: i64 = NX_H2C_S_IN_BYTES + msg_len + 2 + 1 + dst_prime_len
178 let msg_prime: *u8 = sys_mmap(msg_prime_len)
179 var j: i64 = 0
180 while j < NX_H2C_S_IN_BYTES { msg_prime[j] = 0 as u8; j = j + 1 }
181 var k: i64 = 0
182 while k < msg_len { msg_prime[NX_H2C_S_IN_BYTES + k] = msg[k]; k = k + 1 }
183 let rc_lib: i64 = _h2c_i2osp_2(len_in_bytes,
184 (msg_prime as i64 + NX_H2C_S_IN_BYTES + msg_len) as *u8)
185 if rc_lib != NX_H2C_OK { return rc_lib }
186 msg_prime[NX_H2C_S_IN_BYTES + msg_len + 2] = 0 as u8
187 var m: i64 = 0
188 while m < dst_prime_len {
189 msg_prime[NX_H2C_S_IN_BYTES + msg_len + 3 + m] = dst_prime[m]
190 m = m + 1
191 }
192
193 // Step 7: b_0 = H(msg_prime)
194 let b_0: *u8 = sys_mmap(NX_H2C_B_IN_BYTES)
195 sha256_digest(msg_prime, msg_prime_len, b_0)
196
197 // Step 8: b_1 = H(b_0 || I2OSP(1, 1) || DST_prime)
198 // We reuse a scratch buffer for (b_0 XOR b_prev) || ctr || DST_prime
199 // for all subsequent iterations.
200 let xor_scratch_len: i64 = NX_H2C_B_IN_BYTES + 1 + dst_prime_len
201 let xor_scratch: *u8 = sys_mmap(xor_scratch_len)
202 var n: i64 = 0
203 while n < NX_H2C_B_IN_BYTES {
204 xor_scratch[n] = b_0[n]
205 n = n + 1
206 }
207 xor_scratch[NX_H2C_B_IN_BYTES] = 1 as u8
208 var p: i64 = 0
209 while p < dst_prime_len {
210 xor_scratch[NX_H2C_B_IN_BYTES + 1 + p] = dst_prime[p]
211 p = p + 1
212 }
213 let b_curr: *u8 = sys_mmap(NX_H2C_B_IN_BYTES)
214 sha256_digest(xor_scratch, xor_scratch_len, b_curr)
215
216 // Write b_1 into out (first b_in_bytes; may be truncated for last block)
217 var copy1_eff: i64 = NX_H2C_B_IN_BYTES
218 if copy1_eff > len_in_bytes { copy1_eff = len_in_bytes }
219 var q: i64 = 0
220 while q < copy1_eff {
221 out[q] = b_curr[q]
222 q = q + 1
223 }
224 var written: i64 = copy1_eff
225 var prev_b: *u8 = b_curr
226
227 // Step 9: for i in 2..ell
228 var i_ctr: i64 = 2
229 while i_ctr <= ell {
230 // strxor(b_0, prev_b) into xor_scratch[0..32]
231 var r: i64 = 0
232 while r < NX_H2C_B_IN_BYTES {
233 xor_scratch[r] = ((b_0[r] as i64) ^ (prev_b[r] as i64)) as u8
234 r = r + 1
235 }
236 xor_scratch[NX_H2C_B_IN_BYTES] = i_ctr as u8
237 // DST_prime already in scratch tail; unchanged
238 let b_next: *u8 = sys_mmap(NX_H2C_B_IN_BYTES)
239 sha256_digest(xor_scratch, xor_scratch_len, b_next)
240 let remaining: i64 = len_in_bytes - written
241 var copy_n: i64 = NX_H2C_B_IN_BYTES
242 if copy_n > remaining { copy_n = remaining }
243 var s: i64 = 0
244 while s < copy_n {
245 out[written + s] = b_next[s]
246 s = s + 1
247 }
248 written = written + copy_n
249 prev_b = b_next
250 i_ctr = i_ctr + 1
251 }
252
253 return NX_H2C_OK
254}
255
256// ===== hash_to_field for P-256 per RFC 9380 §5.3 =================================================
257//
258// For P256_XMD:SHA-256_SSWU_RO_:
259// m = 1 (P-256 field extension degree)
260// L = 48 (bytes per field element)
261// count = number of field elements to produce
262//
263// Algorithm (RFC 9380 §5.3):
264// 1. len_in_bytes = count * m * L
265// 2. uniform_bytes = expand_message(msg, DST, len_in_bytes)
266// 3. for i in 0..count:
267// elm_offset = L * i * m
268// tv = uniform_bytes[elm_offset : elm_offset + L]
269// e_0 = OS2IP(tv) mod p (OS2IP = big-endian to int)
270// u_i = (e_0,) (m=1 so 1-element tuple)
271// return (u_0, ..., u_{count-1})
272//
273// We output `count` 8-limb LE u256 field elements at consecutive
274// 32-byte slots in out_field_elements.
275
276// 48-byte big-endian → mod p reduction.
277//
278// Input is a 48-byte big-endian integer in [0, 2^384).
279// Decompose as bytes = high (16 bytes) || low (32 bytes).
280// Then bytes_as_int = high * 2^256 + low.
281//
282// (high * 2^256 + low) mod p
283// = (high * (2^256 mod p) + low) mod p
284// = (high * R + low) mod p where R = 2^256 - p
285//
286// For P-256: R = 2^224 - 2^192 - 2^96 + 1, fits comfortably in u256.
287// Implementation: load high as u256 (zero-extend), load low as u256
288// (may need 1 mod-p subtraction since low can be >= p), compute
289// (high * R) mod p via p256_field_mul, then add low mod p.
290//
291// Note: we use p256_field_mul which expects already-reduced inputs.
292// `high` (16 bytes) is < 2^128 << p so trivially canonical. `R` is
293// a known small constant < p. So p256_field_mul gives high*R mod p
294// in canonical form.
295
296func _h2c_load_r_constant(out: *i64) -> i64 {
297 // R = 2^256 - p = 2^224 - 2^192 - 2^96 + 1
298 //
299 // LE 8-limb layout (limb[0] = LSB):
300 // limb[0] = 0x00000001 (the +1)
301 // limb[1] = 0x00000000
302 // limb[2] = 0x00000000
303 // limb[3] = 0xFFFFFFFF (this is -2^96 contribution after carry; see derivation below)
304 // limb[4] = 0xFFFFFFFF
305 // limb[5] = 0xFFFFFFFF
306 // limb[6] = 0xFFFFFFFE (2^224 - 1 in high)
307 // limb[7] = 0x00000000
308 //
309 // Derivation: p = 0xFFFFFFFF 00000001 00000000 00000000 00000000 FFFFFFFF FFFFFFFF FFFFFFFF
310 // 2^256 - p = (above) negated in 256-bit arithmetic
311 // = 0x00000000 FFFFFFFE FFFFFFFF FFFFFFFF FFFFFFFF 00000000 00000000 00000001
312 //
313 // LE limb breakdown (each limb = 4 hex chars from low to high):
314 out[0] = 0x00000001 as i64
315 out[1] = 0x00000000 as i64
316 out[2] = 0x00000000 as i64
317 out[3] = 0xFFFFFFFF as i64
318 out[4] = 0xFFFFFFFF as i64
319 out[5] = 0xFFFFFFFF as i64
320 out[6] = 0xFFFFFFFE as i64
321 out[7] = 0x00000000 as i64
322 return NX_H2C_OK
323}
324
325func _h2c_reduce_48be_mod_p(bytes_48: *u8, out_field: *i64) -> i64 {
326 // high = bytes_48[0..16] (16 bytes BE)
327 // low = bytes_48[16..48] (32 bytes BE)
328
329 let high_u256: *i64 = sys_mmap(NX_U256_LIMBS * 8) as *i64
330 let low_u256: *i64 = sys_mmap(NX_U256_LIMBS * 8) as *i64
331 let R: *i64 = sys_mmap(NX_U256_LIMBS * 8) as *i64
332 let p: *i64 = sys_mmap(NX_U256_LIMBS * 8) as *i64
333
334 // Build high as 32-byte BE: 16 zero bytes || 16 bytes of high.
335 let high_be_32: *u8 = sys_mmap(NX_U256_BYTES)
336 var i: i64 = 0
337 while i < 16 { high_be_32[i] = 0 as u8; i = i + 1 }
338 var j: i64 = 0
339 while j < 16 { high_be_32[16 + j] = bytes_48[j]; j = j + 1 }
340 u256_load_be(high_u256, high_be_32)
341
342 // Load low directly (already 32 BE).
343 u256_load_be(low_u256, (bytes_48 as i64 + 16) as *u8)
344
345 // Reduce low mod p (may need 1 subtraction since low can be >= p).
346 p256_field_load_p(p)
347 if u256_cmp(low_u256, p) >= 0 {
348 let tmp: *i64 = sys_mmap(NX_U256_LIMBS * 8) as *i64
349 u256_sub_with_borrow(tmp, low_u256, p)
350 u256_copy(low_u256, tmp)
351 }
352
353 // Compute high * R mod p via p256_field_mul (high is < 2^128, R < p so
354 // both are canonical).
355 _h2c_load_r_constant(R)
356 let prod_hi_r: *i64 = sys_mmap(NX_U256_LIMBS * 8) as *i64
357 p256_field_mul(prod_hi_r, high_u256, R)
358
359 // out = (prod_hi_r + low_u256) mod p
360 p256_field_add(out_field, prod_hi_r, low_u256)
361 return NX_H2C_OK
362}
363
364func nx_h2c_hash_to_field_p256(
365 msg: *u8, msg_len: i64,
366 dst: *u8, dst_len: i64,
367 count: i64,
368 out_elements: *i64 // caller-allocated: count * NX_U256_LIMBS i64 limbs
369) -> i64 {
370 if count < 1 { return 0 - NX_H2C_BAD_INPUT }
371 if count > 16 { return 0 - NX_H2C_BAD_INPUT } // sane cap; OPRF uses count=2
372
373 let len_total: i64 = count * NX_H2C_L
374 let uniform: *u8 = sys_mmap(len_total)
375 let rc_xmd: i64 = nx_h2c_expand_message_xmd_sha256(msg, msg_len,
376 dst, dst_len,
377 len_total, uniform)
378 if rc_xmd != NX_H2C_OK { return rc_xmd }
379
380 var i: i64 = 0
381 while i < count {
382 let slot_offset: i64 = i * NX_H2C_L
383 let out_slot: *i64 = ((out_elements as i64) + i * NX_U256_LIMBS * 8) as *i64
384 let rc: i64 = _h2c_reduce_48be_mod_p((uniform as i64 + slot_offset) as *u8,
385 out_slot)
386 if rc != NX_H2C_OK { return rc }
387 i = i + 1
388 }
389 return NX_H2C_OK
390}
391
392// ===== Simplified SWU constants for P-256 per RFC 9380 §I.1 =================================================
393//
394// All constants in F_p, 8-limb LE u256 layout.
395//
396// A = -3 mod p
397// B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
398// Z = -10 mod p
399// c1 = (q - 3) / 4 (q is the FIELD prime p; for sqrt_3mod4 fast path)
400// c2 = sqrt(-Z) = sqrt(10) mod p (RFC 9380 §I.1 prescribed value)
401//
402// HONEST-STUB DISCIPLINE: c2 is hard-coded from RFC 9380 §I.1; if the
403// constant is wrong, bench/nx_h2c_p256_smoke.sh test-vector verification
404// will fail. Substrate cannot yet compute sqrt in F_p; V+1 adds
405// p256_field_sqrt (~80 lines) so c2 could be derived at boot.
406
407func _h2c_load_A_neg3(out: *i64) -> i64 {
408 // p - 3 in 8-limb LE
409 // p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFF FFFFFFFF
410 // p-3 = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFF FFFFFFFC
411 out[0] = 0xFFFFFFFC as i64
412 out[1] = 0xFFFFFFFF as i64
413 out[2] = 0xFFFFFFFF as i64
414 out[3] = 0x00000000 as i64
415 out[4] = 0x00000000 as i64
416 out[5] = 0x00000000 as i64
417 out[6] = 0x00000001 as i64
418 out[7] = 0xFFFFFFFF as i64
419 return NX_H2C_OK
420}
421
422func _h2c_load_B(out: *i64) -> i64 {
423 // B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
424 // LE limbs (low to high 32 bits each):
425 out[0] = 0x27D2604B as i64
426 out[1] = 0x3BCE3C3E as i64
427 out[2] = 0xCC53B0F6 as i64
428 out[3] = 0x651D06B0 as i64
429 out[4] = 0x769886BC as i64
430 out[5] = 0xB3EBBD55 as i64
431 out[6] = 0xAA3A93E7 as i64
432 out[7] = 0x5AC635D8 as i64
433 return NX_H2C_OK
434}
435
436func _h2c_load_Z_neg10(out: *i64) -> i64 {
437 // p - 10
438 out[0] = 0xFFFFFFF5 as i64
439 out[1] = 0xFFFFFFFF as i64
440 out[2] = 0xFFFFFFFF as i64
441 out[3] = 0x00000000 as i64
442 out[4] = 0x00000000 as i64
443 out[5] = 0x00000000 as i64
444 out[6] = 0x00000001 as i64
445 out[7] = 0xFFFFFFFF as i64
446 return NX_H2C_OK
447}
448
449// ===== Generic mod-p pow (square-and-multiply) =================================================
450//
451// Substrate's p256_field_inv has the ladder inlined with p-2 hardcoded.
452// We need a pow for arbitrary exponent (specifically (p+1)/4 for sqrt
453// when p ≡ 3 mod 4 per RFC 9380 §F.2.1.1). Compose substrate's
454// p256_field_sq + p256_field_mul + bit_at primitives.
455
456func _h2c_pow_p(out: *i64, base: *i64, exp: *i64) -> i64 {
457 let base_copy: *i64 = u256_alloc()
458 u256_copy(base_copy, base)
459 let result: *i64 = u256_alloc()
460 p256_field_one(result)
461 var bit_pos: i64 = 255
462 while bit_pos >= 0 {
463 p256_field_sq(result, result)
464 if p256_field_bit_at(exp, bit_pos) == 1 {
465 p256_field_mul(result, result, base_copy)
466 }
467 bit_pos = bit_pos - 1
468 }
469 u256_copy(out, result)
470 return NX_H2C_OK
471}
472
473// (p+1)/4 for P-256 (precomputed; bit pattern derivation in module
474// header comment). For p ≡ 3 mod 4: sqrt(a) = a^((p+1)/4) mod p.
475//
476// p+1 = 2^256 - 2^224 + 2^192 + 2^96
477// (p+1)/4 = 2^254 - 2^222 + 2^190 + 2^94
478//
479// Bits set in (p+1)/4:
480// bit 94 -> limb[2] bit 30 = 0x40000000
481// bit 190 -> limb[5] bit 30 = 0x40000000
482// bits 222-253 (32 ones) -> limb[6] bits 30-31 = 0xC0000000
483// -> limb[7] bits 0-29 = 0x3FFFFFFF
484
485func _h2c_load_p_plus_1_div_4(out: *i64) -> i64 {
486 out[0] = 0x00000000 as i64
487 out[1] = 0x00000000 as i64
488 out[2] = 0x40000000 as i64
489 out[3] = 0x00000000 as i64
490 out[4] = 0x00000000 as i64
491 out[5] = 0x40000000 as i64
492 out[6] = 0xC0000000 as i64
493 out[7] = 0x3FFFFFFF as i64
494 return NX_H2C_OK
495}
496
497// sqrt mod p for p ≡ 3 mod 4: y = a^((p+1)/4)
498// Pre: a is a quadratic residue (caller checks via y*y == a).
499// Caller verifies; for SSWU's sqrt_ratio, the "isQR" check is the verification.
500
501func _h2c_sqrt_3mod4(out: *i64, a: *i64) -> i64 {
502 let exp: *i64 = u256_alloc()
503 _h2c_load_p_plus_1_div_4(exp)
504 return _h2c_pow_p(out, a, exp)
505}
506
507// ===== sqrt_ratio_3mod4 per RFC 9380 §F.2.1.1 =================================================
508//
509// Inputs: u, v in F_p, v != 0
510// Output: (is_qr, y) where:
511// if u/v is a QR: is_qr=1, y = sqrt(u/v)
512// else: is_qr=0, y = sqrt(Z * u/v) (Z is the SSWU constant)
513//
514// Algorithm (verbatim spec; substrate composes existing p256_field ops):
515// 1. tv1 = v^2
516// 2. tv2 = u * v
517// 3. tv1 = tv1 * tv2 = u * v^3
518// 4. y1 = tv1^c1 where c1 = (q - 3) / 4 -- but we use (p+1)/4 - 1 = (p-3)/4
519// Wait: spec uses c1 = (q-3)/4. q here is the field prime p (not curve order).
520// (p-3)/4 differs from (p+1)/4 by 1. Per RFC 9380 §F.2.1.1:
521// c1 = (q-3)/4
522// y1 = tv1^c1 then y1 = y1 * tv2 ==> equivalent to sqrt(u*v^3) * (u*v) * v^-(some)
523// Per the spec proof: y1 ends as sqrt(u/v) if QR, else sqrt of related.
524// 5. y1 = y1 * tv2
525// 6. y2 = y1 * c2 where c2 = sqrt(-Z) hardcoded per below
526// 7. tv3 = y1^2
527// 8. tv3 = tv3 * v
528// 9. isQR = tv3 == u
529// 10. y = CMOV(y2, y1, isQR)
530// 11. return (isQR, y)
531
532// c1 = (p-3)/4. Differs from (p+1)/4 by -1.
533// (p+1)/4 - 1 = (p-3)/4
534
535func _h2c_load_p_minus_3_div_4(out: *i64) -> i64 {
536 // (p-3)/4 = (p+1)/4 - 1
537 // Subtract 1 from the (p+1)/4 LE representation:
538 // limb[0] was 0 -> becomes -1 = 0xFFFFFFFF (borrow propagates)
539 // limb[1] was 0 -> borrow consumed -> 0xFFFFFFFF
540 // limb[2] was 0x40000000 -> borrow -> 0x3FFFFFFF
541 // limb[3..7] unchanged
542 out[0] = 0xFFFFFFFF as i64
543 out[1] = 0xFFFFFFFF as i64
544 out[2] = 0x3FFFFFFF as i64
545 out[3] = 0x00000000 as i64
546 out[4] = 0x00000000 as i64
547 out[5] = 0x40000000 as i64
548 out[6] = 0xC0000000 as i64
549 out[7] = 0x3FFFFFFF as i64
550 return NX_H2C_OK
551}
552
553// c2 = sqrt(-Z) mod p, where Z = -10. -Z = 10.
554// Computed at use-time via _h2c_sqrt_3mod4(10) so we have no hardcoded
555// magic constant; the value is verified by virtue of being computed
556// from spec-cited inputs via spec-cited algorithm.
557func _h2c_load_c2(out: *i64) -> i64 {
558 let ten: *i64 = u256_alloc()
559 u256_zero(ten)
560 ten[0] = 10 as i64
561 return _h2c_sqrt_3mod4(out, ten)
562}
563
564func _h2c_sqrt_ratio_3mod4(out_y: *i64, u: *i64, v: *i64) -> i64 {
565 let tv1: *i64 = u256_alloc()
566 let tv2: *i64 = u256_alloc()
567 let tv3: *i64 = u256_alloc()
568 let y1: *i64 = u256_alloc()
569 let y2: *i64 = u256_alloc()
570 let c1: *i64 = u256_alloc()
571 let c2: *i64 = u256_alloc()
572
573 p256_field_sq(tv1, v) // tv1 = v^2
574 p256_field_mul(tv2, u, v) // tv2 = u * v
575 p256_field_mul(tv1, tv1, tv2) // tv1 = u * v^3
576 _h2c_load_p_minus_3_div_4(c1)
577 _h2c_pow_p(y1, tv1, c1) // y1 = tv1^c1
578 p256_field_mul(y1, y1, tv2) // y1 = y1 * tv2
579 _h2c_load_c2(c2)
580 p256_field_mul(y2, y1, c2) // y2 = y1 * c2
581 p256_field_sq(tv3, y1) // tv3 = y1^2
582 p256_field_mul(tv3, tv3, v) // tv3 = tv3 * v
583
584 // isQR = (tv3 == u)
585 var is_qr: i64 = 0
586 if p256_field_eq(tv3, u) == 1 { is_qr = 1 }
587
588 // y = CMOV(y2, y1, isQR)
589 if is_qr == 1 { u256_copy(out_y, y1) }
590 if is_qr == 0 { u256_copy(out_y, y2) }
591 return is_qr
592}
593
594// ===== sgn0 per RFC 9380 §4.1 (m=1, simple case) =================================================
595//
596// For F_p with m=1, sgn0(x) = LSB(x). Returns 0 or 1.
597
598func _h2c_sgn0(x: *i64) -> i64 {
599 return x[0] & 1
600}
601
602// ===== map_to_curve_simple_swu per RFC 9380 §F.2.1.2 =================================================
603//
604// Input: u in F_p
605// Output: (x, y) on E: y^2 = x^3 + A*x + B
606//
607// Algorithm (verbatim from RFC 9380 §F.2.1.2):
608// 1. tv1 = u^2
609// 2. tv1 = Z * tv1
610// 3. tv2 = tv1^2
611// 4. tv2 = tv2 + tv1
612// 5. tv3 = tv2 + 1
613// 6. tv3 = B * tv3
614// 7. tv4 = CMOV(Z, -tv2, tv2 != 0)
615// 8. tv4 = A * tv4
616// 9. tv2 = tv3^2
617// 10. tv6 = tv4^2
618// 11. tv5 = A * tv6
619// 12. tv2 = tv2 + tv5
620// 13. tv2 = tv2 * tv3
621// 14. tv6 = tv6 * tv4
622// 15. tv5 = B * tv6
623// 16. tv2 = tv2 + tv5
624// 17. x = tv1 * tv3
625// 18. (is_gx1_square, y1) = sqrt_ratio_3mod4(tv2, tv6)
626// 19. y = tv1 * u
627// 20. y = y * y1
628// 21. x = CMOV(x, tv3, is_gx1_square)
629// 22. y = CMOV(y, y1, is_gx1_square)
630// 23. e1 = sgn0(u) == sgn0(y)
631// 24. y = CMOV(-y, y, e1)
632// 25. x = x / tv4
633// 26. return (x, y)
634
635func _h2c_map_to_curve_sswu_p256(u: *i64, out_x: *i64, out_y: *i64) -> i64 {
636 let A: *i64 = u256_alloc()
637 let B: *i64 = u256_alloc()
638 let Z: *i64 = u256_alloc()
639 let one: *i64 = u256_alloc()
640 let tv1: *i64 = u256_alloc()
641 let tv2: *i64 = u256_alloc()
642 let tv3: *i64 = u256_alloc()
643 let tv4: *i64 = u256_alloc()
644 let tv5: *i64 = u256_alloc()
645 let tv6: *i64 = u256_alloc()
646 let neg_tv2: *i64 = u256_alloc()
647 let y1: *i64 = u256_alloc()
648 let inv_tv4: *i64 = u256_alloc()
649
650 _h2c_load_A_neg3(A)
651 _h2c_load_B(B)
652 _h2c_load_Z_neg10(Z)
653 p256_field_one(one)
654
655 p256_field_sq(tv1, u) // 1. tv1 = u^2
656 p256_field_mul(tv1, Z, tv1) // 2. tv1 = Z * tv1
657 p256_field_sq(tv2, tv1) // 3. tv2 = tv1^2
658 p256_field_add(tv2, tv2, tv1) // 4. tv2 = tv2 + tv1
659 p256_field_add(tv3, tv2, one) // 5. tv3 = tv2 + 1
660 p256_field_mul(tv3, B, tv3) // 6. tv3 = B * tv3
661 // 7. tv4 = CMOV(Z, -tv2, tv2 != 0)
662 if u256_is_zero(tv2) == 1 {
663 u256_copy(tv4, Z)
664 }
665 if u256_is_zero(tv2) == 0 {
666 p256_field_neg(neg_tv2, tv2)
667 u256_copy(tv4, neg_tv2)
668 }
669 p256_field_mul(tv4, A, tv4) // 8. tv4 = A * tv4
670 p256_field_sq(tv2, tv3) // 9. tv2 = tv3^2
671 p256_field_sq(tv6, tv4) // 10. tv6 = tv4^2
672 p256_field_mul(tv5, A, tv6) // 11. tv5 = A * tv6
673 p256_field_add(tv2, tv2, tv5) // 12. tv2 = tv2 + tv5
674 p256_field_mul(tv2, tv2, tv3) // 13. tv2 = tv2 * tv3
675 p256_field_mul(tv6, tv6, tv4) // 14. tv6 = tv6 * tv4
676 p256_field_mul(tv5, B, tv6) // 15. tv5 = B * tv6
677 p256_field_add(tv2, tv2, tv5) // 16. tv2 = tv2 + tv5
678 p256_field_mul(out_x, tv1, tv3) // 17. x = tv1 * tv3
679 let is_gx1_square: i64 = _h2c_sqrt_ratio_3mod4(y1, tv2, tv6) // 18
680 p256_field_mul(out_y, tv1, u) // 19. y = tv1 * u
681 p256_field_mul(out_y, out_y, y1) // 20. y = y * y1
682 // 21. x = CMOV(x, tv3, is_gx1_square)
683 if is_gx1_square == 1 { u256_copy(out_x, tv3) }
684 // 22. y = CMOV(y, y1, is_gx1_square)
685 if is_gx1_square == 1 { u256_copy(out_y, y1) }
686 // 23-24. e1 = sgn0(u) == sgn0(y); y = CMOV(-y, y, e1)
687 var e1: i64 = 0
688 if _h2c_sgn0(u) == _h2c_sgn0(out_y) { e1 = 1 }
689 if e1 == 0 {
690 let neg_y: *i64 = u256_alloc()
691 p256_field_neg(neg_y, out_y)
692 u256_copy(out_y, neg_y)
693 }
694 // 25. x = x / tv4
695 p256_field_inv(inv_tv4, tv4)
696 p256_field_mul(out_x, out_x, inv_tv4)
697 return NX_H2C_OK
698}
699
700// ===== Public top-level entry: nx_h2c_hash_to_curve_p256 =================================================
701//
702// Per RFC 9380 §3 (RO mode):
703// u = hash_to_field(msg, 2)
704// Q0 = map_to_curve(u[0])
705// Q1 = map_to_curve(u[1])
706// R = Q0 + Q1
707// P = clear_cofactor(R) // P-256 cofactor = 1; P = R
708// return P
709
710func nx_h2c_hash_to_curve_p256(
711 msg: *u8, msg_len: i64,
712 dst: *u8, dst_len: i64,
713 out_point: *P256Point
714) -> i64 {
715 // 1. u[0..2] = hash_to_field(msg, 2)
716 let u_buf: *i64 = (sys_mmap(2 * NX_U256_LIMBS * 8)) as *i64
717 let rc_h2f: i64 = nx_h2c_hash_to_field_p256(msg, msg_len, dst, dst_len, 2, u_buf)
718 if rc_h2f != NX_H2C_OK { return rc_h2f }
719
720 let u0: *i64 = ((u_buf as i64) + 0 * NX_U256_LIMBS * 8) as *i64
721 let u1: *i64 = ((u_buf as i64) + 1 * NX_U256_LIMBS * 8) as *i64
722
723 // 2. Q0 = SSWU(u[0]); Q1 = SSWU(u[1])
724 let q0_x: *i64 = u256_alloc()
725 let q0_y: *i64 = u256_alloc()
726 let q1_x: *i64 = u256_alloc()
727 let q1_y: *i64 = u256_alloc()
728 _h2c_map_to_curve_sswu_p256(u0, q0_x, q0_y)
729 _h2c_map_to_curve_sswu_p256(u1, q1_x, q1_y)
730
731 // Wrap in projective (z=1) P256Point for substrate's point_add API.
732 let q0: *P256Point = p256_point_alloc()
733 let q1: *P256Point = p256_point_alloc()
734 p256_point_set_affine(q0, q0_x, q0_y)
735 p256_point_set_affine(q1, q1_x, q1_y)
736
737 // 3. R = Q0 + Q1 (P-256 cofactor=1, so no clear_cofactor needed).
738 p256_point_add(out_point, q0, q1)
739
740 // Normalize result to affine for caller's convenience.
741 p256_point_to_affine(out_point)
742 return NX_H2C_OK
743}