tc_modular 0.1.0

Modular arithmetic and Montgomery forms for cryptography over the integers of tc_bigint, constant time over the fixed-width and padded ones.
Documentation
//! Modular subtraction of [`PaddedBigUint`].

use num_traits::WrappingAdd;
use num_traits::ops::overflowing::OverflowingSub;
use tc_bigint::PaddedBigUint;
use tc_constant_time::{Choice, ConditionallySelectable};

use crate::{ModSub, NonZero};
use tc_zeroize::Zeroizing;

/// `(self - rhs) mod modulus`, never negative, at the widest of the three
/// widths: the narrower values are extended to it with zeros, and the
/// result takes it. Both operands are reduced first; when the difference of
/// the two residues borrows, it has wrapped around that width, and adding
/// the modulus wraps it back into range. Constant time: the widths are
/// public.
impl ModSub for PaddedBigUint {
    type Output = Self;

    fn mod_sub(&self, rhs: &Self, modulus: &NonZero<Self>) -> Self {
        let modulus: &Self = modulus;
        // The residues and both candidates are wiped once one is chosen.
        let residues = (
            Zeroizing::new(self % modulus),
            Zeroizing::new(rhs % modulus),
        );
        let (difference, borrowed) = residues.0.overflowing_sub(&residues.1);
        let difference = Zeroizing::new(difference);
        let raised = Zeroizing::new(difference.wrapping_add(modulus));
        Self::conditional_select(&difference, &raised, Choice::from_lsb(u8::from(borrowed)))
    }
}

#[cfg(test)]
mod tests {
    use tc_bigint::{PaddedBigUint, Word};

    use crate::{ModSub, NonZero};

    const VALUES: [u128; 8] = [
        0,
        1,
        255,
        u64::MAX as u128,
        u64::MAX as u128 + 1,
        i128::MAX as u128,
        u128::MAX - 1,
        u128::MAX,
    ];

    /// `(a - b) mod m`, never negative.
    fn expected(a: u128, b: u128, m: u128) -> u128 {
        let (a, b) = (a % m, b % m);
        if a >= b { a - b } else { m - (b - a) }
    }

    #[test]
    fn the_difference_is_the_primitive_difference_reduced_by_the_modulus() {
        for m in &VALUES[1..] {
            let modulus = NonZero::new(PaddedBigUint::from(*m)).unwrap();
            for a in VALUES {
                for b in VALUES {
                    let (x, y) = (PaddedBigUint::from(a), PaddedBigUint::from(b));
                    let expected = PaddedBigUint::from(expected(a, b, *m));
                    assert_eq!(x.mod_sub(&y, &modulus), expected, "{a} {b} {m}");
                }
            }
        }
    }

    #[test]
    fn a_difference_below_zero_is_raised_by_the_modulus() {
        let modulus = NonZero::new(PaddedBigUint::from(u128::MAX)).unwrap();
        let (x, y) = (PaddedBigUint::from(1u8), PaddedBigUint::from(2u8));
        assert_eq!(x.mod_sub(&y, &modulus), PaddedBigUint::from(u128::MAX - 1));
    }

    #[test]
    fn the_result_takes_the_widest_of_the_three_widths() {
        let wide = (u128::BITS / Word::BITS) as usize;
        let narrow = |value: u8| PaddedBigUint::from(value);
        let broad = |value: u8| PaddedBigUint::from(u128::from(value));
        for (a, b, m) in [
            (broad(5), narrow(7), narrow(9)),
            (narrow(5), broad(7), narrow(9)),
            (narrow(5), narrow(7), broad(9)),
        ] {
            let difference = a.mod_sub(&b, &NonZero::new(m).unwrap());
            assert_eq!(
                (difference.as_limbs().len(), difference),
                (wide, PaddedBigUint::from(7u8))
            );
        }
    }
}