crypto_bigint/uint/
rand.rs

1//! Random number generator support
2
3use super::{Uint, Word};
4use crate::{Encoding, Limb, NonZero, Random, RandomBits, RandomBitsError, RandomMod, Zero};
5use rand_core::RngCore;
6use subtle::ConstantTimeLess;
7
8impl<const LIMBS: usize> Random for Uint<LIMBS> {
9    fn random(mut rng: &mut (impl RngCore + ?Sized)) -> Self {
10        let mut limbs = [Limb::ZERO; LIMBS];
11
12        for limb in &mut limbs {
13            *limb = Limb::random(&mut rng)
14        }
15
16        limbs.into()
17    }
18}
19
20/// Fill the given limbs slice with random bits.
21///
22/// NOTE: Assumes that the limbs in the given slice are zeroed!
23pub(crate) fn random_bits_core(
24    rng: &mut (impl RngCore + ?Sized),
25    zeroed_limbs: &mut [Limb],
26    bit_length: u32,
27) -> Result<(), RandomBitsError> {
28    if bit_length == 0 {
29        return Ok(());
30    }
31
32    let buffer: Word = 0;
33    let mut buffer = buffer.to_be_bytes();
34
35    let nonzero_limbs = bit_length.div_ceil(Limb::BITS) as usize;
36    let partial_limb = bit_length % Limb::BITS;
37    let mask = Word::MAX >> ((Word::BITS - partial_limb) % Word::BITS);
38
39    for i in 0..nonzero_limbs - 1 {
40        rng.try_fill_bytes(&mut buffer)
41            .map_err(RandomBitsError::RandCore)?;
42        zeroed_limbs[i] = Limb(Word::from_be_bytes(buffer));
43    }
44
45    rng.try_fill_bytes(&mut buffer)
46        .map_err(RandomBitsError::RandCore)?;
47    zeroed_limbs[nonzero_limbs - 1] = Limb(Word::from_be_bytes(buffer) & mask);
48
49    Ok(())
50}
51
52impl<const LIMBS: usize> RandomBits for Uint<LIMBS> {
53    fn try_random_bits(
54        rng: &mut (impl RngCore + ?Sized),
55        bit_length: u32,
56    ) -> Result<Self, RandomBitsError> {
57        Self::try_random_bits_with_precision(rng, bit_length, Self::BITS)
58    }
59
60    fn try_random_bits_with_precision(
61        rng: &mut (impl RngCore + ?Sized),
62        bit_length: u32,
63        bits_precision: u32,
64    ) -> Result<Self, RandomBitsError> {
65        if bits_precision != Self::BITS {
66            return Err(RandomBitsError::BitsPrecisionMismatch {
67                bits_precision,
68                integer_bits: Self::BITS,
69            });
70        }
71        if bit_length > Self::BITS {
72            return Err(RandomBitsError::BitLengthTooLarge {
73                bit_length,
74                bits_precision,
75            });
76        }
77        let mut limbs = [Limb::ZERO; LIMBS];
78        random_bits_core(rng, &mut limbs, bit_length)?;
79        Ok(Self::from(limbs))
80    }
81}
82
83impl<const LIMBS: usize> RandomMod for Uint<LIMBS> {
84    fn random_mod(rng: &mut (impl RngCore + ?Sized), modulus: &NonZero<Self>) -> Self {
85        let mut n = Self::ZERO;
86        random_mod_core(rng, &mut n, modulus, modulus.bits_vartime());
87        n
88    }
89}
90
91/// Generic implementation of `random_mod` which can be shared with `BoxedUint`.
92// TODO(tarcieri): obtain `n_bits` via a trait like `Integer`
93pub(super) fn random_mod_core<T>(
94    rng: &mut (impl RngCore + ?Sized),
95    n: &mut T,
96    modulus: &NonZero<T>,
97    n_bits: u32,
98) where
99    T: AsMut<[Limb]> + AsRef<[Limb]> + ConstantTimeLess + Zero,
100{
101    #[cfg(target_pointer_width = "64")]
102    let mut next_word = || rng.next_u64();
103    #[cfg(target_pointer_width = "32")]
104    let mut next_word = || rng.next_u32();
105
106    let n_limbs = n_bits.div_ceil(Limb::BITS) as usize;
107
108    let hi_word_modulus = modulus.as_ref().as_ref()[n_limbs - 1].0;
109    let mask = !0 >> hi_word_modulus.leading_zeros();
110    let mut hi_word = next_word() & mask;
111
112    loop {
113        while hi_word > hi_word_modulus {
114            hi_word = next_word() & mask;
115        }
116        // Set high limb
117        n.as_mut()[n_limbs - 1] = Limb::from_le_bytes(hi_word.to_le_bytes());
118        // Set low limbs
119        for i in 0..n_limbs - 1 {
120            // Need to deserialize from little-endian to make sure that two 32-bit limbs
121            // deserialized sequentially are equal to one 64-bit limb produced from the same
122            // byte stream.
123            n.as_mut()[i] = Limb::from_le_bytes(next_word().to_le_bytes());
124        }
125        // If the high limb is equal to the modulus' high limb, it's still possible
126        // that the full uint is too big so we check and repeat if it is.
127        if n.ct_lt(modulus).into() {
128            break;
129        }
130        hi_word = next_word() & mask;
131    }
132}
133
134#[cfg(test)]
135mod tests {
136    use crate::{Limb, NonZero, RandomBits, RandomMod, U256};
137    use rand_chacha::ChaCha8Rng;
138    use rand_core::SeedableRng;
139
140    #[test]
141    fn random_mod() {
142        let mut rng = ChaCha8Rng::seed_from_u64(1);
143
144        // Ensure `random_mod` runs in a reasonable amount of time
145        let modulus = NonZero::new(U256::from(42u8)).unwrap();
146        let res = U256::random_mod(&mut rng, &modulus);
147
148        // Check that the value is in range
149        assert!(res < U256::from(42u8));
150
151        // Ensure `random_mod` runs in a reasonable amount of time
152        // when the modulus is larger than 1 limb
153        let modulus = NonZero::new(U256::from(0x10000000000000001u128)).unwrap();
154        let res = U256::random_mod(&mut rng, &modulus);
155
156        // Check that the value is in range
157        assert!(res < U256::from(0x10000000000000001u128));
158    }
159
160    #[test]
161    fn random_bits() {
162        let mut rng = ChaCha8Rng::seed_from_u64(1);
163
164        let lower_bound = 16;
165
166        // Full length of the integer
167        let bit_length = U256::BITS;
168        for _ in 0..10 {
169            let res = U256::random_bits(&mut rng, bit_length);
170            assert!(res > (U256::ONE << (bit_length - lower_bound)));
171        }
172
173        // A multiple of limb size
174        let bit_length = U256::BITS - Limb::BITS;
175        for _ in 0..10 {
176            let res = U256::random_bits(&mut rng, bit_length);
177            assert!(res > (U256::ONE << (bit_length - lower_bound)));
178            assert!(res < (U256::ONE << bit_length));
179        }
180
181        // A multiple of 8
182        let bit_length = U256::BITS - Limb::BITS - 8;
183        for _ in 0..10 {
184            let res = U256::random_bits(&mut rng, bit_length);
185            assert!(res > (U256::ONE << (bit_length - lower_bound)));
186            assert!(res < (U256::ONE << bit_length));
187        }
188
189        // Not a multiple of 8
190        let bit_length = U256::BITS - Limb::BITS - 8 - 3;
191        for _ in 0..10 {
192            let res = U256::random_bits(&mut rng, bit_length);
193            assert!(res > (U256::ONE << (bit_length - lower_bound)));
194            assert!(res < (U256::ONE << bit_length));
195        }
196
197        // One incomplete limb
198        let bit_length = 7;
199        for _ in 0..10 {
200            let res = U256::random_bits(&mut rng, bit_length);
201            assert!(res < (U256::ONE << bit_length));
202        }
203
204        // Zero bits
205        let bit_length = 0;
206        for _ in 0..10 {
207            let res = U256::random_bits(&mut rng, bit_length);
208            assert_eq!(res, U256::ZERO);
209        }
210    }
211}
crypto_bigint/uint/rand.rs

crypto_bigint/uint/
rand.rs
