polyval/field_element/
mul64.rs

1//! Constant-time software implementation of POLYVAL for 64-bit architectures.
2//! Adapted from BearSSL's `ghash_ctmul64.c`:
3//!
4//! <https://bearssl.org/gitweb/?p=BearSSL;a=blob;f=src/hash/ghash_ctmul64.c;hb=4b6046412>
5//!
6//! Copyright (c) 2016 Thomas Pornin <[email protected]>
7
8use crate::field_element::FieldElement;
9use core::{array, ops::BitXor};
10
11impl FieldElement {
12    /// Compute the unreduced 256-bit carryless product of two 128-bit field elements.
13    ///
14    /// Uses a Karatsuba decomposition in which the 128x128 multiplication is reduced to three 64x64
15    /// multiplications together with a bit-reversal trick to efficiently recover the high half.
16    #[inline]
17    pub(crate) fn karatsuba_mul(self, rhs: Self) -> Product {
18        // Karatsuba input decomposition for H
19        let (h0, h1) = self.to_u64x2();
20        let h0r = h0.reverse_bits();
21        let h1r = h1.reverse_bits();
22        let h2 = h0 ^ h1;
23        let h2r = h0r ^ h1r;
24
25        // Karatsuba input decomposition for Y
26        let (y0, y1) = rhs.to_u64x2();
27        let y0r = y0.reverse_bits();
28        let y1r = y1.reverse_bits();
29        let y2 = y0 ^ y1;
30        let y2r = y0r ^ y1r;
31
32        /// Carryless multiplication in GF(2)[X], truncated to the low 64-bits.
33        #[inline]
34        fn bmul64(x: u64, y: u64) -> u64 {
35            super::bmul(x, y, 0x1111_1111_1111_1111)
36        }
37
38        // Perform carryless multiplications
39        let z0 = bmul64(y0, h0);
40        let z1 = bmul64(y1, h1);
41        let mut z2 = bmul64(y2, h2);
42        let mut z0h = bmul64(y0r, h0r);
43        let mut z1h = bmul64(y1r, h1r);
44        let mut z2h = bmul64(y2r, h2r);
45
46        // Karatsuba recombination
47        z2 ^= z0 ^ z1;
48        z2h ^= z0h ^ z1h;
49        z0h = z0h.reverse_bits() >> 1;
50        z1h = z1h.reverse_bits() >> 1;
51        z2h = z2h.reverse_bits() >> 1;
52
53        // Assemble the final 256-bit product as `u64` x 4.
54        let v0 = z0;
55        let v1 = z0h ^ z2;
56        let v2 = z1 ^ z2h;
57        let v3 = z1h;
58        Product([v0, v1, v2, v3])
59    }
60
61    /// Splits into `(lo, hi)`.
62    #[inline]
63    fn to_u64x2(self) -> (u64, u64) {
64        let x = u128::from(self);
65        ((x & 0xFFFF_FFFF_FFFF_FFFF) as u64, (x >> 64) as u64)
66    }
67}
68
69/// Unreduced 256-bit carryless product.
70pub(crate) struct Product([u64; 4]);
71
72impl Product {
73    /// Reduce the 256-bit carryless product of Karatsuba modulo the POLYVAL polynomial.
74    ///
75    /// This performs constant-time folding using shifts and XORs corresponding to the irreducible
76    /// polynomial `x^128 + x^127 + x^126 + x^121 + 1`.
77    ///
78    /// This is closely related to GHASH reduction but the bit order is reversed in POLYVAL.
79    #[inline]
80    pub(crate) fn mont_reduce(self) -> FieldElement {
81        let (v0, mut v1, mut v2, mut v3) = (self.0[0], self.0[1], self.0[2], self.0[3]);
82        v2 ^= v0 ^ (v0 >> 1) ^ (v0 >> 2) ^ (v0 >> 7);
83        v1 ^= (v0 << 63) ^ (v0 << 62) ^ (v0 << 57);
84        v3 ^= v1 ^ (v1 >> 1) ^ (v1 >> 2) ^ (v1 >> 7);
85        v2 ^= (v1 << 63) ^ (v1 << 62) ^ (v1 << 57);
86        (u128::from(v2) | u128::from(v3) << 64).into()
87    }
88}
89
90impl BitXor for Product {
91    type Output = Self;
92
93    #[inline]
94    fn bitxor(self, rhs: Self) -> Self::Output {
95        Self(array::from_fn(|n| self.0[n] ^ rhs.0[n]))
96    }
97}
polyval/field_element/mul64.rs

polyval/field_element/
mul64.rs
