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

binius_field/
ghash.rs
