binius_field/fields/
ghash.rs

1// Copyright 2023-2025 Irreducible Inc.
2// Copyright 2026 The Binius Developers
3
4//! Binary field implementation of GF(2^128) with a modulus of X^128 + X^7 + X^2 + X + 1.
5//! This is the GHASH field used in AES-GCM.
6
7use std::{
8	fmt::{Debug, Display, Formatter},
9	iter::{Product, Sum},
10	ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
11};
12
13use bytemuck::{Pod, Zeroable};
14
15use crate::{
16	Field, PackedGhash1x128b, Rijndael8b,
17	arch::M128,
18	arithmetic_traits::MulX,
19	binary_field::{BinaryField, BinaryField1b, binary_field, impl_field_extension},
20	field::ExtensionField,
21	underlier::{U1, UnderlierView},
22};
23
24// `1 << 121` is the lowest single-bit element of trace 1; `1 << 127` is the only other one.
25binary_field!(
26	pub Ghash128b(M128),
27	M128::from_u128(0x494ef99794d5244f9152df59d87a9186),
28	M128::from_u128(1 << 121)
29);
30
31// Convenience `u128` conversions. `binary_field!` already provides `From<M128>`/`From<.. for
32// M128>`; these let callers keep constructing/inspecting `Ghash128b` via `u128`. `M128`
33// is a distinct type from `u128` on every target, so these never collide with the macro's impls.
34impl From<u128> for Ghash128b {
35	fn from(value: u128) -> Self {
36		Self(M128::from(value))
37	}
38}
39
40impl From<Ghash128b> for u128 {
41	fn from(value: Ghash128b) -> Self {
42		value.0.into()
43	}
44}
45
46unsafe impl Pod for Ghash128b {}
47
48impl Ghash128b {
49	/// Constructs an element from its `u128` value. The underlier is `M128`, but `u128` is the
50	/// ergonomic constructor type, so this converts.
51	pub const fn new(value: u128) -> Self {
52		Self(M128::from_u128(value))
53	}
54}
55
56impl MulX for Ghash128b {
57	#[inline]
58	fn mul_x(self) -> Self {
59		// The width-one packing is this field with one element, so it holds the same scaling.
60		Self::from_underlier(
61			PackedGhash1x128b::from_underlier(self.to_underlier())
62				.mul_x()
63				.to_underlier(),
64		)
65	}
66}
67
68impl_field_extension!(BinaryField1b(U1) < @7 => Ghash128b(M128));
69
70impl From<Rijndael8b> for Ghash128b {
71	#[inline]
72	fn from(value: Rijndael8b) -> Self {
73		// Raw GHASH values as `u128`, converted to the `M128` underlier at the lookup site so the
74		// table needs no const `M128` construction.
75		const LOOKUP_TABLE: [u128; 256] = [
76			0x00000000000000000000000000000000,
77			0x00000000000000000000000000000001,
78			0x0dcb364640a222fe6b8330483c2e9849,
79			0x0dcb364640a222fe6b8330483c2e9848,
80			0x3d5bd35c94646a247573da4a5f7710ed,
81			0x3d5bd35c94646a247573da4a5f7710ec,
82			0x3090e51ad4c648da1ef0ea02635988a4,
83			0x3090e51ad4c648da1ef0ea02635988a5,
84			0x6d58c4e181f9199f41a12db1f974f3ac,
85			0x6d58c4e181f9199f41a12db1f974f3ad,
86			0x6093f2a7c15b3b612a221df9c55a6be5,
87			0x6093f2a7c15b3b612a221df9c55a6be4,
88			0x500317bd159d73bb34d2f7fba603e341,
89			0x500317bd159d73bb34d2f7fba603e340,
90			0x5dc821fb553f51455f51c7b39a2d7b08,
91			0x5dc821fb553f51455f51c7b39a2d7b09,
92			0xa72ec17764d7ced55e2f716f4ede412f,
93			0xa72ec17764d7ced55e2f716f4ede412e,
94			0xaae5f7312475ec2b35ac412772f0d966,
95			0xaae5f7312475ec2b35ac412772f0d967,
96			0x9a75122bf0b3a4f12b5cab2511a951c2,
97			0x9a75122bf0b3a4f12b5cab2511a951c3,
98			0x97be246db011860f40df9b6d2d87c98b,
99			0x97be246db011860f40df9b6d2d87c98a,
100			0xca760596e52ed74a1f8e5cdeb7aab283,
101			0xca760596e52ed74a1f8e5cdeb7aab282,
102			0xc7bd33d0a58cf5b4740d6c968b842aca,
103			0xc7bd33d0a58cf5b4740d6c968b842acb,
104			0xf72dd6ca714abd6e6afd8694e8dda26e,
105			0xf72dd6ca714abd6e6afd8694e8dda26f,
106			0xfae6e08c31e89f90017eb6dcd4f33a27,
107			0xfae6e08c31e89f90017eb6dcd4f33a26,
108			0x4d52354a3a3d8c865cb10fbabcf00118,
109			0x4d52354a3a3d8c865cb10fbabcf00119,
110			0x4099030c7a9fae7837323ff280de9951,
111			0x4099030c7a9fae7837323ff280de9950,
112			0x7009e616ae59e6a229c2d5f0e38711f5,
113			0x7009e616ae59e6a229c2d5f0e38711f4,
114			0x7dc2d050eefbc45c4241e5b8dfa989bc,
115			0x7dc2d050eefbc45c4241e5b8dfa989bd,
116			0x200af1abbbc495191d10220b4584f2b4,
117			0x200af1abbbc495191d10220b4584f2b5,
118			0x2dc1c7edfb66b7e77693124379aa6afd,
119			0x2dc1c7edfb66b7e77693124379aa6afc,
120			0x1d5122f72fa0ff3d6863f8411af3e259,
121			0x1d5122f72fa0ff3d6863f8411af3e258,
122			0x109a14b16f02ddc303e0c80926dd7a10,
123			0x109a14b16f02ddc303e0c80926dd7a11,
124			0xea7cf43d5eea4253029e7ed5f22e4037,
125			0xea7cf43d5eea4253029e7ed5f22e4036,
126			0xe7b7c27b1e4860ad691d4e9dce00d87e,
127			0xe7b7c27b1e4860ad691d4e9dce00d87f,
128			0xd7272761ca8e287777eda49fad5950da,
129			0xd7272761ca8e287777eda49fad5950db,
130			0xdaec11278a2c0a891c6e94d79177c893,
131			0xdaec11278a2c0a891c6e94d79177c892,
132			0x872430dcdf135bcc433f53640b5ab39b,
133			0x872430dcdf135bcc433f53640b5ab39a,
134			0x8aef069a9fb1793228bc632c37742bd2,
135			0x8aef069a9fb1793228bc632c37742bd3,
136			0xba7fe3804b7731e8364c892e542da376,
137			0xba7fe3804b7731e8364c892e542da377,
138			0xb7b4d5c60bd513165dcfb96668033b3f,
139			0xb7b4d5c60bd513165dcfb96668033b3e,
140			0x553e92e8bc0ae9a795ed1f57f3632d4d,
141			0x553e92e8bc0ae9a795ed1f57f3632d4c,
142			0x58f5a4aefca8cb59fe6e2f1fcf4db504,
143			0x58f5a4aefca8cb59fe6e2f1fcf4db505,
144			0x686541b4286e8383e09ec51dac143da0,
145			0x686541b4286e8383e09ec51dac143da1,
146			0x65ae77f268cca17d8b1df555903aa5e9,
147			0x65ae77f268cca17d8b1df555903aa5e8,
148			0x386656093df3f038d44c32e60a17dee1,
149			0x386656093df3f038d44c32e60a17dee0,
150			0x35ad604f7d51d2c6bfcf02ae363946a8,
151			0x35ad604f7d51d2c6bfcf02ae363946a9,
152			0x053d8555a9979a1ca13fe8ac5560ce0c,
153			0x053d8555a9979a1ca13fe8ac5560ce0d,
154			0x08f6b313e935b8e2cabcd8e4694e5645,
155			0x08f6b313e935b8e2cabcd8e4694e5644,
156			0xf210539fd8dd2772cbc26e38bdbd6c62,
157			0xf210539fd8dd2772cbc26e38bdbd6c63,
158			0xffdb65d9987f058ca0415e708193f42b,
159			0xffdb65d9987f058ca0415e708193f42a,
160			0xcf4b80c34cb94d56beb1b472e2ca7c8f,
161			0xcf4b80c34cb94d56beb1b472e2ca7c8e,
162			0xc280b6850c1b6fa8d532843adee4e4c6,
163			0xc280b6850c1b6fa8d532843adee4e4c7,
164			0x9f48977e59243eed8a63438944c99fce,
165			0x9f48977e59243eed8a63438944c99fcf,
166			0x9283a13819861c13e1e073c178e70787,
167			0x9283a13819861c13e1e073c178e70786,
168			0xa2134422cd4054c9ff1099c31bbe8f23,
169			0xa2134422cd4054c9ff1099c31bbe8f22,
170			0xafd872648de276379493a98b2790176a,
171			0xafd872648de276379493a98b2790176b,
172			0x186ca7a286376521c95c10ed4f932c55,
173			0x186ca7a286376521c95c10ed4f932c54,
174			0x15a791e4c69547dfa2df20a573bdb41c,
175			0x15a791e4c69547dfa2df20a573bdb41d,
176			0x253774fe12530f05bc2fcaa710e43cb8,
177			0x253774fe12530f05bc2fcaa710e43cb9,
178			0x28fc42b852f12dfbd7acfaef2ccaa4f1,
179			0x28fc42b852f12dfbd7acfaef2ccaa4f0,
180			0x7534634307ce7cbe88fd3d5cb6e7dff9,
181			0x7534634307ce7cbe88fd3d5cb6e7dff8,
182			0x78ff5505476c5e40e37e0d148ac947b0,
183			0x78ff5505476c5e40e37e0d148ac947b1,
184			0x486fb01f93aa169afd8ee716e990cf14,
185			0x486fb01f93aa169afd8ee716e990cf15,
186			0x45a48659d3083464960dd75ed5be575d,
187			0x45a48659d3083464960dd75ed5be575c,
188			0xbf4266d5e2e0abf497736182014d6d7a,
189			0xbf4266d5e2e0abf497736182014d6d7b,
190			0xb2895093a242890afcf051ca3d63f533,
191			0xb2895093a242890afcf051ca3d63f532,
192			0x8219b5897684c1d0e200bbc85e3a7d97,
193			0x8219b5897684c1d0e200bbc85e3a7d96,
194			0x8fd283cf3626e32e89838b806214e5de,
195			0x8fd283cf3626e32e89838b806214e5df,
196			0xd21aa2346319b26bd6d24c33f8399ed6,
197			0xd21aa2346319b26bd6d24c33f8399ed7,
198			0xdfd1947223bb9095bd517c7bc417069f,
199			0xdfd1947223bb9095bd517c7bc417069e,
200			0xef417168f77dd84fa3a19679a74e8e3b,
201			0xef417168f77dd84fa3a19679a74e8e3a,
202			0xe28a472eb7dffab1c822a6319b601672,
203			0xe28a472eb7dffab1c822a6319b601673,
204			0x93252331bf042b11512625b1f09fa87e,
205			0x93252331bf042b11512625b1f09fa87f,
206			0x9eee1577ffa609ef3aa515f9ccb13037,
207			0x9eee1577ffa609ef3aa515f9ccb13036,
208			0xae7ef06d2b6041352455fffbafe8b893,
209			0xae7ef06d2b6041352455fffbafe8b892,
210			0xa3b5c62b6bc263cb4fd6cfb393c620da,
211			0xa3b5c62b6bc263cb4fd6cfb393c620db,
212			0xfe7de7d03efd328e1087080009eb5bd2,
213			0xfe7de7d03efd328e1087080009eb5bd3,
214			0xf3b6d1967e5f10707b04384835c5c39b,
215			0xf3b6d1967e5f10707b04384835c5c39a,
216			0xc326348caa9958aa65f4d24a569c4b3f,
217			0xc326348caa9958aa65f4d24a569c4b3e,
218			0xceed02caea3b7a540e77e2026ab2d376,
219			0xceed02caea3b7a540e77e2026ab2d377,
220			0x340be246dbd3e5c40f0954debe41e951,
221			0x340be246dbd3e5c40f0954debe41e950,
222			0x39c0d4009b71c73a648a6496826f7118,
223			0x39c0d4009b71c73a648a6496826f7119,
224			0x0950311a4fb78fe07a7a8e94e136f9bc,
225			0x0950311a4fb78fe07a7a8e94e136f9bd,
226			0x049b075c0f15ad1e11f9bedcdd1861f5,
227			0x049b075c0f15ad1e11f9bedcdd1861f4,
228			0x595326a75a2afc5b4ea8796f47351afd,
229			0x595326a75a2afc5b4ea8796f47351afc,
230			0x549810e11a88dea5252b49277b1b82b4,
231			0x549810e11a88dea5252b49277b1b82b5,
232			0x6408f5fbce4e967f3bdba32518420a10,
233			0x6408f5fbce4e967f3bdba32518420a11,
234			0x69c3c3bd8eecb4815058936d246c9259,
235			0x69c3c3bd8eecb4815058936d246c9258,
236			0xde77167b8539a7970d972a0b4c6fa966,
237			0xde77167b8539a7970d972a0b4c6fa967,
238			0xd3bc203dc59b856966141a437041312f,
239			0xd3bc203dc59b856966141a437041312e,
240			0xe32cc527115dcdb378e4f0411318b98b,
241			0xe32cc527115dcdb378e4f0411318b98a,
242			0xeee7f36151ffef4d1367c0092f3621c2,
243			0xeee7f36151ffef4d1367c0092f3621c3,
244			0xb32fd29a04c0be084c3607bab51b5aca,
245			0xb32fd29a04c0be084c3607bab51b5acb,
246			0xbee4e4dc44629cf627b537f28935c283,
247			0xbee4e4dc44629cf627b537f28935c282,
248			0x8e7401c690a4d42c3945ddf0ea6c4a27,
249			0x8e7401c690a4d42c3945ddf0ea6c4a26,
250			0x83bf3780d006f6d252c6edb8d642d26e,
251			0x83bf3780d006f6d252c6edb8d642d26f,
252			0x7959d70ce1ee694253b85b6402b1e849,
253			0x7959d70ce1ee694253b85b6402b1e848,
254			0x7492e14aa14c4bbc383b6b2c3e9f7000,
255			0x7492e14aa14c4bbc383b6b2c3e9f7001,
256			0x44020450758a036626cb812e5dc6f8a4,
257			0x44020450758a036626cb812e5dc6f8a5,
258			0x49c93216352821984d48b16661e860ed,
259			0x49c93216352821984d48b16661e860ec,
260			0x140113ed601770dd121976d5fbc51be5,
261			0x140113ed601770dd121976d5fbc51be4,
262			0x19ca25ab20b55223799a469dc7eb83ac,
263			0x19ca25ab20b55223799a469dc7eb83ad,
264			0x295ac0b1f4731af9676aac9fa4b20b08,
265			0x295ac0b1f4731af9676aac9fa4b20b09,
266			0x2491f6f7b4d138070ce99cd7989c9341,
267			0x2491f6f7b4d138070ce99cd7989c9340,
268			0xc61bb1d9030ec2b6c4cb3ae603fc8533,
269			0xc61bb1d9030ec2b6c4cb3ae603fc8532,
270			0xcbd0879f43ace048af480aae3fd21d7a,
271			0xcbd0879f43ace048af480aae3fd21d7b,
272			0xfb406285976aa892b1b8e0ac5c8b95de,
273			0xfb406285976aa892b1b8e0ac5c8b95df,
274			0xf68b54c3d7c88a6cda3bd0e460a50d97,
275			0xf68b54c3d7c88a6cda3bd0e460a50d96,
276			0xab43753882f7db29856a1757fa88769f,
277			0xab43753882f7db29856a1757fa88769e,
278			0xa688437ec255f9d7eee9271fc6a6eed6,
279			0xa688437ec255f9d7eee9271fc6a6eed7,
280			0x9618a6641693b10df019cd1da5ff6672,
281			0x9618a6641693b10df019cd1da5ff6673,
282			0x9bd39022563193f39b9afd5599d1fe3b,
283			0x9bd39022563193f39b9afd5599d1fe3a,
284			0x613570ae67d90c639ae44b894d22c41c,
285			0x613570ae67d90c639ae44b894d22c41d,
286			0x6cfe46e8277b2e9df1677bc1710c5c55,
287			0x6cfe46e8277b2e9df1677bc1710c5c54,
288			0x5c6ea3f2f3bd6647ef9791c31255d4f1,
289			0x5c6ea3f2f3bd6647ef9791c31255d4f0,
290			0x51a595b4b31f44b98414a18b2e7b4cb8,
291			0x51a595b4b31f44b98414a18b2e7b4cb9,
292			0x0c6db44fe62015fcdb456638b45637b0,
293			0x0c6db44fe62015fcdb456638b45637b1,
294			0x01a68209a6823702b0c656708878aff9,
295			0x01a68209a6823702b0c656708878aff8,
296			0x3136671372447fd8ae36bc72eb21275d,
297			0x3136671372447fd8ae36bc72eb21275c,
298			0x3cfd515532e65d26c5b58c3ad70fbf14,
299			0x3cfd515532e65d26c5b58c3ad70fbf15,
300			0x8b49849339334e30987a355cbf0c842b,
301			0x8b49849339334e30987a355cbf0c842a,
302			0x8682b2d579916ccef3f9051483221c62,
303			0x8682b2d579916ccef3f9051483221c63,
304			0xb61257cfad572414ed09ef16e07b94c6,
305			0xb61257cfad572414ed09ef16e07b94c7,
306			0xbbd96189edf506ea868adf5edc550c8f,
307			0xbbd96189edf506ea868adf5edc550c8e,
308			0xe6114072b8ca57afd9db18ed46787787,
309			0xe6114072b8ca57afd9db18ed46787786,
310			0xebda7634f8687551b25828a57a56efce,
311			0xebda7634f8687551b25828a57a56efcf,
312			0xdb4a932e2cae3d8baca8c2a7190f676a,
313			0xdb4a932e2cae3d8baca8c2a7190f676b,
314			0xd681a5686c0c1f75c72bf2ef2521ff23,
315			0xd681a5686c0c1f75c72bf2ef2521ff22,
316			0x2c6745e45de480e5c6554433f1d2c504,
317			0x2c6745e45de480e5c6554433f1d2c505,
318			0x21ac73a21d46a21badd6747bcdfc5d4d,
319			0x21ac73a21d46a21badd6747bcdfc5d4c,
320			0x113c96b8c980eac1b3269e79aea5d5e9,
321			0x113c96b8c980eac1b3269e79aea5d5e8,
322			0x1cf7a0fe8922c83fd8a5ae31928b4da0,
323			0x1cf7a0fe8922c83fd8a5ae31928b4da1,
324			0x413f8105dc1d997a87f4698208a636a8,
325			0x413f8105dc1d997a87f4698208a636a9,
326			0x4cf4b7439cbfbb84ec7759ca3488aee1,
327			0x4cf4b7439cbfbb84ec7759ca3488aee0,
328			0x7c6452594879f35ef287b3c857d12645,
329			0x7c6452594879f35ef287b3c857d12644,
330			0x71af641f08dbd1a0990483806bffbe0c,
331			0x71af641f08dbd1a0990483806bffbe0d,
332		];
333
334		Ghash128b::new(LOOKUP_TABLE[value.0 as usize])
335	}
336}
337
338#[cfg(test)]
339mod tests {
340	use proptest::{prelude::any, proptest};
341
342	use super::*;
343	use crate::{WideMul, binary_field::tests::is_binary_field_valid_generator};
344
345	#[test]
346	fn test_ghash_mul() {
347		let a = Ghash128b::new(1u128);
348		let b = Ghash128b::new(1u128);
349		let c = a * b;
350
351		assert_eq!(c, Ghash128b::new(1u128));
352
353		let a = Ghash128b::new(1u128);
354		let b = Ghash128b::new(2u128);
355		let c = a * b;
356
357		assert_eq!(c, Ghash128b::new(2u128));
358
359		let a = Ghash128b::new(1u128);
360		let b = Ghash128b::new(1297182698762987u128);
361		let c = a * b;
362
363		assert_eq!(c, Ghash128b::new(1297182698762987u128));
364
365		let a = Ghash128b::new(2u128);
366		let b = Ghash128b::new(2u128);
367		let c = a * b;
368
369		assert_eq!(c, Ghash128b::new(4u128));
370
371		let a = Ghash128b::new(2u128);
372		let b = Ghash128b::new(3u128);
373		let c = a * b;
374
375		assert_eq!(c, Ghash128b::new(6u128));
376
377		let a = Ghash128b::new(3u128);
378		let b = Ghash128b::new(3u128);
379		let c = a * b;
380
381		assert_eq!(c, Ghash128b::new(5u128));
382
383		let a = Ghash128b::from(1u128 << 127);
384		let b = Ghash128b::new(2u128);
385		let c = a * b;
386
387		assert_eq!(c, Ghash128b::from(0b10000111));
388
389		let a = Ghash128b::from((1u128 << 127) + 1);
390		let b = Ghash128b::new(2u128);
391		let c = a * b;
392
393		assert_eq!(c, Ghash128b::from(0b10000101));
394
395		let a = Ghash128b::from(3u128 << 126);
396		let b = Ghash128b::new(2u128);
397		let c = a * b;
398
399		assert_eq!(c, Ghash128b::from(0b10000111 + (1u128 << 127)));
400
401		let a = Ghash128b::from(1u128 << 127);
402		let b = Ghash128b::new(4u128);
403		let c = a * b;
404
405		assert_eq!(c, Ghash128b::from(0b10000111 << 1));
406
407		let a = Ghash128b::from(1u128 << 127);
408		let b = Ghash128b::from(1u128 << 122);
409		let c = a * b;
410
411		assert_eq!(c, Ghash128b::from((0b00000111 << 121) + 0b10000111));
412	}
413
414	#[test]
415	fn test_multiplicative_generator() {
416		assert!(is_binary_field_valid_generator::<Ghash128b>());
417	}
418
419	#[test]
420	fn test_mul_x() {
421		let test_cases = [
422			0x0,                                    // Zero
423			0x1,                                    // One
424			0x2,                                    // Two
425			0x80000000000000000000000000000000u128, // High bit set
426			0x40000000000000000000000000000000u128, // Second highest bit
427			0xffffffffffffffffffffffffffffffffu128, // All bits set
428			0x87u128,                               // GHASH reduction polynomial
429			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
430		];
431
432		for &value in &test_cases {
433			let field_val = Ghash128b::from(value);
434			let mul_x_result = field_val.mul_x();
435			let regular_mul_result = field_val * Ghash128b::new(2u128);
436
437			assert_eq!(
438				mul_x_result, regular_mul_result,
439				"mul_x and regular multiplication by 2 differ for value {:#x}",
440				value
441			);
442		}
443	}
444
445	proptest! {
446		#[test]
447		fn test_conversion_from_aes_consistency(a in any::<u8>(), b in any::<u8>()) {
448			let a_val = Rijndael8b::new(a);
449			let b_val = Rijndael8b::new(b);
450			let converted_a = Ghash128b::from(a_val);
451			let converted_b = Ghash128b::from(b_val);
452			assert_eq!(Ghash128b::from(a_val * b_val), converted_a * converted_b);
453		}
454
455		#[test]
456		fn test_wide_mul_correctness(a in any::<u128>(), b in any::<u128>()) {
457			let a = Ghash128b::from(a);
458			let b = Ghash128b::from(b);
459			let reduced = Ghash128b::reduce(Ghash128b::wide_mul(a, b));
460			assert_eq!(reduced, a * b);
461		}
462
463		// Exercises the point of the trait: accumulate two unreduced products, reduce once.
464		#[test]
465		fn test_wide_mul_deferred_accumulation(
466			a1 in any::<u128>(), b1 in any::<u128>(),
467			a2 in any::<u128>(), b2 in any::<u128>(),
468		) {
469			let (a1, b1) = (Ghash128b::from(a1), Ghash128b::from(b1));
470			let (a2, b2) = (Ghash128b::from(a2), Ghash128b::from(b2));
471			let wide =
472				Ghash128b::wide_mul(a1, b1) + Ghash128b::wide_mul(a2, b2);
473			assert_eq!(Ghash128b::reduce(wide), a1 * b1 + a2 * b2);
474		}
475	}
476}
binius_field/fields/ghash.rs

binius_field/fields/
ghash.rs
