[PATCH v2] stdlib: Simplify arc4random_uniform
Yann Droneaud
ydroneaud@opteya.com
Tue Aug 2 12:08:32 GMT 2022
Hi,
Le 01/08/2022 à 21:20, Noah Goldstein a écrit :
>> diff --git a/stdlib/arc4random_uniform.c b/stdlib/arc4random_uniform.c
>> index 1326dfa593..5aa98d1c13 100644
>> --- a/stdlib/arc4random_uniform.c
>> +++ b/stdlib/arc4random_uniform.c
>>
>> uint32_t
>> __arc4random_uniform (uint32_t n)
>> {
>> @@ -57,83 +38,33 @@ __arc4random_uniform (uint32_t n)
>> + while (1)
>> {
>> + uint32_t value = __arc4random ();
>> +
>> + /* Return if the lower power of 2 minus 1 satisfy the condition. */
>> + uint32_t r = value & mask;
>> + if (r < n)
>> + return r;
>> +
>> + /* Otherwise check if remaining bits of entropy provides fits in the
>> + bound. */
>> + for (int bits_left = z; bits_left >= bits; bits_left -= bits)
>> + {
>> + value >>= bits;
> Can this just be shift by 1 and repeat (32 - z) times or does that
> introduce bias (not seeing exactly why it would)?
That was bothering me too, as I was thinking a rotation would be
possible instead of shift.
I posted the question
https://crypto.stackexchange.com/questions/101325/uniform-rejection-sampling-by-shifting-or-rotating-bits-from-csprng-output-safe
The answer: there's indeed a bias.
This explains why my attempt with rotation leads to dieharder
complaining. It was so obvious ... Damn
Regards.
--
Yann Droneaud
OPTEYA
More information about the Libc-alpha
mailing list