Random Numbers

games like Solitaire more interesting, the use of randomness in generating passwords and encrypting data is critical to security.

Until fairly recently, cpu's had no direct way to generate random numbers. Intel's Pentium III introduced a hardware random number generator that uses thermal noise "to generate high-quality random and nondeterministic numbers" , but prior to that systems that needed good random numbers had to rely on add-on boards or other external input.

The problem, of course, is that the whole point of computer programming is predicability: given the same input, a program will always follow the same path to completion. That makes it impossible to generate random numbers with an algorithm.

For all we know, it may be impossible, period. While thermal noise from a semiconductor certainly seems random to us, if we really understood the physics, it might not be at all. If string theory is real, then the arrangement and orientation of these "strings" might affect their vibration, which in turn affects the behavior of electrons, etc. It's quite possible that the universe is deterministic - we really aren't in any position to even guess right now.

The real question is, does it matter? And the answer is both "yes, it does" and "no, it doesn't", depending on why you asked. On the one hand, we have apparently non-deterministic events like how many visitors this web site will have today. That's an apparently very random number, determined by perhaps hundreds of conflicting factors such as news events, advent of security challenges, the weather, Google rankings: well beyond any ability to calculate. Yet, it's pretty easy for me to guess within a few hundred what that number will be because in large enough populations, the random behavior of individuals is unimportant: statistics and other indicators can tell us what the general group behaviour will be. From this point of view, it doesn't matter if individuals are non-deterministic because group behavior is not. The same thing is true of systems like our own Earth's weather; it's complexity makes precise prediction impossible (at least now) but there are certainly predictable patterns: here in Massachusetts, it WILL be warmer in August than in December most days.

On the other side, things that really aren't random at all can be quite random enough for a particular need. For example, if you had to "randomly" select from a group of 60 items using a computer program, a very simple way to do it would be to use seconds from the current time: if your user runs the program at 23 seconds past the minute, the program selects item 23. This isn't random at all; it's very deterministic. If there was any reason for your users to care about which of the sixy items were selected, they could find ways to "cheat" your program fairly easily. But if it isn't important, the selection may in fact be quite random enough for your needs. The underlying method isn't random, but it appears to be for the expected use, so the algorithm works. Apparent randomness from a very non-random source.

That is the problem with computer generated "random" numbers: they may not be very random at all. Almost all computer languages have some method of selecting a random number, but in fact it's not really random. This Perl script will generate the same results every time it is run:

#!/usr/bin/perl
srand 5;
for ($x=0;$x<10;$x++) {
  print rand() . "\n";
}


If you saw that run once, you'd think it was giving you random numbers. Run it again and you get the same ten numbers. The numbers will not change no matter how many times you run it, so obviously they aren't random at all. That's because it is really only pseudorandom. The argument given to srand seeds the random number generator, and it will always generate the same numbers in the same order for the same starting seed. However if we seed "srand" with something more random (or more apparently random), we get better results:

#!/usr/bin/perl
srand(time() ^($$ + ($$ <<15))) ;
for ($x=0;$x<10;$x++) {
print rand() . "\n";
}
 

This has every appearance of generating random numbers. Yet, a cryptographer would warn you not to rely on that for encrypting bank accounts, because just like our simplistic selection from the sixty items, the seed actually isn't random and given sufficient incentive, that flaw could be very costly.

So how do you get more random? Linux and other operating systems may provide a "/dev/random" and "/dev/urandom". Don't assume you know how these work: Mac OS X and Linux both have these, but the man pages are quite different. If your use is casual (you aren't protecting Fort Knox), the differences are probably unimportant, but "man 4 random" is interesting reading anyway.

Perl has a "TrulyRandom" module that uses interrupt timing discrepancies to get random numbers; but do we know that the discrepancies are truly non-deterministic? Like the thermal activity of a semiconductor, it might actually be predictable. With sufficient knowledge and computing power, any of these things might be as trivial as our "random second" implementation.

Many systems have the PRNG library - many versions of SSH use that. If you've ever generated a GPG key, you probably remember this:

We need to generate a lot of random bytes. It is a good idea to perform
some other action (type on the keyboard, move the mouse, utilize the
disks) during the prime generation; this gives the random number
generator a better chance to gain enough entropy.
 

These unpredicable actions on your part were used to seed the random number generation.

Much attention is paid to the importance of avoiding predicability in random numbers, and yet as we have seen from the most recent ssh exploits, the random numbers used in encryption are only a very small part of the total picture. It was other weaknesses in the ssh code that were exploited, and the encrypted keys were not important at all. The thickest deadbolts on your front door are useless if the back door is wide open.

See http://geminis.dyndns.org/wordpress/index.php/2005/07/04/random-number-generators-what-do-you-need-one-for/ for another take on this.



Got something to add? Send me email.



3 comments



Increase ad revenue 50-250% with Ezoic


