Estimating random number entropy for input into 256 bit hash

Question

Assuming a random number generation process outputs lots of numbers between 0-9. First I gathered up a bunch of the numbers, converted them to binary and created a bitmap.

Not so random as you can see! That must be why you shouldn't just use raw integers as random numbers in a computer program. Look what happens when the numbers are converted to binary:

0  00110000
1  00110001
2  00110010
3  00110011
4  00110100
5  00110101
6  00110110
7  00110111
8  00111000
9  00111001

As you can see the first 4 bits are always 0011 which is not very random. Even looking at the 5th bit that is not very random either. From 0-7 it is always a 0 bit and only for 8 and 9 is it a 1 bit.

What about the last 3 bits are they random?

0  000
1  001
2  010
3  011
4  100
5  101
6  110
7  111
8  000
9  001

It looks like there is all possible combinations of the 3 bits in the numbers 0-7 inclusive. However 8 and 9 bits are duplicates of 1 and 2. Does that matter? Should the numbers 8 and 9 be thrown away to remove bias?

I think the plan might be to run all these raw integers through a cryptographic hash such as SHA 256 then use that as a key. However what is the correct amount of raw integers to feed into the hash to get a quality 256 bit output? I assume I need 256 bits of input to get a good 256 bit output, yes?

If I do some back-of-the-envelope calculations I come up with:

3 bits of entropy per 8 bit (1 byte) number
256/3 = 85.33

This means I need to collect 85~ raw integers (682.67 bits) and feed them into the 256 bit hash. Does that sound about right?

Or would it be better to get the last 3 bits from each number until I have 256 bits of entropy, then convert that to hexadecimal and run that through the crypto hash? I think I've only seen a crypto hash algorithm take hexadecimal or text as input...

Answer 1

It is a little unclear, how you transformed all your numbers... e.g. how did you interpret your decimal numbers "as binary" and "create a bitmap"? Then you look at the binary representation and guess what.... and they are just the numbers 0-9 in binary and added on an static number (no idea where that came from).

Things to consider:

• Of course the numbers 0-9 do not have an integer sized entropy, this range is not of the form $2^{x}$. Actually it is $3.3219...$
• If your numbers are uniform distributed over 0-9, then evaluation of fixed bits will result in a loss of entropy or a loss of uniformity (or both).
• What is your actual goal? In the beginning you mention "in a computer program" and then later on "use that as a key". Random numbers serve a lot of purposes, and different tasks require different properties (and thus different PRNGs).

How to solve your problem?

• Let's assume you want 256 bit of entropy and your RNG is good enough to create cryptographic keys (if you don't know the difference, read up on this).
• If you do not want to "throw away" entropy, you can just calculate a large random number in the decimal system and use your RNG (let's call this $\Re$) for each digit. This way it is uniform distributed. You can do this e.g. by this formula: $r = \sum_{k=0}^{t}10^k\cdot\Re $. You have to choose $t$ large enough, that is covers at least the range from $0$ to $2^{256}-1$, which means $t \ge 77$. But now you $r$ is still uniform distributed in the "wrong range", because it can be greater than $2^{256}$.
• Now you can decide if you want to start over if the result is higher than that, this will result in a uniform distribution in the "correct range" since you don't change the distribution by favoring some values over others... you just start fresh for the wrong results.

• Or you can increase $t$ even more, and then calculate $r' = r \text{ mod }2^{256}$. This does not result in a perfect uniform distribution, but if the range for $r$ is a lot larger than $r'$, it is really close to uniform.

• Otherwise, you can also do the rejection sampling at the bit level (That's throwing away some results, so that others are still uniform to each other): Draw a number from 0 to 9 and if it is 8 or 9, ignore it and draw again. Now you can use the binary representation of the numbers 0-7 as 3 bit for the long binary result. Repeat this and concatenate the 3-bit blocks.

You can even combine these techniques to optimize the number of rejected results, but that's probably going too far, these simple solutions should work.

PS: Concerning your first conclusion

That must be why you shouldn't just use raw integers as random numbers in a computer program.

That statement is just not true. RNGs usually run on integers, and there are different RNGs for different tasks. What else should you use as random numbers? Floating point numbers are much worse to handle than integers, and even harder to actually proof statistical properties Therefore, RNGs use integers, because they are better than anything else, but the properties depend on the actual RNG. For example linear congruential generators and similar constructions are REALLY fast and have a long period, but their randomness has poor quality due to a large correlation of sequential elements. Linear feedback shift registers offer randomness of higher quality, but it is also possible to predict the stream from a short sequence of outputs. For statistical purposes the Mersenne Twister offers probably the best performance and high quality randomness.

But for cryptography, you need other properties (check the first link in this post). For actual computer programs: You should use the implementations in the standard libraries for secure PRNGs, e.g. SecureRandom in java.

Anyway, hashing is usually done to have the one-way property, s.t. you can not compute back to the original message/object/input/... E.g. if you have hashed values, you can compare if two items are the same, but nothing else. If you have to guess this item, you can't.

Answer 2

One thing you can do if you are not too concerned about losing some entropy is this:

For the numbers 0 through 9, divide them evenly into two groups. Assign a 0 bit to any number that occurs in the first group, and a 1 bit for any number that occurs in the second group. For example:

0 = 0
1 = 0
2 = 0
3 = 0
4 = 0
5 = 1
6 = 1
7 = 1
8 = 1
9 = 1

Or you might do something like this:

0 = 0
1 = 1
2 = 0
3 = 1
4 = 0
5 = 1
6 = 0
7 = 1
8 = 0
9 = 1

That will give you a uniform distribution of bits from the numbers 0 - 9. From there you can run 256 bits of that entropy into the cryptographic hash. Use a newer hash function such as Keccak or Skein. I know there are some hash libraries which allow a hexadecimal input so you might need to convert the input bits to hexadecimal.

Alternatively, depending on the quality of your entropy source, collect some more entropy bits and run them through the Von Nuemann extractor.

Take successive pairs of consecutive bits (non-overlapping) from the input stream. If the two bits match, no output is generated. If the bits differ, the value of the first bit is output.

The Von Neumann extractor can be shown to produce a uniform output even if the distribution of input bits is not uniform so long as each bit has the same probability of being one and there is no correlation between successive bits.

From my tests this process tends to produce an output of one third of the input. So you might need ~768 bits input to get a quality 256 bit key.

As always, test the output to make sure it passes randomness tests.