Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
truncated to 7-bits, the result is a value between 0 and 127 –  Richie Frame Jul 3 at 19:33

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
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. –  user4982 Jul 3 at 21:43
    
Yes, you are still taking the remaining $2^{256} \equiv 36 \pmod{100}$ outputs and trying to distribute them equally amongst 100 buckets. –  Stephen Touset Jul 3 at 22:19
    
@user4982: you are correct. In those few cases, you should find something new to hash and hope the hash is small enough. Fixed. –  Ross Millikan Jul 3 at 22:23
    
@RossMillikan That still fundamentally doesn't work. It's just a more abstract approach to "distribute 36 special cases into 100 buckets". –  Stephen Touset Jul 3 at 22:27
1  
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. –  Stephen Touset Jul 3 at 23:04

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

share|improve this answer

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

share|improve this answer
    
This only works if he doesn't require integers. –  Stephen Touset Jul 3 at 21:00
    
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. –  marstato Jul 3 at 21:36
2  
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. –  Stephen Touset Jul 3 at 21:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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