crypto_bigint_syncless/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, TryRngCore};
6use subtle::ConstantTimeLess;
7
8impl<const LIMBS: usize> Random for Uint<LIMBS> {
9    fn try_random<R: TryRngCore + ?Sized>(rng: &mut R) -> Result<Self, R::Error> {
10        let mut limbs = [Limb::ZERO; LIMBS];
11
12        for limb in &mut limbs {
13            *limb = Limb::try_random(rng)?
14        }
15
16        Ok(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!
23///
24/// When combined with a platform-independent "4-byte sequential" `rng`, this function is
25/// platform-independent. We consider an RNG "`X`-byte sequential" whenever
26/// `rng.fill_bytes(&mut bytes[..i]); rng.fill_bytes(&mut bytes[i..])` constructs the same `bytes`,
27/// as long as `i` is a multiple of `X`.
28/// Note that the `TryRngCore` trait does _not_ require this behaviour from `rng`.
29pub(crate) fn random_bits_core<R: TryRngCore + ?Sized>(
30    rng: &mut R,
31    zeroed_limbs: &mut [Limb],
32    bit_length: u32,
33) -> Result<(), RandomBitsError<R::Error>> {
34    if bit_length == 0 {
35        return Ok(());
36    }
37
38    let buffer: Word = 0;
39    let mut buffer = buffer.to_be_bytes();
40
41    let nonzero_limbs = bit_length.div_ceil(Limb::BITS) as usize;
42    let partial_limb = bit_length % Limb::BITS;
43    let mask = Word::MAX >> ((Word::BITS - partial_limb) % Word::BITS);
44
45    for i in 0..nonzero_limbs - 1 {
46        rng.try_fill_bytes(&mut buffer)
47            .map_err(RandomBitsError::RandCore)?;
48        zeroed_limbs[i] = Limb(Word::from_le_bytes(buffer));
49    }
50
51    // This algorithm should sample the same number of random bytes, regardless of the pointer width
52    // of the target platform. To this end, special attention has to be paid to the case where
53    // bit_length - 1 < 32 mod 64. Bit strings of that size can be represented using `2X+1` 32-bit
54    // words or `X+1` 64-bit words. Note that 64*(X+1) - 32*(2X+1) = 32. Hence, if we sample full
55    // words only, a 64-bit platform will sample 32 bits more than a 32-bit platform. We prevent
56    // this by forcing both platforms to only sample 4 bytes for the last word in this case.
57    let slice = if partial_limb > 0 && partial_limb <= 32 {
58        // Note: we do not have to zeroize the second half of the buffer, as the mask will take
59        // care of this in the end.
60        &mut buffer[0..4]
61    } else {
62        buffer.as_mut_slice()
63    };
64
65    rng.try_fill_bytes(slice)
66        .map_err(RandomBitsError::RandCore)?;
67    zeroed_limbs[nonzero_limbs - 1] = Limb(Word::from_le_bytes(buffer) & mask);
68
69    Ok(())
70}
71
72impl<const LIMBS: usize> RandomBits for Uint<LIMBS> {
73    fn try_random_bits<R: TryRngCore + ?Sized>(
74        rng: &mut R,
75        bit_length: u32,
76    ) -> Result<Self, RandomBitsError<R::Error>> {
77        Self::try_random_bits_with_precision(rng, bit_length, Self::BITS)
78    }
79
80    fn try_random_bits_with_precision<R: TryRngCore + ?Sized>(
81        rng: &mut R,
82        bit_length: u32,
83        bits_precision: u32,
84    ) -> Result<Self, RandomBitsError<R::Error>> {
85        if bits_precision != Self::BITS {
86            return Err(RandomBitsError::BitsPrecisionMismatch {
87                bits_precision,
88                integer_bits: Self::BITS,
89            });
90        }
91        if bit_length > Self::BITS {
92            return Err(RandomBitsError::BitLengthTooLarge {
93                bit_length,
94                bits_precision,
95            });
96        }
97        let mut limbs = [Limb::ZERO; LIMBS];
98        random_bits_core(rng, &mut limbs, bit_length)?;
99        Ok(Self::from(limbs))
100    }
101}
102
103impl<const LIMBS: usize> RandomMod for Uint<LIMBS> {
104    fn random_mod<R: RngCore + ?Sized>(rng: &mut R, modulus: &NonZero<Self>) -> Self {
105        let mut n = Self::ZERO;
106        let Ok(()) = random_mod_core(rng, &mut n, modulus, modulus.bits_vartime());
107        n
108    }
109
110    fn try_random_mod<R: TryRngCore + ?Sized>(
111        rng: &mut R,
112        modulus: &NonZero<Self>,
113    ) -> Result<Self, R::Error> {
114        let mut n = Self::ZERO;
115        random_mod_core(rng, &mut n, modulus, modulus.bits_vartime())?;
116        Ok(n)
117    }
118}
119
120/// Generic implementation of `random_mod` which can be shared with `BoxedUint`.
121// TODO(tarcieri): obtain `n_bits` via a trait like `Integer`
122pub(super) fn random_mod_core<T, R: TryRngCore + ?Sized>(
123    rng: &mut R,
124    n: &mut T,
125    modulus: &NonZero<T>,
126    n_bits: u32,
127) -> Result<(), R::Error>
128where
129    T: AsMut<[Limb]> + AsRef<[Limb]> + ConstantTimeLess + Zero,
130{
131    #[cfg(target_pointer_width = "64")]
132    let mut next_word = || rng.try_next_u64();
133    #[cfg(target_pointer_width = "32")]
134    let mut next_word = || rng.try_next_u32();
135
136    let n_limbs = n_bits.div_ceil(Limb::BITS) as usize;
137
138    let hi_word_modulus = modulus.as_ref().as_ref()[n_limbs - 1].0;
139    let mask = !0 >> hi_word_modulus.leading_zeros();
140    let mut hi_word = next_word()? & mask;
141
142    loop {
143        while hi_word > hi_word_modulus {
144            hi_word = next_word()? & mask;
145        }
146        // Set high limb
147        n.as_mut()[n_limbs - 1] = Limb::from_le_bytes(hi_word.to_le_bytes());
148        // Set low limbs
149        for i in 0..n_limbs - 1 {
150            // Need to deserialize from little-endian to make sure that two 32-bit limbs
151            // deserialized sequentially are equal to one 64-bit limb produced from the same
152            // byte stream.
153            n.as_mut()[i] = Limb::from_le_bytes(next_word()?.to_le_bytes());
154        }
155        // If the high limb is equal to the modulus' high limb, it's still possible
156        // that the full uint is too big so we check and repeat if it is.
157        if n.ct_lt(modulus).into() {
158            break;
159        }
160        hi_word = next_word()? & mask;
161    }
162    Ok(())
163}
164
165#[cfg(test)]
166mod tests {
167    use crate::uint::rand::random_bits_core;
168    use crate::{Limb, NonZero, Random, RandomBits, RandomMod, U256, U1024, Uint};
169    use rand_chacha::ChaCha8Rng;
170    use rand_core::{RngCore, SeedableRng};
171
172    const RANDOM_OUTPUT: U1024 = Uint::from_be_hex(concat![
173        "A484C4C693EECC47C3B919AE0D16DF2259CD1A8A9B8EA8E0862878227D4B40A3",
174        "C54302F2EB1E2F69E17653A37F1BCC44277FA208E6B31E08CDC4A23A7E88E660",
175        "EF781C7DD2D368BAD438539D6A2E923C8CAE14CB947EB0BDE10D666732024679",
176        "0F6760A48F9B887CB2FB0D3281E2A6E67746A55FBAD8C037B585F767A79A3B6C"
177    ]);
178
179    /// Construct a 4-sequential `rng`, i.e., an `rng` such that
180    /// `rng.fill_bytes(&mut buffer[..x]); rng.fill_bytes(&mut buffer[x..])` will construct the
181    /// same `buffer`, for `x` any in `0..buffer.len()` that is `0 mod 4`.
182    fn get_four_sequential_rng() -> ChaCha8Rng {
183        ChaCha8Rng::seed_from_u64(0)
184    }
185
186    /// Make sure the random value constructed is consistent across platforms
187    #[test]
188    fn random_platform_independence() {
189        let mut rng = get_four_sequential_rng();
190        assert_eq!(U1024::random(&mut rng), RANDOM_OUTPUT);
191    }
192
193    #[test]
194    fn random_mod() {
195        let mut rng = ChaCha8Rng::seed_from_u64(1);
196
197        // Ensure `random_mod` runs in a reasonable amount of time
198        let modulus = NonZero::new(U256::from(42u8)).unwrap();
199        let res = U256::random_mod(&mut rng, &modulus);
200
201        // Check that the value is in range
202        assert!(res < U256::from(42u8));
203
204        // Ensure `random_mod` runs in a reasonable amount of time
205        // when the modulus is larger than 1 limb
206        let modulus = NonZero::new(U256::from(0x10000000000000001u128)).unwrap();
207        let res = U256::random_mod(&mut rng, &modulus);
208
209        // Check that the value is in range
210        assert!(res < U256::from(0x10000000000000001u128));
211    }
212
213    #[test]
214    fn random_bits() {
215        let mut rng = ChaCha8Rng::seed_from_u64(1);
216
217        let lower_bound = 16;
218
219        // Full length of the integer
220        let bit_length = U256::BITS;
221        for _ in 0..10 {
222            let res = U256::random_bits(&mut rng, bit_length);
223            assert!(res > (U256::ONE << (bit_length - lower_bound)));
224        }
225
226        // A multiple of limb size
227        let bit_length = U256::BITS - Limb::BITS;
228        for _ in 0..10 {
229            let res = U256::random_bits(&mut rng, bit_length);
230            assert!(res > (U256::ONE << (bit_length - lower_bound)));
231            assert!(res < (U256::ONE << bit_length));
232        }
233
234        // A multiple of 8
235        let bit_length = U256::BITS - Limb::BITS - 8;
236        for _ in 0..10 {
237            let res = U256::random_bits(&mut rng, bit_length);
238            assert!(res > (U256::ONE << (bit_length - lower_bound)));
239            assert!(res < (U256::ONE << bit_length));
240        }
241
242        // Not a multiple of 8
243        let bit_length = U256::BITS - Limb::BITS - 8 - 3;
244        for _ in 0..10 {
245            let res = U256::random_bits(&mut rng, bit_length);
246            assert!(res > (U256::ONE << (bit_length - lower_bound)));
247            assert!(res < (U256::ONE << bit_length));
248        }
249
250        // One incomplete limb
251        let bit_length = 7;
252        for _ in 0..10 {
253            let res = U256::random_bits(&mut rng, bit_length);
254            assert!(res < (U256::ONE << bit_length));
255        }
256
257        // Zero bits
258        let bit_length = 0;
259        for _ in 0..10 {
260            let res = U256::random_bits(&mut rng, bit_length);
261            assert_eq!(res, U256::ZERO);
262        }
263    }
264
265    /// Make sure the random_bits output is consistent across platforms
266    #[test]
267    fn random_bits_platform_independence() {
268        let mut rng = get_four_sequential_rng();
269
270        let bit_length = 989;
271        let mut val = U1024::ZERO;
272        random_bits_core(&mut rng, val.as_mut_limbs(), bit_length).expect("safe");
273
274        assert_eq!(
275            val,
276            RANDOM_OUTPUT.bitand(&U1024::ONE.shl(bit_length).wrapping_sub(&Uint::ONE))
277        );
278
279        // Test that the RNG is in the same state
280        let mut state = [0u8; 16];
281        rng.fill_bytes(&mut state);
282
283        assert_eq!(
284            state,
285            [
286                198, 196, 132, 164, 240, 211, 223, 12, 36, 189, 139, 48, 94, 1, 123, 253
287            ]
288        );
289    }
290
291    /// Test that random bytes are sampled consecutively.
292    #[test]
293    fn random_bits_4_bytes_sequential() {
294        // Test for multiples of 4 bytes, i.e., multiples of 32 bits.
295        let bit_lengths = [0, 32, 64, 128, 192, 992];
296
297        for bit_length in bit_lengths {
298            let mut rng = get_four_sequential_rng();
299            let mut first = U1024::ZERO;
300            let mut second = U1024::ZERO;
301            random_bits_core(&mut rng, first.as_mut_limbs(), bit_length).expect("safe");
302            random_bits_core(&mut rng, second.as_mut_limbs(), U1024::BITS - bit_length)
303                .expect("safe");
304            assert_eq!(second.shl(bit_length).bitor(&first), RANDOM_OUTPUT);
305        }
306    }
307}
crypto_bigint_syncless/uint/rand.rs

crypto_bigint_syncless/uint/
rand.rs
