11
$\begingroup$

Is it mathematically possible to take a SHA256 hash and turn it into a 0-99 number where each number in 0-99 range is equally likely to be picked?

As a 256 bit hash means the highest value possible is 2^256, this is not a nice or "round" number for the purposes of simplifying a hash down to ranges more natural for humans.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ truncated to 7-bits, the result is a value between 0 and 127 $\endgroup$
    – Richie Frame
    Jul 3, 2014 at 19:33

3 Answers 3

Reset to default
16
$\begingroup$

If you mean exactly as likely, no, because the number of possible hashes is not a multiple of $100$. This is assuming all the hashes are exactly equally likely. You can come very close just by taking $SHA256 hash \pmod {100}$ This will be within one part in $\frac {2^{256}}{100}$, which is a very small number. If you want truly equal, check that the hash is in the range $[0,100\lfloor \frac {2^{256}}{100}\rfloor)$ and take it $\pmod {100}$ If it is above that, hash something else and try again. Your odds of failing the check are very small, and your odds of failing twice are very small.

In the general case: if one wants a result in the range $0..n\text{-}1$ then use $\bmod n$ and discard if the output $>n\lfloor \frac {2^{256}}{n}\rfloor$ and try another input. This is called the discarding technique; it is commonly used to extract a number in a range from a (pseudo) random number generator.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I have tested all possible SHA-256 hashes which are larger than $100\lfloor \frac {2^{256}}{100}\rfloor$. None of them produce number larger than $100\lfloor \frac {2^{256}}{100}\rfloor$ when hashed the second time. However, double hashing does not remove the bias, the biased numbers are just different. $\endgroup$
    – user4982
    Jul 3, 2014 at 21:43
  • $\begingroup$ Yes, you are still taking the remaining $2^{256} \equiv 36 \pmod{100}$ outputs and trying to distribute them equally amongst 100 buckets. $\endgroup$
    – Stephen Touset
    Jul 3, 2014 at 22:19
  • $\begingroup$ @user4982: you are correct. In those few cases, you should find something new to hash and hope the hash is small enough. Fixed. $\endgroup$
    – Ross Millikan
    Jul 3, 2014 at 22:23
  • $\begingroup$ @RossMillikan That still fundamentally doesn't work. It's just a more abstract approach to "distribute 36 special cases into 100 buckets". $\endgroup$
    – Stephen Touset
    Jul 3, 2014 at 22:27
  • 1
    $\begingroup$ Ah, I see. It only works in the event that the SHA-256 inputs are arbitrary. If you're hashing something out of your control (e.g., the contents of a file), there's nothing you can do. $\endgroup$
    – Stephen Touset
    Jul 3, 2014 at 23:04
4
$\begingroup$

No, it is not possible to get exactly equal probabilities for a deterministic mapping from all 256-bit numbers to the range 0-99.

However, you can ask whether it matters, since a bias on the order of $2^{-256}$ is undetectable. A mapping that took the 256-bit number modulo 100 and refused the inputs less than $2^{256} \bmod 100$ would be unbiased and would never fail in practice.

You can also get the next best thing – probabilities that are not exactly equal, but for which no one knows which of the numbers 0-99 is biased which way. For example, you can define the mapping using another SHA-256 iteration like so:

  1. Take the SHA-256 hash of the initial hash concatenated with the number 1 (e.g. in ASCII): $H(h||1)$. If this is at least $2^{256} \bmod 100$, return it modulo 100.
  2. Otherwise increment the counter and calculate $H(h||2)$, doing the same check.
  3. Continue as long as necessary (i.e. in practice you never need to go further than the first step).

Since we don't know which $h$ (if any) produce $H(h||1) < 36$, we don't know the resulting $H(h||2)$.

Improve this answer
$\endgroup$
-1
$\begingroup$

You could simply just XOR all the bytes of the hash to one single byte (lets call it $b$ for now): $b = hash_0 \oplus hash_1 \oplus ... \oplus hash_{31}$. $b \in [0, 255]$. Calculate $b' = b / 2.55$. $b' \in [0, 100]$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This only works if he doesn't require integers. $\endgroup$
    – Stephen Touset
    Jul 3, 2014 at 21:00
  • $\begingroup$ If the values of the bytes of SHA256-hashes are distributed evenly $b'$ should also be distributed evenly in $[0, 100]$. Rounding $b'$ should not change too much about it. $\endgroup$
    – marstato
    Jul 3, 2014 at 21:36
  • 5
    $\begingroup$ The OP is looking for a mechanism "where each number in 0-99 range is equally likely to be picked". The output of your algorithm is easily distinguishable from random, because some digits will be chosen more or less likely than the others due to aliasing introduced by converting to integers. $\endgroup$
    – Stephen Touset
    Jul 3, 2014 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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