Random Number Generators

[sparkyclarky]

How does a random number generator work? Is it based on a mathematical algorithm that has an infinite number of answers? If in a hardware form, how would it work then (perhaps slot machines use them?)?

 

[jurzdevil]

im not too sure but an algorythm doesnt generate a truely random number. i remember hearing of some network of computers that generates a truely random number.

 

[heliomphalodon]

The generation of "random" numbers is a deep topic -- even defining exactly what is meant by the term "random" is not trivial. Generating "good" pseudo-random numbers is a difficult task. Any deterministic algorithm can, at best, generate only pseudo-random numbers. As Von Neumann said, "Anyone attempting to produce random numbers by purely arithmetic means is, of course, in a state of sin."

To get real random numbers, you need some kind of real random input -- like a noisy diode or a geiger counter.

One of the most common approaches in actual practice is to use a "linear congruential" iteration based on a seed. Often the seed is taken from the system date. Run a search on "linear congruential random number" and you'll find more information than you could ever want.

I doubt that the casino equipment manufacturers will be very forthcoming with details on exactly how their machines fleece fools.

 

[zephyrprime]

The random numbers generated by algorithms are not random by any means. They in fact generate a perfectly orderly, predictable number sequence. Once it's generated like 2^32 numbers, it just rolls over again and starts generating the same sequence. To add some true randomness, all random number generators use some sort of seed number that is actually sorta random. By far the most common seed used is simply the time on the computer's clock. I read about a true hardware random number generator that Intel made that relies upon random voltage fluctuations in circuits. There's a name for this phenomena but I forget its name. I noticed that the new Via C3 have hardware random number generators in them too.

 

[GlassGhost]

http://www.agner.org/random/

That'll give you a good background and some code if you're so inclined.

 

[dejitaru]

To get real random numbers, you need some kind of real random input -- like a noisy diode or a geiger counter.

Even that's predictable and unreliable.

 

[f95toli]

Originally posted by: dejitaru

To get real random numbers, you need some kind of real random input -- like a noisy diode or a geiger counter.

Even that's predictable and unreliable.

No, it is not. Done properly it will be random. I am not 100% sure but i believe the ABC80 (remember?) had a "real" hardware-based random number generator built in based on a reversed-biased diode.
I rememer reading an article about how CIA and NSA uses CDs with recorded cosmic noise as one-time crypto keys. I am not sure if it is true,but it should be very efficient.

There are also some very good pseudo-random number generators, with good seed they work very well. If you have access to some math software like Matlab you can try it.

 

[Shalmanese]

I think that they actually found some order in the lower level bits in the decay of an unstable particle. I have no idea what that means but, effectively, radioactive decay cannot be considered "truely" random.

 

[Jeff7]

Isn't there some chip made by Intel that's able to generate truly random numbers? I saw it mentioned a few years ago - it generates numbers based on the noise of an electon, or something like that.
But it's definitely true what's been said here - standard means of producing "random" numbers in a computer are nowhere near random. If you know the algorithms used, and the beginning number(s), you'll be able to predict the string of numbers from there. I created a Qbasic program awhile back that would output dots on the screen "randomly." They formed a pattern of diagonal lines. Not exactly random.
Random.org looks to have more information on random number generation.

 

[f95toli]

Radioactive decay is really random, that is just basic physics and is not really related to random number generators. Of course there could be problems with the detectors used etc but the process itself is truly random.

About the Qbasic program, mentioned above: Then you were using a bad generator. I checked the help-files for Matlab and the generator used in Matlab 5 and 6 should be able to generate 2^1492 values before repeating itself, so there are some really good generators available.

 

[heliomphalodon]

Originally posted by: Shalmanese
I think that they actually found some order in the lower level bits in the decay of an unstable particle. I have no idea what that means but, effectively, radioactive decay cannot be considered "truely" random.

With all due respect, your statement makes no sense. It's good that you have no idea what it means, since it is in fact meaningless.

 

[ProviaFan]

Originally posted by: Jeff7
I created a Qbasic program awhile back that would output dots on the screen "randomly." They formed a pattern of diagonal lines. Not exactly random.

I had a similar experience. What I was doing wrong was using "RANDOMIZE" to set the seed to the value of "TIMER." before each and every random number I generated. Since each call to RANDOMIZE resets the number sequence, and since the program runs fast enough that each call to TIMER is only slightly different, any numbers generated in that fasion will be in a very predictable sequence. Only call RANDOMIZE once per each time you want a sequence, and you will have somewhat more "random" numbers.

FWIW, some modern operating systems (OpenBSD?) use many sources of "entropy" to feed their random number generation function. Apparently this helps with cryptography, though I don't claim to understand why. More info here, if you're interested.

 

[RaynorWolfcastle]

Originally posted by: Shalmanese
I think that they actually found some order in the lower level bits in the decay of an unstable particle. I have no idea what that means but, effectively, radioactive decay cannot be considered "truely" random.

I'm pretty sure that radioactive decay (for alpha particles anyway) is a quantum process. As such it is random in that you can tell where something is most likely to occur but it is impossible to tell exactly when it will happen (Schrodinger's cat anyone?).

The measure of any quantum effect should yield a true random number. I believe Intel had a plan to build a true random number generator in their CPUs at some point in time by measuring thermal or electrical fluctuations on chip. I think they dropped the idea after the processor ID debacle, though I may be wrong about that.

 

