[clue-talk] Re: [CoLoCo] Random Number Generators

[David Rudder]

They're teaching you about PRNGs in 6th grade?  I'm very impressed!

The unit of measurement for the "randomness" of a system is the 
"entropy".  Which is a scientific word for..."randomness" :)   Entropy 
is measured in bits.  Take 2 to the <entropy-1> to find out how many 
times, on average, you'd have to guess before finding the right answer.  
So, a entropy of 2 means there's 4 different possible values.  On 
average, you'd find the answer in about half the time, so 2 guesses.  An 
entropy of 4 means there 2x2x2x2=16 possible values, so usually it'd 
take around 8 guesses.  I wouldn't trust anything with less than an 
entropy of 128.

Linux has 2 special devices for reading randomness. The first, 
/dev/random, creates random numbers by reading a bunch of different 
system variables.  Stuff like the temperature of the CPU, what all is in 
memory, hard drive read speeds, etc.  A whole buncha' stuff. 

If you run this command:
cat /dev/random
You will see random bytes get displayed to the screen.  If this messes 
up your screen, hit ctrl-c and then type in "reset".
You can see the data dribbles in slowly. 

/dev/urandom is similar to /dev/random, except that it takes the 
existing random data and runs it through an algorithm which allows it to 
spit out as much random data as you need, all at the same entropy.  I'm 
not exactly sure how urandom does it, but RSA's SHA-1 PRNG uses this 
formula (I know because I used to work there.)

    Take a bunch of good random data
    Feed it into a SHA-1 hash function
    Take the output and return it to the user
    For the next block of data needed, feed the output of the last block
    and the original random data into a new SHA-1 hash. 
    You can repeat this over and over to generate as much data as you need.

If you run
cat /dev/urandom
you'll see a stream of random data scroll past, messing up your screen, 
and making it beep like there's no tomorrow.

You can find out how much entropy your linux system is using by running
cat /proc/sys/kernel/random/entropy_avail

There's a lot of good stuff in /proc/sys/kernel/random

Here's a paper which discusses the security of /dev/random
http://www.pinkas.net/PAPERS/gpr06.pdf

Now, onto your questions:

1) Ask your dad to write a script which opens /dev/urandom, reads one 
byte, and does a modulo-6 on it.  That will do a pretty good job of 
simulating a die.  Have it repeat as many times as you'd like.
2) www.gnuplot.org is the normal way of making graphs out of script data
3)  Here are ways I've worked with:
- Read mouse and keyboard movements.  Collect coordinates and keys 
pressed, counting each reading as 1 bit of entropy.  Measure 128 such 
values and you're ready.
- Read the data from the sound card, with the gain turned way up high so 
you are reading noise and real sound together
- Read it from the CPU temperature (there are some Intel chips which can 
do this)
- Read it from network traffic, the current contents of computer memory, 
etc.
There are a number of different ways of turning a little random data 
into a lot.  I talked about RSA's SHA-1 PRNG.  Most of the systems are 
similar to that.  SHA-1 PRNG is about the slowest around, though, so 
many different PRNGs concentrate on speed above improving the entropy
4) The best way to collect random data is to use all the possible means 
available to you.  There's no saying you can only use one or another. 
5) Be aware that EVERYTHING affects your results.  If you flip a coin, 
the amount of finger-grease and hand-sweat on a particular side will 
affect it.  The weight of the pips on a die affect the outcome.  With 
computer random data generation, a skilled hacker can fake the inputs 
and feed in whatever he or she wants. Also, be aware that computers can 
not generate real random data...all these methods only go so far as 
faking them really well.
6) I think you're doing a very cool project!

-Dave

David L. Willson wrote:
> Leina,
>
> Things you want to be aware of, following your numbers:
>
> 1)
>
> You can generate random numbers on a Linux computer from the command
> line, from an interpreted script, or from a compiled program.  The speed
> and complexity of the options increase in the order I mentioned them.
>
> The frequency of each possible result, where the result is defined as
> the sum of the dots on all the rolled dice, will be flat for one die,
> and a linear increase to and decrease from the peak for two dice.  You
> won't see a "bell curve" unless you use three or more dice.
>
> 2)
>
> Some of the scripting languages have access to graphics libraries which
> can render a chart from the data.  You can also make a chart in just
> about any spreadsheet program.
>
> 3)
>
> There are more random-number generators available than can be mentioned
> in a short time.  I am willing to help you write scripts or compiled
> programs to generate random numbers, as long as you are willing to use
> free software to write and run them.  I suppose that others will be
> willing to help with this, too.
>
> 4)
>
> I don't know how to compare or measure the "random-ness" of the
> available random-number generators.  I hope someone else will step in
> with advice on this.
>
> 5)
>
> Most physical systems (dice, cards, coins) can be corrupted to some
> extent.  It might be interesting, although perhaps irrelevant, to show
> the results from "loaded" or "weighted" dice, along with your other
> result sets.
>
> --David
>
> On Sat, 2008-02-09 at 15:01 -0700, Leina Hutchinson wrote:
>   
>> Dear Ubuntu Team,
>>
>> My name is Leina and my dad is Jim Hutchinson. I am doing my 6th grade
>> science project on random number generators and was wondering if you
>> could answer some of my questions. I want to compare pseudo and true
>> RNGs. I have been reading a lot about them on random.org. I plan to
>> use 2 dice and roll them 1000 times but I know it takes a lot of
>> rolling to see the real probabilities. To do that, I want to use the
>> computer to simulate rolling dice, but I don't know how. Here are my
>> questions.
>>      1. How do I get my computer to create random numbers (I use
>>         ubuntu)? I want it to simulate a rolling of 1 die and 2 dice.
>>         The 1 die roll will be to see if each number comes up an equal
>>         number of times, and 2 dice roll will be to add and see a bell
>>         curve based on the probabilities of each sum.
>>      2. Will the computer graph the data for me or do I have to do it
>>         on a spread sheet?
>>      3. How many different ways are there to make a computer generate
>>         RNs? Can you show me how?
>>      4. Are some ways better than others? If so, what?
>>      5. Are there certain things that I should be aware of that might
>>         affect my results?
>>      6. Do you have any tips of suggestions?
>> Thank you for you time. Please reply to my email address.
>> ~Leina
>>     
>
> _______________________________________________
> clue-talk mailing list
> clue-talk at cluedenver.org
> http://www.cluedenver.org/mailman/listinfo/clue-talk
>