concrete_csprng/generators/mod.rs
1//! A module containing random generators objects.
2//!
3//! See [crate-level](`crate`) explanations.
4use crate::seeders::Seed;
5use std::error::Error;
6use std::fmt::{Display, Formatter};
7
8/// The number of children created when a generator is forked.
9#[derive(Debug, Copy, Clone)]
10pub struct ChildrenCount(pub usize);
11
12/// The number of bytes each child can generate, when a generator is forked.
13#[derive(Debug, Copy, Clone)]
14pub struct BytesPerChild(pub usize);
15
16/// A structure representing the number of bytes between two table indices.
17#[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq)]
18pub struct ByteCount(pub u128);
19
20/// An error occurring during a generator fork.
21#[derive(Debug)]
22pub enum ForkError {
23 ForkTooLarge,
24 ZeroChildrenCount,
25 ZeroBytesPerChild,
26}
27
28impl Display for ForkError {
29 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
30 match self {
31 ForkError::ForkTooLarge => {
32 write!(
33 f,
34 "The children generators would output bytes after the parent bound. "
35 )
36 }
37 ForkError::ZeroChildrenCount => {
38 write!(
39 f,
40 "The number of children in the fork must be greater than zero."
41 )
42 }
43 ForkError::ZeroBytesPerChild => {
44 write!(
45 f,
46 "The number of bytes per child must be greater than zero."
47 )
48 }
49 }
50 }
51}
52impl Error for ForkError {}
53
54/// A trait for cryptographically secure pseudo-random generators.
55///
56/// See the [crate-level](#crate) documentation for details.
57pub trait RandomGenerator: Iterator<Item = u8> {
58 /// The iterator over children generators, returned by `try_fork` in case of success.
59 type ChildrenIter: Iterator<Item = Self>;
60
61 /// Creates a new generator from a seed.
62 ///
63 /// This operation is usually costly to perform, as the aes round keys need to be generated from
64 /// the seed.
65 fn new(seed: Seed) -> Self;
66
67 /// Returns the number of bytes that can still be outputted by the generator before reaching its
68 /// bound.
69 ///
70 /// Note:
71 /// -----
72 ///
73 /// A fresh generator can generate 2¹³² bytes. Unfortunately, no rust integer type in is able
74 /// to encode such a large number. Consequently [`ByteCount`] uses the largest integer type
75 /// available to encode this value: the `u128` type. For this reason, this method does not
76 /// effectively return the number of remaining bytes, but instead
77 /// `min(2¹²⁸-1, remaining_bytes)`.
78 fn remaining_bytes(&self) -> ByteCount;
79
80 /// Returns the next byte of the stream, if the generator did not yet reach its bound.
81 fn next_byte(&mut self) -> Option<u8> {
82 self.next()
83 }
84
85 /// Tries to fork the generator into an iterator of `n_children` new generators, each able to
86 /// output `n_bytes` bytes.
87 ///
88 /// Note:
89 /// -----
90 ///
91 /// To be successful, the number of remaining bytes for the parent generator must be larger than
92 /// `n_children*n_bytes`.
93 fn try_fork(
94 &mut self,
95 n_children: ChildrenCount,
96 n_bytes: BytesPerChild,
97 ) -> Result<Self::ChildrenIter, ForkError>;
98}
99
100/// A trait extending [`RandomGenerator`] to the parallel iterators of `rayon`.
101#[cfg(feature = "parallel")]
102pub trait ParallelRandomGenerator: RandomGenerator + Send {
103 /// The iterator over children generators, returned by `par_try_fork` in case of success.
104 type ParChildrenIter: rayon::prelude::IndexedParallelIterator<Item = Self>;
105
106 /// Tries to fork the generator into a parallel iterator of `n_children` new generators, each
107 /// able to output `n_bytes` bytes.
108 ///
109 /// Note:
110 /// -----
111 ///
112 /// To be successful, the number of remaining bytes for the parent generator must be larger than
113 /// `n_children*n_bytes`.
114 fn par_try_fork(
115 &mut self,
116 n_children: ChildrenCount,
117 n_bytes: BytesPerChild,
118 ) -> Result<Self::ParChildrenIter, ForkError>;
119}
120
121mod aes_ctr;
122
123mod implem;
124pub use implem::*;
125
126#[cfg(test)]
127#[allow(unused)] // to please clippy when tests are not activated
128pub mod generator_generic_test {
129 use super::*;
130 use rand::Rng;
131
132 const REPEATS: usize = 1_000;
133
134 fn any_seed() -> impl Iterator<Item = Seed> {
135 std::iter::repeat_with(|| Seed(rand::thread_rng().gen()))
136 }
137
138 fn some_children_count() -> impl Iterator<Item = ChildrenCount> {
139 std::iter::repeat_with(|| ChildrenCount(rand::thread_rng().gen::<usize>() % 16 + 1))
140 }
141
142 fn some_bytes_per_child() -> impl Iterator<Item = BytesPerChild> {
143 std::iter::repeat_with(|| BytesPerChild(rand::thread_rng().gen::<usize>() % 128 + 1))
144 }
145
146 /// Checks that the PRNG roughly generates uniform numbers.
147 ///
148 /// To do that, we perform an histogram of the occurrences of each byte value, over a fixed
149 /// number of samples and check that the empirical probabilities of the bins are close to
150 /// the theoretical probabilities.
151 pub fn test_roughly_uniform<G: RandomGenerator>() {
152 // Number of bins to use for the histogram.
153 const N_BINS: usize = u8::MAX as usize + 1;
154 // Number of samples to use for the histogram.
155 let n_samples = 10_000_000_usize;
156 // Theoretical probability of a each bins.
157 let expected_prob: f64 = 1. / N_BINS as f64;
158 // Absolute error allowed on the empirical probabilities.
159 // This value was tuned to make the test pass on an arguably correct state of
160 // implementation. 10^-4 precision is arguably pretty fine for this rough test, but it would
161 // be interesting to improve this test.
162 let precision = 10f64.powi(-3);
163
164 for _ in 0..REPEATS {
165 // We instantiate a new generator.
166 let seed = any_seed().next().unwrap();
167 let mut generator = G::new(seed);
168 // We create a new histogram
169 let mut counts = [0usize; N_BINS];
170 // We fill the histogram.
171 for _ in 0..n_samples {
172 counts[generator.next_byte().unwrap() as usize] += 1;
173 }
174 // We check that the empirical probabilities are close enough to the theoretical one.
175 counts
176 .iter()
177 .map(|a| (*a as f64) / (n_samples as f64))
178 .for_each(|a| assert!((a - expected_prob).abs() < precision))
179 }
180 }
181
182 /// Checks that given a state and a key, the PRNG is determinist.
183 pub fn test_generator_determinism<G: RandomGenerator>() {
184 for _ in 0..REPEATS {
185 let seed = any_seed().next().unwrap();
186 let mut first_generator = G::new(seed);
187 let mut second_generator = G::new(seed);
188 for _ in 0..1024 {
189 assert_eq!(first_generator.next(), second_generator.next());
190 }
191 }
192 }
193
194 /// Checks that forks returns a bounded child, and that the proper number of bytes can be
195 /// generated.
196 pub fn test_fork_children<G: RandomGenerator>() {
197 for _ in 0..REPEATS {
198 let ((seed, n_children), n_bytes) = any_seed()
199 .zip(some_children_count())
200 .zip(some_bytes_per_child())
201 .next()
202 .unwrap();
203 let mut gen = G::new(seed);
204 let mut bounded = gen.try_fork(n_children, n_bytes).unwrap().next().unwrap();
205 assert_eq!(bounded.remaining_bytes(), ByteCount(n_bytes.0 as u128));
206 for _ in 0..n_bytes.0 {
207 bounded.next().unwrap();
208 }
209
210 // Assert we are at the bound
211 assert!(bounded.next().is_none());
212 }
213 }
214
215 /// Checks that a bounded prng returns none when exceeding the allowed number of bytes.
216 ///
217 /// To properly check for panic use `#[should_panic(expected = "expected test panic")]` as an
218 /// attribute on the test function.
219 pub fn test_bounded_none_should_panic<G: RandomGenerator>() {
220 let ((seed, n_children), n_bytes) = any_seed()
221 .zip(some_children_count())
222 .zip(some_bytes_per_child())
223 .next()
224 .unwrap();
225 let mut gen = G::new(seed);
226 let mut bounded = gen.try_fork(n_children, n_bytes).unwrap().next().unwrap();
227 assert_eq!(bounded.remaining_bytes(), ByteCount(n_bytes.0 as u128));
228 for _ in 0..n_bytes.0 {
229 assert!(bounded.next().is_some());
230 }
231
232 // One call too many, should panic
233 bounded.next().ok_or("expected test panic").unwrap();
234 }
235}