0
$\begingroup$

I want to calculate a random number (1 to 6) from the output of sha256. Can I assurance the probability of 6 abilities is the same?

$\endgroup$
4
$\begingroup$

The approximate way

You don't need to be perfectly even if you can make the unevenness small enough to be undetectable. So you can realistically do this: take the first 128 bits (16 bytes) from the SHA-256 output (or more, if you like), read them in as an unsigned bignum (arbitrary precision integer) using your library of choice, take the remainder modulo 6, and add one. The distribution will not be even—1 will be very slightly more likely than 6—but not distinguishable in practice from an even distribution. The probability of picking 1 is:

$$ {\lfloor 2^{128} \div 6 \rfloor + 1 \over{2^{128}}} $$

...which Wolfram Alpha tells me is about:

$$ 0.166666666666666666666666666666666666667646245292351906256... $$

And the probability of picking 6 is:

$$ {\lfloor 2^{128} \div 6 \rfloor \over{2^{128}}} $$

...which is about this much:

$$ 0.166666666666666666666666666666666666664707509415296187486... $$

These values are only $2^{-128}$ apart, as you can tell algebraically from the expressions above. Good enough for cryptographic purposes.

NIST Special Publication 800-185 (SHA-3 Derived Functions) recommends a similar method for hashing with SHAKE or other variable length output functions into an arbitrary integer range. SP 800-90Ar1 (Recommendation for Random Number Generation Using Deterministic Random Bit Generators), in Section A.5.3, recommends this method as well.

The exact way

Looping over the unsigned bytes in the SHA-256 result byte array, at each step:

  1. If result[i] % 8 is less than six, return (result[i] % 8) + 1;
  2. Otherwise, if (result[i] >> 3) % 8 is less than six, return ((result[i] >> 3) % 8) + 1;
  3. Otherwise, continue on to the next iteration of the loop;
  4. If you looped through the whole thing, be very suspicious you did something wrong, and if you didn't (!) assign result := sha256(result) and try again from the top.

Whatever number is returned, it is equally likely as all the other five.

On any given iteration, the chance that iteration will return is 75%, so with 64 attempts, the probability that none of them will return is $(1 - 0.75)^{64} = (2^{-2})^{64} = 2^{-128}$. And if that happens you hit step #4.

$\endgroup$
  • 2
    $\begingroup$ That's a weird reference. It is called the Simple Modular Method in Recommendation for Random Number Generation Using Deterministic Random Bit Generators, section A.5.3. Why are you only using 128 bits instead of the full 256? That's a bit two dicey for me ;) $\endgroup$ – Maarten Bodewes Dec 13 '19 at 3:42
  • $\begingroup$ @Maarten-reinstateMonica I just figure that 128 bits is strong enough, but as you point out, you can always use the full 256 bits. $\endgroup$ – Luis Casillas Dec 13 '19 at 17:20
  • $\begingroup$ Why didn't you use $128 + \lceil\log_2(6)\rceil$ bits? 🙃 -- But also: using more bits makes the remainder operation take longer. Not that it is matters here. This is a case where the "exact" method is faster than the "approximate" one $\endgroup$ – Future Security Dec 13 '19 at 20:24
  • $\begingroup$ @FutureSecurity: Because, meh, 128 bits is a nicer number than 131 bits. 🤷‍♂️ $\endgroup$ – Luis Casillas Dec 14 '19 at 0:24
  • $\begingroup$ function find(result) { for (var i = 0; i < result.length; i++) { if (result[i]%8 < 6) { return result[i]%8 + 1; } else if (((result[i] % 8) >> 3) < 6) { return ((result[i] % 8) >> 3) + 1; } } return (find(sha256(result, { asBytes: true }))); } I'm using the exact way of you. And this is my statistic about appearances of result = 1 2 3 4 5 6 after run 1000 times: 406 118 124 121 113 118. Appearances's rate of 1 is much more. $\endgroup$ – Công Nguyễn Dec 14 '19 at 4:02

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.