|
|
Mechanical generation of random bit sequences
Posted:
Nov 7, 2009 9:30 AM
|
|
Hi,
In sci.crypt.random-numbers I recently expressed my humble opinion
that for a 'normal' (average) user of security software -- who is
likely to be a layman in cryptology and also not very knowledgeable
in hardware/software to be in a position of always doing technically
correctly in the diverse procedures proposed or available for
collecting random bits from computer hardware and similar sources
of 'natural' randomness -- it seems to be desirable, if some simple
and easy to handle mechanical devices be available for rapidly
and conveniently generating small amounts of good quality random
bits as may be needed e.g. as keys or initialization vectors for
encryption algorithms.
Tossing coins to get even a very small number of bits is rather
tedious. Although throwing dice is generally more efficient, one
has to convert the result from base 6 to base 2 and the procedure
is also not too convenient in practice in my humble view. I like
therefore to solicit in this thread construction ideas that
eventually could be picked up by some interested manufacturers to
produce mechanical devices for sale on the market so that anyone could
with a little expense buy one to comfortably obtain some small
quantities of good quality random bits he needs at any time. (With
adequate tools skilled persons could perhaps even make such devices
themselves.)
Let me start for discussion and critiques with a proposal of my own
which is based on a device that I happen to possess for randomly
choosing 6 numbers from [1, 49] (used for fun in playing lottery,
being a gift of the German Federal Lottery to its customers many
years ago). I'll at fisrt describe this device and later indicate
modifications needed for our purpose. The said device is a tiny
thin flat box of 40*40*6 mm (more exactly, the thickness is tapered
from centre of 6 mm to the boundary of 4 mm), made of plastic so
that one can see the content when the device lies horizontally. The
hollow space inside is 30*30*2 mm. The upper one third of this is
free space as such (a chamber), while the lower two thirds of the
space is occupied largely by platic material in such a way that
there remain five parallel (to the sides of the box) grooves
(channels) of 20*2*2 mm with outlets to the upper space, with one
groove being shorter, of only 18 mm long. Alongside the grooves are
randomly ordered (though this is clearly unessential for the purpose)
printed numerals 1..49 can be seen. Inside the box there are 49 tiny
platic balls, a little bit smaller than 2 mm in diameter, 6 of which
are coloured red, while the rest are white. Now if a user first tilts
the box such that all balls are in the upper space and shakes the box
so the the balls are well mixed with one another and subsequently
tilts the box back while also shaking it a little bit, the balls will
fill the five channels and the numerals opposite to the red balls are
then read out to be the 6 desired random numbers in the range [1, 49].
(The box has a hook for attaching it to one's key bundle and thus can
be conveniently carried around.)
The modification for our purpose would be straightforward. We could
have the five channels equally long so as to accomodate 50 balls
(instead of 49), with 25 coloured white and the rest black. Then the
constellation of the balls in the channels after having been well
mixed in the upper chamber would give us a random bit sequence of
length 50.
As you may have surely noticed, there is however one very serious
deficiency in this design. Since there are 25 white and 25 black
balls in the box, in any sequence of length 50 thus generated the
frequency of white or black is exactly 0.5 and that's evidently no
good. A viable remedy, I suppose, could be to have, instead of
50 balls, 100 balls, with 50 being white and 50 black. Now there
will be 50 balls not falling down into the channels but these we'll
simply ignore. This way, the reading from the five channels would
not have the frequency problem depicted above. Equivalently we
could have 100 balls and 10 channels, with all balls filling the
channels but we ignore the reading from half of the (say, last 5)
channels. Of course, with the additional balls the box would have
to be enlarged a little bit with respect to the dimensions given
above. It may be preferable also to generate bit sequences of
length 64 instead of 50, in order to better suit what is commonly
required by block encryption algorithms like AES, which has key
lengths of 128/256 bits.
Of course, all mechanical devices are not perfect. Anyway, randomness
collected from them could hardly be expected to able to compete with
that e.g. from radioactive decay using sophisticated instruments. But
I suppose there is in practice always a general trade-off between
perfection and affordable cost (including time etc.). Thus I employed
above the term 'good' quality, not 'extremely high' quality, let
alone perfect quality (which would be needed for the theoretical 'one
time pad'). On the other hand, better quality, if desired, could be
achieved through post-processing, e.g. XOR-ing two sequences, etc.
Certainly, the balls in lottery or the dice in the casinos are
carefully maintained by technicians to eliminate bias as far as
possible (or at least most people 'believe' in that), while such is
not available for the class of very primitively manufactured devices
envisaged above. Nonetheless it seems not clear in the particular
case of the device I mentioned above how the imperfection of the
balls could 'as a whole' essentially negatively affect the quality
of the result. For, in contrast to the case of using one or a few
number of dice, one has in our case 100 balls, such that their
'individual' imperfection would in a sense be averaged out in my
humble view.
Thanks,
M. K. Shen
|
|
