diff options
Diffstat (limited to 'vendor/crypto-bigint/src/uint/modular')
22 files changed, 1707 insertions, 0 deletions
diff --git a/vendor/crypto-bigint/src/uint/modular/add.rs b/vendor/crypto-bigint/src/uint/modular/add.rs new file mode 100644 index 0000000..f4d0f79 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/add.rs @@ -0,0 +1,9 @@ +use crate::Uint; + +pub(crate) const fn add_montgomery_form<const LIMBS: usize>( + a: &Uint<LIMBS>, + b: &Uint<LIMBS>, + modulus: &Uint<LIMBS>, +) -> Uint<LIMBS> { + a.add_mod(b, modulus) +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod.rs new file mode 100644 index 0000000..b775af4 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod.rs @@ -0,0 +1,254 @@ +use core::{fmt::Debug, marker::PhantomData}; + +use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}; + +use crate::{Limb, Uint, Zero}; + +use super::{div_by_2::div_by_2, reduction::montgomery_reduction, Retrieve}; + +#[cfg(feature = "rand_core")] +use crate::{rand_core::CryptoRngCore, NonZero, Random, RandomMod}; + +#[cfg(feature = "serde")] +use { + crate::Encoding, + serdect::serde::de::Error, + serdect::serde::{Deserialize, Deserializer, Serialize, Serializer}, +}; + +/// Additions between residues with a constant modulus +mod const_add; +/// Multiplicative inverses of residues with a constant modulus +mod const_inv; +/// Multiplications between residues with a constant modulus +mod const_mul; +/// Negations of residues with a constant modulus +mod const_neg; +/// Exponentiation of residues with a constant modulus +mod const_pow; +/// Subtractions between residues with a constant modulus +mod const_sub; + +/// Macros to remove the boilerplate code when dealing with constant moduli. +#[macro_use] +mod macros; + +pub use macros::*; + +/// The parameters to efficiently go to and from the Montgomery form for a given odd modulus. An easy way to generate these parameters is using the `impl_modulus!` macro. These parameters are constant, so they cannot be set at runtime. +/// +/// Unfortunately, `LIMBS` must be generic for now until const generics are stabilized. +pub trait ResidueParams<const LIMBS: usize>: + Copy + Debug + Default + Eq + Send + Sync + 'static +{ + /// Number of limbs required to encode a residue + const LIMBS: usize; + + /// The constant modulus + const MODULUS: Uint<LIMBS>; + /// Parameter used in Montgomery reduction + const R: Uint<LIMBS>; + /// R^2, used to move into Montgomery form + const R2: Uint<LIMBS>; + /// R^3, used to perform a multiplicative inverse + const R3: Uint<LIMBS>; + /// The lowest limbs of -(MODULUS^-1) mod R + // We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS. + const MOD_NEG_INV: Limb; +} + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +/// A residue mod `MOD`, represented using `LIMBS` limbs. The modulus of this residue is constant, so it cannot be set at runtime. +/// Internally, the value is stored in Montgomery form (multiplied by MOD::R) until it is retrieved. +pub struct Residue<MOD, const LIMBS: usize> +where + MOD: ResidueParams<LIMBS>, +{ + montgomery_form: Uint<LIMBS>, + 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 { + montgomery_form: Uint::<LIMBS>::ZERO, + phantom: PhantomData, + }; + + /// The representation of 1 mod `MOD`. + pub const ONE: Self = Self { + montgomery_form: MOD::R, + phantom: PhantomData, + }; + + // Internal helper function to generate a residue; this lets us wrap the constructors more cleanly + const fn generate_residue(integer: &Uint<LIMBS>) -> Self { + let product = integer.mul_wide(&MOD::R2); + let montgomery_form = + montgomery_reduction::<LIMBS>(&product, &MOD::MODULUS, MOD::MOD_NEG_INV); + + Self { + montgomery_form, + phantom: PhantomData, + } + } + + /// Instantiates a new `Residue` that represents this `integer` mod `MOD`. + /// If the modulus represented by `MOD` is not odd, this function will panic; use [`new_checked`][`Residue::new_checked`] if you want to be able to detect an invalid modulus. + pub const fn new(integer: &Uint<LIMBS>) -> Self { + // A valid modulus must be odd + if MOD::MODULUS.ct_is_odd().to_u8() == 0 { + panic!("modulus must be odd"); + } + + Self::generate_residue(integer) + } + + /// Instantiates a new `Residue` that represents this `integer` mod `MOD` if the modulus is odd. + /// Returns a `CtOption` that is `None` if the provided modulus is not odd; this is a safer version of [`new`][`Residue::new`], which can panic. + // TODO: remove this method when we can use `generic_const_exprs.` to ensure the modulus is + // always valid. + pub fn new_checked(integer: &Uint<LIMBS>) -> CtOption<Self> { + // A valid modulus must be odd, which we can check in constant time + CtOption::new( + Self::generate_residue(integer), + MOD::MODULUS.ct_is_odd().into(), + ) + } + + /// Retrieves the integer currently encoded in this `Residue`, guaranteed to be reduced. + pub const fn retrieve(&self) -> Uint<LIMBS> { + montgomery_reduction::<LIMBS>( + &(self.montgomery_form, Uint::ZERO), + &MOD::MODULUS, + MOD::MOD_NEG_INV, + ) + } + + /// Access the `Residue` value in Montgomery form. + pub const fn as_montgomery(&self) -> &Uint<LIMBS> { + &self.montgomery_form + } + + /// Mutably access the `Residue` value in Montgomery form. + pub fn as_montgomery_mut(&mut self) -> &mut Uint<LIMBS> { + &mut self.montgomery_form + } + + /// Create a `Residue` from a value in Montgomery form. + pub const fn from_montgomery(integer: Uint<LIMBS>) -> Self { + Self { + montgomery_form: integer, + phantom: PhantomData, + } + } + + /// Extract the value from the `Residue` in Montgomery form. + pub const fn to_montgomery(&self) -> Uint<LIMBS> { + self.montgomery_form + } + + /// 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 + for Residue<MOD, LIMBS> +{ + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Residue { + montgomery_form: Uint::conditional_select( + &a.montgomery_form, + &b.montgomery_form, + choice, + ), + phantom: PhantomData, + } + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> ConstantTimeEq for Residue<MOD, LIMBS> { + fn ct_eq(&self, other: &Self) -> Choice { + ConstantTimeEq::ct_eq(&self.montgomery_form, &other.montgomery_form) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Default for Residue<MOD, LIMBS> { + fn default() -> Self { + Self::ZERO + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Zero for Residue<MOD, LIMBS> { + const ZERO: Self = Self::ZERO; +} + +#[cfg(feature = "rand_core")] +impl<MOD, const LIMBS: usize> Random for Residue<MOD, LIMBS> +where + MOD: ResidueParams<LIMBS>, +{ + #[inline] + fn random(rng: &mut impl CryptoRngCore) -> Self { + Self::new(&Uint::random_mod(rng, &NonZero::from_uint(MOD::MODULUS))) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Retrieve for Residue<MOD, LIMBS> { + type Output = Uint<LIMBS>; + fn retrieve(&self) -> Self::Output { + self.retrieve() + } +} + +#[cfg(feature = "serde")] +impl<'de, MOD, const LIMBS: usize> Deserialize<'de> for Residue<MOD, LIMBS> +where + MOD: ResidueParams<LIMBS>, + Uint<LIMBS>: Encoding, +{ + fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> + where + D: Deserializer<'de>, + { + Uint::<LIMBS>::deserialize(deserializer).and_then(|montgomery_form| { + if Uint::ct_lt(&montgomery_form, &MOD::MODULUS).into() { + Ok(Self { + montgomery_form, + phantom: PhantomData, + }) + } else { + Err(D::Error::custom("montgomery form must be reduced")) + } + }) + } +} + +#[cfg(feature = "serde")] +impl<MOD, const LIMBS: usize> Serialize for Residue<MOD, LIMBS> +where + MOD: ResidueParams<LIMBS>, + Uint<LIMBS>: Encoding, +{ + fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> + where + S: Serializer, + { + self.montgomery_form.serialize(serializer) + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_add.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_add.rs new file mode 100644 index 0000000..82eb882 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_add.rs @@ -0,0 +1,98 @@ +use core::ops::{Add, AddAssign}; + +use crate::modular::add::add_montgomery_form; + +use super::{Residue, ResidueParams}; + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> { + /// Adds `rhs`. + pub const fn add(&self, rhs: &Residue<MOD, LIMBS>) -> Self { + Self { + montgomery_form: add_montgomery_form( + &self.montgomery_form, + &rhs.montgomery_form, + &MOD::MODULUS, + ), + phantom: core::marker::PhantomData, + } + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<&Residue<MOD, LIMBS>> + for &Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + fn add(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + self.add(rhs) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<Residue<MOD, LIMBS>> + for &Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + #[allow(clippy::op_ref)] + fn add(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + self + &rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<&Residue<MOD, LIMBS>> + for Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + #[allow(clippy::op_ref)] + fn add(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + &self + rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Add<Residue<MOD, LIMBS>> + for Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + fn add(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + &self + &rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> AddAssign<&Self> for Residue<MOD, LIMBS> { + fn add_assign(&mut self, rhs: &Self) { + *self = *self + rhs; + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> AddAssign<Self> for Residue<MOD, LIMBS> { + fn add_assign(&mut self, rhs: Self) { + *self += &rhs; + } +} + +#[cfg(test)] +mod tests { + use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256}; + + impl_modulus!( + Modulus, + U256, + "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551" + ); + + #[test] + fn add_overflow() { + let x = + U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"); + let mut x_mod = const_residue!(x, Modulus); + + let y = + U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"); + let y_mod = const_residue!(y, Modulus); + + x_mod += &y_mod; + + let expected = + U256::from_be_hex("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956"); + + assert_eq!(expected, x_mod.retrieve()); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_inv.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_inv.rs new file mode 100644 index 0000000..28f0622 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_inv.rs @@ -0,0 +1,69 @@ +use core::marker::PhantomData; + +use subtle::CtOption; + +use crate::{modular::inv::inv_montgomery_form, traits::Invert, CtChoice, NonZero}; + +use super::{Residue, ResidueParams}; + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> { + /// Computes the residue `self^-1` representing the multiplicative inverse of `self`. + /// I.e. `self * self^-1 = 1`. + /// If the number was invertible, the second element of the tuple is the truthy value, + /// otherwise it is the falsy value (in which case the first element's value is unspecified). + pub const fn invert(&self) -> (Self, CtChoice) { + let (montgomery_form, is_some) = inv_montgomery_form( + &self.montgomery_form, + &MOD::MODULUS, + &MOD::R3, + MOD::MOD_NEG_INV, + ); + + let value = Self { + montgomery_form, + phantom: PhantomData, + }; + + (value, is_some) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Invert for Residue<MOD, LIMBS> { + type Output = CtOption<Self>; + fn invert(&self) -> Self::Output { + let (value, is_some) = self.invert(); + CtOption::new(value, is_some.into()) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Invert for NonZero<Residue<MOD, LIMBS>> { + type Output = Self; + fn invert(&self) -> Self::Output { + // Always succeeds for a non-zero argument + let (value, _is_some) = self.as_ref().invert(); + NonZero::new(value).unwrap() + } +} + +#[cfg(test)] +mod tests { + use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256}; + + impl_modulus!( + Modulus, + U256, + "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409" + ); + + #[test] + fn test_self_inverse() { + let x = + U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685"); + let x_mod = const_residue!(x, Modulus); + + let (inv, _is_some) = x_mod.invert(); + let res = x_mod * inv; + + assert_eq!(res.retrieve(), U256::ONE); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_mul.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_mul.rs new file mode 100644 index 0000000..3bce184 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_mul.rs @@ -0,0 +1,94 @@ +use core::{ + marker::PhantomData, + ops::{Mul, MulAssign}, +}; + +use crate::{ + modular::mul::{mul_montgomery_form, square_montgomery_form}, + traits::Square, +}; + +use super::{Residue, ResidueParams}; + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> { + /// Multiplies by `rhs`. + pub const fn mul(&self, rhs: &Self) -> Self { + Self { + montgomery_form: mul_montgomery_form( + &self.montgomery_form, + &rhs.montgomery_form, + &MOD::MODULUS, + MOD::MOD_NEG_INV, + ), + phantom: PhantomData, + } + } + + /// Computes the (reduced) square of a residue. + pub const fn square(&self) -> Self { + Self { + montgomery_form: square_montgomery_form( + &self.montgomery_form, + &MOD::MODULUS, + MOD::MOD_NEG_INV, + ), + phantom: PhantomData, + } + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<&Residue<MOD, LIMBS>> + for &Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + fn mul(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + self.mul(rhs) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<Residue<MOD, LIMBS>> + for &Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + #[allow(clippy::op_ref)] + fn mul(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + self * &rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<&Residue<MOD, LIMBS>> + for Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + #[allow(clippy::op_ref)] + fn mul(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + &self * rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Mul<Residue<MOD, LIMBS>> + for Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + fn mul(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + &self * &rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> MulAssign<&Self> for Residue<MOD, LIMBS> { + fn mul_assign(&mut self, rhs: &Residue<MOD, LIMBS>) { + *self = *self * rhs; + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> MulAssign<Self> for Residue<MOD, LIMBS> { + fn mul_assign(&mut self, rhs: Self) { + *self *= &rhs; + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Square for Residue<MOD, LIMBS> { + fn square(&self) -> Self { + Residue::square(self) + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_neg.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_neg.rs new file mode 100644 index 0000000..1981f5a --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_neg.rs @@ -0,0 +1,48 @@ +use core::ops::Neg; + +use super::{Residue, ResidueParams}; + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> { + /// Negates the number. + pub const fn neg(&self) -> Self { + Self::ZERO.sub(self) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Neg for Residue<MOD, LIMBS> { + type Output = Self; + fn neg(self) -> Self { + Residue::neg(&self) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Neg for &Residue<MOD, LIMBS> { + type Output = Residue<MOD, LIMBS>; + fn neg(self) -> Residue<MOD, LIMBS> { + Residue::neg(self) + } +} + +#[cfg(test)] +mod tests { + use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256}; + + impl_modulus!( + Modulus, + U256, + "15477BCCEFE197328255BFA79A1217899016D927EF460F4FF404029D24FA4409" + ); + + #[test] + fn test_negate() { + let x = + U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685"); + let x_mod = const_residue!(x, Modulus); + + let res = -x_mod; + let expected = + U256::from_be_hex("089B67BB2C124F084701AD76E8750D321385E35044C74CE457301A2A9BE061B1"); + + assert_eq!(res.retrieve(), expected); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_pow.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_pow.rs new file mode 100644 index 0000000..ea3dd1c --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_pow.rs @@ -0,0 +1,101 @@ +use crate::{modular::pow::pow_montgomery_form, PowBoundedExp, Uint}; + +use super::{Residue, ResidueParams}; + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> { + /// Raises to the `exponent` power. + pub const fn pow<const RHS_LIMBS: usize>( + &self, + exponent: &Uint<RHS_LIMBS>, + ) -> Residue<MOD, LIMBS> { + self.pow_bounded_exp(exponent, Uint::<RHS_LIMBS>::BITS) + } + + /// Raises to the `exponent` power, + /// with `exponent_bits` representing the number of (least significant) bits + /// to take into account for the exponent. + /// + /// NOTE: `exponent_bits` may be leaked in the time pattern. + pub const fn pow_bounded_exp<const RHS_LIMBS: usize>( + &self, + exponent: &Uint<RHS_LIMBS>, + exponent_bits: usize, + ) -> Residue<MOD, LIMBS> { + Self { + montgomery_form: pow_montgomery_form( + &self.montgomery_form, + exponent, + exponent_bits, + &MOD::MODULUS, + &MOD::R, + MOD::MOD_NEG_INV, + ), + phantom: core::marker::PhantomData, + } + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> PowBoundedExp<Uint<LIMBS>> + for Residue<MOD, LIMBS> +{ + fn pow_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: usize) -> Self { + self.pow_bounded_exp(exponent, exponent_bits) + } +} + +#[cfg(test)] +mod tests { + use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256}; + + impl_modulus!( + Modulus, + U256, + "9CC24C5DF431A864188AB905AC751B727C9447A8E99E6366E1AD78A21E8D882B" + ); + + #[test] + fn test_powmod_small_base() { + let base = U256::from(105u64); + let base_mod = const_residue!(base, Modulus); + + let exponent = + U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685"); + + let res = base_mod.pow(&exponent); + + let expected = + U256::from_be_hex("7B2CD7BDDD96C271E6F232F2F415BB03FE2A90BD6CCCEA5E94F1BFD064993766"); + assert_eq!(res.retrieve(), expected); + } + + #[test] + fn test_powmod_small_exponent() { + let base = + U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4"); + let base_mod = const_residue!(base, Modulus); + + let exponent = U256::from(105u64); + + let res = base_mod.pow(&exponent); + + let expected = + U256::from_be_hex("89E2A4E99F649A5AE2C18068148C355CA927B34A3245C938178ED00D6EF218AA"); + assert_eq!(res.retrieve(), expected); + } + + #[test] + fn test_powmod() { + let base = + U256::from_be_hex("3435D18AA8313EBBE4D20002922225B53F75DC4453BB3EEC0378646F79B524A4"); + let base_mod = const_residue!(base, Modulus); + + let exponent = + U256::from_be_hex("77117F1273373C26C700D076B3F780074D03339F56DD0EFB60E7F58441FD3685"); + + let res = base_mod.pow(&exponent); + + let expected = + U256::from_be_hex("3681BC0FEA2E5D394EB178155A127B0FD2EF405486D354251C385BDD51B9D421"); + assert_eq!(res.retrieve(), expected); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/const_sub.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_sub.rs new file mode 100644 index 0000000..f650611 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/const_sub.rs @@ -0,0 +1,98 @@ +use core::ops::{Sub, SubAssign}; + +use crate::modular::sub::sub_montgomery_form; + +use super::{Residue, ResidueParams}; + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Residue<MOD, LIMBS> { + /// Subtracts `rhs`. + pub const fn sub(&self, rhs: &Self) -> Self { + Self { + montgomery_form: sub_montgomery_form( + &self.montgomery_form, + &rhs.montgomery_form, + &MOD::MODULUS, + ), + phantom: core::marker::PhantomData, + } + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<&Residue<MOD, LIMBS>> + for &Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + fn sub(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + self.sub(rhs) + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<Residue<MOD, LIMBS>> + for &Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + #[allow(clippy::op_ref)] + fn sub(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + self - &rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<&Residue<MOD, LIMBS>> + for Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + #[allow(clippy::op_ref)] + fn sub(self, rhs: &Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + &self - rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> Sub<Residue<MOD, LIMBS>> + for Residue<MOD, LIMBS> +{ + type Output = Residue<MOD, LIMBS>; + fn sub(self, rhs: Residue<MOD, LIMBS>) -> Residue<MOD, LIMBS> { + &self - &rhs + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> SubAssign<&Self> for Residue<MOD, LIMBS> { + fn sub_assign(&mut self, rhs: &Self) { + *self = *self - rhs; + } +} + +impl<MOD: ResidueParams<LIMBS>, const LIMBS: usize> SubAssign<Self> for Residue<MOD, LIMBS> { + fn sub_assign(&mut self, rhs: Self) { + *self -= &rhs; + } +} + +#[cfg(test)] +mod tests { + use crate::{const_residue, impl_modulus, modular::constant_mod::ResidueParams, U256}; + + impl_modulus!( + Modulus, + U256, + "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551" + ); + + #[test] + fn sub_overflow() { + let x = + U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"); + let mut x_mod = const_residue!(x, Modulus); + + let y = + U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"); + let y_mod = const_residue!(y, Modulus); + + x_mod -= &y_mod; + + let expected = + U256::from_be_hex("6f357a71e1d5a03167f34879d469352add829491c6df41ddff65387d7ed56f56"); + + assert_eq!(expected, x_mod.retrieve()); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/constant_mod/macros.rs b/vendor/crypto-bigint/src/uint/modular/constant_mod/macros.rs new file mode 100644 index 0000000..dfa440e --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/constant_mod/macros.rs @@ -0,0 +1,57 @@ +// TODO: Use `adt_const_params` once stabilized to make a `Residue` generic around a modulus rather than having to implement a ZST + trait +#[macro_export] +/// Implements a modulus with the given name, type, and value, in that specific order. Please `use crypto_bigint::traits::Encoding` to make this work. +/// For example, `impl_modulus!(MyModulus, U256, "73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001");` implements a 256-bit modulus named `MyModulus`. +/// The modulus _must_ be odd, or this will panic. +macro_rules! impl_modulus { + ($name:ident, $uint_type:ty, $value:expr) => { + #[derive(Clone, Copy, Debug, Default, Eq, PartialEq)] + pub struct $name {} + impl<const DLIMBS: usize> + $crate::modular::constant_mod::ResidueParams<{ <$uint_type>::LIMBS }> for $name + where + $uint_type: $crate::ConcatMixed<MixedOutput = $crate::Uint<DLIMBS>>, + { + const LIMBS: usize = <$uint_type>::LIMBS; + const MODULUS: $uint_type = { + let res = <$uint_type>::from_be_hex($value); + + // Check that the modulus is odd + if res.as_limbs()[0].0 & 1 == 0 { + panic!("modulus must be odd"); + } + + res + }; + const R: $uint_type = $crate::Uint::MAX + .const_rem(&Self::MODULUS) + .0 + .wrapping_add(&$crate::Uint::ONE); + const R2: $uint_type = + $crate::Uint::const_rem_wide(Self::R.square_wide(), &Self::MODULUS).0; + const MOD_NEG_INV: $crate::Limb = $crate::Limb( + $crate::Word::MIN.wrapping_sub( + Self::MODULUS + .inv_mod2k_vartime($crate::Word::BITS as usize) + .as_limbs()[0] + .0, + ), + ); + const R3: $uint_type = $crate::modular::montgomery_reduction( + &Self::R2.square_wide(), + &Self::MODULUS, + Self::MOD_NEG_INV, + ); + } + }; +} + +#[macro_export] +/// Creates a `Residue` with the given value for a specific modulus. +/// For example, `residue!(U256::from(105u64), MyModulus);` creates a `Residue` for 105 mod `MyModulus`. +/// The modulus _must_ be odd, or this will panic. +macro_rules! const_residue { + ($variable:ident, $modulus:ident) => { + $crate::modular::constant_mod::Residue::<$modulus, { $modulus::LIMBS }>::new(&$variable) + }; +} 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 0000000..20c0a5d --- /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/inv.rs b/vendor/crypto-bigint/src/uint/modular/inv.rs new file mode 100644 index 0000000..408c03f --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/inv.rs @@ -0,0 +1,14 @@ +use crate::{modular::reduction::montgomery_reduction, CtChoice, Limb, Uint}; + +pub const fn inv_montgomery_form<const LIMBS: usize>( + x: &Uint<LIMBS>, + modulus: &Uint<LIMBS>, + r3: &Uint<LIMBS>, + mod_neg_inv: Limb, +) -> (Uint<LIMBS>, CtChoice) { + let (inverse, is_some) = x.inv_odd_mod(modulus); + ( + montgomery_reduction(&inverse.mul_wide(r3), modulus, mod_neg_inv), + is_some, + ) +} diff --git a/vendor/crypto-bigint/src/uint/modular/mul.rs b/vendor/crypto-bigint/src/uint/modular/mul.rs new file mode 100644 index 0000000..b84ceb5 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/mul.rs @@ -0,0 +1,22 @@ +use crate::{Limb, Uint}; + +use super::reduction::montgomery_reduction; + +pub(crate) const fn mul_montgomery_form<const LIMBS: usize>( + a: &Uint<LIMBS>, + b: &Uint<LIMBS>, + modulus: &Uint<LIMBS>, + mod_neg_inv: Limb, +) -> Uint<LIMBS> { + let product = a.mul_wide(b); + montgomery_reduction::<LIMBS>(&product, modulus, mod_neg_inv) +} + +pub(crate) const fn square_montgomery_form<const LIMBS: usize>( + a: &Uint<LIMBS>, + modulus: &Uint<LIMBS>, + mod_neg_inv: Limb, +) -> Uint<LIMBS> { + let product = a.square_wide(); + montgomery_reduction::<LIMBS>(&product, modulus, mod_neg_inv) +} diff --git a/vendor/crypto-bigint/src/uint/modular/pow.rs b/vendor/crypto-bigint/src/uint/modular/pow.rs new file mode 100644 index 0000000..db9ac99 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/pow.rs @@ -0,0 +1,79 @@ +use crate::{Limb, Uint, Word}; + +use super::mul::{mul_montgomery_form, square_montgomery_form}; + +/// Performs modular exponentiation using Montgomery's ladder. +/// `exponent_bits` represents the number of bits to take into account for the exponent. +/// +/// NOTE: this value is leaked in the time pattern. +pub const fn pow_montgomery_form<const LIMBS: usize, const RHS_LIMBS: usize>( + x: &Uint<LIMBS>, + exponent: &Uint<RHS_LIMBS>, + exponent_bits: usize, + modulus: &Uint<LIMBS>, + r: &Uint<LIMBS>, + mod_neg_inv: Limb, +) -> Uint<LIMBS> { + if exponent_bits == 0 { + return *r; // 1 in Montgomery form + } + + const WINDOW: usize = 4; + const WINDOW_MASK: Word = (1 << WINDOW) - 1; + + // powers[i] contains x^i + let mut powers = [*r; 1 << WINDOW]; + powers[1] = *x; + let mut i = 2; + while i < powers.len() { + powers[i] = mul_montgomery_form(&powers[i - 1], x, modulus, mod_neg_inv); + i += 1; + } + + let starting_limb = (exponent_bits - 1) / Limb::BITS; + let starting_bit_in_limb = (exponent_bits - 1) % Limb::BITS; + let starting_window = starting_bit_in_limb / WINDOW; + let starting_window_mask = (1 << (starting_bit_in_limb % WINDOW + 1)) - 1; + + let mut z = *r; // 1 in Montgomery form + + let mut limb_num = starting_limb + 1; + while limb_num > 0 { + limb_num -= 1; + let w = exponent.as_limbs()[limb_num].0; + + let mut window_num = if limb_num == starting_limb { + starting_window + 1 + } else { + Limb::BITS / WINDOW + }; + while window_num > 0 { + window_num -= 1; + + let mut idx = (w >> (window_num * WINDOW)) & WINDOW_MASK; + + if limb_num == starting_limb && window_num == starting_window { + idx &= starting_window_mask; + } else { + let mut i = 0; + while i < WINDOW { + i += 1; + z = square_montgomery_form(&z, modulus, mod_neg_inv); + } + } + + // Constant-time lookup in the array of powers + let mut power = powers[0]; + let mut i = 1; + while i < 1 << WINDOW { + let choice = Limb::ct_eq(Limb(i as Word), Limb(idx)); + power = Uint::<LIMBS>::ct_select(&power, &powers[i], choice); + i += 1; + } + + z = mul_montgomery_form(&z, &power, modulus, mod_neg_inv); + } + } + + z +} diff --git a/vendor/crypto-bigint/src/uint/modular/reduction.rs b/vendor/crypto-bigint/src/uint/modular/reduction.rs new file mode 100644 index 0000000..b206ae3 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/reduction.rs @@ -0,0 +1,55 @@ +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>( + lower_upper: &(Uint<LIMBS>, Uint<LIMBS>), + modulus: &Uint<LIMBS>, + mod_neg_inv: Limb, +) -> Uint<LIMBS> { + let (mut lower, mut upper) = *lower_upper; + + 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); + + 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) { + (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 { + (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; + } + + (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, + // so `meta_carry` is either 0 or 1) + + 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 new file mode 100644 index 0000000..ad5cfd5 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod.rs @@ -0,0 +1,301 @@ +use crate::{Limb, Uint, Word}; + +use super::{ + constant_mod::{Residue, ResidueParams}, + div_by_2::div_by_2, + reduction::montgomery_reduction, + Retrieve, +}; + +use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption}; + +/// Additions between residues with a modulus set at runtime +mod runtime_add; +/// Multiplicative inverses of residues with a modulus set at runtime +mod runtime_inv; +/// Multiplications between residues with a modulus set at runtime +mod runtime_mul; +/// Negations of residues with a modulus set at runtime +mod runtime_neg; +/// Exponentiation of residues with a modulus set at runtime +mod runtime_pow; +/// Subtractions between residues with a modulus set at runtime +mod runtime_sub; + +/// The parameters to efficiently go to and from the Montgomery form for an odd modulus provided at runtime. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct DynResidueParams<const LIMBS: usize> { + // The constant modulus + modulus: Uint<LIMBS>, + // Parameter used in Montgomery reduction + r: Uint<LIMBS>, + // R^2, used to move into Montgomery form + r2: Uint<LIMBS>, + // R^3, used to compute the multiplicative inverse + r3: Uint<LIMBS>, + // The lowest limbs of -(MODULUS^-1) mod R + // We only need the LSB because during reduction this value is multiplied modulo 2**Limb::BITS. + mod_neg_inv: Limb, +} + +impl<const LIMBS: usize> DynResidueParams<LIMBS> { + // Internal helper function to generate parameters; this lets us wrap the constructors more cleanly + const fn generate_params(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_lo.inv_mod2k_vartime(Word::BITS as usize).limbs[0].0), + ); + + let r3 = montgomery_reduction(&r2.square_wide(), modulus, mod_neg_inv); + + Self { + modulus: *modulus, + r, + r2, + r3, + mod_neg_inv, + } + } + + /// Instantiates a new set of `ResidueParams` representing the given `modulus`, which _must_ be odd. + /// If `modulus` is not odd, this function will panic; use [`new_checked`][`DynResidueParams::new_checked`] if you want to be able to detect an invalid modulus. + pub const fn new(modulus: &Uint<LIMBS>) -> Self { + // A valid modulus must be odd + if modulus.ct_is_odd().to_u8() == 0 { + panic!("modulus must be odd"); + } + + Self::generate_params(modulus) + } + + /// Instantiates a new set of `ResidueParams` representing the given `modulus` if it is odd. + /// Returns a `CtOption` that is `None` if the provided modulus is not odd; this is a safer version of [`new`][`DynResidueParams::new`], which can panic. + #[deprecated( + since = "0.5.3", + note = "This functionality will be moved to `new` in a future release." + )] + pub fn new_checked(modulus: &Uint<LIMBS>) -> CtOption<Self> { + // A valid modulus must be odd, which we check in constant time + CtOption::new(Self::generate_params(modulus), modulus.ct_is_odd().into()) + } + + /// Returns the modulus which was used to initialize these parameters. + pub const fn modulus(&self) -> &Uint<LIMBS> { + &self.modulus + } + + /// Create `DynResidueParams` corresponding to a `ResidueParams`. + pub const fn from_residue_params<P>() -> Self + where + P: ResidueParams<LIMBS>, + { + Self { + modulus: P::MODULUS, + r: P::R, + r2: P::R2, + r3: P::R3, + mod_neg_inv: P::MOD_NEG_INV, + } + } +} + +impl<const LIMBS: usize> ConditionallySelectable for DynResidueParams<LIMBS> { + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Self { + modulus: Uint::conditional_select(&a.modulus, &b.modulus, choice), + r: Uint::conditional_select(&a.r, &b.r, choice), + r2: Uint::conditional_select(&a.r2, &b.r2, choice), + r3: Uint::conditional_select(&a.r3, &b.r3, choice), + mod_neg_inv: Limb::conditional_select(&a.mod_neg_inv, &b.mod_neg_inv, choice), + } + } +} + +impl<const LIMBS: usize> ConstantTimeEq for DynResidueParams<LIMBS> { + fn ct_eq(&self, other: &Self) -> Choice { + self.modulus.ct_eq(&other.modulus) + & self.r.ct_eq(&other.r) + & self.r2.ct_eq(&other.r2) + & self.r3.ct_eq(&other.r3) + & self.mod_neg_inv.ct_eq(&other.mod_neg_inv) + } +} + +/// A residue represented using `LIMBS` limbs. The odd modulus of this residue is set at runtime. +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct DynResidue<const LIMBS: usize> { + montgomery_form: Uint<LIMBS>, + residue_params: DynResidueParams<LIMBS>, +} + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Instantiates a new `Residue` that represents this `integer` mod `MOD`. + pub const fn new(integer: &Uint<LIMBS>, residue_params: DynResidueParams<LIMBS>) -> Self { + let product = integer.mul_wide(&residue_params.r2); + let montgomery_form = montgomery_reduction( + &product, + &residue_params.modulus, + residue_params.mod_neg_inv, + ); + + Self { + montgomery_form, + residue_params, + } + } + + /// Retrieves the integer currently encoded in this `Residue`, guaranteed to be reduced. + pub const fn retrieve(&self) -> Uint<LIMBS> { + montgomery_reduction( + &(self.montgomery_form, Uint::ZERO), + &self.residue_params.modulus, + self.residue_params.mod_neg_inv, + ) + } + + /// Instantiates a new `Residue` that represents zero. + pub const fn zero(residue_params: DynResidueParams<LIMBS>) -> Self { + Self { + montgomery_form: Uint::<LIMBS>::ZERO, + residue_params, + } + } + + /// Instantiates a new `Residue` that represents 1. + pub const fn one(residue_params: DynResidueParams<LIMBS>) -> Self { + Self { + montgomery_form: residue_params.r, + residue_params, + } + } + + /// Returns the parameter struct used to initialize this residue. + pub const fn params(&self) -> &DynResidueParams<LIMBS> { + &self.residue_params + } + + /// Access the `DynResidue` value in Montgomery form. + pub const fn as_montgomery(&self) -> &Uint<LIMBS> { + &self.montgomery_form + } + + /// Mutably access the `DynResidue` value in Montgomery form. + pub fn as_montgomery_mut(&mut self) -> &mut Uint<LIMBS> { + &mut self.montgomery_form + } + + /// Create a `DynResidue` from a value in Montgomery form. + pub const fn from_montgomery( + integer: Uint<LIMBS>, + residue_params: DynResidueParams<LIMBS>, + ) -> Self { + Self { + montgomery_form: integer, + residue_params, + } + } + + /// Extract the value from the `DynResidue` in Montgomery form. + pub const fn to_montgomery(&self) -> Uint<LIMBS> { + self.montgomery_form + } + + /// 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> { + type Output = Uint<LIMBS>; + fn retrieve(&self) -> Self::Output { + self.retrieve() + } +} + +impl<const LIMBS: usize, P: ResidueParams<LIMBS>> From<&Residue<P, LIMBS>> for DynResidue<LIMBS> { + fn from(residue: &Residue<P, LIMBS>) -> Self { + Self { + montgomery_form: residue.to_montgomery(), + residue_params: DynResidueParams::from_residue_params::<P>(), + } + } +} + +impl<const LIMBS: usize> ConditionallySelectable for DynResidue<LIMBS> { + fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self { + Self { + montgomery_form: Uint::conditional_select( + &a.montgomery_form, + &b.montgomery_form, + choice, + ), + residue_params: DynResidueParams::conditional_select( + &a.residue_params, + &b.residue_params, + choice, + ), + } + } +} + +impl<const LIMBS: usize> ConstantTimeEq for DynResidue<LIMBS> { + fn ct_eq(&self, other: &Self) -> Choice { + self.montgomery_form.ct_eq(&other.montgomery_form) + & self.residue_params.ct_eq(&other.residue_params) + } +} + +/// NOTE: this does _not_ zeroize the parameters, in order to maintain some form of type consistency +#[cfg(feature = "zeroize")] +impl<const LIMBS: usize> zeroize::Zeroize for DynResidue<LIMBS> { + fn zeroize(&mut self) { + self.montgomery_form.zeroize() + } +} + +#[cfg(test)] +mod test { + use super::*; + use crate::nlimbs; + + const LIMBS: usize = nlimbs!(64); + + #[test] + #[allow(deprecated)] + // Test that a valid modulus yields `DynResidueParams` + fn test_valid_modulus() { + let valid_modulus = Uint::<LIMBS>::from(3u8); + + DynResidueParams::<LIMBS>::new_checked(&valid_modulus).unwrap(); + DynResidueParams::<LIMBS>::new(&valid_modulus); + } + + #[test] + #[allow(deprecated)] + // Test that an invalid checked modulus does not yield `DynResidueParams` + fn test_invalid_checked_modulus() { + assert!(bool::from( + DynResidueParams::<LIMBS>::new_checked(&Uint::from(2u8)).is_none() + )) + } + + #[test] + #[should_panic] + // Tets that an invalid modulus panics + fn test_invalid_modulus() { + DynResidueParams::<LIMBS>::new(&Uint::from(2u8)); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_add.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_add.rs new file mode 100644 index 0000000..eb47086 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_add.rs @@ -0,0 +1,92 @@ +use core::ops::{Add, AddAssign}; + +use crate::modular::add::add_montgomery_form; + +use super::DynResidue; + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Adds `rhs`. + pub const fn add(&self, rhs: &Self) -> Self { + Self { + montgomery_form: add_montgomery_form( + &self.montgomery_form, + &rhs.montgomery_form, + &self.residue_params.modulus, + ), + residue_params: self.residue_params, + } + } +} + +impl<const LIMBS: usize> Add<&DynResidue<LIMBS>> for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn add(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> { + debug_assert_eq!(self.residue_params, rhs.residue_params); + self.add(rhs) + } +} + +impl<const LIMBS: usize> Add<DynResidue<LIMBS>> for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + #[allow(clippy::op_ref)] + fn add(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> { + self + &rhs + } +} + +impl<const LIMBS: usize> Add<&DynResidue<LIMBS>> for DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + #[allow(clippy::op_ref)] + fn add(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> { + &self + rhs + } +} + +impl<const LIMBS: usize> Add<DynResidue<LIMBS>> for DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn add(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> { + &self + &rhs + } +} + +impl<const LIMBS: usize> AddAssign<&DynResidue<LIMBS>> for DynResidue<LIMBS> { + fn add_assign(&mut self, rhs: &DynResidue<LIMBS>) { + *self = *self + rhs; + } +} + +impl<const LIMBS: usize> AddAssign<DynResidue<LIMBS>> for DynResidue<LIMBS> { + fn add_assign(&mut self, rhs: DynResidue<LIMBS>) { + *self += &rhs; + } +} + +#[cfg(test)] +mod tests { + use crate::{ + modular::runtime_mod::{DynResidue, DynResidueParams}, + U256, + }; + + #[test] + fn add_overflow() { + let params = DynResidueParams::new(&U256::from_be_hex( + "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", + )); + + let x = + U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"); + let mut x_mod = DynResidue::new(&x, params); + + let y = + U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"); + let y_mod = DynResidue::new(&y, params); + + x_mod += &y_mod; + + let expected = + U256::from_be_hex("1a2472fde50286541d97ca6a3592dd75beb9c9646e40c511b82496cfc3926956"); + + assert_eq!(expected, x_mod.retrieve()); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_inv.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_inv.rs new file mode 100644 index 0000000..5e639d4 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_inv.rs @@ -0,0 +1,35 @@ +use subtle::CtOption; + +use crate::{modular::inv::inv_montgomery_form, traits::Invert, CtChoice}; + +use super::DynResidue; + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Computes the residue `self^-1` representing the multiplicative inverse of `self`. + /// I.e. `self * self^-1 = 1`. + /// If the number was invertible, the second element of the tuple is the truthy value, + /// otherwise it is the falsy value (in which case the first element's value is unspecified). + pub const fn invert(&self) -> (Self, CtChoice) { + let (montgomery_form, is_some) = inv_montgomery_form( + &self.montgomery_form, + &self.residue_params.modulus, + &self.residue_params.r3, + self.residue_params.mod_neg_inv, + ); + + let value = Self { + montgomery_form, + residue_params: self.residue_params, + }; + + (value, is_some) + } +} + +impl<const LIMBS: usize> Invert for DynResidue<LIMBS> { + type Output = CtOption<Self>; + fn invert(&self) -> Self::Output { + let (value, is_some) = self.invert(); + CtOption::new(value, is_some.into()) + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_mul.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_mul.rs new file mode 100644 index 0000000..30c4b9c --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_mul.rs @@ -0,0 +1,84 @@ +use core::ops::{Mul, MulAssign}; + +use crate::{ + modular::mul::{mul_montgomery_form, square_montgomery_form}, + traits::Square, +}; + +use super::DynResidue; + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Multiplies by `rhs`. + pub const fn mul(&self, rhs: &Self) -> Self { + Self { + montgomery_form: mul_montgomery_form( + &self.montgomery_form, + &rhs.montgomery_form, + &self.residue_params.modulus, + self.residue_params.mod_neg_inv, + ), + residue_params: self.residue_params, + } + } + + /// Computes the (reduced) square of a residue. + pub const fn square(&self) -> Self { + Self { + montgomery_form: square_montgomery_form( + &self.montgomery_form, + &self.residue_params.modulus, + self.residue_params.mod_neg_inv, + ), + residue_params: self.residue_params, + } + } +} + +impl<const LIMBS: usize> Mul<&DynResidue<LIMBS>> for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn mul(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> { + debug_assert_eq!(self.residue_params, rhs.residue_params); + self.mul(rhs) + } +} + +impl<const LIMBS: usize> Mul<DynResidue<LIMBS>> for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + #[allow(clippy::op_ref)] + fn mul(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> { + self * &rhs + } +} + +impl<const LIMBS: usize> Mul<&DynResidue<LIMBS>> for DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + #[allow(clippy::op_ref)] + fn mul(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> { + &self * rhs + } +} + +impl<const LIMBS: usize> Mul<DynResidue<LIMBS>> for DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn mul(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> { + &self * &rhs + } +} + +impl<const LIMBS: usize> MulAssign<&DynResidue<LIMBS>> for DynResidue<LIMBS> { + fn mul_assign(&mut self, rhs: &DynResidue<LIMBS>) { + *self = *self * rhs; + } +} + +impl<const LIMBS: usize> MulAssign<DynResidue<LIMBS>> for DynResidue<LIMBS> { + fn mul_assign(&mut self, rhs: DynResidue<LIMBS>) { + *self *= &rhs; + } +} + +impl<const LIMBS: usize> Square for DynResidue<LIMBS> { + fn square(&self) -> Self { + DynResidue::square(self) + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_neg.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_neg.rs new file mode 100644 index 0000000..fca1ff8 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_neg.rs @@ -0,0 +1,24 @@ +use core::ops::Neg; + +use super::DynResidue; + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Negates the number. + pub const fn neg(&self) -> Self { + Self::zero(self.residue_params).sub(self) + } +} + +impl<const LIMBS: usize> Neg for DynResidue<LIMBS> { + type Output = Self; + fn neg(self) -> Self { + DynResidue::neg(&self) + } +} + +impl<const LIMBS: usize> Neg for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn neg(self) -> DynResidue<LIMBS> { + DynResidue::neg(self) + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_pow.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_pow.rs new file mode 100644 index 0000000..889e41b --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_pow.rs @@ -0,0 +1,42 @@ +use crate::{modular::pow::pow_montgomery_form, PowBoundedExp, Uint}; + +use super::DynResidue; + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Raises to the `exponent` power. + pub const fn pow<const RHS_LIMBS: usize>( + &self, + exponent: &Uint<RHS_LIMBS>, + ) -> DynResidue<LIMBS> { + self.pow_bounded_exp(exponent, Uint::<RHS_LIMBS>::BITS) + } + + /// Raises to the `exponent` power, + /// with `exponent_bits` representing the number of (least significant) bits + /// to take into account for the exponent. + /// + /// NOTE: `exponent_bits` may be leaked in the time pattern. + pub const fn pow_bounded_exp<const RHS_LIMBS: usize>( + &self, + exponent: &Uint<RHS_LIMBS>, + exponent_bits: usize, + ) -> Self { + Self { + montgomery_form: pow_montgomery_form( + &self.montgomery_form, + exponent, + exponent_bits, + &self.residue_params.modulus, + &self.residue_params.r, + self.residue_params.mod_neg_inv, + ), + residue_params: self.residue_params, + } + } +} + +impl<const LIMBS: usize> PowBoundedExp<Uint<LIMBS>> for DynResidue<LIMBS> { + fn pow_bounded_exp(&self, exponent: &Uint<LIMBS>, exponent_bits: usize) -> Self { + self.pow_bounded_exp(exponent, exponent_bits) + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_sub.rs b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_sub.rs new file mode 100644 index 0000000..dd6fd84 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/runtime_mod/runtime_sub.rs @@ -0,0 +1,92 @@ +use core::ops::{Sub, SubAssign}; + +use crate::modular::sub::sub_montgomery_form; + +use super::DynResidue; + +impl<const LIMBS: usize> DynResidue<LIMBS> { + /// Subtracts `rhs`. + pub const fn sub(&self, rhs: &Self) -> Self { + Self { + montgomery_form: sub_montgomery_form( + &self.montgomery_form, + &rhs.montgomery_form, + &self.residue_params.modulus, + ), + residue_params: self.residue_params, + } + } +} + +impl<const LIMBS: usize> Sub<&DynResidue<LIMBS>> for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn sub(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> { + debug_assert_eq!(self.residue_params, rhs.residue_params); + self.sub(rhs) + } +} + +impl<const LIMBS: usize> Sub<DynResidue<LIMBS>> for &DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + #[allow(clippy::op_ref)] + fn sub(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> { + self - &rhs + } +} + +impl<const LIMBS: usize> Sub<&DynResidue<LIMBS>> for DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + #[allow(clippy::op_ref)] + fn sub(self, rhs: &DynResidue<LIMBS>) -> DynResidue<LIMBS> { + &self - rhs + } +} + +impl<const LIMBS: usize> Sub<DynResidue<LIMBS>> for DynResidue<LIMBS> { + type Output = DynResidue<LIMBS>; + fn sub(self, rhs: DynResidue<LIMBS>) -> DynResidue<LIMBS> { + &self - &rhs + } +} + +impl<const LIMBS: usize> SubAssign<&DynResidue<LIMBS>> for DynResidue<LIMBS> { + fn sub_assign(&mut self, rhs: &DynResidue<LIMBS>) { + *self = *self - rhs; + } +} + +impl<const LIMBS: usize> SubAssign<DynResidue<LIMBS>> for DynResidue<LIMBS> { + fn sub_assign(&mut self, rhs: DynResidue<LIMBS>) { + *self -= &rhs; + } +} + +#[cfg(test)] +mod tests { + use crate::{ + modular::runtime_mod::{DynResidue, DynResidueParams}, + U256, + }; + + #[test] + fn sub_overflow() { + let params = DynResidueParams::new(&U256::from_be_hex( + "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", + )); + + let x = + U256::from_be_hex("44acf6b7e36c1342c2c5897204fe09504e1e2efb1a900377dbc4e7a6a133ec56"); + let mut x_mod = DynResidue::new(&x, params); + + let y = + U256::from_be_hex("d5777c45019673125ad240f83094d4252d829516fac8601ed01979ec1ec1a251"); + let y_mod = DynResidue::new(&y, params); + + x_mod -= &y_mod; + + let expected = + U256::from_be_hex("6f357a71e1d5a03167f34879d469352add829491c6df41ddff65387d7ed56f56"); + + assert_eq!(expected, x_mod.retrieve()); + } +} diff --git a/vendor/crypto-bigint/src/uint/modular/sub.rs b/vendor/crypto-bigint/src/uint/modular/sub.rs new file mode 100644 index 0000000..9c47170 --- /dev/null +++ b/vendor/crypto-bigint/src/uint/modular/sub.rs @@ -0,0 +1,9 @@ +use crate::Uint; + +pub(crate) const fn sub_montgomery_form<const LIMBS: usize>( + a: &Uint<LIMBS>, + b: &Uint<LIMBS>, + modulus: &Uint<LIMBS>, +) -> Uint<LIMBS> { + a.sub_mod(b, modulus) +} |