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.
On Nov 7, 3:30 pm, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
> 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.
Any mechanical device is nowadays probably much more expensive than an electronic one.
> 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.
This is surely no problem as any good hash function helps and is more than milion times faster than you throwing dice or typing in the results.
> 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.
The entropy gained is about 47 bits (or less in case the throwing is not random). Using a hash function solves all your problems here.
> 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.
By using more balls you can get more entropy. Throwing a part of it away by ignoring some balls makes no sense since it's better to use a hash.
> This way, the reading from the five channels would > not have the frequency problem depicted above.
Yes but you do NOT get 50 bits of entropy!
> 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.
You'd better use more colors. With 4 colors and only 36 balls you can get 100 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.
Xoring may help, but using a strong hash is here virtually for free and surely better.
> 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),
I do believe it since any bias could be used againt the casino.
> 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.
In another thread here, somebody adviced a use of carefully chosen dice for password generation. But it's easy to find out that a bias of let say 10% (I mean a completelly crappy dice which could ruin your day when used in a board game; or your life when used in casino) is quite harmless (you only need to throw it some more times to get the same entropy).
> 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.
>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
The cheapest mechanical generator would be a toy BINGO cage. Just remove all balls over 49 and rotate the cage. At this time of the year such sets can be bought for $ 7-10.
> 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. > [general description]
Unfortunately, such a box can hide very sizable biases, the effect of even slightly different balls weights is notable. in fact in all the lottery/keno/similar games such biases become noticable.
> The modification for our purpose would be straightforward. [description > removed]
The modification doesn't help. The likely difference in weight between the two pigments is enough to bias the system, and increasing the number of inputs doesn't change too much. Not to mention being a large physical object it has difficulties in usage.
As for why the lottery and keno systems tolerate such biases, there are actually good reasons. For lottery systems the money coming in is split according to fixed rules, no randomness is involved so the biases really don't matter. Keno systems are setup very much the same as roulette, the odds of hitting on roulette are 1/37 or 1/38, but the payout is 35/1 or lower, multiple these together and the casino actually has a surprising advantage to absorb any flaws in the wheel. The same applies to the Keno machines, the payout is calculated according to the worst case entropy and also a house advantage, any better case for the casino is just extra money. That's why these systems don't work very well for cryptography, for a 1/37 odds, we'd be looking for a 36.999999999999999999999999999999999999999999999999999999999999999999999999 9:1 payout or better.
A better idea would be to use electronics, no normal person is going to be qualified to build a high quality lottery machine, a normal person likely can't weigh anything except with a bathroom scale anyway, far too imprecise for entropy collection. Using a small electronic device it is relatively easy to build a small device with a switch, pressure pad, and an entropy system from thermal noise in resistors. use the pressure pad to clock the measurement, every time the slope of the pressure over time changes take a measurement, any of the simple series elimination systems will work nicely. Since a human muscle actually twitches hundreds of times a second, and everyone's muscles twitch slightly differently (along with additional human factors entering) there is a small amount of entropy in the clocking cycle, this addresses some cyclic problems that happen in thermal noise in resistors. The device will be far from perfect (100 bits of output may have as much as 30 bits of entropy, probably less) but the attacker apparent randomness will be very high. Joe
On Sun, 8 Nov 2009 04:21:46 -0800, "Joseph Ashwood" <ashw...@msn.com> wrote: >A better idea would be to use electronics,....an entropy >system from thermal noise in resistors...
The electronic systems are not trivial to build properly either. A device that senses thermal noise in resistors is also likely to be affected by power line interference or EMI, which degrades entropy.
Regardless of which system is used to generate raw random data (mechanical or electronic), the entropy can be improved by oversampling the raw data and reducing the data with a good cryptographic hash. If you start with 1000 bits of raw data and reduce it to 100 with a hash, the effects of any bias in the 1000 bits will be masked. Here is the real advantage of an electronic system: it is not that the bits are so much better quality, it is that the bits are so much easier to sample, so that gross oversampling becomes feasible. If you had to sample 10 times as many bits as you really wanted in a mechanical system, it might become too much effort.
Maaartin wrote: > Mok-Kong Shen wrote: [snip] >> 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.
On Sun, 08 Nov 2009 20:43:10 +0100, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>Maaartin wrote: >> Mok-Kong Shen wrote: >[snip] >>> 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.
>> Yes but you do NOT get 50 bits of entropy!
>Could you please explain why?
Imagine betting on color of the last ball. If you really had 50 bits of entropy, then seeing the first 49 balls gives you no advantage in betting on the color of the 50th ball. But suppose I see the first 49 balls and they are 40 blacks and 9 whites. Now I know that the last ball must be chosen from 10 blacks and 41 whites. I think I will bet that the 50th ball is white. And I would be right much more than 50% of the time. So the entropy is obviously not perfect.
Joseph Ashwood wrote: > A better idea would be to use electronics, no normal person is going to > be qualified to build a high quality lottery machine, a normal person > likely can't weigh anything except with a bathroom scale anyway, far too > imprecise for entropy collection. Using a small electronic device it is > relatively easy to build a small device with a switch, pressure pad, and > an entropy system from thermal noise in resistors. use the pressure pad > to clock the measurement, every time the slope of the pressure over time > changes take a measurement, any of the simple series elimination systems > will work nicely. Since a human muscle actually twitches hundreds of > times a second, and everyone's muscles twitch slightly differently > (along with additional human factors entering) there is a small amount > of entropy in the clocking cycle, this addresses some cyclic problems > that happen in thermal noise in resistors. The device will be far from > perfect (100 bits of output may have as much as 30 bits of entropy, > probably less) but the attacker apparent randomness will be very high.
But the problem is that no such devices are available on the market for a normal user to buy and to use (hopefully without difficulties by a layman).
Robert Scott wrote: > Mok-Kong Shen wrote: >> Maaartin wrote: >>> Mok-Kong Shen wrote: >> [snip] >>>> 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. >>> Yes but you do NOT get 50 bits of entropy! >> Could you please explain why?
> Imagine betting on color of the last ball. If you really had 50 bits of > entropy, then seeing the first 49 balls gives you no advantage in betting on the > color of the 50th ball. But suppose I see the first 49 balls and they are 40 > blacks and 9 whites. Now I know that the last ball must be chosen from 10 > blacks and 41 whites. I think I will bet that the 50th ball is white. And I > would be right much more than 50% of the time. So the entropy is obviously not > perfect.
But you have to consider that the 100 balls are all competing to enter the five channels. If the balls have been well mixed, the chance of a white ball or a black ball entering a channel is the same, isn't it?
On Sun, 08 Nov 2009 22:06:46 +0100, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>But you have to consider that the 100 balls are all competing to >enter the five channels. If the balls have been well mixed, the >chance of a white ball or a black ball entering a channel is the >same, isn't it?
Yes, the chance of any one ball being black or white is exactly 50%. But when evaluating entropy, you also have to take into account the conditional probabiltiy of a ball being a certain color given the knowledge of what other balls are. Couldn't you say the same thing about the original proposal that used 25 black and 25 white balls? They were also throroughly mixed, and the chance of a white or black ball entering a channel is the same. Yet you realize that this method is flawed because after you see the first 49 balls, you know with exact certainty what color the last ball is before you see it. Well, the defect in that proposal just gets watered down a little by adding 50 more balls. But the defect does not ever get completely eliminated. It still detracts from the ideal 50 bits of entropy. Maybe it is just 48 bits. I don't know. But it is definitely not 50 bits.
> On Sun, 08 Nov 2009 22:06:46 +0100, Mok-Kong Shen <mok-kong.s...@t-online.de> > wrote:
>> But you have to consider that the 100 balls are all competing to >> enter the five channels. If the balls have been well mixed, the >> chance of a white ball or a black ball entering a channel is the >> same, isn't it?
> Yes, the chance of any one ball being black or white is exactly 50%. But when > evaluating entropy, you also have to take into account the conditional > probabiltiy of a ball being a certain color given the knowledge of what other > balls are. Couldn't you say the same thing about the original proposal that > used 25 black and 25 white balls? They were also throroughly mixed, and the > chance of a white or black ball entering a channel is the same. Yet you realize > that this method is flawed because after you see the first 49 balls, you know > with exact certainty what color the last ball is before you see it. Well, the > defect in that proposal just gets watered down a little by adding 50 more balls. > But the defect does not ever get completely eliminated. It still detracts from > the ideal 50 bits of entropy. Maybe it is just 48 bits. I don't know. But it > is definitely not 50 bits.
No. The flaw with 50 balls is different. Note, for example, this: In a random sequence there is a certain probability that in a sequence of length 100 all bits may be 0, and this is not the case with 50 balls in the device.
Mok-Kong Shen wrote: > No. The flaw with 50 balls is different. Note, for example, this: > In a random sequence there is a certain probability that in a > sequence of length 100 all bits may be 0, and this is not the > case with 50 balls in the device.
On Sun, 08 Nov 2009 23:13:52 +0100, Mok-Kong Shen <mok-kong.s...@t-online.de> wrote:
>No. The flaw with 50 balls is different. Note, for example, this: >In a random sequence there is a certain probability that in a >sequence of length 100 all bits may be 0, and this is not the >case with 50 balls in the device.
The 100 balls have a similar flaw, just to a lesser degree. In a perfectly random uncorrelated sequence of 50 bits, the probability that they are all 0 is exactly 2^(-50). But when choosing 50 balls from 100, the probability that all 50 chosen balls are black is 50! * 50!* / 100!. I leave it as an exercise to verify that these two numbers are not the same.
>> No. The flaw with 50 balls is different. Note, for example, this: >> In a random sequence there is a certain probability that in a >> sequence of length 100 all bits may be 0, and this is not the >> case with 50 balls in the device.
> The 100 balls have a similar flaw, just to a lesser degree. In a perfectly > random uncorrelated sequence of 50 bits, the probability that they are all 0 is > exactly 2^(-50). But when choosing 50 balls from 100, the probability that all > 50 chosen balls are black is 50! * 50!* / 100!. I leave it as an exercise to > verify that these two numbers are not the same.
Being layman, I am confused. Let's simplify the scenario so that there is only one channel with capacity of 2 and there are four balls, 2 white and 2 black. What is the probability of 2 black balls getting into the channel?
Mok-Kong Shen wrote: > Robert Scott wrote: >> Mok-Kong Shen wrote:
>>> No. The flaw with 50 balls is different. Note, for example, this: >>> In a random sequence there is a certain probability that in a >>> sequence of length 100 all bits may be 0, and this is not the >>> case with 50 balls in the device.
>> The 100 balls have a similar flaw, just to a lesser degree. In a >> perfectly >> random uncorrelated sequence of 50 bits, the probability that they are >> all 0 is >> exactly 2^(-50). But when choosing 50 balls from 100, the probability >> that all >> 50 chosen balls are black is 50! * 50!* / 100!. I leave it as an >> exercise to >> verify that these two numbers are not the same.
> Being layman, I am confused. Let's simplify the scenario so that > there is only one channel with capacity of 2 and there are four balls, > 2 white and 2 black. What is the probability of 2 black balls getting > into the channel?
I see in the meantime why my way of thinking is incorrect.
Mok-Kong Shen wrote: > Mok-Kong Shen wrote: >> Robert Scott wrote: >>> Mok-Kong Shen wrote:
>>>> No. The flaw with 50 balls is different. Note, for example, this: >>>> In a random sequence there is a certain probability that in a >>>> sequence of length 100 all bits may be 0, and this is not the >>>> case with 50 balls in the device.
>>> The 100 balls have a similar flaw, just to a lesser degree. In a >>> perfectly >>> random uncorrelated sequence of 50 bits, the probability that they >>> are all 0 is >>> exactly 2^(-50). But when choosing 50 balls from 100, the >>> probability that all >>> 50 chosen balls are black is 50! * 50!* / 100!. I leave it as an >>> exercise to >>> verify that these two numbers are not the same.
>> Being layman, I am confused. Let's simplify the scenario so that >> there is only one channel with capacity of 2 and there are four balls, >> 2 white and 2 black. What is the probability of 2 black balls getting >> into the channel?
> I see in the meantime why my way of thinking is incorrect.
If on the other hand one has two channels of capacity 1 instead, then the chance of having both channels filled black is 1/4. Is that right?
Mok-Kong Shen wrote: > If on the other hand one has two channels of capacity 1 instead, > then the chance of having both channels filled black is 1/4. > Is that right?
I am mistaken. Apology for the several useless posts from me.
>> A better idea would be to use electronics, no normal person is going to >> be qualified to build a high quality lottery machine, a normal person >> likely can't weigh anything except with a bathroom scale anyway, far too >> imprecise for entropy collection. Using a small electronic device it is >> relatively easy to build a small device with a switch, pressure pad, and >> an entropy system from thermal noise in resistors. use the pressure pad >> to clock the measurement, every time the slope of the pressure over time >> changes take a measurement, any of the simple series elimination systems >> will work nicely. Since a human muscle actually twitches hundreds of >> times a second, and everyone's muscles twitch slightly differently (along >> with additional human factors entering) there is a small amount of >> entropy in the clocking cycle, this addresses some cyclic problems that >> happen in thermal noise in resistors. The device will be far from perfect >> (100 bits of output may have as much as 30 bits of entropy, probably >> less) but the attacker apparent randomness will be very high.
> But the problem is that no such devices are available on the market > for a normal user to buy and to use (hopefully without difficulties by > a layman).
They aren't, but there are no dependable devices that deliver high entropy output on the market. Either way the device will have to be built. In terms of use, about the only assumption I made was that a layman can press and hold a button. Joe
> On Sun, 8 Nov 2009 04:21:46 -0800, "Joseph Ashwood" <ashw...@msn.com> > wrote:
>>A better idea would be to use electronics,....an entropy >>system from thermal noise in resistors...
> The electronic systems are not trivial to build properly either. A device > that > senses thermal noise in resistors is also likely to be affected by power > line > interference or EMI, which degrades entropy.
I had a assumed a reasonable design, typically encased in metal or a metallic paint building a farraday cage, just like your cellphone already has.
> Regardless of which system is used to generate raw random data (mechanical > or > electronic), the entropy can be improved by oversampling the raw data
Actually it very often reduces the entropy. Take a simple sin curve, sampling randomly gives random numbers, oversampling gives a higher precision sin curve, the same applies with disk seem timings, thread scheduling, many of the best sources of entropy available, and the entropy level in the resistor drops with too much over sampling (the more you know about it, the less is unknown). Entropy is not limitless, trying to sample too frequently you very quickly reach the limit of entropy that can be pulled, sampling beyond that is problematic at best. Joe
> ........... 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. ........ > .......... On the other hand, better quality, if desired, could be > achieved through post-processing, e.g. XOR-ing two sequences, etc. > ........ 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.
[snip]
I like to thank Robert Scott for showing that the sequence generated by such a device is biased. This naturally leads to thinking of applying unbiasing schemes, of which the one of von Neumann (00,11 -> ignore, 10 -> 1, 01 -> 0) seems to be the most practical one for convenient application by laypeople. Further possibilities are interleaving of bits of two sequences and XOR-ing two sequences and even simultaneous and multiple applications of these schemes. It is my humble conviction that more complicated processing should be left to those users that are knowledgeable and normal (average) users should only be trusted to do simple and straightforward operations. For otherwise there could be very undesirable consequneces out of their mistakes. So I would think that, before good and easy to handle hardware bit generators based on electronics etc. are on the market, devices of the sort I mentioned could be a viable 'interim' solution satisfying the practical needs of random bit sequences. I like thus to once again solicit design ideas of mechanical random bit generators from interested readers of this thread.
Mok-Kong Shen <mok-kong.s...@t-online.de> writes: >Mok-Kong Shen wrote: >[snip] >> ........... 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. ........ >> .......... On the other hand, better quality, if desired, could be >> achieved through post-processing, e.g. XOR-ing two sequences, etc. >> ........ 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. >[snip] >I like to thank Robert Scott for showing that the sequence generated >by such a device is biased. This naturally leads to thinking of applying >unbiasing schemes, of which the one of von Neumann (00,11 -> ignore, >10 -> 1, 01 -> 0) seems to be the most practical one for convenient
While that gets rid of independent biases it does not cure correlations.
>application by laypeople. Further possibilities are interleaving of >bits of two sequences and XOR-ing two sequences and even simultaneous >and multiple applications of these schemes. It is my humble conviction >that more complicated processing should be left to those users that >are knowledgeable and normal (average) users should only be trusted to >do simple and straightforward operations. For otherwise there could be
click on a window and read off the number. Is that difficult? Ie, elecgtronic ( eg based on /dev/urandom) are easier, and far better than any of your mechanical schemes.
>very undesirable consequneces out of their mistakes. So I would think >that, before good and easy to handle hardware bit generators based on >electronics etc. are on the market, devices of the sort I mentioned >could be a viable 'interim' solution satisfying the practical needs of >random bit sequences. I like thus to once again solicit design ideas
Aand where is this pent up need in the population at large for "random number sequences"?
On Mon, 9 Nov 2009 04:15:30 -0800, "Joseph Ashwood" <ashw...@msn.com> wrote: >> Regardless of which system is used to generate raw random data (mechanical >> or >> electronic), the entropy can be improved by oversampling the raw data
>Actually it very often reduces the entropy. Take a simple sin curve, >sampling randomly gives random numbers, oversampling gives a higher >precision sin curve, the same applies with disk seem timings, thread >scheduling, many of the best sources of entropy available, and the entropy >level in the resistor drops with too much over sampling (the more you know >about it, the less is unknown). Entropy is not limitless, trying to sample >too frequently you very quickly reach the limit of entropy that can be >pulled, sampling beyond that is problematic at best.
I agree. The sampling rate has to be limited to a rate appropriate to the source. And when I suggested oversampling, I also assumed a "reasonable design". If you find yourself sampling faster than the source is uncorrelated, then you have to sample slower and deliver fewer random bits per second, and just take more time. This is a real problem for the mechanical balls method because it takes so long to mix the balls and select. It is less of a problem with the thermal noise of resistors method because that noise is wideband and can be sampled quite fast without exposing too much correlation in the samples. In either case, some bit-reduction with a cryptographic hash is the best way to remove what little useable correlation or bias might remain.
>> Mok-Kong Shen wrote: >> [snip] >>> ........... 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. ........ >>> .......... On the other hand, better quality, if desired, could be >>> achieved through post-processing, e.g. XOR-ing two sequences, etc. >>> ........ 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. >> [snip]
>> I like to thank Robert Scott for showing that the sequence generated >> by such a device is biased. This naturally leads to thinking of applying >> unbiasing schemes, of which the one of von Neumann (00,11 -> ignore, >> 10 -> 1, 01 -> 0) seems to be the most practical one for convenient
> While that gets rid of independent biases it does not cure correlations.
In my humble view, generation with hardware (including mechanics) tends to have by nature lesser degree of problems with correlations. Anyway, XOR-ing sequences would reduce correlations, if I don't err.
>> application by laypeople. Further possibilities are interleaving of >> bits of two sequences and XOR-ing two sequences and even simultaneous >> and multiple applications of these schemes. It is my humble conviction >> that more complicated processing should be left to those users that >> are knowledgeable and normal (average) users should only be trusted to >> do simple and straightforward operations. For otherwise there could be
> click on a window and read off the number. Is that difficult? Ie, elecgtronic ( > eg based on /dev/urandom) are easier, and far better than any of your mechanical > schemes.
Use of primitive generation methods has an (of course arguable depending on one's standpoint) advantage that it is far less subject to malicious manipulations in my humble view, i.e. you know what you have.
>> very undesirable consequneces out of their mistakes. So I would think >> that, before good and easy to handle hardware bit generators based on >> electronics etc. are on the market, devices of the sort I mentioned >> could be a viable 'interim' solution satisfying the practical needs of >> random bit sequences. I like thus to once again solicit design ideas
> Aand where is this pent up need in the population at large for "random number > sequences"?
Because that up to now there are no good hardware generators that layman could buy and easily use, the normal users simply can do anything in this direction. This certainly doesn't mean that there is therefore no need. The situation is the same, I would say, with encryption of SMS. Because the mobile phone products up to now are not provided by the producers adequate features for encryption, there is no SMS security for the general public. (According to a follow-up in a thread intiated by me, the mobile phone of the president of US does however have encryption, I suppose including voice encryption.) That does not mean that general users have no desire/need of privacy of their SMS. Personally I have even the suspicion (you might call it fantacy if you perfer) that this is somehow influenced by politics. (To support that, let me tell that to my personal knowledge in the eighties of the last century the UNIX computer systems delivered to Europe had one subtle difference to those run in America in that the DES module was removed. That was clearly a result of influence from politics in my conviction.)
One simple idea that trivially comes to mind would be to have a tiny device working on the same principle as a roulette, producing in one spinning 4 or maybe more bits. Though we know that even big routlettes may be imperfect, in our humble context extreme perfection seems unnecessary. As I wrote previously, such devices are valuable as an 'interim' solution before technically sophisticated and much more satisfying devices based on electronics, that are suitable for handling by laypeople and are above all inexpensive, become available on the market for the general public. The possibility of some simple post-procesing of the bits obtained, if desired, may be mentioned here once again.
BTW, there has been a German made device for generating random numbers named 'Violine'. See Fig.2.9.3 on p.172 of K. Schmeh, Codeknacker gegen Codemaker, 2007. There a number of small balls were used in a device having the shape of a violine. You can access part of the book with:
|
