Differences between version 11 and predecessor to the previous major change of RandomNumberGenerator.
Other diffs: Previous Revision, Previous Author, or view the Annotated Edit History
| Newer page: | version 11 | Last edited on Friday, March 26, 2004 3:26:38 am | by AristotlePagaltzis | Revert |
| Older page: | version 7 | Last edited on Thursday, March 25, 2004 9:23:55 pm | by StuartYeates | Revert |
@@ -9,17 +9,26 @@
A pseudo random number generator such as offered by the random(3) and rand(3) functions of the standard [C] library generates numbers using mathematical [Algorithm]s.
;: ''Anyone attempting to produce random numbers by purely arithmetic means is, of course, in a state of sin.'' --JohnVonNeumann
-The proof of this derives from the fact that computers are [FiniteStateMachine]s.
An inevitable consequence is that such a generator has a "period", which means that it produces a repeating sequence of numbers. With a good algorithm though, the period length can well reach billions of numbers.
+An inevitable consequence is that such a generator has a "period", which means that it produces a repeating sequence of numbers. The proof of this derives from the fact that computers are [FiniteStateMachine]s
. With a good algorithm though, the period length can well reach billions of numbers.
However, designing such an algorithm is difficult terrain which requires thorough understanding of statistics and very sharp math skills. __Do not attempt to roll your own.__ Most naive attempts at handrolled pseudorandom number generators have alarmingly short period lengths. Often, hapless programmers will try to make a "better" generator by lumping together two different algorithms with decent period lengths each -- but the result is almost invariably a generator with a ''shorter'' period!
Another problem in cryptographical applications of pseudorandom numbers is that the algorithm is known. If you know a long enough sequence of generated numbers, you can simply solve the resulting equations yourself and then predict the numbers the generator will be producing next. There is an obvious solution: the algorithm must include enough hidden state so that a solvable set of equations cannot be formulated just by looking at a number sequence it generated.
But note that true randomness still is not always desirable. Random number sequences often have certain specific characteristics which make them better suited as input to certain kinds of statistical algorithm, because they cause a far faster convergence toward the same final result than truly random numbers could. Truly random numbers also make debugging much harder for obvious reasons; if you want to verify an algorithm, you want to be able to replay "random" number sequences as necessary. On the other hand, you will usually need a statistically decently random sequence to examine the longterm behaviour of the algorithm, so just using a sequence with regular characteristics wouldn't work.
So there are many areas where pseudorandom numbers are actually more desirable than truly random ones.
+
+See also: srand(3), srandom(3), drand48(3), erand48(3), jrand48(3), lrand48(3), mrand48(3), nrand48(3), srand48(3)
!!! Hybrids
-In [Unix] systems, there's
commonly a __/dev/
random__ device to access a
pseudorandom number generator. This generator, however
, includes
a twist that lets it
generate higher quality random numbers than otherwise expected: its
seed is periodically perturbed using using low-level timing information from the network, mouse, keyboard, and possibly other
entropy sources,
which only the [Kernel] has proper access to. This generator is also
a FiniteStateMachine but it has access
to unique
inputs which
are hard to predict and very hard to
spy on. The weakness of this approach can
be seen
by imagining
the [Kernel] running
as UserModeLinux and the underlying kernel manipulating the value
of the ''hardware'' clock---in
such a situation it would be possible to force
/dev/random to produce the same
results repeatedly. It is generally considered a sufficiently good generator for everything except the random numbers to be used in cryptographic suituations PublicKey generation
.
+In [Unix] systems, there are
commonly random(4) and urandom(4) devices. They are regular
pseudorandom number generators
, but include
a twist that lets them
generate higher quality random numbers than otherwise expected: their
seed is periodically perturbed using using low-level timing information from entropy sources which only the [Kernel] has proper access to, such as the network, mouse, and keyboard
. These generators are considered
a sufficient for everything except highly sensitive cryptographic applications such as PublicKey generation (see RFC:1750 on best practices).
+
+In [Java] systems, instances of the class __java.security.!SecureRandom__ operate in a similar fashion. Making instances of this class can take several seconds while the [JVM] tries
to russle up entropy.
+
+The weakness of such a hybrid approach is that while its
inputs are hard to predict from outside or
spy on from inside the system encapsulated by the [Kernel] or [Java] VirtualMachine, it may itself may
be separated from the hardware
by a middle man. This is
the case with a
[Kernel] run
as UserModeLinux, f.ex,
and almost always
the case with a [JVM] which usually runs as a regular process under control
of an OperatingSystem. In
such a situation it would be possible to cause __
/dev/random__
to produce repetitive
results.
+
+----
+CategoryCryptography
