primitives/random/

mod.rs

pub mod prf;
pub mod prg;
pub mod rng;

use std::sync::Arc;

pub use rand_chacha::rand_core::CryptoRngCore;
#[cfg(any(test, feature = "dev"))]
pub use rng::test_rng;
pub use rng::{BaseRng, Seed, SeedableRng};
use subtle::Choice;
use typenum::Unsigned;

use crate::{
    algebra::field::FieldExtension,
    constants::Lambda,
    errors::PrimitiveError,
    types::{HeapArray, Positive},
    utils::IntoExactSizeIterator,
};

/// A trait for getting a random value for a type. Will be replaced by the `random` feature
/// once it is included in std (https://github.com/rust-lang/rust/issues/130703).
pub trait Random: Sized {
    // Generates a random value.
    fn random(rng: impl CryptoRngCore) -> Self;

    // Generates a container with `size` random elements.
    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
    ) -> Container {
        (0..size).map(|_| Self::random(&mut rng)).collect()
    }

    // Generates an array with `M` random elements, known at compile time.
    fn random_array<M: Positive>(rng: impl CryptoRngCore) -> HeapArray<Self, M> {
        HeapArray::random(rng)
    }
}

impl Random for Seed {
    #[inline]
    fn random(mut rng: impl CryptoRngCore) -> Self {
        let mut seed = [0u8; 32];
        rng.fill_bytes(&mut seed);
        seed
    }
}

impl<T: Random> Random for Arc<T> {
    #[inline]
    fn random(mut source: impl CryptoRngCore) -> Self {
        Arc::new(T::random(&mut source))
    }
}

impl<T1: Random, T2: Random> Random for (T1, T2) {
    #[inline]
    fn random(mut source: impl CryptoRngCore) -> Self {
        (T1::random(&mut source), T2::random(&mut source))
    }
}

impl<T: Random> RandomWith<usize> for Vec<T> {
    #[inline]
    fn random_with(mut source: impl CryptoRngCore, n_elements: usize) -> Self {
        (0..n_elements).map(|_| T::random(&mut source)).collect()
    }
}

/// A trait for getting a random instance of a type alongside some data.
pub trait RandomWith<D: Clone>: Sized {
    // Generates a random value given additional data.
    fn random_with(rng: impl CryptoRngCore, data: D) -> Self;

    // Generates a container with `size` random elements and some available data.
    fn random_n_with<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
        data: D,
    ) -> Container {
        (0..size)
            .map(|_| Self::random_with(&mut rng, data.clone()))
            .collect()
    }

    // Generates a container with `[data.len()]` random elements and some available data.
    fn random_n_with_each<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        all_data: impl IntoExactSizeIterator<Item = D>,
    ) -> Container {
        all_data
            .into_iter()
            .map(|data| Self::random_with(&mut rng, data))
            .collect()
    }
}

impl<D: Clone, T: RandomWith<D>> RandomWith<Vec<D>> for Vec<T> {
    /// Generates a container with an element of T for each element in `data`,
    /// yielding a container of `[data.len()]` length.
    #[inline]
    fn random_with(mut source: impl CryptoRngCore, data: Vec<D>) -> Self {
        T::random_n_with_each(&mut source, data)
    }

    /// Generates `size` instances of T for each element in `data.len()`,
    /// yielding a container of `[data.len()][size]` dimensions.
    #[inline]
    fn random_n_with<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
        data: Vec<D>,
    ) -> Container {
        let mut res = (0..data.len())
            .map(|_| Vec::<T>::with_capacity(size))
            .collect::<Vec<_>>();
        for _ in 0..size {
            let row: Vec<_> = T::random_n_with_each(&mut rng, data.clone());
            for (res_row, item) in res.iter_mut().zip(row) {
                res_row.push(item);
            }
        }
        res.into_iter().collect()
    }
}

/// Generate random non-zero values.
pub trait RandomNonZero: Sized {
    // Generates a non-zero element.
    fn random_non_zero(rng: impl CryptoRngCore) -> Result<Self, PrimitiveError>;

    // Generates a container with `size` random non-zero elements.
    fn random_n_non_zero<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
    ) -> Result<Container, PrimitiveError> {
        (0..size).map(|_| Self::random_non_zero(&mut rng)).collect()
    }
}

impl<T: FieldExtension> RandomNonZero for T {
    /// Generates a random non-zero value.
    ///
    /// May error out if it cannot find a non-zero value after a certain number
    /// of tries, defined so that:
    ///
    /// > `Prob(out == 0) <= 2^-(λ)` as long as `Prob(random()==0) <= 2^-(size_of::<Self>)`
    ///
    /// The default implementation repetitively calls `random()` (rejection sampling).
    /// As such, it is not constant-time, but the side channel leakage should not impact security
    /// as long as the rng is evaluated in constant time and produces uniformly random values.
    ///
    /// If needed, override with a constant-time implementation using `ConditionallySelectable` and
    /// always running for a fixed number of iterations, potentially returning a zero value
    /// (with overwhelmingly low probability).
    #[inline]
    fn random_non_zero(mut rng: impl CryptoRngCore) -> Result<Self, PrimitiveError> {
        let n_tries = (Lambda::USIZE).div_ceil(std::mem::size_of::<Self>()) + 1;
        for _ in 0..n_tries {
            let value = <Self as ff::Field>::random(&mut rng);
            if !<Choice as Into<bool>>::into(value.is_zero()) {
                return Ok(value);
            }
        }
        Err(PrimitiveError::ZeroValueSampled(
            std::any::type_name::<Self>().into(),
        ))
    }
}

impl Random for u8 {
    #[inline]
    fn random(mut rng: impl CryptoRngCore) -> Self {
        let mut buf = [0u8; 1];
        rng.fill_bytes(&mut buf);
        buf[0]
    }

    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
    ) -> Container {
        let mut buf = vec![0u8; size];
        rng.fill_bytes(&mut buf);
        buf.into_iter().collect()
    }
}

impl Random for usize {
    #[inline]
    fn random(mut rng: impl CryptoRngCore) -> Self {
        let mut buf = [0u8; std::mem::size_of::<usize>()];
        rng.fill_bytes(&mut buf);
        usize::from_le_bytes(buf)
    }

    fn random_n<Container: FromIterator<Self>>(
        mut rng: impl CryptoRngCore,
        size: usize,
    ) -> Container {
        let mut buf = vec![0u8; size * std::mem::size_of::<usize>()];
        rng.fill_bytes(&mut buf);
        buf.chunks_exact(std::mem::size_of::<usize>())
            .map(|chunk| usize::from_le_bytes(chunk.try_into().unwrap()))
            .collect()
    }
}