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	extension::ExtensionField,
28	underlier::WithUnderlier,
29};
30use crate::{
31	AESTowerField8b, Field,
32	arch::packed_ghash_128::PackedBinaryGhash1x128b,
33	arithmetic_traits::Square,
34	binary_field_arithmetic::{
35		invert_or_zero_using_packed, multiple_using_packed, square_using_packed,
36	},
37	field::FieldOps,
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 FieldOps<BinaryField128bGhash> for BinaryField128bGhash {
244	#[inline]
245	fn zero() -> Self {
246		Self::ZERO
247	}
248
249	#[inline]
250	fn one() -> Self {
251		Self::ONE
252	}
253}
254
255impl Field for BinaryField128bGhash {
256	const ZERO: Self = Self(0);
257	const ONE: Self = Self(1);
258	const CHARACTERISTIC: usize = 2;
259	const MULTIPLICATIVE_GENERATOR: Self = Self(0x494ef99794d5244f9152df59d87a9186);
260
261	fn double(&self) -> Self {
262		Self::ZERO
263	}
264}
265
266impl Distribution<BinaryField128bGhash> for StandardUniform {
267	fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BinaryField128bGhash {
268		BinaryField128bGhash(rng.random())
269	}
270}
271
272impl InvertOrZero for BinaryField128bGhash {
273	#[inline]
274	fn invert_or_zero(self) -> Self {
275		invert_or_zero_using_packed::<PackedBinaryGhash1x128b>(self)
276	}
277}
278
279impl From<u128> for BinaryField128bGhash {
280	#[inline]
281	fn from(value: u128) -> Self {
282		Self(value)
283	}
284}
285
286impl From<BinaryField128bGhash> for u128 {
287	#[inline]
288	fn from(value: BinaryField128bGhash) -> Self {
289		value.0
290	}
291}
292
293impl Display for BinaryField128bGhash {
294	fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
295		write!(f, "0x{repr:0>32x}", repr = self.0)
296	}
297}
298
299impl Debug for BinaryField128bGhash {
300	fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
301		write!(f, "BinaryField128bGhash({self})")
302	}
303}
304
305unsafe impl Pod for BinaryField128bGhash {}
306
307impl TryInto<BinaryField1b> for BinaryField128bGhash {
308	type Error = ();
309
310	#[inline]
311	fn try_into(self) -> Result<BinaryField1b, Self::Error> {
312		if self == Self::ZERO {
313			Ok(BinaryField1b::ZERO)
314		} else if self == Self::ONE {
315			Ok(BinaryField1b::ONE)
316		} else {
317			Err(())
318		}
319	}
320}
321
322impl From<BinaryField1b> for BinaryField128bGhash {
323	#[inline]
324	fn from(value: BinaryField1b) -> Self {
325		debug_assert_eq!(Self::ZERO, Self(0));
326
327		Self(Self::ONE.0 & u128::fill_with_bit(value.val().val()))
328	}
329}
330
331impl Add<BinaryField1b> for BinaryField128bGhash {
332	type Output = Self;
333
334	#[inline]
335	fn add(self, rhs: BinaryField1b) -> Self::Output {
336		self + Self::from(rhs)
337	}
338}
339
340impl Sub<BinaryField1b> for BinaryField128bGhash {
341	type Output = Self;
342
343	#[inline]
344	fn sub(self, rhs: BinaryField1b) -> Self::Output {
345		self - Self::from(rhs)
346	}
347}
348
349impl Mul<BinaryField1b> for BinaryField128bGhash {
350	type Output = Self;
351
352	#[inline]
353	#[allow(clippy::suspicious_arithmetic_impl)]
354	fn mul(self, rhs: BinaryField1b) -> Self::Output {
355		crate::tracing::trace_multiplication!(BinaryField128bGhash, BinaryField1b);
356
357		Self(self.0 & u128::fill_with_bit(u8::from(rhs.0)))
358	}
359}
360
361impl AddAssign<BinaryField1b> for BinaryField128bGhash {
362	#[inline]
363	fn add_assign(&mut self, rhs: BinaryField1b) {
364		*self = *self + rhs;
365	}
366}
367
368impl SubAssign<BinaryField1b> for BinaryField128bGhash {
369	#[inline]
370	fn sub_assign(&mut self, rhs: BinaryField1b) {
371		*self = *self - rhs;
372	}
373}
374
375impl MulAssign<BinaryField1b> for BinaryField128bGhash {
376	#[inline]
377	fn mul_assign(&mut self, rhs: BinaryField1b) {
378		*self = *self * rhs;
379	}
380}
381
382impl Add<BinaryField128bGhash> for BinaryField1b {
383	type Output = BinaryField128bGhash;
384
385	#[inline]
386	fn add(self, rhs: BinaryField128bGhash) -> Self::Output {
387		rhs + self
388	}
389}
390
391impl Sub<BinaryField128bGhash> for BinaryField1b {
392	type Output = BinaryField128bGhash;
393
394	#[inline]
395	fn sub(self, rhs: BinaryField128bGhash) -> Self::Output {
396		rhs - self
397	}
398}
399
400impl Mul<BinaryField128bGhash> for BinaryField1b {
401	type Output = BinaryField128bGhash;
402
403	#[inline]
404	fn mul(self, rhs: BinaryField128bGhash) -> Self::Output {
405		rhs * self
406	}
407}
408
409impl ExtensionField<BinaryField1b> for BinaryField128bGhash {
410	const LOG_DEGREE: usize = 7;
411
412	#[inline]
413	fn basis(i: usize) -> Self {
414		assert!(i < 128, "index {i} out of range for degree 128");
415		Self::new(1 << i)
416	}
417
418	#[inline]
419	fn from_bases_sparse(
420		base_elems: impl IntoIterator<Item = BinaryField1b>,
421		log_stride: usize,
422	) -> Self {
423		assert!(log_stride == 7, "log_stride must be 7 for BinaryField128bGhash");
424		let value = base_elems
425			.into_iter()
426			.enumerate()
427			.fold(0, |value, (i, elem)| value | (u128::from(elem.0) << i));
428		Self::new(value)
429	}
430
431	#[inline]
432	fn iter_bases(&self) -> impl Iterator<Item = BinaryField1b> {
433		Divisible::<U1>::value_iter(self.0).map_skippable(BinaryField1b::from)
434	}
435
436	#[inline]
437	fn into_iter_bases(self) -> impl Iterator<Item = BinaryField1b> {
438		Divisible::<U1>::value_iter(self.0).map_skippable(BinaryField1b::from)
439	}
440
441	#[inline]
442	unsafe fn get_base_unchecked(&self, i: usize) -> BinaryField1b {
443		BinaryField1b(U1::num_cast_from(self.0 >> i))
444	}
445
446	#[inline]
447	fn square_transpose(values: &mut [Self]) {
448		square_transforms_extension_field::<BinaryField1b, Self>(values)
449	}
450}
451
452impl SerializeBytes for BinaryField128bGhash {
453	fn serialize(&self, write_buf: impl BufMut) -> Result<(), SerializationError> {
454		self.0.serialize(write_buf)
455	}
456}
457
458impl DeserializeBytes for BinaryField128bGhash {
459	fn deserialize(read_buf: impl Buf) -> Result<Self, SerializationError>
460	where
461		Self: Sized,
462	{
463		Ok(Self(DeserializeBytes::deserialize(read_buf)?))
464	}
465}
466
467impl BinaryField for BinaryField128bGhash {}
468
469impl TowerField for BinaryField128bGhash {
470	fn min_tower_level(self) -> usize {
471		match self {
472			Self::ZERO | Self::ONE => 0,
473			_ => 7,
474		}
475	}
476
477	fn mul_primitive(self, _iota: usize) -> Self {
478		// This method could be implemented by multiplying by isomorphic alpha value
479		// But it's not being used as for now
480		unimplemented!()
481	}
482}
483
484impl From<AESTowerField8b> for BinaryField128bGhash {
485	fn from(value: AESTowerField8b) -> Self {
486		const LOOKUP_TABLE: [BinaryField128bGhash; 256] = [
487			BinaryField128bGhash(0x00000000000000000000000000000000),
488			BinaryField128bGhash(0x00000000000000000000000000000001),
489			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9849),
490			BinaryField128bGhash(0x0dcb364640a222fe6b8330483c2e9848),
491			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ed),
492			BinaryField128bGhash(0x3d5bd35c94646a247573da4a5f7710ec),
493			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a4),
494			BinaryField128bGhash(0x3090e51ad4c648da1ef0ea02635988a5),
495			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ac),
496			BinaryField128bGhash(0x6d58c4e181f9199f41a12db1f974f3ad),
497			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be5),
498			BinaryField128bGhash(0x6093f2a7c15b3b612a221df9c55a6be4),
499			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e341),
500			BinaryField128bGhash(0x500317bd159d73bb34d2f7fba603e340),
501			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b08),
502			BinaryField128bGhash(0x5dc821fb553f51455f51c7b39a2d7b09),
503			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412f),
504			BinaryField128bGhash(0xa72ec17764d7ced55e2f716f4ede412e),
505			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d966),
506			BinaryField128bGhash(0xaae5f7312475ec2b35ac412772f0d967),
507			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c2),
508			BinaryField128bGhash(0x9a75122bf0b3a4f12b5cab2511a951c3),
509			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98b),
510			BinaryField128bGhash(0x97be246db011860f40df9b6d2d87c98a),
511			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab283),
512			BinaryField128bGhash(0xca760596e52ed74a1f8e5cdeb7aab282),
513			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842aca),
514			BinaryField128bGhash(0xc7bd33d0a58cf5b4740d6c968b842acb),
515			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26e),
516			BinaryField128bGhash(0xf72dd6ca714abd6e6afd8694e8dda26f),
517			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a27),
518			BinaryField128bGhash(0xfae6e08c31e89f90017eb6dcd4f33a26),
519			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00118),
520			BinaryField128bGhash(0x4d52354a3a3d8c865cb10fbabcf00119),
521			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9951),
522			BinaryField128bGhash(0x4099030c7a9fae7837323ff280de9950),
523			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f5),
524			BinaryField128bGhash(0x7009e616ae59e6a229c2d5f0e38711f4),
525			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bc),
526			BinaryField128bGhash(0x7dc2d050eefbc45c4241e5b8dfa989bd),
527			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b4),
528			BinaryField128bGhash(0x200af1abbbc495191d10220b4584f2b5),
529			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afd),
530			BinaryField128bGhash(0x2dc1c7edfb66b7e77693124379aa6afc),
531			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e259),
532			BinaryField128bGhash(0x1d5122f72fa0ff3d6863f8411af3e258),
533			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a10),
534			BinaryField128bGhash(0x109a14b16f02ddc303e0c80926dd7a11),
535			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4037),
536			BinaryField128bGhash(0xea7cf43d5eea4253029e7ed5f22e4036),
537			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87e),
538			BinaryField128bGhash(0xe7b7c27b1e4860ad691d4e9dce00d87f),
539			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950da),
540			BinaryField128bGhash(0xd7272761ca8e287777eda49fad5950db),
541			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c893),
542			BinaryField128bGhash(0xdaec11278a2c0a891c6e94d79177c892),
543			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39b),
544			BinaryField128bGhash(0x872430dcdf135bcc433f53640b5ab39a),
545			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd2),
546			BinaryField128bGhash(0x8aef069a9fb1793228bc632c37742bd3),
547			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da376),
548			BinaryField128bGhash(0xba7fe3804b7731e8364c892e542da377),
549			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3f),
550			BinaryField128bGhash(0xb7b4d5c60bd513165dcfb96668033b3e),
551			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4d),
552			BinaryField128bGhash(0x553e92e8bc0ae9a795ed1f57f3632d4c),
553			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db504),
554			BinaryField128bGhash(0x58f5a4aefca8cb59fe6e2f1fcf4db505),
555			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da0),
556			BinaryField128bGhash(0x686541b4286e8383e09ec51dac143da1),
557			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e9),
558			BinaryField128bGhash(0x65ae77f268cca17d8b1df555903aa5e8),
559			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee1),
560			BinaryField128bGhash(0x386656093df3f038d44c32e60a17dee0),
561			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a8),
562			BinaryField128bGhash(0x35ad604f7d51d2c6bfcf02ae363946a9),
563			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0c),
564			BinaryField128bGhash(0x053d8555a9979a1ca13fe8ac5560ce0d),
565			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5645),
566			BinaryField128bGhash(0x08f6b313e935b8e2cabcd8e4694e5644),
567			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c62),
568			BinaryField128bGhash(0xf210539fd8dd2772cbc26e38bdbd6c63),
569			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42b),
570			BinaryField128bGhash(0xffdb65d9987f058ca0415e708193f42a),
571			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8f),
572			BinaryField128bGhash(0xcf4b80c34cb94d56beb1b472e2ca7c8e),
573			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c6),
574			BinaryField128bGhash(0xc280b6850c1b6fa8d532843adee4e4c7),
575			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fce),
576			BinaryField128bGhash(0x9f48977e59243eed8a63438944c99fcf),
577			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70787),
578			BinaryField128bGhash(0x9283a13819861c13e1e073c178e70786),
579			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f23),
580			BinaryField128bGhash(0xa2134422cd4054c9ff1099c31bbe8f22),
581			BinaryField128bGhash(0xafd872648de276379493a98b2790176a),
582			BinaryField128bGhash(0xafd872648de276379493a98b2790176b),
583			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c55),
584			BinaryField128bGhash(0x186ca7a286376521c95c10ed4f932c54),
585			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41c),
586			BinaryField128bGhash(0x15a791e4c69547dfa2df20a573bdb41d),
587			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb8),
588			BinaryField128bGhash(0x253774fe12530f05bc2fcaa710e43cb9),
589			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f1),
590			BinaryField128bGhash(0x28fc42b852f12dfbd7acfaef2ccaa4f0),
591			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff9),
592			BinaryField128bGhash(0x7534634307ce7cbe88fd3d5cb6e7dff8),
593			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b0),
594			BinaryField128bGhash(0x78ff5505476c5e40e37e0d148ac947b1),
595			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf14),
596			BinaryField128bGhash(0x486fb01f93aa169afd8ee716e990cf15),
597			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575d),
598			BinaryField128bGhash(0x45a48659d3083464960dd75ed5be575c),
599			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7a),
600			BinaryField128bGhash(0xbf4266d5e2e0abf497736182014d6d7b),
601			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f533),
602			BinaryField128bGhash(0xb2895093a242890afcf051ca3d63f532),
603			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d97),
604			BinaryField128bGhash(0x8219b5897684c1d0e200bbc85e3a7d96),
605			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5de),
606			BinaryField128bGhash(0x8fd283cf3626e32e89838b806214e5df),
607			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed6),
608			BinaryField128bGhash(0xd21aa2346319b26bd6d24c33f8399ed7),
609			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069f),
610			BinaryField128bGhash(0xdfd1947223bb9095bd517c7bc417069e),
611			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3b),
612			BinaryField128bGhash(0xef417168f77dd84fa3a19679a74e8e3a),
613			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601672),
614			BinaryField128bGhash(0xe28a472eb7dffab1c822a6319b601673),
615			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87e),
616			BinaryField128bGhash(0x93252331bf042b11512625b1f09fa87f),
617			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13037),
618			BinaryField128bGhash(0x9eee1577ffa609ef3aa515f9ccb13036),
619			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b893),
620			BinaryField128bGhash(0xae7ef06d2b6041352455fffbafe8b892),
621			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620da),
622			BinaryField128bGhash(0xa3b5c62b6bc263cb4fd6cfb393c620db),
623			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd2),
624			BinaryField128bGhash(0xfe7de7d03efd328e1087080009eb5bd3),
625			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39b),
626			BinaryField128bGhash(0xf3b6d1967e5f10707b04384835c5c39a),
627			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3f),
628			BinaryField128bGhash(0xc326348caa9958aa65f4d24a569c4b3e),
629			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d376),
630			BinaryField128bGhash(0xceed02caea3b7a540e77e2026ab2d377),
631			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e951),
632			BinaryField128bGhash(0x340be246dbd3e5c40f0954debe41e950),
633			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7118),
634			BinaryField128bGhash(0x39c0d4009b71c73a648a6496826f7119),
635			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bc),
636			BinaryField128bGhash(0x0950311a4fb78fe07a7a8e94e136f9bd),
637			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f5),
638			BinaryField128bGhash(0x049b075c0f15ad1e11f9bedcdd1861f4),
639			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afd),
640			BinaryField128bGhash(0x595326a75a2afc5b4ea8796f47351afc),
641			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b4),
642			BinaryField128bGhash(0x549810e11a88dea5252b49277b1b82b5),
643			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a10),
644			BinaryField128bGhash(0x6408f5fbce4e967f3bdba32518420a11),
645			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9259),
646			BinaryField128bGhash(0x69c3c3bd8eecb4815058936d246c9258),
647			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa966),
648			BinaryField128bGhash(0xde77167b8539a7970d972a0b4c6fa967),
649			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312f),
650			BinaryField128bGhash(0xd3bc203dc59b856966141a437041312e),
651			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98b),
652			BinaryField128bGhash(0xe32cc527115dcdb378e4f0411318b98a),
653			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c2),
654			BinaryField128bGhash(0xeee7f36151ffef4d1367c0092f3621c3),
655			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5aca),
656			BinaryField128bGhash(0xb32fd29a04c0be084c3607bab51b5acb),
657			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c283),
658			BinaryField128bGhash(0xbee4e4dc44629cf627b537f28935c282),
659			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a27),
660			BinaryField128bGhash(0x8e7401c690a4d42c3945ddf0ea6c4a26),
661			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26e),
662			BinaryField128bGhash(0x83bf3780d006f6d252c6edb8d642d26f),
663			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e849),
664			BinaryField128bGhash(0x7959d70ce1ee694253b85b6402b1e848),
665			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7000),
666			BinaryField128bGhash(0x7492e14aa14c4bbc383b6b2c3e9f7001),
667			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a4),
668			BinaryField128bGhash(0x44020450758a036626cb812e5dc6f8a5),
669			BinaryField128bGhash(0x49c93216352821984d48b16661e860ed),
670			BinaryField128bGhash(0x49c93216352821984d48b16661e860ec),
671			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be5),
672			BinaryField128bGhash(0x140113ed601770dd121976d5fbc51be4),
673			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ac),
674			BinaryField128bGhash(0x19ca25ab20b55223799a469dc7eb83ad),
675			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b08),
676			BinaryField128bGhash(0x295ac0b1f4731af9676aac9fa4b20b09),
677			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9341),
678			BinaryField128bGhash(0x2491f6f7b4d138070ce99cd7989c9340),
679			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8533),
680			BinaryField128bGhash(0xc61bb1d9030ec2b6c4cb3ae603fc8532),
681			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7a),
682			BinaryField128bGhash(0xcbd0879f43ace048af480aae3fd21d7b),
683			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95de),
684			BinaryField128bGhash(0xfb406285976aa892b1b8e0ac5c8b95df),
685			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d97),
686			BinaryField128bGhash(0xf68b54c3d7c88a6cda3bd0e460a50d96),
687			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769f),
688			BinaryField128bGhash(0xab43753882f7db29856a1757fa88769e),
689			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed6),
690			BinaryField128bGhash(0xa688437ec255f9d7eee9271fc6a6eed7),
691			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6672),
692			BinaryField128bGhash(0x9618a6641693b10df019cd1da5ff6673),
693			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3b),
694			BinaryField128bGhash(0x9bd39022563193f39b9afd5599d1fe3a),
695			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41c),
696			BinaryField128bGhash(0x613570ae67d90c639ae44b894d22c41d),
697			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c55),
698			BinaryField128bGhash(0x6cfe46e8277b2e9df1677bc1710c5c54),
699			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f1),
700			BinaryField128bGhash(0x5c6ea3f2f3bd6647ef9791c31255d4f0),
701			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb8),
702			BinaryField128bGhash(0x51a595b4b31f44b98414a18b2e7b4cb9),
703			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b0),
704			BinaryField128bGhash(0x0c6db44fe62015fcdb456638b45637b1),
705			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff9),
706			BinaryField128bGhash(0x01a68209a6823702b0c656708878aff8),
707			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275d),
708			BinaryField128bGhash(0x3136671372447fd8ae36bc72eb21275c),
709			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf14),
710			BinaryField128bGhash(0x3cfd515532e65d26c5b58c3ad70fbf15),
711			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842b),
712			BinaryField128bGhash(0x8b49849339334e30987a355cbf0c842a),
713			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c62),
714			BinaryField128bGhash(0x8682b2d579916ccef3f9051483221c63),
715			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c6),
716			BinaryField128bGhash(0xb61257cfad572414ed09ef16e07b94c7),
717			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8f),
718			BinaryField128bGhash(0xbbd96189edf506ea868adf5edc550c8e),
719			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787787),
720			BinaryField128bGhash(0xe6114072b8ca57afd9db18ed46787786),
721			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efce),
722			BinaryField128bGhash(0xebda7634f8687551b25828a57a56efcf),
723			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676a),
724			BinaryField128bGhash(0xdb4a932e2cae3d8baca8c2a7190f676b),
725			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff23),
726			BinaryField128bGhash(0xd681a5686c0c1f75c72bf2ef2521ff22),
727			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c504),
728			BinaryField128bGhash(0x2c6745e45de480e5c6554433f1d2c505),
729			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4d),
730			BinaryField128bGhash(0x21ac73a21d46a21badd6747bcdfc5d4c),
731			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e9),
732			BinaryField128bGhash(0x113c96b8c980eac1b3269e79aea5d5e8),
733			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da0),
734			BinaryField128bGhash(0x1cf7a0fe8922c83fd8a5ae31928b4da1),
735			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a8),
736			BinaryField128bGhash(0x413f8105dc1d997a87f4698208a636a9),
737			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee1),
738			BinaryField128bGhash(0x4cf4b7439cbfbb84ec7759ca3488aee0),
739			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12645),
740			BinaryField128bGhash(0x7c6452594879f35ef287b3c857d12644),
741			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0c),
742			BinaryField128bGhash(0x71af641f08dbd1a0990483806bffbe0d),
743		];
744
745		LOOKUP_TABLE[value.0 as usize]
746	}
747}
748
749#[inline(always)]
750pub fn is_ghash_tower<F: TowerField>() -> bool {
751	TypeId::of::<F>() == TypeId::of::<BinaryField128bGhash>()
752		|| TypeId::of::<F>() == TypeId::of::<BinaryField1b>()
753}
754
755#[cfg(test)]
756mod tests {
757	use proptest::{prelude::any, proptest};
758
759	use super::*;
760	use crate::binary_field::tests::is_binary_field_valid_generator;
761
762	#[test]
763	fn test_ghash_mul() {
764		let a = BinaryField128bGhash(1u128);
765		let b = BinaryField128bGhash(1u128);
766		let c = a * b;
767
768		assert_eq!(c, BinaryField128bGhash::from(1u128));
769
770		let a = BinaryField128bGhash(1u128);
771		let b = BinaryField128bGhash(2u128);
772		let c = a * b;
773
774		assert_eq!(c, BinaryField128bGhash::from(2u128));
775
776		let a = BinaryField128bGhash(1u128);
777		let b = BinaryField128bGhash(1297182698762987u128);
778		let c = a * b;
779
780		assert_eq!(c, BinaryField128bGhash::from(1297182698762987u128));
781
782		let a = BinaryField128bGhash(2u128);
783		let b = BinaryField128bGhash(2u128);
784		let c = a * b;
785
786		assert_eq!(c, BinaryField128bGhash::from(4u128));
787
788		let a = BinaryField128bGhash(2u128);
789		let b = BinaryField128bGhash(3u128);
790		let c = a * b;
791
792		assert_eq!(c, BinaryField128bGhash::from(6u128));
793
794		let a = BinaryField128bGhash(3u128);
795		let b = BinaryField128bGhash(3u128);
796		let c = a * b;
797
798		assert_eq!(c, BinaryField128bGhash::from(5u128));
799
800		let a = BinaryField128bGhash(1u128 << 127);
801		let b = BinaryField128bGhash(2u128);
802		let c = a * b;
803
804		assert_eq!(c, BinaryField128bGhash::from(0b10000111));
805
806		let a = BinaryField128bGhash((1u128 << 127) + 1);
807		let b = BinaryField128bGhash(2u128);
808		let c = a * b;
809
810		assert_eq!(c, BinaryField128bGhash::from(0b10000101));
811
812		let a = BinaryField128bGhash(3u128 << 126);
813		let b = BinaryField128bGhash(2u128);
814		let c = a * b;
815
816		assert_eq!(c, BinaryField128bGhash::from(0b10000111 + (1u128 << 127)));
817
818		let a = BinaryField128bGhash(1u128 << 127);
819		let b = BinaryField128bGhash(4u128);
820		let c = a * b;
821
822		assert_eq!(c, BinaryField128bGhash::from(0b10000111 << 1));
823
824		let a = BinaryField128bGhash(1u128 << 127);
825		let b = BinaryField128bGhash(1u128 << 122);
826		let c = a * b;
827
828		assert_eq!(c, BinaryField128bGhash::from((0b00000111 << 121) + 0b10000111));
829	}
830
831	#[test]
832	fn test_multiplicative_generator() {
833		assert!(is_binary_field_valid_generator::<BinaryField128bGhash>());
834	}
835
836	#[test]
837	fn test_mul_x() {
838		let test_cases = [
839			0x0,                                    // Zero
840			0x1,                                    // One
841			0x2,                                    // Two
842			0x80000000000000000000000000000000u128, // High bit set
843			0x40000000000000000000000000000000u128, // Second highest bit
844			0xffffffffffffffffffffffffffffffffu128, // All bits set
845			0x87u128,                               // GHASH reduction polynomial
846			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
847		];
848
849		for &value in &test_cases {
850			let field_val = BinaryField128bGhash::new(value);
851			let mul_x_result = field_val.mul_x();
852			let regular_mul_result = field_val * BinaryField128bGhash::new(2u128);
853
854			assert_eq!(
855				mul_x_result, regular_mul_result,
856				"mul_x and regular multiplication by 2 differ for value {:#x}",
857				value
858			);
859		}
860	}
861
862	#[test]
863	fn test_mul_inv_x() {
864		let test_cases = [
865			0x0,                                    // Zero
866			0x1,                                    // One
867			0x2,                                    // Two
868			0x1u128,                                // Low bit set
869			0x3u128,                                // Two lowest bits set
870			0xffffffffffffffffffffffffffffffffu128, // All bits set
871			0x87u128,                               // GHASH reduction polynomial
872			0x21ac73a21d46a21badd6747bcdfc5d4d,     // Random value
873		];
874
875		for &value in &test_cases {
876			let field_val = BinaryField128bGhash::new(value);
877			let mul_inv_x_result = field_val.mul_inv_x();
878			let regular_mul_result = field_val
879				* BinaryField128bGhash::new(2u128)
880					.invert()
881					.expect("2 is invertible");
882
883			assert_eq!(
884				mul_inv_x_result, regular_mul_result,
885				"mul_inv_x and regular multiplication by 2 differ for value {:#x}",
886				value
887			);
888		}
889	}
890
891	proptest! {
892		#[test]
893		fn test_conversion_from_aes_consistency(a in any::<u8>(), b in any::<u8>()) {
894			let a_val = AESTowerField8b::new(a);
895			let b_val = AESTowerField8b::new(b);
896			let converted_a = BinaryField128bGhash::from(a_val);
897			let converted_b = BinaryField128bGhash::from(b_val);
898			assert_eq!(BinaryField128bGhash::from(a_val * b_val), converted_a * converted_b);
899		}
900	}
901}
binius_field/ghash.rs

binius_field/
ghash.rs
