Merging upstream version 1.72.1+dfsg1.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

11 files changed, 138 insertions, 68 deletions

diff --git a/vendor/crypto-bigint/src/ct_choice.rs b/vendor/crypto-bigint/src/ct_choice.rs
index 1308dd328..56bb79d82 100644
--- a/vendor/crypto-bigint/src/ct_choice.rs
+++ b/vendor/crypto-bigint/src/ct_choice.rs
@@ -9,10 +9,10 @@ use crate::Word;
 pub struct CtChoice(Word);
 
 impl CtChoice {
-    /// The falsy vaue.
+    /// The falsy value.
     pub const FALSE: Self = Self(0);
 
-    /// The truthy vaue.
+    /// The truthy value.
     pub const TRUE: Self = Self(Word::MAX);
 
     /// Returns the truthy value if `value == Word::MAX`, and the falsy value if `value == 0`.
@@ -25,7 +25,7 @@ impl CtChoice {
     /// Returns the truthy value if `value == 1`, and the falsy value if `value == 0`.
     /// Panics for other values.
     pub(crate) const fn from_lsb(value: Word) -> Self {
-        debug_assert!(value == Self::FALSE.0 || value == 1);
+        debug_assert!(value == 0 || value == 1);
         Self(value.wrapping_neg())
     }
 
@@ -37,10 +37,6 @@ impl CtChoice {
         Self(self.0 & other.0)
     }
 
-    pub(crate) const fn or(&self, other: Self) -> Self {
-        Self(self.0 | other.0)
-    }
-
     /// Return `b` if `self` is truthy, otherwise return `a`.
     pub(crate) const fn select(&self, a: Word, b: Word) -> Word {
         a ^ (self.0 & (a ^ b))
diff --git a/vendor/crypto-bigint/src/traits.rs b/vendor/crypto-bigint/src/traits.rs
index 3ace16c4a..da9b9b646 100644
--- a/vendor/crypto-bigint/src/traits.rs
+++ b/vendor/crypto-bigint/src/traits.rs
@@ -177,7 +177,7 @@ pub trait CheckedMul<Rhs = Self>: Sized {
     fn checked_mul(&self, rhs: Rhs) -> CtOption<Self>;
 }
 
-/// Checked substraction.
+/// Checked subtraction.
 pub trait CheckedSub<Rhs = Self>: Sized {
     /// Output type.
     type Output;
diff --git a/vendor/crypto-bigint/src/uint/add_mod.rs b/vendor/crypto-bigint/src/uint/add_mod.rs
index bfdda6ff5..70674f5e8 100644
--- a/vendor/crypto-bigint/src/uint/add_mod.rs
+++ b/vendor/crypto-bigint/src/uint/add_mod.rs
@@ -16,19 +16,9 @@ impl<const LIMBS: usize> Uint<LIMBS> {
         // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
         // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the
         // modulus.
-        let mut i = 0;
-        let mut res = Self::ZERO;
-        let mut carry = Limb::ZERO;
-
-        while i < LIMBS {
-            let rhs = p.limbs[i].bitand(borrow);
-            let (limb, c) = w.limbs[i].adc(rhs, carry);
-            res.limbs[i] = limb;
-            carry = c;
-            i += 1;
-        }
-
-        res
+        let mask = Uint::from_words([borrow.0; LIMBS]);
+
+        w.wrapping_add(&p.bitand(&mask))
     }
 
     /// Computes `self + rhs mod p` in constant time for the special modulus
@@ -43,8 +33,7 @@ impl<const LIMBS: usize> Uint<LIMBS> {
         // for the overflow. Otherwise, we need to subtract `c` again, which
         // in that case cannot underflow.
         let l = carry.0.wrapping_sub(1) & c.0;
-        let (out, _) = out.sbb(&Uint::from_word(l), Limb::ZERO);
-        out
+        out.wrapping_sub(&Uint::from_word(l))
     }
 }
 
diff --git a/vendor/crypto-bigint/src/uint/div_limb.rs b/vendor/crypto-bigint/src/uint/div_limb.rs
index 9bbd828e4..c00bc77c9 100644
--- a/vendor/crypto-bigint/src/uint/div_limb.rs
+++ b/vendor/crypto-bigint/src/uint/div_limb.rs
@@ -147,7 +147,7 @@ const fn div2by1(u1: Word, u0: Word, reciprocal: &Reciprocal) -> (Word, Word) {
     let r = Limb::ct_select(Limb(r), Limb(r.wrapping_add(d)), r_gt_q0).0;
 
     // If this was a normal `if`, we wouldn't need wrapping ops, because there would be no overflow.
-    // But since we caluculate both results either way, have to wrap.
+    // But since we calculate both results either way, we have to wrap.
     // Added an assert to still check the lack of overflow in debug mode.
     debug_assert!(r < d || q1 < Word::MAX);
     let r_ge_d = Limb::ct_le(Limb(d), Limb(r));
diff --git a/vendor/crypto-bigint/src/uint/modular.rs b/vendor/crypto-bigint/src/uint/modular.rs
index ff20f443d..cd560aa38 100644
--- a/vendor/crypto-bigint/src/uint/modular.rs
+++ b/vendor/crypto-bigint/src/uint/modular.rs
@@ -6,6 +6,7 @@ pub mod constant_mod;
 pub mod runtime_mod;
 
 mod add;
+mod div_by_2;
 mod inv;
 mod mul;
 mod pow;
diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod.rs
index f94e4c475..3e9b522ef 100644
--- a/vendor/crypto-bigint/src/uint/modular/constant_mod.rs
+++ b/vendor/crypto-bigint/src/uint/modular/constant_mod.rs
@@ -4,7 +4,7 @@ use subtle::{Choice, ConditionallySelectable, ConstantTimeEq};
 
 use crate::{Limb, Uint, Zero};
 
-use super::{reduction::montgomery_reduction, Retrieve};
+use super::{div_by_2::div_by_2, reduction::montgomery_reduction, Retrieve};
 
 #[cfg(feature = "rand_core")]
 use crate::{rand_core::CryptoRngCore, NonZero, Random, RandomMod};
@@ -67,6 +67,12 @@ where
     phantom: PhantomData<MOD>,
 }
 
+#[cfg(feature = "zeroize")]
+impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> zeroize::DefaultIsZeroes
+    for Residue<MOD, LIMBS>
+{
+}
+
 impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
     /// The representation of 0 mod `MOD`.
     pub const ZERO: Self = Self {
@@ -100,6 +106,18 @@ impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> {
             MOD::MOD_NEG_INV,
         )
     }
+
+    /// Performs the modular division by 2, that is for given `x` returns `y`
+    /// such that `y * 2 = x mod p`. This means:
+    /// - if `x` is even, returns `x / 2`,
+    /// - if `x` is odd, returns `(x + p) / 2`
+    ///   (since the modulus `p` in Montgomery form is always odd, this divides entirely).
+    pub fn div_by_2(&self) -> Self {
+        Self {
+            montgomery_form: div_by_2(&self.montgomery_form, &MOD::MODULUS),
+            phantom: PhantomData,
+        }
+    }
 }
 
 impl<MOD: ResidueParams<LIMBS> + Copy, const LIMBS: usize> ConditionallySelectable
diff --git a/vendor/crypto-bigint/src/uint/modular/div_by_2.rs b/vendor/crypto-bigint/src/uint/modular/div_by_2.rs
new file mode 100644
index 000000000..20c0a5d86
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/modular/div_by_2.rs
@@ -0,0 +1,30 @@
+use crate::Uint;
+
+pub(crate) fn div_by_2<const LIMBS: usize>(a: &Uint<LIMBS>, modulus: &Uint<LIMBS>) -> Uint<LIMBS> {
+    // We are looking for such `x` that `x * 2 = y mod modulus`,
+    // where the given `a = M(y)` is the Montgomery representation of some `y`.
+    // This means that in Montgomery representation it would still apply:
+    // `M(x) + M(x) = a mod modulus`.
+    // So we can just forget about Montgomery representation, and return whatever is
+    // `a` divided by 2, and this will be the Montgomery representation of `x`.
+    // (Which means that this function works regardless of whether `a`
+    // is in Montgomery representation or not, but the algorithm below
+    // does need `modulus` to be odd)
+
+    // Two possibilities:
+    // - if `a` is even, we can just divide by 2;
+    // - if `a` is odd, we divide `(a + modulus)` by 2.
+    // To stay within the modulus we open the parentheses turning it into `a / 2 + modulus / 2 + 1`
+    // ("+1" because both `a` and `modulus` are odd, we lose 0.5 in each integer division).
+    // This will not overflow, so we can just use wrapping operations.
+
+    let (half, is_odd) = a.shr_1();
+    let half_modulus = modulus.shr_vartime(1);
+
+    let if_even = half;
+    let if_odd = half
+        .wrapping_add(&half_modulus)
+        .wrapping_add(&Uint::<LIMBS>::ONE);
+
+    Uint::<LIMBS>::ct_select(&if_even, &if_odd, is_odd)
+}
diff --git a/vendor/crypto-bigint/src/uint/modular/reduction.rs b/vendor/crypto-bigint/src/uint/modular/reduction.rs
index d3543bf97..b206ae32f 100644
--- a/vendor/crypto-bigint/src/uint/modular/reduction.rs
+++ b/vendor/crypto-bigint/src/uint/modular/reduction.rs
@@ -1,4 +1,14 @@
-use crate::{CtChoice, Limb, Uint, WideWord, Word};
+use crate::{Limb, Uint, WideWord, Word};
+
+/// Returns `(hi, lo)` such that `hi * R + lo = x * y + z + w`.
+#[inline(always)]
+const fn muladdcarry(x: Word, y: Word, z: Word, w: Word) -> (Word, Word) {
+    let res = (x as WideWord)
+        .wrapping_mul(y as WideWord)
+        .wrapping_add(z as WideWord)
+        .wrapping_add(w as WideWord);
+    ((res >> Word::BITS) as Word, res as Word)
+}
 
 /// Algorithm 14.32 in Handbook of Applied Cryptography <https://cacr.uwaterloo.ca/hac/about/chap14.pdf>
 pub const fn montgomery_reduction<const LIMBS: usize>(
@@ -8,49 +18,38 @@ pub const fn montgomery_reduction<const LIMBS: usize>(
 ) -> Uint<LIMBS> {
     let (mut lower, mut upper) = *lower_upper;
 
-    let mut meta_carry: WideWord = 0;
+    let mut meta_carry = Limb(0);
+    let mut new_sum;
 
     let mut i = 0;
     while i < LIMBS {
-        let u = (lower.limbs[i].0.wrapping_mul(mod_neg_inv.0)) as WideWord;
+        let u = lower.limbs[i].0.wrapping_mul(mod_neg_inv.0);
 
-        let new_limb =
-            (u * modulus.limbs[0].0 as WideWord).wrapping_add(lower.limbs[i].0 as WideWord);
-        let mut carry = new_limb >> Word::BITS;
+        let (mut carry, _) = muladdcarry(u, modulus.limbs[0].0, lower.limbs[i].0, 0);
+        let mut new_limb;
 
         let mut j = 1;
         while j < (LIMBS - i) {
-            let new_limb = (u * modulus.limbs[j].0 as WideWord)
-                .wrapping_add(lower.limbs[i + j].0 as WideWord)
-                .wrapping_add(carry);
-            carry = new_limb >> Word::BITS;
-            lower.limbs[i + j] = Limb(new_limb as Word);
-
+            (carry, new_limb) = muladdcarry(u, modulus.limbs[j].0, lower.limbs[i + j].0, carry);
+            lower.limbs[i + j] = Limb(new_limb);
             j += 1;
         }
         while j < LIMBS {
-            let new_limb = (u * modulus.limbs[j].0 as WideWord)
-                .wrapping_add(upper.limbs[i + j - LIMBS].0 as WideWord)
-                .wrapping_add(carry);
-            carry = new_limb >> Word::BITS;
-            upper.limbs[i + j - LIMBS] = Limb(new_limb as Word);
-
+            (carry, new_limb) =
+                muladdcarry(u, modulus.limbs[j].0, upper.limbs[i + j - LIMBS].0, carry);
+            upper.limbs[i + j - LIMBS] = Limb(new_limb);
             j += 1;
         }
 
-        let new_sum = (upper.limbs[i].0 as WideWord)
-            .wrapping_add(carry)
-            .wrapping_add(meta_carry);
-        meta_carry = new_sum >> Word::BITS;
-        upper.limbs[i] = Limb(new_sum as Word);
+        (new_sum, meta_carry) = upper.limbs[i].adc(Limb(carry), meta_carry);
+        upper.limbs[i] = new_sum;
 
         i += 1;
     }
 
     // Division is simply taking the upper half of the limbs
-    // Final reduction (at this point, the value is at most 2 * modulus)
-    let must_reduce = CtChoice::from_lsb(meta_carry as Word).or(Uint::ct_gt(modulus, &upper).not());
-    upper = upper.wrapping_sub(&Uint::ct_select(&Uint::ZERO, modulus, must_reduce));
+    // Final reduction (at this point, the value is at most 2 * modulus,
+    // so `meta_carry` is either 0 or 1)
 
-    upper
+    upper.sub_mod_with_carry(meta_carry, modulus, modulus)
 }
diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs
index 72f1094cf..84622d167 100644
--- a/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs
+++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs
@@ -1,6 +1,6 @@
 use crate::{Limb, Uint, Word};
 
-use super::{reduction::montgomery_reduction, Retrieve};
+use super::{div_by_2::div_by_2, reduction::montgomery_reduction, Retrieve};
 
 /// Additions between residues with a modulus set at runtime
 mod runtime_add;
@@ -33,11 +33,16 @@ pub struct DynResidueParams<const LIMBS: usize> {
 
 impl<const LIMBS: usize> DynResidueParams<LIMBS> {
     /// Instantiates a new set of `ResidueParams` representing the given `modulus`.
-    pub fn new(modulus: &Uint<LIMBS>) -> Self {
+    pub const fn new(modulus: &Uint<LIMBS>) -> Self {
         let r = Uint::MAX.const_rem(modulus).0.wrapping_add(&Uint::ONE);
         let r2 = Uint::const_rem_wide(r.square_wide(), modulus).0;
+
+        // Since we are calculating the inverse modulo (Word::MAX+1),
+        // we can take the modulo right away and calculate the inverse of the first limb only.
+        let modulus_lo = Uint::<1>::from_words([modulus.limbs[0].0]);
         let mod_neg_inv =
-            Limb(Word::MIN.wrapping_sub(modulus.inv_mod2k(Word::BITS as usize).limbs[0].0));
+            Limb(Word::MIN.wrapping_sub(modulus_lo.inv_mod2k(Word::BITS as usize).limbs[0].0));
+
         let r3 = montgomery_reduction(&r2.square_wide(), modulus, mod_neg_inv);
 
         Self {
@@ -48,6 +53,11 @@ impl<const LIMBS: usize> DynResidueParams<LIMBS> {
             mod_neg_inv,
         }
     }
+
+    /// Returns the modulus which was used to initialize these parameters.
+    pub const fn modulus(&self) -> &Uint<LIMBS> {
+        &self.modulus
+    }
 }
 
 /// A residue represented using `LIMBS` limbs. The odd modulus of this residue is set at runtime.
@@ -97,6 +107,23 @@ impl<const LIMBS: usize> DynResidue<LIMBS> {
             residue_params,
         }
     }
+
+    /// Returns the parameter struct used to initialize this residue.
+    pub const fn params(&self) -> &DynResidueParams<LIMBS> {
+        &self.residue_params
+    }
+
+    /// Performs the modular division by 2, that is for given `x` returns `y`
+    /// such that `y * 2 = x mod p`. This means:
+    /// - if `x` is even, returns `x / 2`,
+    /// - if `x` is odd, returns `(x + p) / 2`
+    ///   (since the modulus `p` in Montgomery form is always odd, this divides entirely).
+    pub fn div_by_2(&self) -> Self {
+        Self {
+            montgomery_form: div_by_2(&self.montgomery_form, &self.residue_params.modulus),
+            residue_params: self.residue_params,
+        }
+    }
 }
 
 impl<const LIMBS: usize> Retrieve for DynResidue<LIMBS> {
diff --git a/vendor/crypto-bigint/src/uint/shr.rs b/vendor/crypto-bigint/src/uint/shr.rs
index 071788fb4..3698b970b 100644
--- a/vendor/crypto-bigint/src/uint/shr.rs
+++ b/vendor/crypto-bigint/src/uint/shr.rs
@@ -5,7 +5,8 @@ use crate::{limb::HI_BIT, CtChoice, Limb};
 use core::ops::{Shr, ShrAssign};
 
 impl<const LIMBS: usize> Uint<LIMBS> {
-    /// Computes `self >> 1` in constant-time, returning the overflowing bit as a `Word` that is either 0...0 or 1...1.
+    /// Computes `self >> 1` in constant-time, returning [`CtChoice::TRUE`] if the overflowing bit
+    /// was set, and [`CtChoice::FALSE`] otherwise.
     pub(crate) const fn shr_1(&self) -> (Self, CtChoice) {
         let mut shifted_bits = [0; LIMBS];
         let mut i = 0;
diff --git a/vendor/crypto-bigint/src/uint/sub_mod.rs b/vendor/crypto-bigint/src/uint/sub_mod.rs
index 728a92760..b32babb89 100644
--- a/vendor/crypto-bigint/src/uint/sub_mod.rs
+++ b/vendor/crypto-bigint/src/uint/sub_mod.rs
@@ -7,21 +7,31 @@ impl<const LIMBS: usize> Uint<LIMBS> {
     ///
     /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`.
     pub const fn sub_mod(&self, rhs: &Uint<LIMBS>, p: &Uint<LIMBS>) -> Uint<LIMBS> {
-        let (mut out, borrow) = self.sbb(rhs, Limb::ZERO);
+        let (out, borrow) = self.sbb(rhs, Limb::ZERO);
 
         // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
         // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
-        let mut carry = Limb::ZERO;
-        let mut i = 0;
+        let mask = Uint::from_words([borrow.0; LIMBS]);
+
+        out.wrapping_add(&p.bitand(&mask))
+    }
 
-        while i < LIMBS {
-            let (l, c) = out.limbs[i].adc(p.limbs[i].bitand(borrow), carry);
-            out.limbs[i] = l;
-            carry = c;
-            i += 1;
-        }
+    /// Returns `(self..., carry) - (rhs...) mod (p...)`, where `carry <= 1`.
+    /// Assumes `-(p...) <= (self..., carry) - (rhs...) < (p...)`.
+    #[inline(always)]
+    pub(crate) const fn sub_mod_with_carry(&self, carry: Limb, rhs: &Self, p: &Self) -> Self {
+        debug_assert!(carry.0 <= 1);
+
+        let (out, borrow) = self.sbb(rhs, Limb::ZERO);
+
+        // The new `borrow = Word::MAX` iff `carry == 0` and `borrow == Word::MAX`.
+        let borrow = (!carry.0.wrapping_neg()) & borrow.0;
+
+        // If underflow occurred on the final limb, borrow = 0xfff...fff, otherwise
+        // borrow = 0x000...000. Thus, we use it as a mask to conditionally add the modulus.
+        let mask = Uint::from_words([borrow; LIMBS]);
 
-        out
+        out.wrapping_add(&p.bitand(&mask))
     }
 
     /// Computes `self - rhs mod p` in constant time for the special modulus
@@ -35,8 +45,7 @@ impl<const LIMBS: usize> Uint<LIMBS> {
         // the underflow. This cannot underflow due to the assumption
         // `self - rhs >= -p`.
         let l = borrow.0 & c.0;
-        let (out, _) = out.sbb(&Uint::from_word(l), Limb::ZERO);
-        out
+        out.wrapping_sub(&Uint::from_word(l))
     }
 }