binius_field/
ghash.rs

1// Copyright 2023-2025 Irreducible Inc.
2
3//! Binary field implementation of GF(2^128) with a modulus of X^128 + X^7 + X^2 + X + 1.
4//! This is the GHASH field used in AES-GCM.
5
6use std::{
7	any::TypeId,
8	fmt::{Debug, Display, Formatter},
9	iter::{Product, Sum},
10	ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
11};
12
13use binius_utils::{
14	DeserializeBytes, SerializationError, SerializeBytes,
15	bytes::{Buf, BufMut},
16};
17use bytemuck::{Pod, Zeroable};
18
19use super::{
20	binary_field::{BinaryField, BinaryField1b, TowerField, binary_field, impl_field_extension},
21	extension::ExtensionField,
22};
23use crate::{
24	AESTowerField8b, Field,
25	arch::packed_ghash_128::PackedBinaryGhash1x128b,
26	arithmetic_traits::InvertOrZero,
27	binary_field_arithmetic::{
28		TowerFieldArithmetic, invert_or_zero_using_packed, multiple_using_packed,
29		square_using_packed,
30	},
31	mul_by_binary_field_1b,
32	underlier::{U1, WithUnderlier},
33};
34
35binary_field!(pub BinaryField128bGhash(u128), 0x494ef99794d5244f9152df59d87a9186);
36
37unsafe impl Pod for BinaryField128bGhash {}
38
39impl BinaryField128bGhash {
40	#[inline]
41	pub fn mul_x(self) -> Self {
42		let val = self.to_underlier();
43		let shifted = val << 1;
44
45		// GHASH irreducible polynomial: x^128 + x^7 + x^2 + x + 1
46		// When the high bit is set, we need to XOR with the reduction polynomial 0x87
47		// All 1s if the top bit is set, all 0s otherwise
48		let mask = (val >> 127).wrapping_neg();
49		let result = shifted ^ (0x87 & mask);
50
51		Self::from_underlier(result)
52	}
53
54	#[inline]
55	pub fn mul_inv_x(self) -> Self {
56		let val = self.to_underlier();
57		let shifted = val >> 1;
58
59		// If low bit was set, we need to add compensation for the remainder
60		// When dividing by x with remainder 1, we add x^(-1) = x^127 to the result
61		// Since x^128 ≡ x^7 + x^2 + x + 1, we have x^127 ≡ x^6 + x + 1
62		// So 0x43 = x^6 + x + 1 (bits 6, 1, 0) and we set bit 127 for the x^127 term
63		// All 1s if the bottom bit is set, all 0s otherwise
64		let mask = (val & 1).wrapping_neg();
65		let result = shifted ^ (((1u128 << 127) | 0x43) & mask);
66
67		Self::from_underlier(result)
68	}
69}
70
71impl TowerField for BinaryField128bGhash {
72	fn min_tower_level(self) -> usize {
73		match self {
74			Self::ZERO | Self::ONE => 0,
75			_ => 7,
76		}
77	}
78}
79
80// Cannot use `impl_arithmetic_using_packed!` because `PackedSubfield<Self, Self>` resolves
81// via `Underlier = u128`, but on SIMD targets `PackedBinaryGhash1x128b` uses `M128`.
82impl TowerFieldArithmetic for BinaryField128bGhash {
83	fn multiply(self, rhs: Self) -> Self {
84		multiple_using_packed::<PackedBinaryGhash1x128b>(self, rhs)
85	}
86
87	fn square(self) -> Self {
88		square_using_packed::<PackedBinaryGhash1x128b>(self)
89	}
90}
91
92impl InvertOrZero for BinaryField128bGhash {
93	#[inline]
94	fn invert_or_zero(self) -> Self {
95		invert_or_zero_using_packed::<PackedBinaryGhash1x128b>(self)
96	}
97}
98
99impl_field_extension!(BinaryField1b(U1) < @7 => BinaryField128bGhash(u128));
100
101mul_by_binary_field_1b!(BinaryField128bGhash);
102
103impl SerializeBytes for BinaryField128bGhash {
104	fn serialize(&self, write_buf: impl BufMut) -> Result<(), SerializationError> {
105		self.0.serialize(write_buf)
106	}
107}
108
109impl DeserializeBytes for BinaryField128bGhash {
110	fn deserialize(read_buf: impl Buf) -> Result<Self, SerializationError>
111	where
112		Self: Sized,
113	{
114		Ok(Self(DeserializeBytes::deserialize(read_buf)?))
115	}
116}
117
118impl From<AESTowerField8b> for BinaryField128bGhash {
119	#[inline]
120	fn from(value: AESTowerField8b) -> Self {
121		const LOOKUP_TABLE: [BinaryField128bGhash; 256] = [
122			BinaryField128bGhash(0x00000000000000000000000000000000),
123			BinaryField128bGhash(0x00000000000000000000000000000001),
124			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9849),
125			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9848),
126			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ed),
127			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ec),
128			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a4),
129			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a5),
130			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ac),
131			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ad),
132			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be5),
133			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be4),
134			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e341),
135			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e340),
136			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b08),
137			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b09),
138			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412f),
139			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412e),
140			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d966),
141			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d967),
142			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c2),
143			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c3),
144			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98b),
145			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98a),
146			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab283),
147			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab282),
148			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842aca),
149			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842acb),
150			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26e),
151			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26f),
152			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a27),
153			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a26),
154			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00118),
155			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00119),
156			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9951),
157			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9950),
158			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f5),
159			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f4),
160			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bc),
161			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bd),
162			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b4),
163			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b5),
164			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afd),
165			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afc),
166			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e259),
167			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e258),
168			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a10),
169			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a11),
170			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4037),
171			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4036),
172			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87e),
173			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87f),
174			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950da),
175			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950db),
176			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c893),
177			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c892),
178			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39b),
179			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39a),
180			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd2),
181			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd3),
182			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da376),
183			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da377),
184			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3f),
185			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3e),
186			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4d),
187			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4c),
188			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db504),
189			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db505),
190			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da0),
191			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da1),
192			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e9),
193			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e8),
194			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee1),
195			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee0),
196			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a8),
197			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a9),
198			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0c),
199			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0d),
200			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5645),
201			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5644),
202			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c62),
203			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c63),
204			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42b),
205			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42a),
206			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8f),
207			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8e),
208			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c6),
209			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c7),
210			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fce),
211			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fcf),
212			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70787),
213			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70786),
214			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f23),
215			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f22),
216			BinaryField128bGhash(0xafd872648de276379493a98b2790176a),
217			BinaryField128bGhash(0xafd872648de276379493a98b2790176b),
218			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c55),
219			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c54),
220			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41c),
221			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41d),
222			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb8),
223			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb9),
224			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f1),
225			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f0),
226			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff9),
227			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff8),
228			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b0),
229			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b1),
230			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf14),
231			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf15),
232			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575d),
233			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575c),
234			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7a),
235			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7b),
236			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f533),
237			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f532),
238			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d97),
239			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d96),
240			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5de),
241			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5df),
242			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed6),
243			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed7),
244			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069f),
245			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069e),
246			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3b),
247			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3a),
248			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601672),
249			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601673),
250			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87e),
251			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87f),
252			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13037),
253			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13036),
254			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b893),
255			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b892),
256			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620da),
257			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620db),
258			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd2),
259			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd3),
260			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39b),
261			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39a),
262			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3f),
263			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3e),
264			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d376),
265			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d377),
266			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e951),
267			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e950),
268			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7118),
269			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7119),
270			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bc),
271			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bd),
272			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f5),
273			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f4),
274			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afd),
275			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afc),
276			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b4),
277			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b5),
278			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a10),
279			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a11),
280			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9259),
281			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9258),
282			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa966),
283			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa967),
284			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312f),
285			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312e),
286			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98b),
287			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98a),
288			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c2),
289			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c3),
290			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5aca),
291			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5acb),
292			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c283),
293			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c282),
294			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a27),
295			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a26),
296			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26e),
297			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26f),
298			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e849),
299			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e848),
300			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7000),
301			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7001),
302			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a4),
303			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a5),
304			BinaryField128bGhash(0x49c93216352821984d48b16661e860ed),
305			BinaryField128bGhash(0x49c93216352821984d48b16661e860ec),
306			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be5),
307			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be4),
308			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ac),
309			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ad),
310			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b08),
311			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b09),
312			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9341),
313			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9340),
314			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8533),
315			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8532),
316			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7a),
317			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7b),
318			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95de),
319			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95df),
320			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d97),
321			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d96),
322			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769f),
323			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769e),
324			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed6),
325			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed7),
326			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6672),
327			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6673),
328			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3b),
329			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3a),
330			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41c),
331			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41d),
332			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c55),
333			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c54),
334			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f1),
335			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f0),
336			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb8),
337			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb9),
338			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b0),
339			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b1),
340			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff9),
341			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff8),
342			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275d),
343			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275c),
344			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf14),
345			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf15),
346			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842b),
347			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842a),
348			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c62),
349			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c63),
350			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c6),
351			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c7),
352			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8f),
353			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8e),
354			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787787),
355			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787786),
356			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efce),
357			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efcf),
358			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676a),
359			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676b),
360			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff23),
361			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff22),
362			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c504),
363			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c505),
364			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4d),
365			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4c),
366			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e9),
367			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e8),
368			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da0),
369			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da1),
370			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a8),
371			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a9),
372			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee1),
373			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee0),
374			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12645),
375			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12644),
376			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0c),
377			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0d),
378		];
379
380		LOOKUP_TABLE[value.0 as usize]
381	}
382}
383
384#[inline(always)]
385pub fn is_ghash_tower<F: TowerField>() -> bool {
386	TypeId::of::<F>() == TypeId::of::<BinaryField128bGhash>()
387		|| TypeId::of::<F>() == TypeId::of::<BinaryField1b>()
388}
389
390#[cfg(test)]
391mod tests {
392	use proptest::{prelude::any, proptest};
393
394	use super::*;
395	use crate::binary_field::tests::is_binary_field_valid_generator;
396
397	#[test]
398	fn test_ghash_mul() {
399		let a = BinaryField128bGhash(1u128);
400		let b = BinaryField128bGhash(1u128);
401		let c = a * b;
402
403		assert_eq!(c, BinaryField128bGhash::from(1u128));
404
405		let a = BinaryField128bGhash(1u128);
406		let b = BinaryField128bGhash(2u128);
407		let c = a * b;
408
409		assert_eq!(c, BinaryField128bGhash::from(2u128));
410
411		let a = BinaryField128bGhash(1u128);
412		let b = BinaryField128bGhash(1297182698762987u128);
413		let c = a * b;
414
415		assert_eq!(c, BinaryField128bGhash::from(1297182698762987u128));
416
417		let a = BinaryField128bGhash(2u128);
418		let b = BinaryField128bGhash(2u128);
419		let c = a * b;
420
421		assert_eq!(c, BinaryField128bGhash::from(4u128));
422
423		let a = BinaryField128bGhash(2u128);
424		let b = BinaryField128bGhash(3u128);
425		let c = a * b;
426
427		assert_eq!(c, BinaryField128bGhash::from(6u128));
428
429		let a = BinaryField128bGhash(3u128);
430		let b = BinaryField128bGhash(3u128);
431		let c = a * b;
432
433		assert_eq!(c, BinaryField128bGhash::from(5u128));
434
435		let a = BinaryField128bGhash(1u128 << 127);
436		let b = BinaryField128bGhash(2u128);
437		let c = a * b;
438
439		assert_eq!(c, BinaryField128bGhash::from(0b10000111));
440
441		let a = BinaryField128bGhash((1u128 << 127) + 1);
442		let b = BinaryField128bGhash(2u128);
443		let c = a * b;
444
445		assert_eq!(c, BinaryField128bGhash::from(0b10000101));
446
447		let a = BinaryField128bGhash(3u128 << 126);
448		let b = BinaryField128bGhash(2u128);
449		let c = a * b;
450
451		assert_eq!(c, BinaryField128bGhash::from(0b10000111 + (1u128 << 127)));
452
453		let a = BinaryField128bGhash(1u128 << 127);
454		let b = BinaryField128bGhash(4u128);
455		let c = a * b;
456
457		assert_eq!(c, BinaryField128bGhash::from(0b10000111 << 1));
458
459		let a = BinaryField128bGhash(1u128 << 127);
460		let b = BinaryField128bGhash(1u128 << 122);
461		let c = a * b;
462
463		assert_eq!(c, BinaryField128bGhash::from((0b00000111 << 121) + 0b10000111));
464	}
465
466	#[test]
467	fn test_multiplicative_generator() {
468		assert!(is_binary_field_valid_generator::<BinaryField128bGhash>());
469	}
470
471	#[test]
472	fn test_mul_x() {
473		let test_cases = [
474			0x0,                                    // Zero
475			0x1,                                    // One
476			0x2,                                    // Two
477			0x80000000000000000000000000000000u128, // High bit set
478			0x40000000000000000000000000000000u128, // Second highest bit
479			0xffffffffffffffffffffffffffffffffu128, // All bits set
480			0x87u128,                               // GHASH reduction polynomial
481			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
482		];
483
484		for &value in &test_cases {
485			let field_val = BinaryField128bGhash::new(value);
486			let mul_x_result = field_val.mul_x();
487			let regular_mul_result = field_val * BinaryField128bGhash::new(2u128);
488
489			assert_eq!(
490				mul_x_result, regular_mul_result,
491				"mul_x and regular multiplication by 2 differ for value {:#x}",
492				value
493			);
494		}
495	}
496
497	#[test]
498	fn test_mul_inv_x() {
499		let test_cases = [
500			0x0,                                    // Zero
501			0x1,                                    // One
502			0x2,                                    // Two
503			0x1u128,                                // Low bit set
504			0x3u128,                                // Two lowest bits set
505			0xffffffffffffffffffffffffffffffffu128, // All bits set
506			0x87u128,                               // GHASH reduction polynomial
507			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
508		];
509
510		for &value in &test_cases {
511			let field_val = BinaryField128bGhash::new(value);
512			let mul_inv_x_result = field_val.mul_inv_x();
513			let regular_mul_result = field_val
514				* BinaryField128bGhash::new(2u128)
515					.invert()
516					.expect("2 is invertible");
517
518			assert_eq!(
519				mul_inv_x_result, regular_mul_result,
520				"mul_inv_x and regular multiplication by 2 differ for value {:#x}",
521				value
522			);
523		}
524	}
525
526	proptest! {
527		#[test]
528		fn test_conversion_from_aes_consistency(a in any::<u8>(), b in any::<u8>()) {
529			let a_val = AESTowerField8b::new(a);
530			let b_val = AESTowerField8b::new(b);
531			let converted_a = BinaryField128bGhash::from(a_val);
532			let converted_b = BinaryField128bGhash::from(b_val);
533			assert_eq!(BinaryField128bGhash::from(a_val * b_val), converted_a * converted_b);
534		}
535	}
536}
binius_field/ghash.rs

binius_field/
ghash.rs