[Bovinicus]

Random number generators usually use something called a seed. A seed is basically a starting point for the algorithm (This is simplified). The best way to make a random number is to take something that will never be the same, like time, and use that as the seed.

 

[Agent004]

Rather basing 'randomness' from a man-made device (include algorithms), why do we take a more natural source for it. As some suggested, decaying is a good way. I like to take the weather as a basis for generating random numbers

 

[brjames]

The way programmers typically get random numbers is to use the least significant digit of the computers clock. If they need a random bit in hardware (for something like a prediction algrothim) they typically just get a bit from some other part of the hardware that is completely random... typically the program counter.

 

[Barnaby W. Füi]

Originally posted by: jliechty

Originally posted by: Jeff7
I created a Qbasic program awhile back that would output dots on the screen "randomly." They formed a pattern of diagonal lines. Not exactly random.

I had a similar experience. What I was doing wrong was using "RANDOMIZE" to set the seed to the value of "TIMER." before each and every random number I generated. Since each call to RANDOMIZE resets the number sequence, and since the program runs fast enough that each call to TIMER is only slightly different, any numbers generated in that fasion will be in a very predictable sequence. Only call RANDOMIZE once per each time you want a sequence, and you will have somewhat more "random" numbers.

FWIW, some modern operating systems (OpenBSD?) use many sources of "entropy" to feed their random number generation function. Apparently this helps with cryptography, though I don't claim to understand why. More info here, if you're interested.

The "randomness" of random sequences, and the integrity of cryptography, are very closely related. If your random number generator is spitting out predictable sequences, it could be analyzed to reverse engineer encrypted data.

This article does a good job of explaining ssh handshakes, which gives you a general idea of the role of random numbers in cryptography.

 

[Peter]

The silliest cryptography attempt was an early revision of my local bank's internet software ... the Java applet would insist you wave the mouse around in its window for a few seconds before continuing

 

[Evadman]

Originally posted by: Peter
The silliest cryptography attempt was an early revision of my local bank's internet software ... the Java applet would insist you wave the mouse around in its window for a few seconds before continuing

wow. that is a new one. *makes note*

 

[chsh1ca]

PuttyGen also does something similar to create the random seed that it uses for its key generation. Pretty funny if you ask me, but it's also pretty secure, since it's highly unlikely anyone could produce the exact same sequences of mouse movements (shy of recording them).

Not only that, but you don't have to waste a load of processor cycles to generate a decent random seed.

 

[Sunner]

The rng in Intel's i8x0 chipsets uses a couple of variables, don't remember off the top of my head, but I think it involves things like measured temps, time, etc, maybe what Jeff7 was talking about?

I believe /dev/(u)random under Linux gathers seed from things like disk activity, mouse/keyboard input, etc.

 

[Mark R]

There are a huge number of pseudo-random number generators available - some are good, some are terrible. The 'best' ones tend to be more complex and slower than others.

If you are running a scientific simulation needing a vast quantity of random numbers, then a fast algorithm may be acceptable - but there are interesting reports of some experiments showing very bizzare behaviour when an inadequate PRNG is used.

Where highest quality random numbers are required - either in science, or in cryptography the best option is to use a hardware random number generator. These use unpredictable physical phenomena to generate the numbers.

Many modern devices work using a high quality 'noise' source - usually a diode. The current flowing through a diode will actually show minute variability because of the quantum nature of electrical charge. The resulting noise can then be analysed and processed into a random number. A simple example might work as follows - for 1 ms count the number of times the current changes from below average to above average. If the number of transitions is odd, then the next bit in your number is a 0, otherwise it is a 1. Such a circuit is relatively simple and reliable. A more sophisticated variant of this type was implemented in intel's PC chipsets.

Other practical methods have included measuring the inaccuracy of a deliberately low-quality oscillator by comparing it to a very high quality one (used by ERNIE to select winning premium bonds), and geiger counters detecting background radiation.

There are major problems with true random number generators which limit their use - a sequence cannot be repeated (if needed for a repeat analysis); debugging of a program is difficult as the results will be different each time; how do you know it is working correctly?

For most people a good PRNG with careful and secure seeding should be adequate.

 

[Shalmanese]

A related question: How much would it cost to build a real random number generator into a CPU or chipset and do any CPU's have one (ie. Sparcs, Alphas etc). Are there any plans to put one into a consumer class CPU? I imagine it would be very useful for crypto use.

 

[dejitaru]

Any random occurrence is based on some uncontrollable, subatomic event. Particles directly affected by those which came before them, hence predictable.
Even the best RNG's are notably flawed.

Entropy is not mathematically or physically possible.

A related question: How much would it cost to build a real random number generator into a CPU or chipset and do any CPU's have one (ie. Sparcs, Alphas etc). Are there any plans to put one into a consumer class CPU? I imagine it would be very useful for crypto use.

Get a random seed. Generate a random number and use this for a new seed. Repeat with multiples, powers, square roots, etc. of your new number. -The exact algorithm would, of course, need be highly classified. Repeat. Repeat.

Some programs count (active) clock ticks since xxx event, use for seed.

 

[sparkyclarky]

Thanks for the replies folks. They have clarified things greatly!