2
$\begingroup$

I would like to generate a 128 bit random number with dices, but I have heard that dices are pretty biased, especially low quality (non casino dices).

  1. Would it make sense to generate a higher bit number, like a 1000 bit number? Would that "absorb" the flaws and biases exhibited in the dices. In the sense that the overall bias diminishes, the more bits you add to it?

  2. What is the best method to make the bias go away?

    • Concatenating the individual numbers thrown into a 128 bit string
    • Multiplying the individual numbers thrown
    • A combination of both, for example with 2 dices: (R1+R2)x(R3+R4)x(R5+R6)…
$\endgroup$
  • $\begingroup$ If you can just use a computer, pass the output through a randomness extractor. $\endgroup$ – otus Dec 8 '16 at 5:59
  • $\begingroup$ Can you use a computer for it? If yes, I'd just throw them into a cryptographic hash function like SHA2. $\endgroup$ – CodesInChaos Dec 8 '16 at 9:03
  • $\begingroup$ There is the von Neumann unbiasing method (which however throws away quit a lot of bits), $\endgroup$ – Mok-Kong Shen Dec 8 '16 at 11:47
  • $\begingroup$ How do you know that your dice are pretty biased? 128 bits is only 57 dice rolls. Unless your dice are missing some spots, it's practically impossible to gather any useful statistical information after 57 samples. Natural random variability will in all likelihood swamp any bias. If you consecutively roll six sixes, who is to say that's not truly random? $\endgroup$ – Paul Uszak Dec 8 '16 at 15:54
1
$\begingroup$


What is the best method to make the bias go away?

No matter if we’re talking about the bias coming from manufacturing flaws, or the bias we know from casino-quality dice, you can use the Von Neumann skew-correction algorithm to generate uniformly random data from skewed input.

The Von Neumann skew-correction algorithm was published in “Various techniques used in connection with random digits.” (NIST journal, Applied Math Series, 12:36-38, 1951). Since the paper is hard to find online due to its age and publication date, I‘ve put a copy in my Google Drive account (PDF) for reference purposes.

The general idea behind Von Neumann’s skew correction is to consider sequences of rolls/coin-tosses/whatever instead of isolate ones while picking a sequence length long enough that an even number of possible outcomes has equal probabilities.

Explaining the Von Neumann skew-correction algorithm:

For dice, pick a sequence length where $n>2$. The reason for picking a sequence length of $n>2$ is that no subset of possible outcomes of equal probability for $n=1$ or $n=2$ has a cardinal divisible by $6$.

So, for this example, let’s simply take $n=3$. Doing so, the outcomes of any dice can be partitioned into 6 categories of equal probability according to the relative ordering of the successive numbers rolled – provided these numbers are all different.

We need this, so that sequences can be grouped according to whether the second number is greater – 1 – or smaller – 0 – than the first, and whether the 3rd number is greater 111,011 or smaller 100,000 than both the first and the second, or between them 110,001.

All 6 possible orderings will occur with equal probability because each of the sequences belonging to any of these orderings matches exactly one sequence of equal probability in every other ordering. Meaning: 1,2,4,1,2,4 matches the ordering 111, while 2,1,4,2,1,4 (which is equally likely to be rolled) matches 011.

EDIT

@fgrieu describes a different, yet equally practical implementation in his comment below.

$\endgroup$
  • 2
    $\begingroup$ One practical implementation of Von Neumann skew-correction / debiasing could be: throw the dice twice, strongly / far from the table so that rolls are independent; if the first roll is even, and the second odd, write a 0; if the first roll is odd, and the second is even, write a 1; otherwise write nothing . Repeat (throwing dices twice) until 128 bits are written; that is obtained for an expected 512 throws (slightly more with a very biased dice). It is possible to use much less dice throws, but the procedure becomes more complex. $\endgroup$ – fgrieu Dec 16 '16 at 11:55
-1
$\begingroup$

Yes, die can be noticeably biased but i would be very surprised if the output of die from different manufacturers were to be bad enough to lead to any practical attack whatsoever of even something with requirements as stringent as that of a one-time pad (unless the dice were deliberately sabotaged).

Personally, if you are not allowed to use a computer i would do the following: get d6 dice from different manufacturers (at least 2 dice, look for die without rounded edges), build a 6x6 table (example below, but there could be many variations of this) and choose your characters from the intersection of 2 die rolls. If you want to determine if a letter is upper or lower case you could do something like a coin flip.

Keep building your key via this method until you have the desired output amount.

\|1|2|3|4|5|6|
1|a|b|c|d|e|f|
2|g|h|i|j|k|l|
3|m|n|o|p|q|r|
4|s|t|u|v|w|x|
5|y|z|0|1|2|3|
6|4|5|6|7|8|9|

Update: I just noticed you said you needed to generate numbers only. here's a different table (but 16.67% of your rolls will be invalid):

\|1|2|3|4|5|6
1|0|1|2|3|4|5
2|6|7|8|9|0|1
3|2|3|4|5|6|7
4|8|9|0|1|2|3
5|4|5|6|7|8|9
6|R|E|R|O|L|L

6x6 table with 86.11% odds of only 2 dice rolls (with 2.77% odds of invalid roll) and 13.89% odds of 2 dice rolls + 1 coin flip:

\|1  |2  |3  |4  |5   |6
1|0  |1  |2  |3  |4   |5
2|6  |7  |8  |9  |0   |1
3|2  |3  |4  |5  |6   |7
4|8  |9  |0  |1  |2   |3
5|4  |5  |6  |7  |8   |9
6|0/1|2/3|4/5|6/7|8/9 |REROLL
$\endgroup$
  • $\begingroup$ Whats wrong with a D16 dice? Each roll would give you 4 random bits. $\endgroup$ – dave.zap Dec 8 '16 at 11:53
  • $\begingroup$ @dave.zap I chose the d6 because it's the most basic and ubiquitous dice which is more likely to be available from many manufacturers wherever OP lives, and because i think it's the most simple (least likely to be royally screwed up by any given mfg) dice which is usable for the purposes OP wants. And since OP is concerned with dice bias (which is very much real) a good option is combining at least 2 independent dice rolls, regardless of the die choice. If OP doesn't want to be so conservative he could easily combine 2 dice rolls into >5 random bits by modifying the table to be from 0-35. $\endgroup$ – cipher Dec 8 '16 at 13:21
  • $\begingroup$ Yeah but s/he would be wasting energy by discarding some of the information on each roll. I think if anyone were to go to the trouble of actually generating random numbers with dice they could locate some decently manufactured D16. Just get 32 of them and throw them all at once. At any rate going by the posters username I think we are all being trolled anyway. $\endgroup$ – dave.zap Dec 8 '16 at 18:44
  • 2
    $\begingroup$ The question is to generate "a 128 bit random number" and the current answer addresses generating decimal numbers. Also the question considers a biased dice (with unknown bias), and the answer does not satisfactorily address that situation, beside (rightly) stating that it's likely a non-issue in practice. $\endgroup$ – fgrieu Dec 16 '16 at 11:46

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.