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/// An element in POLYVAL's field.
43///
44/// This type represents an element of the binary field GF(2^128) modulo the irreducible polynomial
45/// `x^128 + x^127 + x^126 + x^121 + 1` as described in [RFC8452 §3].
46///
47/// Arithmetic in POLYVAL's field has the following properties:
48/// - All arithmetic operations are performed modulo the polynomial above.
49/// - Addition is equivalent to the XOR operation applied to the two field elements
50/// - Multiplication is carryless
51///
52/// [RFC8452 §3]: https://tools.ietf.org/html/rfc8452#section-3
53#[derive(Clone, Copy, Default)]
54#[cfg_attr(test, derive(Eq, PartialEq))]
55#[repr(align(16))] // Alignment-friendly for SIMD registers
56pub struct FieldElement([u8; BLOCK_SIZE]);
57
58impl FieldElement {
59    /// Reverse this field element at a byte-level of granularity.
60    ///
61    /// This is useful when implementing GHASH in terms of POLYVAL.
62    #[inline]
63    #[must_use]
64    pub fn reverse(mut self) -> Self {
65        self.0.reverse();
66        self
67    }
68}
69
70impl Debug for FieldElement {
71    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
72        write!(f, "FieldElement(")?;
73        for byte in self.0 {
74            write!(f, "{:02x}", byte)?;
75        }
76        write!(f, ")")
77    }
78}
79
80impl From<Block> for FieldElement {
81    #[inline]
82    fn from(block: Block) -> Self {
83        Self(block.into())
84    }
85}
86
87impl From<&Block> for FieldElement {
88    #[inline]
89    fn from(block: &Block) -> Self {
90        Self::from(*block)
91    }
92}
93
94impl From<FieldElement> for Block {
95    #[inline]
96    fn from(fe: FieldElement) -> Self {
97        fe.0.into()
98    }
99}
100
101impl From<&FieldElement> for Block {
102    #[inline]
103    fn from(fe: &FieldElement) -> Self {
104        Self::from(*fe)
105    }
106}
107
108impl From<[u8; BLOCK_SIZE]> for FieldElement {
109    #[inline]
110    fn from(bytes: [u8; BLOCK_SIZE]) -> Self {
111        Self(bytes)
112    }
113}
114
115impl From<FieldElement> for [u8; BLOCK_SIZE] {
116    #[inline]
117    fn from(fe: FieldElement) -> [u8; BLOCK_SIZE] {
118        fe.0
119    }
120}
121
122impl From<u128> for FieldElement {
123    #[inline]
124    fn from(x: u128) -> Self {
125        Self(x.to_le_bytes())
126    }
127}
128
129impl From<FieldElement> for u128 {
130    #[inline]
131    fn from(fe: FieldElement) -> Self {
132        u128::from_le_bytes(fe.0)
133    }
134}
135
136impl Add for FieldElement {
137    type Output = Self;
138
139    /// Adds two POLYVAL field elements.
140    ///
141    /// In POLYVAL's field, addition is the equivalent operation to XOR.
142    #[inline]
143    fn add(self, rhs: Self) -> Self::Output {
144        (u128::from(self) ^ u128::from(rhs)).into()
145    }
146}
147
148impl Mul for FieldElement {
149    type Output = Self;
150
151    /// Perform carryless multiplication within POLYVAL's field modulo its polynomial.
152    #[inline]
153    fn mul(self, rhs: Self) -> Self {
154        self.karatsuba_mul(rhs).mont_reduce()
155    }
156}
157
158impl MulAssign for FieldElement {
159    #[inline]
160    fn mul_assign(&mut self, rhs: Self) {
161        *self = *self * rhs;
162    }
163}
164
165/// Multiplication in GF(2)[X], implemented generically for use with `u32` and `u64`.
166///
167/// Uses "holes" (sequences of zeroes) to avoid carry spilling, as specified in the mask operand
168/// `m0` which should have a full-width value with the following bit pattern:
169///
170/// `0b100010001...0001` (e.g. `0x1111_1111u32`)
171///
172/// When carries do occur, they wind up in a "hole" and are subsequently masked out of the result.
173#[inline]
174fn bmul<T>(x: T, y: T, m0: T) -> T
175where
176    T: BitAnd<Output = T> + BitOr<Output = T> + Copy + Shl<u32, Output = T>,
177    Wrapping<T>: BitXor<Output = Wrapping<T>> + Mul<Output = Wrapping<T>>,
178{
179    let m1 = m0 << 1;
180    let m2 = m1 << 1;
181    let m3 = m2 << 1;
182
183    let x0 = Wrapping(x & m0);
184    let x1 = Wrapping(x & m1);
185    let x2 = Wrapping(x & m2);
186    let x3 = Wrapping(x & m3);
187
188    let y0 = Wrapping(y & m0);
189    let y1 = Wrapping(y & m1);
190    let y2 = Wrapping(y & m2);
191    let y3 = Wrapping(y & m3);
192
193    let z0 = (x0 * y0) ^ (x1 * y3) ^ (x2 * y2) ^ (x3 * y1);
194    let z1 = (x0 * y1) ^ (x1 * y0) ^ (x2 * y3) ^ (x3 * y2);
195    let z2 = (x0 * y2) ^ (x1 * y1) ^ (x2 * y0) ^ (x3 * y3);
196    let z3 = (x0 * y3) ^ (x1 * y2) ^ (x2 * y1) ^ (x3 * y0);
197
198    (z0.0 & m0) | (z1.0 & m1) | (z2.0 & m2) | (z3.0 & m3)
199}
200
201#[cfg(test)]
202mod tests {
203    use super::*;
204    use hex_literal::hex;
205
206    const A: [u8; 16] = hex!("66e94bd4ef8a2c3b884cfa59ca342b2e");
207    const B: [u8; 16] = hex!("ff000000000000000000000000000000");
208
209    #[test]
210    fn fe_add() {
211        let a = FieldElement::from(A);
212        let b = FieldElement::from(B);
213
214        let expected = FieldElement::from(hex!("99e94bd4ef8a2c3b884cfa59ca342b2e"));
215        assert_eq!(a + b, expected);
216        assert_eq!(b + a, expected);
217    }
218
219    #[test]
220    fn fe_mul() {
221        let a = FieldElement::from(A);
222        let b = FieldElement::from(B);
223
224        let expected = FieldElement::from(hex!("ebe563401e7e91ea3ad6426b8140c394"));
225        assert_eq!(a * b, expected);
226        assert_eq!(b * a, expected);
227    }
228}
polyval/field_element.rs

polyval/
field_element.rs
