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

binius_field/
ghash.rs