More Articles by

Find me on Google+

© Tony Lawrence



Good article! Totally...er...random! &lt;Grin&gt;

Maybe we will some day figure out how to generate random values from the background radiation emanating from outer space. Or perhaps by sampling the noise of many conversations being simultaneously heard. I've often wondered if true randomness can ever be achieved by mechanical or electronic means. After all, randomness is ultimately limited by the granularity of what it is you want to be random.

--BigDumbDinosaur

There's also the folding or mapping problem that I forget to mention. Say you have only fifty items to select from, and use the "seconds" algorithm above. You might naively do a modulo 50 on the current second, but that gives more weight to numbers from 0 to 9. For this method, that's rather obvious, but what happens when we map other supposedly random noise to finite sets? If the noise isn't really random, certain results will be more common than others. That could screw you up in ways you might never comprehend.

Like the saying goes, "trust everyone, but count the money".
Anytime you are hashing, folding or mapping, you run the risk of weighting your distribution somewhere. If your algorithm depends on randomness, that weighting can be unexpected and unseen, yet still there. With the mod 50 above, you'd notice. Other applications might not.

Which leads to the interesting idea of testing for randomness. The way to do it is to use different "random" sources and compare their results. All kinds of stat analysis uses such tests to detect bias and other problems, but what if the random source really isn't? If background radiation from space is actually deterministic, using it will create some bias - we might never be able to understand what that bias is, but that doesn't mean that it couldn't be there. Ultimately, the absence of bias is unknowable with certainty, but that doesn't mean that it would never be possible to detect it - and just imagine how interesting THAT would be.

--TonyLawrence

"Which leads to the interesting idea of testing for randomness."

The idea of somehow devising a test to determine if a result is truly random reminds me of a scientific paper of years ago that discussed the problem of trying to view subatomic particles. The core of the paper seemed to propound a theory that, in effect, said we would never "see" them because the shortest wavelength of the visible light spectrum was too long to "illuminate" even a neutron. Also, the author suggested that the energy of the light photons being used to illuminate the particles would constantly deflect them, preventing one from ever seeing anything.

"Ultimately, the absence of bias is unknowable with certainty, but that doesn't mean that it would never be possible to detect it - and just imagine how interesting THAT would be."

I think the same sort of basic thinking that "explains" the seeming impossibility of "seeing" subatomic particles could be valid in dealing with random quantities and events: the act of trying to determine if randomness was achieved would effectively invalidate randomness. Assuming that to be true, we would seem to be destined to become mathematical Flying Dutchmen, forever doomed to chase after that which cannot be caught.

--BigDumbDinosaur


If you take the 50 item example, you can observe that the source isn't random by examining your results - you don't need to know how the input was produced. It's just looking for repetition and patterns. Same can be applied to cosmic radiation - exactly like we're doing with the SETI project, looking for patterns.

--TonyLawrence

"Same can be applied to cosmic radiation - exactly like we're doing with the SETI project, looking for patterns."

True enough, although we don't actually know what it is we expect to see in this case. There are radio frequency emitters in the universe that produce regularly spaced impulses -- deep space "Morse Code," which could (and has) confuse a naive SETI participant. On the other hand, it is conceivable that a true SETI source could be mistaken for random noise simply because we humans aren't equipped to recognize the source as intelligible. &lt;Smile&gt;

--BigDumbDinosaur
Good one !!!!
--Varun


---MidTerm Ex.
Brilliant, just what I was looking for! A simple google search on random.. Gives pretty random numbers of hits.
-----







Wed Jan 23 10:22:15 2008: 3510   Henri


String theory is pseudo-esoteric. Chaos theory is more useful in this context.



Wed Jan 23 12:25:26 2008: 3511   TonyLawrence

gravatar
You are missing the point. It doesn't matter if the fundamental element is "strings" or "turtles" - knowing what it is and how it works might show that what we now think is random is not - or the opposite.





Tue Jul 13 13:10:13 2010: 8815   TonyLawrence

gravatar


In a conversation about determinism, I happened to think of Arthur C. Clark said "Any sufficiently advanced technology is indistinguishable from magic" quote.

I'd add that any sufficiently complex machine can also appear to be non-deterministic.

At the end, it doesn't matter anyway: even if the Universe is deterministic, it will always be non-deterministic to us. Even if we knew how physics really works, we couldn't calculate our way to omniscience because the only thing that can hold the state of the Universe is the Universe itself.

So randomness is safe, I think.

------------------------
Kerio Connect Mailserver

Kerio Samepage

Kerio Control Firewall

Have you tried Searching this site?

Unix/Linux/Mac OS X support by phone, email or on-site: Support Rates

This is a Unix/Linux resource website. It contains technical articles about Unix, Linux and general computing related subjects, opinion, news, help files, how-to's, tutorials and more.

Contact us

privacy policy