nx_kyber_poly_basemul_acc_wasm.nx source
↩ module page · 117 lines · 5330 B
1// nx_kyber_poly_basemul_acc_wasm.nx -- full-polynomial basemul accumulate.
2//
3// Where K-PKE inner-product loops live. Each call accumulates ONE
4// basemul-product polynomial into the accumulator -- caller invokes this
5// k times to compute a vector inner product (matrix row times vector).
6//
7// FIPS 203 ML-KEM-768 cost:
8// keygen: 9 basemul_acc + 3 poly_zero (= 1 matrix * 1 vec)
9// encrypt: 18 basemul_acc + 6 poly_zero (= 2 matrix-vec + 1 vec dot)
10// decrypt: 3 basemul_acc + 1 poly_zero (= 1 vector dot)
11//
12// Inlined: zetas[64..127] (64 entries from FIPS 203 / PQClean) +
13// montgomery_reduce + fqmul. The L117 nx_kyber_ntt also has these but
14// each WAT module must be self-contained per the build pipeline.
15//
16// API:
17// nx_kyber_poly_zero(p) -> i64 set all 256 coefs = 0
18// nx_kyber_poly_basemul_acc(acc, a, b) -> i64 acc += basemul(a, b)
19//
20// Result is in Montgomery form (basemul uses fqmul, which has the
21// Mont factor). Caller composes with INVNTT (= invntt_tomont) which
22// expects Montgomery-form input and produces canonical * R output.
23//
24// Per PQClean poly_basemul_montgomery (FIPS 203 ยง4.3.3 equivalent):
25// for i in 0..64:
26// basemul(r[4i..4i+2], a[4i..4i+2], b[4i..4i+2], zetas[64+i])
27// basemul(r[4i+2..4i+4], a[4i+2..4i+4], b[4i+2..4i+4], -zetas[64+i])
28//
29// Verified: KAT cross-checked against pure-JS reference implementation.
30//
31// license_tier: INDEPENDENT_REDERIVE
32// genealogy_id: international-research-sources/nist/fips_203
33// lineage_id: nishi_kyber_poly_basemul_acc_wasm_q1
34// safe_shift_audit: no 64-bit rotations in this module
35
36const KYBER_Q: i64 = 3329
37const KYBER_QINV: i64 = 62209
38const KYBER_N: i64 = 256
39
40func _pload(p: *u8, i: i64) -> i64 {
41 let lo: i64 = p[i * 2]
42 let hi: i64 = p[i * 2 + 1]
43 let raw: i64 = lo | (hi << 8)
44 if raw >= 32768 { return raw - 65536 }
45 return raw
46}
47
48func _pstore(p: *u8, i: i64, v: i64) -> i64 {
49 var vv: i64 = v
50 if vv < 0 { vv = vv + 65536 }
51 p[i * 2] = vv & 0xff
52 p[i * 2 + 1] = (vv >> 8) & 0xff
53 return 0
54}
55
56func _mont(a: i64) -> i64 {
57 var u: i64 = (a * KYBER_QINV) & 0xffff
58 if u >= 32768 { u = u - 65536 }
59 return (a - u * KYBER_Q) >> 16
60}
61
62func _fqmul(a: i64, b: i64) -> i64 { return _mont(a * b) }
63
64// Zetas[64..127] -- the basemul-only second half of the full Kyber zeta table.
65// Indexed _zbm(i) for i in 0..63 -> _zetas(64+i) per the PQClean ordering.
66func _zbm(i: i64) -> i64 {
67 if i == 0 { return -1103 } if i == 1 { return 430 } if i == 2 { return 555 } if i == 3 { return 843 }
68 if i == 4 { return -1251 } if i == 5 { return 871 } if i == 6 { return 1550 } if i == 7 { return 105 }
69 if i == 8 { return 422 } if i == 9 { return 587 } if i == 10 { return 177 } if i == 11 { return -235 }
70 if i == 12 { return -291 } if i == 13 { return -460 } if i == 14 { return 1574 } if i == 15 { return 1653 }
71 if i == 16 { return -246 } if i == 17 { return 778 } if i == 18 { return 1159 } if i == 19 { return -147 }
72 if i == 20 { return -777 } if i == 21 { return 1483 } if i == 22 { return -602 } if i == 23 { return 1119 }
73 if i == 24 { return -1590 } if i == 25 { return 644 } if i == 26 { return -872 } if i == 27 { return 349 }
74 if i == 28 { return 418 } if i == 29 { return 329 } if i == 30 { return -156 } if i == 31 { return -75 }
75 if i == 32 { return 817 } if i == 33 { return 1097 } if i == 34 { return 603 } if i == 35 { return 610 }
76 if i == 36 { return 1322 } if i == 37 { return -1285 } if i == 38 { return -1465 } if i == 39 { return 384 }
77 if i == 40 { return -1215 } if i == 41 { return -136 } if i == 42 { return 1218 } if i == 43 { return -1335 }
78 if i == 44 { return -874 } if i == 45 { return 220 } if i == 46 { return -1187 } if i == 47 { return -1659 }
79 if i == 48 { return -1185 } if i == 49 { return -1530 } if i == 50 { return -1278 } if i == 51 { return 794 }
80 if i == 52 { return -1510 } if i == 53 { return -854 } if i == 54 { return -870 } if i == 55 { return 478 }
81 if i == 56 { return -108 } if i == 57 { return -308 } if i == 58 { return 996 } if i == 59 { return 991 }
82 if i == 60 { return 958 } if i == 61 { return -1460 } if i == 62 { return 1522 }
83 return 1628
84}
85
86func nx_kyber_poly_zero(p: *u8) -> i64 {
87 var i: i64 = 0
88 while i < KYBER_N { _pstore(p, i, 0); i = i + 1 }
89 return 0
90}
91
92// One pair basemul into ACCUMULATOR.
93// r[0] += a[1]*b[1]*zeta + a[0]*b[0]
94// r[1] += a[0]*b[1] + a[1]*b[0]
95func _basemul_pair_acc(acc: *u8, off: i64,
96 a: *u8, b: *u8, zeta: i64) -> i64 {
97 let a0: i64 = _pload(a, off)
98 let a1: i64 = _pload(a, off + 1)
99 let b0: i64 = _pload(b, off)
100 let b1: i64 = _pload(b, off + 1)
101 let r0: i64 = _fqmul(_fqmul(a1, b1), zeta) + _fqmul(a0, b0)
102 let r1: i64 = _fqmul(a0, b1) + _fqmul(a1, b0)
103 _pstore(acc, off, _pload(acc, off) + r0)
104 _pstore(acc, off + 1, _pload(acc, off + 1) + r1)
105 return 0
106}
107
108func nx_kyber_poly_basemul_acc(acc: *u8, a: *u8, b: *u8) -> i64 {
109 var i: i64 = 0
110 while i < 64 {
111 let z: i64 = _zbm(i)
112 _basemul_pair_acc(acc, i * 4, a, b, z)
113 _basemul_pair_acc(acc, i * 4 + 2, a, b, -z)
114 i = i + 1
115 }
116 return 0
117}