5
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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|$.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Hurricane Development Aug 4 '16 at 21:37
  • 1
    $\begingroup$ @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. $\endgroup$ – poncho Aug 5 '16 at 3:27
  • $\begingroup$ ahh I see. Awesome thank you so much for explaining. $\endgroup$ – Hurricane Development Aug 5 '16 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.