# Cryptographic random number on interval $[0,n]$ from bytes

I really like this answer: Creating a small number from a random octet string

While this works, is it safe to generate random number like so?

1. I am looking for a number on interval $[0,203]$
2. Generate crypto random secure 8 bits
3. convert to a decimal variable $d$
4. final answer $=\frac{d}{255}* 203$

Is this safe and does it work? Is it better or worse (maybe performance wise) than the answer in the other SE post?

If by safe you mean you get a uniformly random number in the interval $[0,203]$ then, no.

Consider that $d$ is sampled in the interval $[0, 255]$ uniformly at random. On the other hand the number you are sampling (let us call it $r$) is in the interval $[0,203]$. There are then $256$ possibilities for $d$ and $204$ possibilities for $r$. Your sampling method maps each of the possible values for $d$ to one of the possible values for $r$. Since $204$ does not divide $256$ there must be some values for $r$ more likely to be drawn than others.

In other words, since there cannot be an equal amount of values for $d$ mapping to each possible value of $r$ some values of $r$ must be more likely to be drawn.

Note that this argument holds for any function from $[0,255]$ to $[0,203]$. Or more generally any function mapping from a set $D$ to $R$ so that $|R|$ does not divide $|D|$.

Is this safe and does it work?

Well, it works in the sense that it doesn't pagefault or anything; however its output will be strongly biased. When you think about it, it takes a value $d$ between 0 and 255, and based on that input, outputs a value between 0 and 203; that means that, for at least least 52 pairs of $d$ values will result in the same output, and so those output values will happen with significantly more probability than expected.

The post you linked gave several viable options; I will second those and add one further one (which doesn't give a precisely uniform distribution, but one that is close enough):

The general idea is to generate a (say) 64 bit random number $r$, and compute $r % 204$, and output that. Again, this won't be exactly uniform; however an observer would need circa $2^{128}$ outputs before he can distinguish it from random, and so it's pretty good.

And, if you're afraid of the bignum math, actually it's fairly simple (given a 16 bit modulo an 8 bit operation); here's some simple pseudocode:

uint_8 r = 0;
for (i=0; i<8; i))
uint_16 temp = (256 * r + crypto_rng());
/* We assume that crypto_rng generates 8 bits */
r = temp % 204;
/* result in r */


It does use up more random bits than other methods; however it is constant time (assuming the modulo operation is constant time), and that can be important.

• "for at least 52 pairs of d values will result in the same output" How? It's creating basically a decimal then multiplying it by the max number I want. I just don't get the 52 values thing. – Hurricane Development Aug 4 '16 at 21:37
• @HurricaneDevelopment: let us assume that you're doing simple round down; then if $d$ is 0, then the output is 0, if $d$ is 1, then $d / 255 * 203 = 0.796078...$, which rounds down to 0; hence we have two different $d$ inputs which both generate 0; in contrast, you'll output a 1 only if $d$ is 2. – poncho Aug 5 '16 at 3:27
• ahh I see. Awesome thank you so much for explaining. – Hurricane Development Aug 5 '16 at 4:35