From dc0db358abe19481e475e10c32149b53370f1a1c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 30 May 2024 05:57:31 +0200 Subject: Merging upstream version 1.72.1+dfsg1. Signed-off-by: Daniel Baumann --- vendor/crypto-bigint/src/ct_choice.rs | 10 ++-- vendor/crypto-bigint/src/traits.rs | 2 +- vendor/crypto-bigint/src/uint/add_mod.rs | 19 ++------ vendor/crypto-bigint/src/uint/div_limb.rs | 2 +- vendor/crypto-bigint/src/uint/modular.rs | 1 + .../crypto-bigint/src/uint/modular/constant_mod.rs | 20 +++++++- vendor/crypto-bigint/src/uint/modular/div_by_2.rs | 30 ++++++++++++ vendor/crypto-bigint/src/uint/modular/reduction.rs | 53 +++++++++++----------- .../crypto-bigint/src/uint/modular/runtime_mod.rs | 33 ++++++++++++-- vendor/crypto-bigint/src/uint/shr.rs | 3 +- vendor/crypto-bigint/src/uint/sub_mod.rs | 33 +++++++++----- 11 files changed, 138 insertions(+), 68 deletions(-) create mode 100644 vendor/crypto-bigint/src/uint/modular/div_by_2.rs (limited to 'vendor/crypto-bigint/src') 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: Sized { fn checked_mul(&self, rhs: Rhs) -> CtOption; } -/// Checked substraction. +/// Checked subtraction. pub trait CheckedSub: 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 Uint { // 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 Uint { // 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, } +#[cfg(feature = "zeroize")] +impl, const LIMBS: usize> zeroize::DefaultIsZeroes + for Residue +{ +} + impl, const LIMBS: usize> Residue { /// The representation of 0 mod `MOD`. pub const ZERO: Self = Self { @@ -100,6 +106,18 @@ impl, const LIMBS: usize> Residue { 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 + 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(a: &Uint, modulus: &Uint) -> Uint { + // 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::::ONE); + + Uint::::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 pub const fn montgomery_reduction( @@ -8,49 +18,38 @@ pub const fn montgomery_reduction( ) -> Uint { 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 { impl DynResidueParams { /// Instantiates a new set of `ResidueParams` representing the given `modulus`. - pub fn new(modulus: &Uint) -> Self { + pub const fn new(modulus: &Uint) -> 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 DynResidueParams { mod_neg_inv, } } + + /// Returns the modulus which was used to initialize these parameters. + pub const fn modulus(&self) -> &Uint { + &self.modulus + } } /// A residue represented using `LIMBS` limbs. The odd modulus of this residue is set at runtime. @@ -97,6 +107,23 @@ impl DynResidue { residue_params, } } + + /// Returns the parameter struct used to initialize this residue. + pub const fn params(&self) -> &DynResidueParams { + &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 Retrieve for DynResidue { 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 Uint { - /// 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 Uint { /// /// Assumes `self - rhs` as unbounded signed integer is in `[-p, p)`. pub const fn sub_mod(&self, rhs: &Uint, p: &Uint) -> Uint { - 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 Uint { // 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)) } } -- cgit v1.2.3