nx_kyber_msg_codec_wasm.nx source
↩ module page · 103 lines · 3528 B
1// nx_kyber_msg_codec_wasm.nx -- 1-bit message <-> polynomial codec.
2//
3// FIPS 203 §4.2.4 Compress_1 / Decompress_1 specialized for the K-PKE
4// message-embedding step. Each bit of the 32-byte message becomes one
5// coefficient of a 256-coef polynomial (32 * 8 = 256 bits).
6//
7// Encoding direction (msg -> poly, used in K-PKE encrypt step 10):
8// For each bit b in msg: coefficient = b * Decompress_1(1)
9// = b * round(q/2)
10// = b * 1665 (since (3329 + 1) / 2 = 1665)
11//
12// Decoding direction (poly -> msg, used in K-PKE decrypt step 9):
13// For each coefficient c (canonical [0, q)): bit = Compress_1(c)
14// = round((2 * c) / q) mod 2
15// = ((c << 1) + q/2) / q mod 2
16// = ((2*c + 1665) / 3329) & 1
17//
18// The decoding boundary is c = q/2 = 1665 (and -1665 = 1664 in [0,q)).
19// Coefficients close to 0 decode to bit 0; coefficients close to q/2
20// decode to bit 1. This is the error-correcting margin that makes
21// K-PKE robust to the small noise added during encrypt.
22//
23// API:
24// nx_kyber_msg_to_poly(poly_out, msg_32) -> i64
25// nx_kyber_msg_from_poly(msg_out, poly) -> i64
26//
27// Verified: KAT round-trip on random 32-byte messages + boundary cases.
28//
29// license_tier: INDEPENDENT_REDERIVE
30// genealogy_id: international-research-sources/nist/fips_203
31// lineage_id: nishi_kyber_msg_codec_wasm_q1
32// safe_shift_audit: no 64-bit rotations in this module
33
34const KYBER_Q: i64 = 3329
35const KYBER_N: i64 = 256
36const KYBER_HALF: i64 = 1665 // (q+1)/2 = Decompress_1(1)
37
38func _pstore(p: *u8, i: i64, v: i64) -> i64 {
39 var vv: i64 = v
40 if vv < 0 { vv = vv + 65536 }
41 p[i * 2] = vv & 0xff
42 p[i * 2 + 1] = (vv >> 8) & 0xff
43 return 0
44}
45
46func _pload(p: *u8, i: i64) -> i64 {
47 let lo: i64 = p[i * 2]
48 let hi: i64 = p[i * 2 + 1]
49 let raw: i64 = lo | (hi << 8)
50 if raw >= 32768 { return raw - 65536 }
51 return raw
52}
53
54// msg_32: 32 bytes; bit b of byte k -> coefficient at index (8k + b).
55// Each bit -> 0 or KYBER_HALF.
56func nx_kyber_msg_to_poly(poly_out: *u8, msg_in: *u8) -> i64 {
57 var i: i64 = 0
58 while i < 32 {
59 let byte: i64 = msg_in[i]
60 var b: i64 = 0
61 while b < 8 {
62 let bit: i64 = (byte >> b) & 1
63 _pstore(poly_out, i * 8 + b, bit * KYBER_HALF)
64 b = b + 1
65 }
66 i = i + 1
67 }
68 return 0
69}
70
71// Reduce a signed coefficient to canonical [0, q).
72func _canon(v: i64) -> i64 {
73 var x: i64 = v % KYBER_Q
74 if x < 0 { x = x + KYBER_Q }
75 return x
76}
77
78// Compress_1(c) per FIPS 203 §4.2.1:
79// round((2 * c) / q) mod 2
80// Implemented as floor((c * 2 + (q+1)/2) / q) mod 2 using ceiling-half.
81// Equivalently: subtract q/2; if result is in (-q/2, q/2] it's bit 0,
82// else bit 1. We use the direct formula.
83func _compress_1(c: i64) -> i64 {
84 // (((c << 1) + 1665) / q) & 1, where 1665 = (q+1)/2 = q/2 rounded up
85 return (((c << 1) + KYBER_HALF) / KYBER_Q) & 1
86}
87
88func nx_kyber_msg_from_poly(msg_out: *u8, poly_in: *u8) -> i64 {
89 var i: i64 = 0
90 while i < 32 {
91 var byte: i64 = 0
92 var b: i64 = 0
93 while b < 8 {
94 let c: i64 = _canon(_pload(poly_in, i * 8 + b))
95 let bit: i64 = _compress_1(c)
96 byte = byte | (bit << b)
97 b = b + 1
98 }
99 msg_out[i] = byte & 0xff
100 i = i + 1
101 }
102 return 0
103}