2
$\begingroup$

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.

enter image description here

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

$\endgroup$
10
  • $\begingroup$ The last three bits are NOT uniformly distributed. 000 and 001 appear twice whereas the others appear only once. If you use these directly to build up a 256-bit bitstring you have a weakness. Either feed them into SHA-256, assuming around (but not exactly) 3 bits of entropy per number (you can calculate the exact entropy with Shannon's entropy equation) and collect the final digest when you've reached 256 bits of input entropy, or use rejection sampling to correctly extract uniformly distributed bits from a stream of such 0-9 numbers, assuming you have enough of them to avoid running out. $\endgroup$
    – Thomas
    Oct 21, 2013 at 8:27
  • $\begingroup$ Personally, if 0-9 were your only options, I would get around 312 of them before sending the bits to the hash. If you convert 8 numbers at 3-bits per number, that is 3 bytes of data. 312 numbers is then a total of 117 bytes of input to the hash, which should cycle the compression function twice, assuming you are only using the last 3 bits. $\endgroup$ Oct 21, 2013 at 8:41
  • $\begingroup$ Thanks @Thomas. Is there a computer algorithm around for calculating the entropy with Shannon's entropy equation (I assume that's the correct link)? With your rejection sampling, would you remove the numbers 8 and 9 from the stream, then take the last 3 bits of every number? $\endgroup$
    – liquin
    Oct 21, 2013 at 10:36
  • $\begingroup$ Thanks @Richie. How did you arrive at 312 numbers? And 117 Bytes? What's the maths behind that? $\endgroup$
    – liquin
    Oct 21, 2013 at 10:39
  • 1
    $\begingroup$ @liquin Yes, that is correct, and, yes, that is correct. You would reject values 8 and 9 and try a new number until you get a value between 0 and 7 (which you interpret as three bits). The problem is the algorithm only works well if you have a large number of such numbers (preferably infinitely many) since you are probabilistically rejecting some of them. And to be fair using SHA-256 is probably the safest option, unless you have some requirements you have not told us about. $\endgroup$
    – Thomas
    Oct 21, 2013 at 10:49

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Many thanks tylo good answer. I think I meant in my 'first conclusion' that we shouldn't use raw random numbers as a cryptographic key without some sort of post-processing as there are long repeated sequences of 0011 if the numbers are converted directly from ASCII to binary. $\endgroup$
    – liquin
    Oct 22, 2013 at 9:09
  • $\begingroup$ There's your problem: The symbol "1" in ascii is not the number 1. It is a symbol in the ascii table, which has the code 01100001, as you found out yourself. An easy conversion can be achieved by "int one = '1' - '0' " $\endgroup$
    – tylo
    Oct 22, 2013 at 10:35
  • $\begingroup$ That is correct they are as a string at the moment, hence the ASCII conversion. If I convert each number to integers then I get the following binary: 0=0, 1=1, 2=10, 3=11, 4=100, 5=101, 6=110, 7=111, 8=1000, 9=1001. If you left pad those binary results with 0's they are the same as the last 4-bits of the ASCII representations. At any rate I can't convert a long set of numbers into an integer and then feed it into the hash because it exceeds an int64 which maxes out at unsigned 18,446,744,073,709,551,615 and also the hash function only supports string input anyway. $\endgroup$
    – liquin
    Oct 23, 2013 at 8:02
  • $\begingroup$ Uhm, handling the number format is a different problem, and that is specific to your programming language. It has nothing to do with the algorithm to sample a true uniform random value. Btw, there are ways to get larger numbers by using arrays of fixed size numbers. And you can define math for those numbers... or just use a format which supports this, e.g. BigInteger in Java. I think the real question is: What do you actually want to achieve? $\endgroup$
    – tylo
    Oct 23, 2013 at 15:32
  • $\begingroup$ I just want to feed 256 bits of entropy into a 256 bit hash to get a usable output for a cryptographic key. I don't think I can feed an array of integers or anything into the hash algorithm. The library I'm using only accepts a string input. Therefore I have to use the ASCII representation of the numbers as a long string. I think the only way I can do it is to do Thomas' recommendation in his first comment (feed them into SHA-256, assuming around (but not exactly) 3 bits of entropy per number). $\endgroup$
    – liquin
    Oct 26, 2013 at 0:46
1
$\begingroup$

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.

$\endgroup$

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.