[Cryptography] Throwing dice for "random" numbers

[John Denker]

On 08/15/2018 01:08 PM, Christian Huitema wrote:

> If you do not mark the dice, then the
> experimenter will input the 12 numbers "in whatever order they see fit".
> Maybe left to right, maybe nearer to further, maybe even results first,
> maybe odd, maybe smaller result to larger. The choice by the operator
> may be unconscious, but it is still very likely to introduce a bias,
> resulting in fewer than 12*log(6) bits of entropy.

0) Worrying about biasing the order is a very minor optimization.

1) Marking the dice and then reading them out in marked
 order is a pain in the neck.

2) If you are really worried about the order, it would
 be better to separate them mechanically in advance,
 using something like an egg carton or a spice rack
 with one die per cell.
   https://img.etsystatic.com/il/42ccaa/907993090/il_340x270.907993090_cz0j.jpg

============

On 08/15/2018 07:20 AM, Dave Horsfall wrote:

> it occurred to me that it's not as simple as it seems, with the
> generated output (e.g. modulo 10) not being as uniform as one would
> hope.

Suppose you want decimal digits.  Twelve 6-sided dice can
be treated as a 12-digit base-6 number.  In decimal that
is a number from 0 to 2.18e9.  Roll the dice.  Whenever
there is an outcome greater than or equal to 2e9, throw
it away and re-roll.  Take the result modulo 1e9.  That
gives you a uniform distribution over 9-digit decimal
numbers, limited only by imperfections in the dice, with
no non-uniformity introduced by the modulo operation.

The same procedure generalizes to bases other than 10,
including 2, 8, 16, and 36 or 62 (i.e. alphanumeric).
Discarding out-of-range outcomes has been standard
practice since the 1940s (which is kind of a long
time in the computer business).

Also, for what it's worth (which is not much):  8-sided
dice are cheap and widely available (more so than
16-sided dice).  You can use those to generate bytes
or words having any integer number of bits, with no
need to re-roll.  This is not worth much because the
inefficiency introduced by re-rolling is very small.
It's at most a cosmetic issue, not a serious issue.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180818/9350e27e/attachment.sig>