nx_ghash_clmul.nx source
↩ module page · 186 lines · 7793 B
1// nx_ghash_clmul.nx -- hardware PCLMULQDQ backend for GF(2^128) multiply (GHASH core).
2// Byte-IDENTICAL drop-in for nx_ghash.nx's nx_ghash_mul, ~hardware speed vs the ~1 MB/s
3// bit-by-bit reference. Gated against that reference as the oracle (KAT-equality).
4//
5// Bridge from GCM's bit convention to PCLMULQDQ:
6// GCM (SP 800-38D) stores coeff(x^i) MSB-FIRST: byte (i>>3), bit position (7-(i&7)).
7// PCLMULQDQ multiplies polynomials where integer-bit k = coeff(x^k) (LSB-first).
8// A BYTEWISE bit-reversal (reverse the 8 bits WITHIN each byte; byte order unchanged)
9// maps GCM coeff(x^k) onto little-endian integer-bit k -- exactly pclmulqdq's input.
10// So: bitrev each input -> 4 clmuls (schoolbook 128x128 -> 256) -> reduce mod
11// P(x)=x^128+x^7+x^2+x+1 -> bitrev the 128-bit result back to GCM byte order.
12//
13// The reduction uses x^128 = x^7+x^2+x+1 (mod P): fold the high 128 bits H by H*(x^7+x^2+x+1)
14// (two folds -- the first leaves <=7 overflow bits past bit 127, the second clears them).
15// NishiLang `>>` is ARITHMETIC, so gh_lshr() masks to emulate a logical shift.
16//
17// license_tier: ORIGINAL (composes nx_ghash.nx conventions; new CLMUL lowering)
18// genealogy_id: international-research-sources/intel/clmul-gcm
19// lineage_id: nishi_ghash_clmul_q1
20
21import "nx_syscalls.nx"
22
23// one-time scratch arena (single-threaded GHASH):
24// xr[0:16] hr[16:32] tprod[32:48] rbuf[48:64] acc256[64:96]
25static GH_CLMUL_SCRATCH: i64
26
27func gh_scratch() -> *u8 {
28 if GH_CLMUL_SCRATCH == 0 { GH_CLMUL_SCRATCH = sys_mmap(96) as i64 }
29 return GH_CLMUL_SCRATCH as *u8
30}
31
32// reverse the 8 bits within one byte (0..255) -- used once to build the lookup table
33func gh_revbyte(b: i64) -> i64 {
34 var r: i64 = 0
35 var i: i64 = 0
36 while i < 8 {
37 r = r | (((b >> i) & 1) << (7 - i))
38 i = i + 1
39 }
40 return r
41}
42
43// 256-entry bit-reverse table, built once. Turns the per-block bytewise reversal from
44// 8 ops/byte (the dominant GHASH cost after CLMUL) into a single table load.
45static GH_REVTAB: i64
46func gh_revtab() -> *u8 {
47 if GH_REVTAB == 0 {
48 let t: *u8 = sys_mmap(256)
49 var i: i64 = 0
50 while i < 256 { t[i] = gh_revbyte(i) as u8; i = i + 1 }
51 GH_REVTAB = t as i64
52 }
53 return GH_REVTAB as *u8
54}
55
56// bytewise bit-reversal of a 16-byte block (byte order preserved) via table lookup
57func gh_byterev_bits(src: *u8, dst: *u8) -> i64 {
58 let t: *u8 = gh_revtab()
59 var i: i64 = 0
60 while i < 16 { dst[i] = t[src[i] & 0xff]; i = i + 1 }
61 return 0
62}
63
64// LOGICAL right shift (NishiLang `>>` is arithmetic): keep only the (64-n) low result bits.
65// Valid for 1 <= n <= 63. Used with n in {57,62,63} -> masks {0x7f,0x3,0x1}.
66func gh_lshr(x: i64, n: i64) -> i64 {
67 return (x >> n) & ((1 << (64 - n)) - 1)
68}
69
70// ---- REFLECTED-DOMAIN CORE (the hot path for fast AES-GCM) ----------------------------
71//
72// bit-reflection (gh_byterev_bits) is a field ISOMORPHISM phi between the GCM
73// (SP 800-38D, MSB-first) representation and the PCLMULQDQ integer representation:
74// phi(a XOR b) = phi(a) XOR phi(b), phi(a * b) = phi(a) (x) phi(b), phi(phi(a)) = a
75// where (x) is GF(2^128) multiply reduced by P(x)=x^128+x^7+x^2+x+1 in the pclmul domain.
76//
77// gh_clmul_core computes out = a (x) b directly in the REFLECTED domain (a, b, out already
78// reflected -- NO per-call byte reversals). Callers that keep the running GHASH state
79// reflected reverse ONLY the normal-domain input blocks (once each) + the final result
80// (once), instead of 3 reversals per multiply.
81//
82// Split into a bilinear 256-bit accumulate (gh_clmul_mul256_acc) + a linear 256->128
83// reduce (gh_clmul_reduce256) so N products can be XOR-accumulated and reduced ONCE
84// (4-way GHASH aggregation -- one reduction per 4 blocks). gh_clmul_core = the N=1 case,
85// and it is what nx_ghash_mul_clmul delegates to, so the 2004-vector nx_ghash_clmul_gate
86// re-proves BOTH primitives == the bit-by-bit reference on every build.
87
88// XOR-accumulate the 256-bit carry-less product of reflected a16,b16 into acc[0..3]
89// (little-endian bit 0..255). Bilinear over GF(2): sum-of-products before reduction.
90// tp scratch = gh_scratch() base+32..48 (disjoint from acc / a / b).
91func gh_clmul_mul256_acc(a16: *u8, b16: *u8, acc: *i64) -> i64 {
92 let base: *u8 = gh_scratch()
93 let tp: *u8 = ((base as i64) + 32) as *u8
94 let ai: *i64 = a16 as *i64
95 let tpi: *i64 = tp as *i64
96
97 // four 64x64 carry-less half-products (schoolbook 128x128 -> 256).
98 tpi[0] = ai[0]; tpi[1] = ai[1]
99 let r0: i64 = __clmul_ll(tp, b16) // t0 = a.lo * b.lo
100 let t0_lo: i64 = tpi[0]; let t0_hi: i64 = tpi[1]
101 tpi[0] = ai[0]; tpi[1] = ai[1]
102 let r3: i64 = __clmul_hh(tp, b16) // t3 = a.hi * b.hi
103 let t3_lo: i64 = tpi[0]; let t3_hi: i64 = tpi[1]
104 tpi[0] = ai[0]; tpi[1] = ai[1]
105 let r1: i64 = __clmul_lh(tp, b16) // t1 = a.lo * b.hi
106 let t1_lo: i64 = tpi[0]; let t1_hi: i64 = tpi[1]
107 tpi[0] = ai[0]; tpi[1] = ai[1]
108 let r2: i64 = __clmul_hl(tp, b16) // t2 = a.hi * b.lo
109 let t2_lo: i64 = tpi[0]; let t2_hi: i64 = tpi[1]
110
111 let mid_lo: i64 = t1_lo ^ t2_lo
112 let mid_hi: i64 = t1_hi ^ t2_hi
113
114 // assemble the 256-bit product into 4 words (bit 0..255) and XOR into the accumulator
115 acc[0] = acc[0] ^ t0_lo
116 acc[1] = acc[1] ^ (t0_hi ^ mid_lo)
117 acc[2] = acc[2] ^ (t3_lo ^ mid_hi)
118 acc[3] = acc[3] ^ t3_hi
119 return 0
120}
121
122// reduce a 256-bit accumulator acc[0..3] mod P(x)=x^128+x^7+x^2+x+1 into the reflected
123// 128-bit result out16. Linear over GF(2).
124func gh_clmul_reduce256(acc: *i64, out16: *u8) -> i64 {
125 let z0: i64 = acc[0]
126 let z1: i64 = acc[1]
127 let Hlo: i64 = acc[2] // high 128 bits = (z2,z3)
128 let Hhi: i64 = acc[3]
129 var D_lo: i64 = Hlo // k=0 term (H*1)
130 var D_hi: i64 = Hhi
131 var D_ovf: i64 = 0
132 // k=1
133 D_lo = D_lo ^ (Hlo << 1)
134 D_hi = D_hi ^ (Hhi << 1) ^ gh_lshr(Hlo, 63)
135 D_ovf = D_ovf ^ gh_lshr(Hhi, 63)
136 // k=2
137 D_lo = D_lo ^ (Hlo << 2)
138 D_hi = D_hi ^ (Hhi << 2) ^ gh_lshr(Hlo, 62)
139 D_ovf = D_ovf ^ gh_lshr(Hhi, 62)
140 // k=7
141 D_lo = D_lo ^ (Hlo << 7)
142 D_hi = D_hi ^ (Hhi << 7) ^ gh_lshr(Hlo, 57)
143 D_ovf = D_ovf ^ gh_lshr(Hhi, 57)
144
145 // second fold: the <=7 overflow bits past bit 127 (D_ovf*x^128) == D_ovf*(x^7+x^2+x+1),
146 // degree <= 13 -> fits the low word, no further overflow.
147 let E: i64 = D_ovf ^ (D_ovf << 1) ^ (D_ovf << 2) ^ (D_ovf << 7)
148
149 let R_lo: i64 = z0 ^ D_lo ^ E
150 let R_hi: i64 = z1 ^ D_hi
151
152 let oi: *i64 = out16 as *i64
153 oi[0] = R_lo
154 oi[1] = R_hi
155 return 0
156}
157
158// N=1 reflected-domain multiply: out = a (x) b. acc256 = gh_scratch() base+64..96.
159func gh_clmul_core(a16: *u8, b16: *u8, out16: *u8) -> i64 {
160 let base: *u8 = gh_scratch()
161 let acc: *i64 = ((base as i64) + 64) as *i64
162 acc[0] = 0; acc[1] = 0; acc[2] = 0; acc[3] = 0
163 gh_clmul_mul256_acc(a16, b16, acc)
164 gh_clmul_reduce256(acc, out16)
165 return 0
166}
167
168// z = x * h over GF(2^128) (MSB-first per SP 800-38D) -- byte-identical to nx_ghash_mul.
169// Delegates the field arithmetic to gh_clmul_core; adds the two input reflections + the
170// output reflection so the GCM-domain API surface is unchanged (still gated as the oracle).
171func nx_ghash_mul_clmul(x16: *u8, h16: *u8, z16: *u8) -> i64 {
172 let base: *u8 = gh_scratch()
173 let xr: *u8 = base
174 let hr: *u8 = ((base as i64) + 16) as *u8
175 let rb: *u8 = ((base as i64) + 48) as *u8
176
177 gh_byterev_bits(x16, xr)
178 gh_byterev_bits(h16, hr)
179 gh_clmul_core(xr, hr, rb) // reflected-domain a (x) b
180 gh_byterev_bits(rb, z16) // back to GCM MSB-first byte order
181 return 0
182}
183
184func main() -> i64 {
185 return 0
186}