polyval/
field_element.rs

1//! POLYVAL field element implementation.
2//!
3//! This module contains a portable pure Rust implementation which can computes carryless POLYVAL
4//! multiplication over GF (2^128) in constant time. Both 32-bit and 64-bit backends are available.
5//!
6//! Method described at: <https://www.bearssl.org/constanttime.html#ghash-for-gcm>
7//!
8//! POLYVAL multiplication is effectively the little endian equivalent of GHASH multiplication,
9//! aside from one small detail described here:
10//!
11//! <https://crypto.stackexchange.com/questions/66448/how-does-bearssls-gcm-modular-reduction-work/66462#66462>
12//!
13//! > The product of two bit-reversed 128-bit polynomials yields the
14//! > bit-reversed result over 255 bits, not 256. The BearSSL code ends up
15//! > with a 256-bit result in zw[], and that value is shifted by one bit,
16//! > because of that reversed convention issue. Thus, the code must
17//! > include a shifting step to put it back where it should
18//!
19//! This shift is unnecessary for POLYVAL (it is in fact what distinguishes POLYVAL from GHASH) and
20//! has been removed.
21
22cpubits::cpubits! {
23    16 | 32 => {
24        #[path = "field_element/mul32.rs"]
25        mod mul;
26    }
27    64 => {
28        #[path = "field_element/mul64.rs"]
29        mod mul;
30    }
31}
32
33mod mulx;
34
35use crate::{BLOCK_SIZE, Block};
36use core::{
37    fmt::{self, Debug},
38    num::Wrapping,
39    ops::{Add, BitAnd, BitOr, BitXor, Mul, MulAssign, Shl},
40};
41
42#[cfg(feature = "zeroize")]
43use zeroize::Zeroize;
44
45/// An element in POLYVAL's field.
46///
47/// This type represents an element of the binary field GF(2^128) modulo the irreducible polynomial
48/// `x^128 + x^127 + x^126 + x^121 + 1` as described in [RFC8452 §3].
49///
50/// Arithmetic in POLYVAL's field has the following properties:
51/// - All arithmetic operations are performed modulo the polynomial above.
52/// - Addition is equivalent to the XOR operation applied to the two field elements
53/// - Multiplication is carryless
54///
55/// [RFC8452 §3]: https://tools.ietf.org/html/rfc8452#section-3
56#[derive(Clone, Copy, Default)]
57#[cfg_attr(test, derive(Eq, PartialEq))]
58#[repr(align(16))] // Alignment-friendly for SIMD registers
59pub struct FieldElement([u8; BLOCK_SIZE]);
60
61impl FieldElement {
62    /// Reverse this field element at a byte-level of granularity.
63    ///
64    /// This is useful when implementing GHASH in terms of POLYVAL.
65    #[inline]
66    #[must_use]
67    pub fn reverse(mut self) -> Self {
68        self.0.reverse();
69        self
70    }
71}
72
73impl Debug for FieldElement {
74    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75        write!(f, "FieldElement(")?;
76        for byte in self.0 {
77            write!(f, "{:02x}", byte)?;
78        }
79        write!(f, ")")
80    }
81}
82
83impl From<Block> for FieldElement {
84    #[inline]
85    fn from(block: Block) -> Self {
86        Self(block.into())
87    }
88}
89
90impl From<&Block> for FieldElement {
91    #[inline]
92    fn from(block: &Block) -> Self {
93        Self::from(*block)
94    }
95}
96
97impl From<FieldElement> for Block {
98    #[inline]
99    fn from(fe: FieldElement) -> Self {
100        fe.0.into()
101    }
102}
103
104impl From<&FieldElement> for Block {
105    #[inline]
106    fn from(fe: &FieldElement) -> Self {
107        Self::from(*fe)
108    }
109}
110
111impl From<[u8; BLOCK_SIZE]> for FieldElement {
112    #[inline]
113    fn from(bytes: [u8; BLOCK_SIZE]) -> Self {
114        Self(bytes)
115    }
116}
117
118impl From<FieldElement> for [u8; BLOCK_SIZE] {
119    #[inline]
120    fn from(fe: FieldElement) -> [u8; BLOCK_SIZE] {
121        fe.0
122    }
123}
124
125impl From<u128> for FieldElement {
126    #[inline]
127    fn from(x: u128) -> Self {
128        Self(x.to_le_bytes())
129    }
130}
131
132impl From<FieldElement> for u128 {
133    #[inline]
134    fn from(fe: FieldElement) -> Self {
135        u128::from_le_bytes(fe.0)
136    }
137}
138
139impl Add for FieldElement {
140    type Output = Self;
141
142    /// Adds two POLYVAL field elements.
143    ///
144    /// In POLYVAL's field, addition is the equivalent operation to XOR.
145    #[inline]
146    fn add(self, rhs: Self) -> Self::Output {
147        (u128::from(self) ^ u128::from(rhs)).into()
148    }
149}
150
151impl Mul for FieldElement {
152    type Output = Self;
153
154    /// Perform carryless multiplication within POLYVAL's field modulo its polynomial.
155    #[inline]
156    fn mul(self, rhs: Self) -> Self {
157        self.karatsuba_mul(rhs).mont_reduce()
158    }
159}
160
161impl MulAssign for FieldElement {
162    #[inline]
163    fn mul_assign(&mut self, rhs: Self) {
164        *self = *self * rhs;
165    }
166}
167
168#[cfg(feature = "zeroize")]
169impl Zeroize for FieldElement {
170    fn zeroize(&mut self) {
171        self.0.zeroize();
172    }
173}
174
175/// Multiplication in GF(2)[X], implemented generically for use with `u32` and `u64`.
176///
177/// Uses "holes" (sequences of zeroes) to avoid carry spilling, as specified in the mask operand
178/// `m0` which should have a full-width value with the following bit pattern:
179///
180/// `0b100010001...0001` (e.g. `0x1111_1111u32`)
181///
182/// When carries do occur, they wind up in a "hole" and are subsequently masked out of the result.
183#[inline]
184fn bmul<T>(x: T, y: T, m0: T) -> T
185where
186    T: BitAnd<Output = T> + BitOr<Output = T> + Copy + Shl<u32, Output = T>,
187    Wrapping<T>: BitXor<Output = Wrapping<T>> + Mul<Output = Wrapping<T>>,
188{
189    let m1 = m0 << 1;
190    let m2 = m1 << 1;
191    let m3 = m2 << 1;
192
193    let x0 = Wrapping(x & m0);
194    let x1 = Wrapping(x & m1);
195    let x2 = Wrapping(x & m2);
196    let x3 = Wrapping(x & m3);
197
198    let y0 = Wrapping(y & m0);
199    let y1 = Wrapping(y & m1);
200    let y2 = Wrapping(y & m2);
201    let y3 = Wrapping(y & m3);
202
203    let z0 = (x0 * y0) ^ (x1 * y3) ^ (x2 * y2) ^ (x3 * y1);
204    let z1 = (x0 * y1) ^ (x1 * y0) ^ (x2 * y3) ^ (x3 * y2);
205    let z2 = (x0 * y2) ^ (x1 * y1) ^ (x2 * y0) ^ (x3 * y3);
206    let z3 = (x0 * y3) ^ (x1 * y2) ^ (x2 * y1) ^ (x3 * y0);
207
208    (z0.0 & m0) | (z1.0 & m1) | (z2.0 & m2) | (z3.0 & m3)
209}
210
211#[cfg(test)]
212mod tests {
213    use super::*;
214    use hex_literal::hex;
215
216    const A: [u8; 16] = hex!("66e94bd4ef8a2c3b884cfa59ca342b2e");
217    const B: [u8; 16] = hex!("ff000000000000000000000000000000");
218
219    #[test]
220    fn fe_add() {
221        let a = FieldElement::from(A);
222        let b = FieldElement::from(B);
223
224        let expected = FieldElement::from(hex!("99e94bd4ef8a2c3b884cfa59ca342b2e"));
225        assert_eq!(a + b, expected);
226        assert_eq!(b + a, expected);
227    }
228
229    #[test]
230    fn fe_mul() {
231        let a = FieldElement::from(A);
232        let b = FieldElement::from(B);
233
234        let expected = FieldElement::from(hex!("ebe563401e7e91ea3ad6426b8140c394"));
235        assert_eq!(a * b, expected);
236        assert_eq!(b * a, expected);
237    }
238}
polyval/field_element.rs

polyval/
field_element.rs
