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::{self, 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	iter::IterExtensions,
17};
18use bytemuck::{Pod, Zeroable};
19use rand::{
20	Rng,
21	distr::{Distribution, StandardUniform},
22};
23
24use super::{
25	arithmetic_traits::InvertOrZero,
26	binary_field::{BinaryField, BinaryField1b, TowerField},
27	error::Error,
28	extension::ExtensionField,
29	underlier::WithUnderlier,
30};
31use crate::{
32	AESTowerField8b, Field,
33	arch::packed_ghash_128::PackedBinaryGhash1x128b,
34	arithmetic_traits::Square,
35	binary_field_arithmetic::{
36		invert_or_zero_using_packed, multiple_using_packed, square_using_packed,
37	},
38	transpose::square_transforms_extension_field,
39	underlier::{Divisible, NumCast, U1, UnderlierWithBitOps},
40};
41
42#[derive(
43	Default,
44	Clone,
45	Copy,
46	PartialEq,
47	Eq,
48	PartialOrd,
49	Ord,
50	Hash,
51	Zeroable,
52	bytemuck::TransparentWrapper,
53)]
54#[repr(transparent)]
55pub struct BinaryField128bGhash(pub(crate) u128);
56
57impl BinaryField128bGhash {
58	#[inline]
59	pub const fn new(value: u128) -> Self {
60		Self(value)
61	}
62
63	#[inline]
64	pub const fn val(self) -> u128 {
65		self.0
66	}
67
68	#[inline]
69	pub fn mul_x(self) -> Self {
70		let val = self.to_underlier();
71		let shifted = val << 1;
72
73		// GHASH irreducible polynomial: x^128 + x^7 + x^2 + x + 1
74		// When the high bit is set, we need to XOR with the reduction polynomial 0x87
75		// All 1s if the top bit is set, all 0s otherwise
76		let mask = (val >> 127).wrapping_neg();
77		let result = shifted ^ (0x87 & mask);
78
79		Self::from_underlier(result)
80	}
81
82	#[inline]
83	pub fn mul_inv_x(self) -> Self {
84		let val = self.to_underlier();
85		let shifted = val >> 1;
86
87		// If low bit was set, we need to add compensation for the remainder
88		// When dividing by x with remainder 1, we add x^(-1) = x^127 to the result
89		// Since x^128 ≡ x^7 + x^2 + x + 1, we have x^127 ≡ x^6 + x + 1
90		// So 0x43 = x^6 + x + 1 (bits 6, 1, 0) and we set bit 127 for the x^127 term
91		// All 1s if the bottom bit is set, all 0s otherwise
92		let mask = (val & 1).wrapping_neg();
93		let result = shifted ^ (((1u128 << 127) | 0x43) & mask);
94
95		Self::from_underlier(result)
96	}
97}
98
99unsafe impl WithUnderlier for BinaryField128bGhash {
100	type Underlier = u128;
101}
102
103impl Neg for BinaryField128bGhash {
104	type Output = Self;
105
106	#[inline]
107	fn neg(self) -> Self::Output {
108		self
109	}
110}
111
112impl Add<Self> for BinaryField128bGhash {
113	type Output = Self;
114
115	#[allow(clippy::suspicious_arithmetic_impl)]
116	fn add(self, rhs: Self) -> Self::Output {
117		Self(self.0 ^ rhs.0)
118	}
119}
120
121impl Add<&Self> for BinaryField128bGhash {
122	type Output = Self;
123
124	#[allow(clippy::suspicious_arithmetic_impl)]
125	fn add(self, rhs: &Self) -> Self::Output {
126		Self(self.0 ^ rhs.0)
127	}
128}
129
130impl Sub<Self> for BinaryField128bGhash {
131	type Output = Self;
132
133	#[allow(clippy::suspicious_arithmetic_impl)]
134	fn sub(self, rhs: Self) -> Self::Output {
135		Self(self.0 ^ rhs.0)
136	}
137}
138
139impl Sub<&Self> for BinaryField128bGhash {
140	type Output = Self;
141
142	#[allow(clippy::suspicious_arithmetic_impl)]
143	fn sub(self, rhs: &Self) -> Self::Output {
144		Self(self.0 ^ rhs.0)
145	}
146}
147
148impl Mul<Self> for BinaryField128bGhash {
149	type Output = Self;
150
151	#[inline]
152	fn mul(self, rhs: Self) -> Self::Output {
153		multiple_using_packed::<PackedBinaryGhash1x128b>(self, rhs)
154	}
155}
156
157impl Mul<&Self> for BinaryField128bGhash {
158	type Output = Self;
159
160	#[inline]
161	fn mul(self, rhs: &Self) -> Self::Output {
162		self * *rhs
163	}
164}
165
166impl AddAssign<Self> for BinaryField128bGhash {
167	#[inline]
168	fn add_assign(&mut self, rhs: Self) {
169		*self = *self + rhs;
170	}
171}
172
173impl AddAssign<&Self> for BinaryField128bGhash {
174	#[inline]
175	fn add_assign(&mut self, rhs: &Self) {
176		*self = *self + rhs;
177	}
178}
179
180impl SubAssign<Self> for BinaryField128bGhash {
181	#[inline]
182	fn sub_assign(&mut self, rhs: Self) {
183		*self = *self - rhs;
184	}
185}
186
187impl SubAssign<&Self> for BinaryField128bGhash {
188	#[inline]
189	fn sub_assign(&mut self, rhs: &Self) {
190		*self = *self - rhs;
191	}
192}
193
194impl MulAssign<Self> for BinaryField128bGhash {
195	#[inline]
196	fn mul_assign(&mut self, rhs: Self) {
197		*self = *self * rhs;
198	}
199}
200
201impl MulAssign<&Self> for BinaryField128bGhash {
202	#[inline]
203	fn mul_assign(&mut self, rhs: &Self) {
204		*self = *self * rhs;
205	}
206}
207
208impl Sum<Self> for BinaryField128bGhash {
209	#[inline]
210	fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
211		iter.fold(Self::ZERO, |acc, x| acc + x)
212	}
213}
214
215impl<'a> Sum<&'a Self> for BinaryField128bGhash {
216	#[inline]
217	fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
218		iter.fold(Self::ZERO, |acc, x| acc + x)
219	}
220}
221
222impl Product<Self> for BinaryField128bGhash {
223	#[inline]
224	fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
225		iter.fold(Self::ONE, |acc, x| acc * x)
226	}
227}
228
229impl<'a> Product<&'a Self> for BinaryField128bGhash {
230	#[inline]
231	fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
232		iter.fold(Self::ONE, |acc, x| acc * x)
233	}
234}
235
236impl Square for BinaryField128bGhash {
237	#[inline]
238	fn square(self) -> Self {
239		square_using_packed::<PackedBinaryGhash1x128b>(self)
240	}
241}
242
243impl Field for BinaryField128bGhash {
244	const ZERO: Self = Self(0);
245	const ONE: Self = Self(1);
246	const CHARACTERISTIC: usize = 2;
247	const MULTIPLICATIVE_GENERATOR: Self = Self(0x494ef99794d5244f9152df59d87a9186);
248
249	fn double(&self) -> Self {
250		Self(0)
251	}
252}
253
254impl Distribution<BinaryField128bGhash> for StandardUniform {
255	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BinaryField128bGhash {
256		BinaryField128bGhash(rng.random())
257	}
258}
259
260impl InvertOrZero for BinaryField128bGhash {
261	#[inline]
262	fn invert_or_zero(self) -> Self {
263		invert_or_zero_using_packed::<PackedBinaryGhash1x128b>(self)
264	}
265}
266
267impl From<u128> for BinaryField128bGhash {
268	#[inline]
269	fn from(value: u128) -> Self {
270		Self(value)
271	}
272}
273
274impl From<BinaryField128bGhash> for u128 {
275	#[inline]
276	fn from(value: BinaryField128bGhash) -> Self {
277		value.0
278	}
279}
280
281impl Display for BinaryField128bGhash {
282	fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
283		write!(f, "0x{repr:0>32x}", repr = self.0)
284	}
285}
286
287impl Debug for BinaryField128bGhash {
288	fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
289		write!(f, "BinaryField128bGhash({self})")
290	}
291}
292
293unsafe impl Pod for BinaryField128bGhash {}
294
295impl TryInto<BinaryField1b> for BinaryField128bGhash {
296	type Error = ();
297
298	#[inline]
299	fn try_into(self) -> Result<BinaryField1b, Self::Error> {
300		if self == Self::ZERO {
301			Ok(BinaryField1b::ZERO)
302		} else if self == Self::ONE {
303			Ok(BinaryField1b::ONE)
304		} else {
305			Err(())
306		}
307	}
308}
309
310impl From<BinaryField1b> for BinaryField128bGhash {
311	#[inline]
312	fn from(value: BinaryField1b) -> Self {
313		debug_assert_eq!(Self::ZERO, Self(0));
314
315		Self(Self::ONE.0 & u128::fill_with_bit(value.val().val()))
316	}
317}
318
319impl Add<BinaryField1b> for BinaryField128bGhash {
320	type Output = Self;
321
322	#[inline]
323	fn add(self, rhs: BinaryField1b) -> Self::Output {
324		self + Self::from(rhs)
325	}
326}
327
328impl Sub<BinaryField1b> for BinaryField128bGhash {
329	type Output = Self;
330
331	#[inline]
332	fn sub(self, rhs: BinaryField1b) -> Self::Output {
333		self - Self::from(rhs)
334	}
335}
336
337impl Mul<BinaryField1b> for BinaryField128bGhash {
338	type Output = Self;
339
340	#[inline]
341	#[allow(clippy::suspicious_arithmetic_impl)]
342	fn mul(self, rhs: BinaryField1b) -> Self::Output {
343		crate::tracing::trace_multiplication!(BinaryField128bGhash, BinaryField1b);
344
345		Self(self.0 & u128::fill_with_bit(u8::from(rhs.0)))
346	}
347}
348
349impl AddAssign<BinaryField1b> for BinaryField128bGhash {
350	#[inline]
351	fn add_assign(&mut self, rhs: BinaryField1b) {
352		*self = *self + rhs;
353	}
354}
355
356impl SubAssign<BinaryField1b> for BinaryField128bGhash {
357	#[inline]
358	fn sub_assign(&mut self, rhs: BinaryField1b) {
359		*self = *self - rhs;
360	}
361}
362
363impl MulAssign<BinaryField1b> for BinaryField128bGhash {
364	#[inline]
365	fn mul_assign(&mut self, rhs: BinaryField1b) {
366		*self = *self * rhs;
367	}
368}
369
370impl Add<BinaryField128bGhash> for BinaryField1b {
371	type Output = BinaryField128bGhash;
372
373	#[inline]
374	fn add(self, rhs: BinaryField128bGhash) -> Self::Output {
375		rhs + self
376	}
377}
378
379impl Sub<BinaryField128bGhash> for BinaryField1b {
380	type Output = BinaryField128bGhash;
381
382	#[inline]
383	fn sub(self, rhs: BinaryField128bGhash) -> Self::Output {
384		rhs - self
385	}
386}
387
388impl Mul<BinaryField128bGhash> for BinaryField1b {
389	type Output = BinaryField128bGhash;
390
391	#[inline]
392	fn mul(self, rhs: BinaryField128bGhash) -> Self::Output {
393		rhs * self
394	}
395}
396
397impl ExtensionField<BinaryField1b> for BinaryField128bGhash {
398	const LOG_DEGREE: usize = 7;
399
400	#[inline]
401	fn basis_checked(i: usize) -> Result<Self, Error> {
402		if i >= 128 {
403			return Err(Error::ExtensionDegreeMismatch);
404		}
405		Ok(Self::new(1 << i))
406	}
407
408	#[inline]
409	fn from_bases_sparse(
410		base_elems: impl IntoIterator<Item = BinaryField1b>,
411		log_stride: usize,
412	) -> Result<Self, Error> {
413		if log_stride != 7 {
414			return Err(Error::ExtensionDegreeMismatch);
415		}
416		let value = base_elems
417			.into_iter()
418			.enumerate()
419			.fold(0, |value, (i, elem)| value | (u128::from(elem.0) << i));
420		Ok(Self::new(value))
421	}
422
423	#[inline]
424	fn iter_bases(&self) -> impl Iterator<Item = BinaryField1b> {
425		Divisible::<U1>::value_iter(self.0).map_skippable(BinaryField1b::from)
426	}
427
428	#[inline]
429	fn into_iter_bases(self) -> impl Iterator<Item = BinaryField1b> {
430		Divisible::<U1>::value_iter(self.0).map_skippable(BinaryField1b::from)
431	}
432
433	#[inline]
434	unsafe fn get_base_unchecked(&self, i: usize) -> BinaryField1b {
435		BinaryField1b(U1::num_cast_from(self.0 >> i))
436	}
437
438	#[inline]
439	fn square_transpose(values: &mut [Self]) -> Result<(), Error> {
440		square_transforms_extension_field::<BinaryField1b, Self>(values)
441			.map_err(|_| Error::ExtensionDegreeMismatch)
442	}
443}
444
445impl SerializeBytes for BinaryField128bGhash {
446	fn serialize(&self, write_buf: impl BufMut) -> Result<(), SerializationError> {
447		self.0.serialize(write_buf)
448	}
449}
450
451impl DeserializeBytes for BinaryField128bGhash {
452	fn deserialize(read_buf: impl Buf) -> Result<Self, SerializationError>
453	where
454		Self: Sized,
455	{
456		Ok(Self(DeserializeBytes::deserialize(read_buf)?))
457	}
458}
459
460impl BinaryField for BinaryField128bGhash {}
461
462impl TowerField for BinaryField128bGhash {
463	fn min_tower_level(self) -> usize {
464		match self {
465			Self::ZERO | Self::ONE => 0,
466			_ => 7,
467		}
468	}
469
470	fn mul_primitive(self, _iota: usize) -> Result<Self, Error> {
471		// This method could be implemented by multiplying by isomorphic alpha value
472		// But it's not being used as for now
473		unimplemented!()
474	}
475}
476
477impl From<AESTowerField8b> for BinaryField128bGhash {
478	fn from(value: AESTowerField8b) -> Self {
479		const LOOKUP_TABLE: [BinaryField128bGhash; 256] = [
480			BinaryField128bGhash(0x00000000000000000000000000000000),
481			BinaryField128bGhash(0x00000000000000000000000000000001),
482			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9849),
483			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9848),
484			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ed),
485			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ec),
486			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a4),
487			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a5),
488			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ac),
489			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ad),
490			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be5),
491			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be4),
492			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e341),
493			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e340),
494			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b08),
495			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b09),
496			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412f),
497			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412e),
498			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d966),
499			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d967),
500			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c2),
501			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c3),
502			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98b),
503			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98a),
504			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab283),
505			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab282),
506			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842aca),
507			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842acb),
508			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26e),
509			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26f),
510			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a27),
511			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a26),
512			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00118),
513			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00119),
514			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9951),
515			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9950),
516			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f5),
517			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f4),
518			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bc),
519			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bd),
520			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b4),
521			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b5),
522			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afd),
523			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afc),
524			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e259),
525			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e258),
526			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a10),
527			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a11),
528			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4037),
529			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4036),
530			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87e),
531			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87f),
532			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950da),
533			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950db),
534			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c893),
535			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c892),
536			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39b),
537			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39a),
538			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd2),
539			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd3),
540			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da376),
541			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da377),
542			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3f),
543			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3e),
544			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4d),
545			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4c),
546			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db504),
547			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db505),
548			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da0),
549			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da1),
550			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e9),
551			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e8),
552			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee1),
553			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee0),
554			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a8),
555			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a9),
556			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0c),
557			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0d),
558			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5645),
559			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5644),
560			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c62),
561			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c63),
562			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42b),
563			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42a),
564			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8f),
565			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8e),
566			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c6),
567			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c7),
568			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fce),
569			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fcf),
570			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70787),
571			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70786),
572			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f23),
573			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f22),
574			BinaryField128bGhash(0xafd872648de276379493a98b2790176a),
575			BinaryField128bGhash(0xafd872648de276379493a98b2790176b),
576			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c55),
577			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c54),
578			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41c),
579			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41d),
580			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb8),
581			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb9),
582			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f1),
583			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f0),
584			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff9),
585			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff8),
586			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b0),
587			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b1),
588			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf14),
589			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf15),
590			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575d),
591			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575c),
592			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7a),
593			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7b),
594			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f533),
595			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f532),
596			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d97),
597			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d96),
598			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5de),
599			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5df),
600			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed6),
601			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed7),
602			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069f),
603			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069e),
604			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3b),
605			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3a),
606			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601672),
607			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601673),
608			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87e),
609			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87f),
610			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13037),
611			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13036),
612			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b893),
613			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b892),
614			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620da),
615			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620db),
616			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd2),
617			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd3),
618			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39b),
619			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39a),
620			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3f),
621			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3e),
622			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d376),
623			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d377),
624			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e951),
625			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e950),
626			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7118),
627			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7119),
628			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bc),
629			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bd),
630			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f5),
631			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f4),
632			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afd),
633			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afc),
634			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b4),
635			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b5),
636			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a10),
637			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a11),
638			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9259),
639			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9258),
640			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa966),
641			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa967),
642			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312f),
643			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312e),
644			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98b),
645			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98a),
646			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c2),
647			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c3),
648			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5aca),
649			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5acb),
650			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c283),
651			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c282),
652			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a27),
653			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a26),
654			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26e),
655			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26f),
656			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e849),
657			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e848),
658			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7000),
659			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7001),
660			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a4),
661			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a5),
662			BinaryField128bGhash(0x49c93216352821984d48b16661e860ed),
663			BinaryField128bGhash(0x49c93216352821984d48b16661e860ec),
664			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be5),
665			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be4),
666			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ac),
667			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ad),
668			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b08),
669			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b09),
670			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9341),
671			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9340),
672			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8533),
673			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8532),
674			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7a),
675			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7b),
676			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95de),
677			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95df),
678			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d97),
679			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d96),
680			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769f),
681			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769e),
682			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed6),
683			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed7),
684			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6672),
685			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6673),
686			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3b),
687			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3a),
688			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41c),
689			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41d),
690			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c55),
691			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c54),
692			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f1),
693			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f0),
694			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb8),
695			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb9),
696			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b0),
697			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b1),
698			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff9),
699			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff8),
700			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275d),
701			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275c),
702			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf14),
703			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf15),
704			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842b),
705			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842a),
706			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c62),
707			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c63),
708			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c6),
709			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c7),
710			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8f),
711			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8e),
712			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787787),
713			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787786),
714			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efce),
715			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efcf),
716			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676a),
717			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676b),
718			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff23),
719			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff22),
720			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c504),
721			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c505),
722			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4d),
723			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4c),
724			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e9),
725			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e8),
726			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da0),
727			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da1),
728			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a8),
729			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a9),
730			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee1),
731			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee0),
732			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12645),
733			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12644),
734			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0c),
735			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0d),
736		];
737
738		LOOKUP_TABLE[value.0 as usize]
739	}
740}
741
742#[inline(always)]
743pub fn is_ghash_tower<F: TowerField>() -> bool {
744	TypeId::of::<F>() == TypeId::of::<BinaryField128bGhash>()
745		|| TypeId::of::<F>() == TypeId::of::<BinaryField1b>()
746}
747
748#[cfg(test)]
749mod tests {
750	use proptest::{prelude::any, proptest};
751
752	use super::*;
753	use crate::binary_field::tests::is_binary_field_valid_generator;
754
755	#[test]
756	fn test_ghash_mul() {
757		let a = BinaryField128bGhash(1u128);
758		let b = BinaryField128bGhash(1u128);
759		let c = a * b;
760
761		assert_eq!(c, BinaryField128bGhash::from(1u128));
762
763		let a = BinaryField128bGhash(1u128);
764		let b = BinaryField128bGhash(2u128);
765		let c = a * b;
766
767		assert_eq!(c, BinaryField128bGhash::from(2u128));
768
769		let a = BinaryField128bGhash(1u128);
770		let b = BinaryField128bGhash(1297182698762987u128);
771		let c = a * b;
772
773		assert_eq!(c, BinaryField128bGhash::from(1297182698762987u128));
774
775		let a = BinaryField128bGhash(2u128);
776		let b = BinaryField128bGhash(2u128);
777		let c = a * b;
778
779		assert_eq!(c, BinaryField128bGhash::from(4u128));
780
781		let a = BinaryField128bGhash(2u128);
782		let b = BinaryField128bGhash(3u128);
783		let c = a * b;
784
785		assert_eq!(c, BinaryField128bGhash::from(6u128));
786
787		let a = BinaryField128bGhash(3u128);
788		let b = BinaryField128bGhash(3u128);
789		let c = a * b;
790
791		assert_eq!(c, BinaryField128bGhash::from(5u128));
792
793		let a = BinaryField128bGhash(1u128 << 127);
794		let b = BinaryField128bGhash(2u128);
795		let c = a * b;
796
797		assert_eq!(c, BinaryField128bGhash::from(0b10000111));
798
799		let a = BinaryField128bGhash((1u128 << 127) + 1);
800		let b = BinaryField128bGhash(2u128);
801		let c = a * b;
802
803		assert_eq!(c, BinaryField128bGhash::from(0b10000101));
804
805		let a = BinaryField128bGhash(3u128 << 126);
806		let b = BinaryField128bGhash(2u128);
807		let c = a * b;
808
809		assert_eq!(c, BinaryField128bGhash::from(0b10000111 + (1u128 << 127)));
810
811		let a = BinaryField128bGhash(1u128 << 127);
812		let b = BinaryField128bGhash(4u128);
813		let c = a * b;
814
815		assert_eq!(c, BinaryField128bGhash::from(0b10000111 << 1));
816
817		let a = BinaryField128bGhash(1u128 << 127);
818		let b = BinaryField128bGhash(1u128 << 122);
819		let c = a * b;
820
821		assert_eq!(c, BinaryField128bGhash::from((0b00000111 << 121) + 0b10000111));
822	}
823
824	#[test]
825	fn test_multiplicative_generator() {
826		assert!(is_binary_field_valid_generator::<BinaryField128bGhash>());
827	}
828
829	#[test]
830	fn test_mul_x() {
831		let test_cases = [
832			0x0,                                    // Zero
833			0x1,                                    // One
834			0x2,                                    // Two
835			0x80000000000000000000000000000000u128, // High bit set
836			0x40000000000000000000000000000000u128, // Second highest bit
837			0xffffffffffffffffffffffffffffffffu128, // All bits set
838			0x87u128,                               // GHASH reduction polynomial
839			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
840		];
841
842		for &value in &test_cases {
843			let field_val = BinaryField128bGhash::new(value);
844			let mul_x_result = field_val.mul_x();
845			let regular_mul_result = field_val * BinaryField128bGhash::new(2u128);
846
847			assert_eq!(
848				mul_x_result, regular_mul_result,
849				"mul_x and regular multiplication by 2 differ for value {:#x}",
850				value
851			);
852		}
853	}
854
855	#[test]
856	fn test_mul_inv_x() {
857		let test_cases = [
858			0x0,                                    // Zero
859			0x1,                                    // One
860			0x2,                                    // Two
861			0x1u128,                                // Low bit set
862			0x3u128,                                // Two lowest bits set
863			0xffffffffffffffffffffffffffffffffu128, // All bits set
864			0x87u128,                               // GHASH reduction polynomial
865			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
866		];
867
868		for &value in &test_cases {
869			let field_val = BinaryField128bGhash::new(value);
870			let mul_inv_x_result = field_val.mul_inv_x();
871			let regular_mul_result = field_val
872				* BinaryField128bGhash::new(2u128)
873					.invert()
874					.expect("2 is invertible");
875
876			assert_eq!(
877				mul_inv_x_result, regular_mul_result,
878				"mul_inv_x and regular multiplication by 2 differ for value {:#x}",
879				value
880			);
881		}
882	}
883
884	proptest! {
885		#[test]
886		fn test_conversion_from_aes_consistency(a in any::<u8>(), b in any::<u8>()) {
887			let a_val = AESTowerField8b::new(a);
888			let b_val = AESTowerField8b::new(b);
889			let converted_a = BinaryField128bGhash::from(a_val);
890			let converted_b = BinaryField128bGhash::from(b_val);
891			assert_eq!(BinaryField128bGhash::from(a_val * b_val), converted_a * converted_b);
892		}
893	}
894}
binius_field/ghash.rs

binius_field/
ghash.rs
