From 2aadc03ef15cb5ca5cc2af8a7c08e070742f0ac4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 4 May 2024 14:47:55 +0200 Subject: Adding upstream version 0.70.1+ds1. Signed-off-by: Daniel Baumann --- vendor/crypto-bigint/src/boxed/uint.rs | 231 +++++++++++++++++++++++++++++ vendor/crypto-bigint/src/boxed/uint/add.rs | 62 ++++++++ vendor/crypto-bigint/src/boxed/uint/cmp.rs | 47 ++++++ 3 files changed, 340 insertions(+) create mode 100644 vendor/crypto-bigint/src/boxed/uint.rs create mode 100644 vendor/crypto-bigint/src/boxed/uint/add.rs create mode 100644 vendor/crypto-bigint/src/boxed/uint/cmp.rs (limited to 'vendor/crypto-bigint/src/boxed') diff --git a/vendor/crypto-bigint/src/boxed/uint.rs b/vendor/crypto-bigint/src/boxed/uint.rs new file mode 100644 index 0000000..4771a69 --- /dev/null +++ b/vendor/crypto-bigint/src/boxed/uint.rs @@ -0,0 +1,231 @@ +//! Heap-allocated big unsigned integers. + +mod add; +mod cmp; + +use crate::{Limb, Word}; +use alloc::{vec, vec::Vec}; +use core::fmt; + +#[cfg(feature = "zeroize")] +use zeroize::Zeroize; + +/// Fixed-precision heap-allocated big unsigned integer. +/// +/// Alternative to the stack-allocated [`Uint`][`crate::Uint`] but with a +/// fixed precision chosen at runtime instead of compile time. +/// +/// Unlike many other heap-allocated big integer libraries, this type is not +/// arbitrary precision and will wrap at its fixed-precision rather than +/// automatically growing. +#[derive(Clone, Default)] +pub struct BoxedUint { + /// Inner limb vector. Stored from least significant to most significant. + limbs: Vec, +} + +impl BoxedUint { + /// Get the value `0`, represented as succinctly as possible. + pub fn zero() -> Self { + Self::default() + } + + /// Get the value `1`, represented as succinctly as possible. + pub fn one() -> Self { + Self { + limbs: vec![Limb::ONE; 1], + } + } + + /// Create a new [`BoxedUint`] with the given number of bits of precision. + /// + /// Returns `None` if the number of bits is not a multiple of the + /// [`Limb`] size. + pub fn new(bits_precision: usize) -> Option { + if bits_precision == 0 || bits_precision % Limb::BITS != 0 { + return None; + } + + let nlimbs = bits_precision / Limb::BITS; + + Some(Self { + limbs: vec![Limb::ZERO; nlimbs], + }) + } + + /// Get the maximum value for a given number of bits of precision. + /// + /// Returns `None` if the number of bits is not a multiple of the + /// [`Limb`] size. + pub fn max(bits_precision: usize) -> Option { + let mut ret = Self::new(bits_precision)?; + + for limb in &mut ret.limbs { + *limb = Limb::MAX; + } + + Some(ret) + } + + /// Create a [`BoxedUint`] from an array of [`Word`]s (i.e. word-sized unsigned + /// integers). + #[inline] + pub fn from_words(words: &[Word]) -> Self { + Self { + limbs: words.iter().copied().map(Into::into).collect(), + } + } + + /// Create an array of [`Word`]s (i.e. word-sized unsigned integers) from + /// a [`BoxedUint`]. + #[inline] + pub fn to_words(&self) -> Vec { + self.limbs.iter().copied().map(Into::into).collect() + } + + /// Borrow the inner limbs as a slice of [`Word`]s. + pub fn as_words(&self) -> &[Word] { + // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word` + #[allow(trivial_casts, unsafe_code)] + unsafe { + &*((self.limbs.as_slice() as *const _) as *const [Word]) + } + } + + /// Borrow the inner limbs as a mutable array of [`Word`]s. + pub fn as_words_mut(&mut self) -> &mut [Word] { + // SAFETY: `Limb` is a `repr(transparent)` newtype for `Word` + #[allow(trivial_casts, unsafe_code)] + unsafe { + &mut *((self.limbs.as_mut_slice() as *mut _) as *mut [Word]) + } + } + + /// Borrow the limbs of this [`BoxedUint`]. + pub fn as_limbs(&self) -> &[Limb] { + self.limbs.as_ref() + } + + /// Borrow the limbs of this [`BoxedUint`] mutably. + pub fn as_limbs_mut(&mut self) -> &mut [Limb] { + self.limbs.as_mut() + } + + /// Convert this [`BoxedUint`] into its inner limbs. + pub fn to_limbs(&self) -> Vec { + self.limbs.clone() + } + + /// Convert this [`BoxedUint`] into its inner limbs. + pub fn into_limbs(self) -> Vec { + self.limbs + } + + /// Get the precision of this [`BoxedUint`] in bits. + pub fn bits(&self) -> usize { + self.limbs.len() * Limb::BITS + } + + /// Sort two [`BoxedUint`]s by precision, returning a tuple of the shorter + /// followed by the longer, or the original order if their precision is + /// equal. + fn sort_by_precision<'a>(a: &'a Self, b: &'a Self) -> (&'a Self, &'a Self) { + if a.limbs.len() <= b.limbs.len() { + (a, b) + } else { + (b, a) + } + } + + /// Perform a carry chain-like operation over the limbs of the inputs, + /// constructing a result from the returned limbs and carry. + /// + /// If one of the two values has fewer limbs than the other, passes + /// [`Limb::ZERO`] as the value for that limb. + fn chain(a: &Self, b: &Self, mut carry: Limb, f: F) -> (Self, Limb) + where + F: Fn(Limb, Limb, Limb) -> (Limb, Limb), + { + let (shorter, longer) = Self::sort_by_precision(a, b); + let mut limbs = Vec::with_capacity(longer.limbs.len()); + + for i in 0..longer.limbs.len() { + let &a = shorter.limbs.get(i).unwrap_or(&Limb::ZERO); + let &b = longer.limbs.get(i).unwrap_or(&Limb::ZERO); + let (limb, c) = f(a, b, carry); + limbs.push(limb); + carry = c; + } + + (Self { limbs }, carry) + } +} + +impl AsRef<[Word]> for BoxedUint { + fn as_ref(&self) -> &[Word] { + self.as_words() + } +} + +impl AsMut<[Word]> for BoxedUint { + fn as_mut(&mut self) -> &mut [Word] { + self.as_words_mut() + } +} + +impl AsRef<[Limb]> for BoxedUint { + fn as_ref(&self) -> &[Limb] { + self.as_limbs() + } +} + +impl AsMut<[Limb]> for BoxedUint { + fn as_mut(&mut self) -> &mut [Limb] { + self.as_limbs_mut() + } +} + +impl fmt::Debug for BoxedUint { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "BoxedUint(0x{self:X})") + } +} + +impl fmt::Display for BoxedUint { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::UpperHex::fmt(self, f) + } +} + +impl fmt::LowerHex for BoxedUint { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if self.limbs.is_empty() { + return fmt::LowerHex::fmt(&Limb::ZERO, f); + } + + for limb in self.limbs.iter().rev() { + fmt::LowerHex::fmt(limb, f)?; + } + Ok(()) + } +} + +impl fmt::UpperHex for BoxedUint { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + if self.limbs.is_empty() { + return fmt::LowerHex::fmt(&Limb::ZERO, f); + } + + for limb in self.limbs.iter().rev() { + fmt::UpperHex::fmt(limb, f)?; + } + Ok(()) + } +} + +#[cfg(feature = "zeroize")] +impl Zeroize for BoxedUint { + fn zeroize(&mut self) { + self.limbs.zeroize(); + } +} diff --git a/vendor/crypto-bigint/src/boxed/uint/add.rs b/vendor/crypto-bigint/src/boxed/uint/add.rs new file mode 100644 index 0000000..b6cedc7 --- /dev/null +++ b/vendor/crypto-bigint/src/boxed/uint/add.rs @@ -0,0 +1,62 @@ +//! [`BoxedUint`] addition operations. + +use crate::{BoxedUint, CheckedAdd, Limb, Zero}; +use subtle::CtOption; + +impl BoxedUint { + /// Computes `a + b + carry`, returning the result along with the new carry. + #[inline(always)] + pub fn adc(&self, rhs: &Self, carry: Limb) -> (Self, Limb) { + Self::chain(self, rhs, carry, |a, b, c| a.adc(b, c)) + } + + /// Perform wrapping addition, discarding overflow. + pub fn wrapping_add(&self, rhs: &Self) -> Self { + self.adc(rhs, Limb::ZERO).0 + } +} + +impl CheckedAdd<&BoxedUint> for BoxedUint { + type Output = Self; + + fn checked_add(&self, rhs: &Self) -> CtOption { + let (result, carry) = self.adc(rhs, Limb::ZERO); + CtOption::new(result, carry.is_zero()) + } +} + +#[cfg(test)] +#[allow(clippy::unwrap_used)] +mod tests { + use super::{BoxedUint, CheckedAdd, Limb}; + + #[test] + fn adc_no_carry() { + let (res, carry) = BoxedUint::zero().adc(&BoxedUint::one(), Limb::ZERO); + assert_eq!(res, BoxedUint::one()); + assert_eq!(carry, Limb::ZERO); + } + + #[test] + fn adc_with_carry() { + let (res, carry) = BoxedUint::max(Limb::BITS) + .unwrap() + .adc(&BoxedUint::one(), Limb::ZERO); + assert_eq!(res, BoxedUint::zero()); + assert_eq!(carry, Limb::ONE); + } + + #[test] + fn checked_add_ok() { + let result = BoxedUint::zero().checked_add(&BoxedUint::one()); + assert_eq!(result.unwrap(), BoxedUint::one()); + } + + #[test] + fn checked_add_overflow() { + let result = BoxedUint::max(Limb::BITS) + .unwrap() + .checked_add(&BoxedUint::one()); + assert!(!bool::from(result.is_some())); + } +} diff --git a/vendor/crypto-bigint/src/boxed/uint/cmp.rs b/vendor/crypto-bigint/src/boxed/uint/cmp.rs new file mode 100644 index 0000000..d850fc7 --- /dev/null +++ b/vendor/crypto-bigint/src/boxed/uint/cmp.rs @@ -0,0 +1,47 @@ +//! [`BoxedUint`] comparisons. +//! +//! By default these are all constant-time and use the `subtle` crate. + +use super::BoxedUint; +use crate::Limb; +use subtle::{Choice, ConstantTimeEq}; + +impl ConstantTimeEq for BoxedUint { + #[inline] + fn ct_eq(&self, other: &Self) -> Choice { + let (shorter, longer) = Self::sort_by_precision(self, other); + let mut ret = Choice::from(1u8); + + for i in 0..longer.limbs.len() { + let a = shorter.limbs.get(i).unwrap_or(&Limb::ZERO); + let b = longer.limbs.get(i).unwrap_or(&Limb::ZERO); + ret &= a.ct_eq(b); + } + + ret + } +} + +impl Eq for BoxedUint {} +impl PartialEq for BoxedUint { + fn eq(&self, other: &Self) -> bool { + self.ct_eq(other).into() + } +} + +#[cfg(test)] +mod tests { + use super::BoxedUint; + use subtle::ConstantTimeEq; + + #[test] + fn ct_eq() { + let a = BoxedUint::zero(); + let b = BoxedUint::one(); + + assert!(bool::from(a.ct_eq(&a))); + assert!(!bool::from(a.ct_eq(&b))); + assert!(!bool::from(b.ct_eq(&a))); + assert!(bool::from(b.ct_eq(&b))); + } +} -- cgit v1.2.3