Does using modulo (%) affect quality of randomness?

Question

I'm writing a small script that generates random non-signed decimal integers within a certain range of values. I'm using GNU od, with the following command:

od /dev/hwrng --address-radix=n --read-bytes=4 --format=u4

/dev/hwrng is linked to a SoC thermal noise sensor (bcm2708 on Raspberry Pi), so it would return pure random bits. Once obtained a pure random integer from od, I would use the modulo operator (eg: % in C/C++) to restrict the range of values (eg: 96-127). I have some doubts:

1. Does modulo affect the quality of randomness, faking in some way the distribution of values?
2. I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon
3. Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of the question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo
4. Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG.

Answer 1

Let me begin by saying that if you have a hardware source of randomness, you don't need to be stingy with it.

1) Does modulo affect the quality of randomness, faking in some way the distribution of values?

Yes, it does. Or at any rate, it can --- see my answer to (3) below for more details. (I'm assuming by "quality of randomness", you specifically mean that each possible output should be equally likely, and every output should be independent of the others.)

For example, let's say that you wanted to generate a random integer between zero and three. If you did this by rolling a fair six-sided die (with sides labeled zero through five) and taking the result modulo four, what would the resulting distribution look like? Well, rolling either a 0 or a 4 would cause you to output 0, so the probability of outputting a 0 would be 2/6. On the other hand, the only way you'd output a 3 would be if you actually rolled a 3. So the probability of outputting a 3 would be 1/6. This means that you'd output a 0 twice as often as you'd output a 3.

2) I'm not sure whether bits gathered from /dev/hwrng can be considered truly random, but I guess so, since its entropy is based on a physical phenomenon.

The term "truly random" usually means by definition based on some physical source of randomness. But truly random doesn't imply uniformly random. In the example above, the output of a dice roll modulo four was truly random, but some outputs were more likely than others. Physical processes rarely produce a uniform distribution. They have biases -- for example, they might produce a normal distribution -- and often have state (leading to correlations).

It's possible to transform true randomness into uniform randomness using so-called randomness extractors (aka entropy extractors). It's possible that an extractor is already built into the bcm2708. But I'm not aware of any documentation that establishes this.

Various /dev/random implementations include (attempts at) randomness extractors internally. If you trust these algorithms, you can always read bits from /dev/hwrng into /dev/urandom, and then read from /dev/urandom.

3) Can I use 2 bytes instead of 4 bytes as int size, assuming that the needed range of generated values is low (eg: maximum value = 200)? I mean, probably 2 bytes are enough for small numbers. I ask this, because of the question (1): probably using bigger ranges in od results in higher quality of randomness when using modulo

Your intuition is correct here; if you're taking the result modulo some small number, then you can reduce bias to an acceptably small amount by using a really large range of numbers to begin with.

Concretely, if you start with a (uniform) random number in $\{0, 1, \ldots, N - 1\}$ and take the result modulo n, the result will differ from a uniform distribution by statistical distance of less than $(N \mod n)/N$. This is a useful measure because statistical distance is in turn an upperbound on how much you're increasing an attacker's probability of mounting a successful attack. So if you're protecting nuclear launch codes, you'd probably want to keep $(N \mod n)/N < 2^{-80}$. If you're protecting against SSH access to your media server, $(N \mod n)/N < 2^{-30}$ is probably a comfortable security margin.

Note than if N is divisible by n, there's no bias whatsoever introduced during this step. In your context, N will be a power of two (either $N = 2^{16}$ if you use two bytes, or $N = 2^{32}$ if you use four). So if n is a smaller power of two, you're good.

4) Is using /dev/hwrng only for the seed value still true randomness? I would use the default PHP rand() as PRNG

From the PHP documentation:

This function [rand()] does not generate cryptographically secure values, and should not be used for cryptographic purposes. If you need a cryptographically secure value, consider using openssl_random_pseudo_bytes() instead.

To answer your more general question, though: No. Given a 128-bit seed, it's mathematically impossible to generate more than 128 bits of "true" randomness (as measured by, e.g., min-entropy). But: Given a 128-bit seed and a cryptographically secure PRNG, this doesn't really matter. A 128 bit seed is plenty for all practical purposes. "True randomness" doesn't really gain you anything after that point.

Answer 2

I once gave this some thought and came up with this:

1. Determine the number of values in your range. For example -7 to 14, which provides 22 values.

2. Create constant num_values = 22

3. Create constant min_range_value=-7

4. Find the largest common multiple of your quantity of values less than unsigned $2^{64}$

   $$(2^{64})/22=838488366986797800.72727272727$$

   Discard everything to the right of the decimal. Assign this to the constant:

$$\text{max_usable_value}=838488366986797800$$

4. Begin retrieving values from your 64 bit unsigned random data source.

5. execute:

   do{
       retrieved_value=  your_lang_random_retrieval_func()
   } While(retrieved_value less than max_usable_value)`
   

6. value_in_range= (retrived_value % num_values) + min_range_value

Now use value_in_range and be assured that large quantities will have the same evenness of distribution as your random source has, and WILL NOT have a bias due to the difference in number bases and difference in the range of your source.