1 files changed, 79 insertions, 0 deletions
diff --git a/vendor/crypto-bigint/src/uint/rand.rs b/vendor/crypto-bigint/src/uint/rand.rs
new file mode 100644
index 0000000..c5f730b
--- /dev/null
+++ b/vendor/crypto-bigint/src/uint/rand.rs
@@ -0,0 +1,79 @@
+//! Random number generator support
+
+use super::Uint;
+use crate::{Limb, NonZero, Random, RandomMod};
+use rand_core::CryptoRngCore;
+use subtle::ConstantTimeLess;
+
+impl<const LIMBS: usize> Random for Uint<LIMBS> {
+    /// Generate a cryptographically secure random [`Uint`].
+    fn random(mut rng: &mut impl CryptoRngCore) -> Self {
+        let mut limbs = [Limb::ZERO; LIMBS];
+
+        for limb in &mut limbs {
+            *limb = Limb::random(&mut rng)
+        }
+
+        limbs.into()
+    }
+}
+
+impl<const LIMBS: usize> RandomMod for Uint<LIMBS> {
+    /// Generate a cryptographically secure random [`Uint`] which is less than
+    /// a given `modulus`.
+    ///
+    /// This function uses rejection sampling, a method which produces an
+    /// unbiased distribution of in-range values provided the underlying
+    /// CSRNG is unbiased, but runs in variable-time.
+    ///
+    /// The variable-time nature of the algorithm should not pose a security
+    /// issue so long as the underlying random number generator is truly a
+    /// CSRNG, where previous outputs are unrelated to subsequent
+    /// outputs and do not reveal information about the RNG's internal state.
+    fn random_mod(mut rng: &mut impl CryptoRngCore, modulus: &NonZero<Self>) -> Self {
+        let mut n = Self::ZERO;
+
+        let n_bits = modulus.as_ref().bits_vartime();
+        let n_limbs = (n_bits + Limb::BITS - 1) / Limb::BITS;
+        let mask = Limb::MAX >> (Limb::BITS * n_limbs - n_bits);
+
+        loop {
+            for i in 0..n_limbs {
+                n.limbs[i] = Limb::random(&mut rng);
+            }
+            n.limbs[n_limbs - 1] = n.limbs[n_limbs - 1] & mask;
+
+            if n.ct_lt(modulus).into() {
+                return n;
+            }
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use crate::{NonZero, RandomMod, U256};
+    use rand_core::SeedableRng;
+
+    #[test]
+    fn random_mod() {
+        let mut rng = rand_chacha::ChaCha8Rng::seed_from_u64(1);
+
+        // Ensure `random_mod` runs in a reasonable amount of time
+        let modulus = NonZero::new(U256::from(42u8)).unwrap();
+        let res = U256::random_mod(&mut rng, &modulus);
+
+        // Check that the value is in range
+        assert!(res >= U256::ZERO);
+        assert!(res < U256::from(42u8));
+
+        // Ensure `random_mod` runs in a reasonable amount of time
+        // when the modulus is larger than 1 limb
+        let modulus = NonZero::new(U256::from(0x10000000000000001u128)).unwrap();
+        let res = U256::random_mod(&mut rng, &modulus);
+
+        // Check that the value is in range
+        assert!(res >= U256::ZERO);
+        assert!(res < U256::from(0x10000000000000001u128));
+    }
+}