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	fn from(value: AESTowerField8b) -> Self {
120		const LOOKUP_TABLE: [BinaryField128bGhash; 256] = [
121			BinaryField128bGhash(0x00000000000000000000000000000000),
122			BinaryField128bGhash(0x00000000000000000000000000000001),
123			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9849),
124			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9848),
125			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ed),
126			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ec),
127			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a4),
128			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a5),
129			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ac),
130			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ad),
131			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be5),
132			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be4),
133			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e341),
134			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e340),
135			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b08),
136			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b09),
137			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412f),
138			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412e),
139			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d966),
140			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d967),
141			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c2),
142			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c3),
143			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98b),
144			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98a),
145			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab283),
146			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab282),
147			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842aca),
148			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842acb),
149			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26e),
150			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26f),
151			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a27),
152			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a26),
153			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00118),
154			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00119),
155			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9951),
156			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9950),
157			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f5),
158			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f4),
159			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bc),
160			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bd),
161			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b4),
162			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b5),
163			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afd),
164			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afc),
165			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e259),
166			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e258),
167			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a10),
168			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a11),
169			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4037),
170			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4036),
171			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87e),
172			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87f),
173			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950da),
174			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950db),
175			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c893),
176			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c892),
177			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39b),
178			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39a),
179			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd2),
180			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd3),
181			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da376),
182			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da377),
183			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3f),
184			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3e),
185			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4d),
186			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4c),
187			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db504),
188			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db505),
189			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da0),
190			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da1),
191			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e9),
192			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e8),
193			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee1),
194			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee0),
195			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a8),
196			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a9),
197			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0c),
198			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0d),
199			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5645),
200			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5644),
201			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c62),
202			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c63),
203			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42b),
204			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42a),
205			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8f),
206			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8e),
207			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c6),
208			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c7),
209			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fce),
210			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fcf),
211			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70787),
212			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70786),
213			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f23),
214			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f22),
215			BinaryField128bGhash(0xafd872648de276379493a98b2790176a),
216			BinaryField128bGhash(0xafd872648de276379493a98b2790176b),
217			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c55),
218			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c54),
219			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41c),
220			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41d),
221			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb8),
222			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb9),
223			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f1),
224			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f0),
225			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff9),
226			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff8),
227			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b0),
228			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b1),
229			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf14),
230			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf15),
231			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575d),
232			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575c),
233			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7a),
234			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7b),
235			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f533),
236			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f532),
237			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d97),
238			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d96),
239			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5de),
240			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5df),
241			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed6),
242			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed7),
243			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069f),
244			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069e),
245			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3b),
246			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3a),
247			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601672),
248			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601673),
249			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87e),
250			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87f),
251			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13037),
252			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13036),
253			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b893),
254			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b892),
255			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620da),
256			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620db),
257			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd2),
258			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd3),
259			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39b),
260			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39a),
261			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3f),
262			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3e),
263			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d376),
264			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d377),
265			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e951),
266			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e950),
267			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7118),
268			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7119),
269			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bc),
270			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bd),
271			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f5),
272			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f4),
273			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afd),
274			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afc),
275			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b4),
276			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b5),
277			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a10),
278			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a11),
279			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9259),
280			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9258),
281			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa966),
282			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa967),
283			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312f),
284			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312e),
285			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98b),
286			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98a),
287			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c2),
288			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c3),
289			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5aca),
290			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5acb),
291			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c283),
292			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c282),
293			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a27),
294			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a26),
295			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26e),
296			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26f),
297			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e849),
298			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e848),
299			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7000),
300			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7001),
301			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a4),
302			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a5),
303			BinaryField128bGhash(0x49c93216352821984d48b16661e860ed),
304			BinaryField128bGhash(0x49c93216352821984d48b16661e860ec),
305			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be5),
306			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be4),
307			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ac),
308			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ad),
309			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b08),
310			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b09),
311			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9341),
312			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9340),
313			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8533),
314			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8532),
315			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7a),
316			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7b),
317			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95de),
318			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95df),
319			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d97),
320			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d96),
321			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769f),
322			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769e),
323			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed6),
324			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed7),
325			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6672),
326			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6673),
327			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3b),
328			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3a),
329			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41c),
330			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41d),
331			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c55),
332			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c54),
333			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f1),
334			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f0),
335			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb8),
336			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb9),
337			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b0),
338			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b1),
339			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff9),
340			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff8),
341			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275d),
342			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275c),
343			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf14),
344			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf15),
345			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842b),
346			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842a),
347			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c62),
348			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c63),
349			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c6),
350			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c7),
351			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8f),
352			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8e),
353			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787787),
354			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787786),
355			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efce),
356			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efcf),
357			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676a),
358			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676b),
359			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff23),
360			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff22),
361			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c504),
362			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c505),
363			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4d),
364			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4c),
365			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e9),
366			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e8),
367			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da0),
368			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da1),
369			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a8),
370			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a9),
371			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee1),
372			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee0),
373			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12645),
374			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12644),
375			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0c),
376			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0d),
377		];
378
379		LOOKUP_TABLE[value.0 as usize]
380	}
381}
382
383#[inline(always)]
384pub fn is_ghash_tower<F: TowerField>() -> bool {
385	TypeId::of::<F>() == TypeId::of::<BinaryField128bGhash>()
386		|| TypeId::of::<F>() == TypeId::of::<BinaryField1b>()
387}
388
389#[cfg(test)]
390mod tests {
391	use proptest::{prelude::any, proptest};
392
393	use super::*;
394	use crate::binary_field::tests::is_binary_field_valid_generator;
395
396	#[test]
397	fn test_ghash_mul() {
398		let a = BinaryField128bGhash(1u128);
399		let b = BinaryField128bGhash(1u128);
400		let c = a * b;
401
402		assert_eq!(c, BinaryField128bGhash::from(1u128));
403
404		let a = BinaryField128bGhash(1u128);
405		let b = BinaryField128bGhash(2u128);
406		let c = a * b;
407
408		assert_eq!(c, BinaryField128bGhash::from(2u128));
409
410		let a = BinaryField128bGhash(1u128);
411		let b = BinaryField128bGhash(1297182698762987u128);
412		let c = a * b;
413
414		assert_eq!(c, BinaryField128bGhash::from(1297182698762987u128));
415
416		let a = BinaryField128bGhash(2u128);
417		let b = BinaryField128bGhash(2u128);
418		let c = a * b;
419
420		assert_eq!(c, BinaryField128bGhash::from(4u128));
421
422		let a = BinaryField128bGhash(2u128);
423		let b = BinaryField128bGhash(3u128);
424		let c = a * b;
425
426		assert_eq!(c, BinaryField128bGhash::from(6u128));
427
428		let a = BinaryField128bGhash(3u128);
429		let b = BinaryField128bGhash(3u128);
430		let c = a * b;
431
432		assert_eq!(c, BinaryField128bGhash::from(5u128));
433
434		let a = BinaryField128bGhash(1u128 << 127);
435		let b = BinaryField128bGhash(2u128);
436		let c = a * b;
437
438		assert_eq!(c, BinaryField128bGhash::from(0b10000111));
439
440		let a = BinaryField128bGhash((1u128 << 127) + 1);
441		let b = BinaryField128bGhash(2u128);
442		let c = a * b;
443
444		assert_eq!(c, BinaryField128bGhash::from(0b10000101));
445
446		let a = BinaryField128bGhash(3u128 << 126);
447		let b = BinaryField128bGhash(2u128);
448		let c = a * b;
449
450		assert_eq!(c, BinaryField128bGhash::from(0b10000111 + (1u128 << 127)));
451
452		let a = BinaryField128bGhash(1u128 << 127);
453		let b = BinaryField128bGhash(4u128);
454		let c = a * b;
455
456		assert_eq!(c, BinaryField128bGhash::from(0b10000111 << 1));
457
458		let a = BinaryField128bGhash(1u128 << 127);
459		let b = BinaryField128bGhash(1u128 << 122);
460		let c = a * b;
461
462		assert_eq!(c, BinaryField128bGhash::from((0b00000111 << 121) + 0b10000111));
463	}
464
465	#[test]
466	fn test_multiplicative_generator() {
467		assert!(is_binary_field_valid_generator::<BinaryField128bGhash>());
468	}
469
470	#[test]
471	fn test_mul_x() {
472		let test_cases = [
473			0x0,                                    // Zero
474			0x1,                                    // One
475			0x2,                                    // Two
476			0x80000000000000000000000000000000u128, // High bit set
477			0x40000000000000000000000000000000u128, // Second highest bit
478			0xffffffffffffffffffffffffffffffffu128, // All bits set
479			0x87u128,                               // GHASH reduction polynomial
480			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
481		];
482
483		for &value in &test_cases {
484			let field_val = BinaryField128bGhash::new(value);
485			let mul_x_result = field_val.mul_x();
486			let regular_mul_result = field_val * BinaryField128bGhash::new(2u128);
487
488			assert_eq!(
489				mul_x_result, regular_mul_result,
490				"mul_x and regular multiplication by 2 differ for value {:#x}",
491				value
492			);
493		}
494	}
495
496	#[test]
497	fn test_mul_inv_x() {
498		let test_cases = [
499			0x0,                                    // Zero
500			0x1,                                    // One
501			0x2,                                    // Two
502			0x1u128,                                // Low bit set
503			0x3u128,                                // Two lowest bits set
504			0xffffffffffffffffffffffffffffffffu128, // All bits set
505			0x87u128,                               // GHASH reduction polynomial
506			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
507		];
508
509		for &value in &test_cases {
510			let field_val = BinaryField128bGhash::new(value);
511			let mul_inv_x_result = field_val.mul_inv_x();
512			let regular_mul_result = field_val
513				* BinaryField128bGhash::new(2u128)
514					.invert()
515					.expect("2 is invertible");
516
517			assert_eq!(
518				mul_inv_x_result, regular_mul_result,
519				"mul_inv_x and regular multiplication by 2 differ for value {:#x}",
520				value
521			);
522		}
523	}
524
525	proptest! {
526		#[test]
527		fn test_conversion_from_aes_consistency(a in any::<u8>(), b in any::<u8>()) {
528			let a_val = AESTowerField8b::new(a);
529			let b_val = AESTowerField8b::new(b);
530			let converted_a = BinaryField128bGhash::from(a_val);
531			let converted_b = BinaryField128bGhash::from(b_val);
532			assert_eq!(BinaryField128bGhash::from(a_val * b_val), converted_a * converted_b);
533		}
534	}
535}
binius_field/ghash.rs

binius_field/
ghash.rs
