PUBLISHED: Ritter, T. 1991. The Efficient Generation of Cryptographic Confusion Sequences.

Cryptologia. 15(2): 81-139.

ADDRESS: Blue Jean Software, 2609 Choctaw Trail, Austin, Texas 78745.

ABSTRACT: A survey of pseudo-random sequence or random number generators (RNG's) for cryptographic applications, with extensive reference to the literature, and seemingly unresolved issues discussed throughout.

An introduction to random sequences is presented, with some consequences suggested by Godel's incompleteness theorem. Implications of a necessarily deterministic implementation, techniques of external analysis, and ways to complicate such analysis are discussed.

A basis for RNG comparison is suggested. Various RNG's are described, including Chaos, Cebysev Mixing, Cellular Automata, x^2 mod N, Linear Congruential, Linear Feedback Shift Register, Non-linear Shift Register, Generalized Feedback Shift Register, and Additive types. Randomizer and isolator mechanisms, one-way functions, the combination of sequences from multiple RNG's, random permutations, and the generation of primitive mod 2 polynomials are also described.

An empirical state-trajectory approach to RNG design analysis is given, and experimental results tabulated for several Cellular Automata, x^2 mod N, GFSR and Additive designs.

KEYWORD LIST: cryptology, cryptography, computer cryptography, confusion sequences, pseudo-random sequences, random number generators, cellular automata, GFSR, additive, lagged- Fibonacci, randomizers, isolators, primitive polynomials, combined RNG's, random permutations, exposure class, exhaustive state analysis

Random number generators (RNG's) have a central place in some
cryptosystem designs. For example, stream ciphers use an RNG to
provide a confusion sequence which is used to hide plaintext data.
Unfortunately, there are so many RNG designs, and so many different
claims for them, that it is difficult even to compare the claims,
let alone the designs. Accordingly, one purpose of this paper is
to provide one man's overview of various RNG designs, with special
attention to the needs of a cryptographic system. While no survey
can provide complete details of all designs, it can provide basis
for comparison and an
*index to the literature*
for those who are more seriously interested.

Although an RNG is just one part of a cryptographic system, here we assume that the rest of the system has somehow been penetrated, and wish to know how effective the RNG will be in resisting penetration on its own. We seek to understand the design of strong cryptographic RNG's, and are therefore interested in the weaknesses of RNG designs. Cryptographic "strength" is the ability to resist attack; in order to understand the strength of a design, we are necessarily forced to consider how to attack it.

The use of random number generators is central to stream ciphers [e.g., 12, 45], where the RNG constitutes most of the system. In broad terms, a Vernam stream cipher [194] consists of a combiner (generally a single exclusive-OR gate or instruction) and a confusion sequence generator. Usually, an arbitrary user key somehow selects a particular (and hopefully unique) sequence; the sequence generator may be the most complex part of the design. Although cryptographic applications obviously impose special requirements, one approach is to use one of the random number generators which have been developed for statistical use.

The major reference on the design and testing of computer based
RNG's is volume 2 of Knuth's classic
*The Art of Programming*
[91].
Unfortunately, Knuth never really addresses the special needs of
cryptography
[177: 90],
and the material is now seriously out of date even with respect to
statistical RNG's. Left without a current encyclopedic handbook, we
are left to peruse the original papers, and to form our own
conclusions.

Over the last decade, a new body of theoretical work has developed which seemingly has "solved" the RNG problem. (This includes papers by Shamir [167], Blum, Blum, and Shub [20], Long and Wigderson [107], Vazirani and Vazirani [191], Blum and Micali [24], Alexi, Chor, Goldreich, and Schnorr [4], Winternitz [205], Chor, Goldreich, and Goldwasser [32], Levin [103], Vazirani and Vazirani [192], Allender [6], Reif and Tygar [148], Goldreich, Krawczyk, and Luby [67], and Nisan and Wigderson [130].) This work describes RNG's which are said to be "unpredictable." The papers include detailed statistical proofs in algorithmic complexity theory, but they are very difficult to follow without a similar background. Hopefully, we will soon see introductions to this theory which will include all the tools necessary to follow these proofs, since these papers imply that this may be the future of all cryptographic design. It may be especially important to understand the consequences and limitations of these results. But, for our current purposes, it is just too early to assume that the RNG problem has been completely "solved."

From the perspective of classical probability, any sequence of equally-probable events is equally likely, and thus equally "random" [e.g., 91: 2-3 §3.1]. Obviously, this point of view fails to capture the essence of the difference between a sequence of identical values, and a mixed-value sequence of similar length. (Various approaches to "randomness" are discussed in Knuth [91: 142-166 §3.5].)

Perhaps a more useful interpretation is given in an outstanding
article by Chaitin
[30],
which develops "randomness" as
*information*
(also from Martin-Löf
[116]
and Kolmogorov
[93]).
At first this may seem very odd: Randomness is commonly considered
the
*enemy*
of information. When a radio signal is weak, reception is
noisy; when the antenna fails, a TV displays snow and delivers hiss.
The noise, snow, and hiss are randomness, and the normal role of
communication is to rise above the background noise to deliver
information in a pattern; now randomness is said to be the occurrence
of
*maximum information*. (The confluence between the ideas of
randomness and information, although apparently implicit in Shannon
[168]
and Pierce
[137],
is nearly explicit in Campbell
[29: 63, 68-69, 72],
and is explicit in Berlinski
[18: 69-70].)

If noise is just a massive amount of information, perhaps noise sources simply reflect a complex, hidden, internal order [80: 408-409]. Consequently, it is possible that cryptanalytic techniques could be useful in the physical understanding of nature [53]. (See also the discussion on the "layers" of a message by Hofstadter [80: 166-171].)

One aspect of data is that it is often redundant, and so can be
compressed.
*Data compression* finds and exploits patterns in the
data to reduce the overall size; the result is a smaller, more
random-like sequence. A "completely compressed" sequence presumably
would have no patterns at all; it would thus appear completely
random and would be difficult to perceive as intelligence, even
under intense analysis. But a sequence intended to be later
expanded probably will contain some amount of decidedly non-random
information representing the data deleted during compression. (Data
compression is a popular area of research, and includes work by
Huffman
[83],
Lempel-Ziv
[102],
Ziv and Lempel
[213],
Storer and Szymanski
[180],
Langdon
[97],
Welch
[199],
Cormack and Horspool
[39],
Cleary and Witten
[35],
and Bell
[15].)

Confusion sequences might also contain patterns which could be compressed. But no expansion would be necessary, so there would need to be no expansion information in the result.

One definition of a random sequence is that it has a size
approximately equal to its complexity.
*Complexity* is "the number
of bits that must be put into a computing machine in order to obtain
the original series as output"
[30: 49].
But minimizing the number of bits is what data compression is all
about. Thus, we can obtain a
*coarse*
measure of complexity by
actually compressing a sequence, and noting the resulting size
[56, 57].
(Many measures and tests of randomness are available: See Knuth
[91: 38-113 §3.3, 142-169 §3.5],
and also Massey
[117],
Yuen
[209],
Marsaglia
[114],
Tezuka
[185],
Rueppel
[161],
and Feldman
[55]).

According to the interpretation of information as the
non-redundant incompressible core of the data, it
*may*
be possible to show that a sequence is
*not*
random (by demonstrating a shorter
sequence which can reproduce the original), but it probably is
*not*
possible to show that a random sequence
*is*
random (since this would correspond to proving that
*no possible algorithm*
could compress that sequence). Thus, proving that a sequence is
non-random seemingly corresponds to the impossible task of "proving
a negative" in an unbounded system.

When we have only two possibilities (A,B), we may choose either
to prove the positive (A happened) or the negative (B did not
happen). But when we have a huge number of possibilities
(A,B,C,D,E,...) it quickly becomes impractical to prove that every
alternative possibility did not happen. When the number of
possibilities is unbounded, such proof is clearly impossible. But
to state that a sequence contains no sub-pattern is seemingly to
say that we have considered
*all possible*
sub-patterns and
*all possible*
relationships; clearly an impractical task. (If we did
have a process which could identify
*any*
pattern or relationship, we would seem to have the makings of a
"universal scientist" device.)

Chaitin relates the understanding of randomness (as a lack of pattern) to Gödel's incompleteness theorem [30, 31] (within any formal axiomatic system of sufficient complexity, assertions exist which cannot be proven either true or false). (Perhaps the best introduction to Gödel is Hofstadter [80], except it is difficult to use as a reference.) There are various limitations which are inherent in logic systems, but Gödel's result applies to almost all systems of reasoning and proof. An intuitive reason for this sort of thing is that a formal system can be used to build an unbounded number of assertions. But finding the correctness of some assertions may require the construction of an unbounded number of other assertions, which is clearly impossible [80: 72]. (Normally, the biggest problems involve self-reference, which Gödel attacked by inventing a coding scheme to convert a statement about number theory into a number which could be operated upon inside number theory.)

It is probably dangerous to extend these ideas beyond formal
systems, but it is certainly tempting to make a word-analogy with
respect to ciphers: Although it may be possible to show that a
cipher is weak, it may
*not*
be possible to prove that a cipher is
strong (since this would correspond to proving that
*no possible technique*
could break the cipher). (Perhaps the sole exception
applies to those ciphers which could reasonably be "deciphered" to
produce any possible message
[76, 108];
here the issue would not be the ability to recover a message, but,
rather, the inability to know
*which*
of all possible messages was intended.)

Since a similar word-analogy would seem to apply to RNG's, it is
difficult to imagine how an RNG could possibly be
*proven*
to resist
*every possible*
attack. It is not clear that there is an exception
for special types of RNG; we simply may have to make do with RNG's
designed to resist every
*known* class of attack.

By this line of reasoning, a deep proof of the "unpredictability"
of a deterministic sequence would seem to be at odds with the
definition of randomness as a lack of any pattern or relationship.
This result
*seems*
reasonable, but it is not clear to me whether it is actually
*valid*.

Although many RNG techniques were apparently developed from a
real-number mathematical base, within a computer
*every*
RNG is a discrete logic mechanism, a
*finite state machine* (FSM)
[e.g., 71, 12]
functioning step-by-step. The consequence of such discreteness is
an inherent regularity in a mechanism intended to display
"randomness."

Most computer RNG's are iterative mechanisms; they take some
amount of stored data or
*state*,
transform it into a new value, and
output part or all of the new data as a "random" number. Clearly,
the result is
*deterministic*,
and so is
*anything but*
random; given the stored data and the transform equation, the next
state is
*absolutely*
predictable. However, absent knowledge of the internal
state, the external results may
*appear* to be random. Such a
sequence is often called
*pseudo*-random,
and has the advantage that
the identical sequence can be reproduced at another place or time,
given the only the stored data and the transformation process. For
cryptographic purposes, it is often possible to develop the state
for the first RNG operation from a keyword or key phrase; this
allows a user to generate a generally unique, seemingly-random
sequence corresponding to each arbitrary key selection.

It is important to remember that digital computers can perform
only
*discrete*
computations; there is no way of reproducing the
mathematical concept of continuous "real" values within such a
machine. Computer "floating point" numbers generally are fine
replacements for mathematical "reals," but there are only so many
floating point values, and such computations often imply a result
which is not exactly representable as floating point. A
random-number scheme based on continuous mathematical values may
not provide acceptable results in a computer environment. Because
floating-point implementations vary, such a scheme may not even
provide the same results in different machines.

Within an RNG mechanism there is a given amount of internal state
data, say *k* bits, and the output value is some function of
that state; such a mechanism can produce, at most, only *2^k*
different output values. For any deterministic RNG mechanism, linear
or non-linear, each particular internal state will
*transition* or *step*
to one and only one particular succeeding state. Thus, whenever a
particular state re-occurs, all subsequent states must also re-occur,
in order; this is a direct consequence of the deterministic nature
of the mechanism, and is independent of the "linearity" of the
next-state transformation.

The maximum number of states possible in *k* bits is
exactly *2^k*, so this is the maximum possible sequence
length before repetition. If an RNG state re-occurs after exactly
*2^k* steps, here we call the RNG
*perfect*. (The
formation of repetitive cycles in continuous systems is the job of
an oscillator, for which there is extensive theory; perhaps a
related theory could be developed for discrete systems like RNG's.)

Since each particular state implies a particular next state,
every perfect RNG generates exactly
*one*
sequence containing
*all*
possible states (that is, a perfect RNG generates a
*permutation* of
the possible states). The fact that a perfect RNG generates just
one sequence is important, for a cryptographic RNG is generally
initialized in an arbitrary state as some function of an arbitrary
user key. If every possible state value is included in the RNG
sequence, then any possible initialization of the state data is
part of the perfect sequence. Indeed, in this case initialization
is equivalent to starting the RNG at a different part of the
sequence, and this is a logical consequence of the deterministic
nature of the system. Of course, even with a perfect RNG there can
be only *2^k* different starting positions, and, thus, only
*2^k* even
*apparently*
different output sequences.

For our purposes, a sequence of states in state-space is a
*path* or *trajectory*;
a path which repeats endlessly is a
*cycle*; a path
which does not repeat itself is an
*arc*.
Here it is convenient
to define that every state which is not part of a cycle is part
of an arc, and we know that every arc inevitably connects to, or
*joins*,
a cycle. (Suppose not: then an acyclic arc will run out of
states, but the last unused state must step to
*some*
other state,
which will have already been used, and is thus part of a cycle.)
An arc may join another arc, which joins another arc, and so on,
in the form of a sub-tree, or
*branch*, but within a finite
state-space any arc must eventually join a cycle, even if only a
single-state
*degenerate*
cycle. Note that if branches occur, they
are necessarily "narrowing" branches (joins) as opposed to
"expanding" branches; a state cannot have multiple next states,
unless affected by something outside the system.

Most RNG's fail to achieve a perfect sequence length; such
systems thus include various possibilities of multiple independent
paths of arcs and cycles. In general, short cycles are possible,
perhaps even likely. But the actual use of a short cycle could be
a cryptographic disaster, for such a sequence would be easy to
cryptanalyze
[157].
(Also see Johnsen and Kjeldsen
[85]).
For cryptography, a sequence might be considered "long enough" if it
would not repeat during the longest message or session,
*and* would be
extremely unlikely to re-occur throughout all use by all fielded
systems over all of time.

If an RNG supports multiple cycles of different length, then an
arbitrary initialization may well start the RNG within a "shorter"
cycle. This means that some user keys may be "better" than others;
unfortunately, the user is unlikely to know the difference, and so
may pick a "less-secure" key. Normally, the RNG designer must
*guarantee*
that the minimum possible cycle length is "long enough,"
and will be unable to do this experimentally for a system of useful
size. Thus, the RNG design will generally
*require*
a useful theory
of operation, including a guarantee of minimum cycle length.
Moreover, if the design supports any degenerate cycles, the designer
must also guarantee that the system is not initialized
*in* a
degenerate cycle,
*or on*
any reasonably-short arc
*leading* to a
degenerate cycle (or give the system the ability to detect such a
cycle at run time). Such initialization guarantees are not
available in many RNG designs, and may imply substantial overhead
when they are available.

Normally, a cryptanalyst attacks an entire cipher, and the first part of such an attack on a stream cipher may be a penetration of the combiner; the analyst then confronts the confusion sequence directly. Consequently, the cryptographic designer must be concerned with the resistance of the RNG when the analyst has the sequence at the combiner (this may not be the direct output of the RNG). There seem to be three main categories of attack on an RNG: repetition, inference, and brute force:

**Repetition** involves the search for plaintext fragments
which have been enciphered with the same confusion sequence. The
properties of the usual additive combiner allow a repeated sequence
to be eliminated; the result is an additive combination of two
plaintext language messages, which should be fairly easy to decipher.

In practice, it may not be possible to externally identify the
start of a particular RNG sequence, and attempting such an attack
on every character position of every message combined with every
character position of every other message seems like a very big
job. Nevertheless, to some extent this may be automated, and has
the advantage that it can be applied to
*any* confusion sequence, no
matter how complex or "unpredictable" the generating mechanism.
It is unnecessary to "predict" an RNG sequence, if it will repeat
soon.

**Inference** is the standard intellectual attack we usually
associate with RNG penetration. Given an understanding of the
RNG mechanism, and some amount of the sequence, the content of
the RNG is refined until it is fully known. One approach would
be to develop a set of simultaneous equations, which, when
satisfied, define the RNG state completely. These equations do
not have to be linear. Although the solution to the general
case of simultaneous non-linear real-value equations may be
difficult, the particular case of non-linear binary equations
(e.g., AND, OR) can actually
*support*
cryptanalysis
[171].

Should it ever become possible to partition or select only those RNG states which provide a particular output value, and then select from those a similar fraction which match the next output value, an RNG can be broken quickly. Each bit of RNG output might discard fully half of the potential states, so that a number of output bits equivalent to the number of RNG state bits should be sufficient to fully define the RNG. The problem, of course, lies in finding a selection process which avoids actually having to store each and every RNG state, and compute each next state, since an actual cryptographic RNG would be large enough to make this impossible. (A probabilistic approach is given in Anderson [7].)

**Brute Force** is another method which is always applicable,
and if the analyst is very lucky, just might turn up the answer, even
if this would be statistically unlikely. One approach would simply
be to step an equivalent RNG through its possible states until the
reproduced sequence matches the known one. Usually, the system
designer will have arranged to make the RNG large enough to make
such an attack impractical, although brute force can also be
efficiently automated, to some unknown extent.

Brute force may also be used along with other results, and so be much less impractical than it may at first appear. For example, suppose most of the RNG state is known (or guessed); brute force can then be applied to find only the missing information, which may be a far easier task.

It is desirable to maximize the resistance of an RNG design to
external attack; I use the concept of *exposure class* to help
describe a modest degree of resistance, and define various exposure
classes:

**Class A**: The output value is the entire internal state.
The knowledge of the precise internal design plus
*just one* RNG value
should be sufficient to penetrate such a system. Even with only
a general knowledge of the internal design, a few steps of the
entire internal state should be enough to pin down the system
precisely. Secrecy is not an issue for statistical use, and most
common computer language RNG's are "Class A" mechanisms for statistics.
Obviously, the cryptographic use of this sort of RNG, without added
protection, is not a good idea.

**Class B**: The output value constitutes the entire
*change* in the
internal state (although the change is a proper subset of the total
state). In many cases, a sufficient sequence of output values will
eventually define the complete internal state, thus eventually making
the system as vulnerable as "Class A." Again, such an RNG design
needs additional protection for use in a cryptographic system.

**Class C**: The output value is a proper subset of the state
change.
In this case, a knowledge of the output sequence will disclose only
partial information about the internal state. Alone, this may not
provide much added protection, but is nevertheless an improvement
over no protection, as provided by "Class A," or the simple minimum
sequence requirement of "Class B."

An RNG has some amount of internal state; some function of that
state is produced as output. Seemingly, each output bit must deliver
*some*
amount of information about the content of the RNG, and so eventually the
total information should be enough to penetrate the system. Purely from
an information perspective, one definition of a well-designed RNG might be
that it cannot be penetrated
*by any technique whatsoever* until the analyst
has at least as much output as the total RNG internal state. (This certainly
seems like a familiar idea: Could it be reasonable to have a sort of "unicity
distance"
[e.g., 44; 124: 607-648,
728-740]
for an arbitrary RNG design?)

Alas, when the RNG is used to produce
*more* output than the total
of its internal state, things seem considerably less certain. Any
RNG which produces more output than some constant factor of its
internal state is probably in the hazy twilight world of having
revealed itself sufficiently for solution, if only some efficient
procedure could be found to do it. Although we can perhaps analyze
the strength of an RNG with respect to a
*particular* attack, it seems
rather unlikely that analysis could address *any possible*
attack.

For example, even if the output carries
*absolutely no information at all*
about the RNG state, the sequence must nevertheless repeat
eventually, and becomes vulnerable at the point of repetition. This
approach does not require the RNG to reveal itself; and since this
approach obviously exists, the question is: "Is it the only such
approach?" It does seem clearly unreasonable that any sort of RNG
could produce pseudo-random output
*forever* without limit and yet always resist penetration.

The ability to infer some part of the content of a system is not the same as the ability to predict the output. One way to clarify this is to examine how we might attack a few simple systems:

Consider a simple counter, of which the least significant bit (lsb) is used as output. Obviously, no external analysis of any sort could be expected to resolve the full state of the counter, since the lsb does not depend on the other bits. But this would scarcely hinder our prediction of the next output value, for the lsb simply alternates.

Now consider the same counter, this time with the most significant bit (msb) as output. Apparently, examination of that bit would reduce the possible internal states by half, but only once; subsequent bits would provide little additional information until the msb actually changed. Of course, when the msb did change, it would completely resolve the counter state, for at this time it depends upon a particular state of all lower bits. Again, our understanding of the internal state would have little effect on our ability to predict the output, since the msb generally does not change.

A better situation for analysis, but worse for prediction, would seem to be an output bit which always depends on the entire internal state, and in which the internal state changes in a pseudo-random fashion. By examining the output bit, we are able to reject half of the possible states on each step: We at first assume any possible internal state, but about half of those states will be inconsistent with the first output. Then we step each of the remaining possible states to its logical next state, and again find that we can reject about half of those with the next output bit. Consequently, a definite resolution of the internal state should be fairly quick, but until we have such a resolution, we may well be unable to predict the output.

Thus, the inability to predict the next output value does not necessarily prevent us from eventually resolving the complete internal state, which would then allow computation of all subsequent values. It is unnecessary to "predict" the output, if you can compute it.

In order to compare different RNG's it is necessary to have some basis for comparison, and I have selected some attributes which seem most important. From a design point of view, a cryptographic RNG should:

**allow arbitrary initialization**, to support unbiased keys;**have a guaranteed long sequence**, to make repetition (coincidence) attacks impractical;**be easy to customize**, so that different users can have different sequences when using exactly the same key;**be fast**, for an unused system is . . . , well . . . , useless;**be difficult to analyze**, since analysis could penetrate the cryptographic system (although we may be able to improve this with a separate isolator mechanism); and,**produce a good distribution of values**.

The statistical properties of the RNG, which are the main requirement for statistical use, may be less important for cryptography; we assume that a cryptanalyst will already have a deep understanding of the mechanism itself, and so will not have to infer its structure from the statistics of the sequence. This is just as well, for most cryptographic RNG's are used over only tiny portions of their sequences, yet the statistical descriptions of their sequences (if any) are generally restricted to the entire sequence.

There are many different techniques for the production of pseudo-random sequences. Techniques of particular interest, and which will be covered in the indicated sections, include:

4.1 Chaos, or non-linear dynamical equations;

4.2 Cebysev Mixing, used in computational physics;

4.3 Cellular Automata, a sort of 1-dimensional "Life";

4.4 x^2 mod N, said to be "unpredictable";

4.5 Linear Congruential, the common computer RNG;

4.6 Linear Feedback Shift Register (LFSR), which produces an almost-perfect sequence, but is easily inferred externally;

4.7 Non-Linear Shift Register, perhaps more opaque than the linear version, but also more difficult to customize;

4.8 Clock-Controlled Shift Registers, which are systems of multiple shift registers with clock enable or disable signals, and combined output;

4.9 Generalized Feedback Shift Register (GFSR), which allows customized element width, shift-register height and polynomial; and the

4.10 Additive RNG, which is easier to initialize than a GFSR, and produces a longer sequence than a GFSR of similar size.

One of the most exciting new areas in mathematics is the exploration of non-linear dynamics, or "chaos." Various popular books [e.g., 65] are available as overviews; Rietman [151] and Beker and Dorfler [13] are computer-oriented introductions, Nicolis and Prigogine [128] is a serious introduction, Rasband [145] a math text, and Pickover [136] shows the development of chaos in mathematical networks.

Chaos can be used to produce complex and interesting graphic images, and can be appreciated at that level. But chaos is particularly exciting in the way it reveals that incredibly complex systems are defined by very simple, even trivial equations, for example (here we use brackets [...] to enclose subscripts):

x[n+1] = Ax[n](1 - x[n]), with 0 < x[n] < 1.

To those of us conditioned to "solve" fairly complicated systems,
this at first seems to be an exceedingly dull equation. Certainly,
if the left-hand-side were
"*y*," little would remain to be said. But
since the left-hand-side is
"*x*[*n*+1]," we have an
*iterative* equation,
and this makes all the difference. It is the sequence of values
produced by repeatedly applying the equation which forms the
complex system and chaos. (The repeated application of a function
is also central to group theory.)

The insight that even very simple iterative equations can produce
exceedingly complex sequences should be a warning to us, since
*most if not all*
RNG systems are iterative. But just because a system is
complex for certain starting values does not mean that the same
system will necessarily be complex for
*any* particular starting value;
this is one of the fascinations of chaos. Matthews
[119]
generalizes the simpler equation and, with cryptographic constraints,
develops the following:

g(x) = ((B+1)(1+1/B)^B)(x(1-x)^B), with 1 <= B <= 4, 0 < x < 1.

Only a subset of each result is used as the random value; Matthews uses the last two decimal digits. Wheeler [201] describes some results from the system, and Mitchell [125] re-directs the design toward one-way functions.

Although nonlinear dynamical equations seem to imply essentially continuous real values, when implemented on a computer such equations must be just another discrete system with a finite state-space. Such systems obviously must have some maximum sequence length, and may well have many independent short cycles. There would currently seem to be no theoretical insight into sequence length for chaos equations.

The study of chaos was triggered by the discovery of ways to
find and analyze order present in an apparently chaotic result;
ironically, the analysis of apparently chaotic results is precisely
what we wish to
*avoid*
in a cryptographic RNG. Of course, a
*theoretical*
analysis is common with other RNG's to avoid dangerous
short cycles (although we have no such results here). But until
we know the limits of external analysis using chaos experimental
techniques, we might well wonder whether chaotic RNG's are
"inherently tainted" for cryptographic use.

Because chaos equations generally imply floating point evaluation, such a sequence is likely to differ on various types of computer or calculator, and computation time is likely to be substantial. Matthews' equation seems to require three transcendental evaluations for each pseudo-random result; this is a great deal more computation than most RNG mechanisms require.

Another floating-point iteration (and perhaps related to chaos) comes from "computational physics." Apparently, very long pseudo-random sequences are used to simulate physical reality on a molecular level. Moreover, the results of such a simulation would have the refreshing consequence of detailed experimental verification.

One such mechanism, championed by Erber [51, 52], is the Cebysev "mixing" polynomial (a similar term, "mixing transformation," has been attributed to probability theory [169: 711]), for example:

Z[n+1] = (Z[n])^2 - 2, on the interval [-2, 2],and

output = (4/Pi) ArcCos(Z[n+1]/2) - 2,or

output = Z[n+1] without the most-significant fractional n bits

Erber's extensive analysis of this simple iterative formula
seems to be a statistical education in itself. Nevertheless, it is
quickly obvious that some particular precise values for
*Z*[*n*]
must be avoided (e.g., -2, -1, 0, 1, 2); with a non-integral seed,
it is expected that these values will "never" be encountered. (Such
hopes may be unacceptable in cryptographic service, unless a
mechanism is included to detect such an occurrence.) Eventually,
floating-point "roundoff" and other errors come to dominate the
computation, and this particular scheme is found to remain "stable"
(that is, pseudo-random) under those conditions. A system with
12-decimal-digit math seems to provide arc lengths and terminating
cycle periods of around 105 steps.

Unfortunately, several investigators have found Cebysev mixing RNG's to perform rather poorly. Hosack [82] gives it the advantage of being "amenable to theoretical analysis," but recommends that "because of its strong correlations, it should be used with caution." Wikramaratna [204] is even more discouraging, and says that Cebysev mixing "possesses undesirable qualities which make it unsuitable as a source of random numbers."

The common form of Cebysev mixing displays its complete internal state, and thus is "Class A"-exposed in cryptographic service, and so needs some form of isolation. Cebysev mixing also seems to require floating point arithmetic (although a sort of scaled-integer form should be possible). The single multiply and subtract are just about the minimum possible iterative computation, but an integer-math RNG would still probably be faster. Moreover, the floating point requirement generally causes different sequences to be produced on different types of machine.

Another new RNG approach is Wolfram's [207] "cellular automata" generator. The field of cellular automata (CA) has a rich history outside cryptology, from von Neumann and Burks [27], through John Conway's "Life" game [e.g., 63, 141], to the current field of "artificial life" [9]. Wolfram has examined a range of rules for linear CA's, and has proposed [206] two similar rules which seem suitable for cryptographic use. Wayner [198] provides a popular description and simple software implementation of this system (in BASIC). (Some statements were missing from the listings in the printed article.)

Basically, the suggested Wolfram system consists of a
one-dimensional "vector" or linear array of elements,
*a*[0]..*a*[*n*],
and the iterative equation:

a[i] = a[i]-1 XOR (a[i] OR a[i+1]).The array is considered circular, and the new element values are considered to be updated in parallel. The output is taken from one element (e.g., a bit or byte) only; thus the CA RNG is normally operated "Class C."

This is relatively new work, and the current state of the theory of these systems is comparatively weak (there is some investigation in Rietman [151: 113-131]). Every discrete system must have sequences of some length, but currently there seems to be no theory to support statements about CA sequence length or the distribution of CA pseudo-random values.

This particular CA method requires three array-access operations
plus two logical operations
*for each element of the array*. While
fairly simple as a hardware mechanism (since hardware may perform
each cell computation in parallel), a large CA RNG may involve more
computation than desired for a software implementation.

(Also see the Cellular Automata experimental results in Section 7.)

Yet another new RNG approach is the "x^2 mod N" generator of
Blum, Blum, and Shub
[20, 21].
This RNG seems unique in that it is claimed
[21]
to be "polynomial-time unpredictable" (p. 372) and "cryptographically
secure" (p. 381). To put this in perspective, we should recall that
all digital computer RNG's,
*including*
x^2 mod N, are deterministic
within a finite state-space. Such mechanisms necessarily repeat
eventually, and may well include many short or degenerate cycles.
It is unnecessary to "predict" a sequence which will repeat soon.
Accordingly, the x^2 mod N RNG requires some fairly-complex design
procedures, which are apparently intended to assure long cycle
operation.

Basically, the RNG consists of the iterative equation [207: 125]:

x[i+1] = x[i]^2 mod N,where

N is the product of two large distinct primes,and

result bit = parity(x[i+1]),or

result bit = lsb(x[i+1]),or

result = log2(N) lsb's of x[i+1].

The x^2 mod N design
[21]
originally produced only the single bit of output per iteration, the
"parity" of x (p. 368). The paper then goes on to say: "Parity(x)
is the least significant bit of x" (p. 376), which is apparently
common mathematical usage. (The standard communications and
computer design usage of the term "parity," is the mod 2
*sum*
of the bits in a single code value
[e.g., 127: 44; 84:
472-473].)

Alexi, Chor, Goldreich and Schnorr [4] shows that at least log log N bits can be used safely, while Vazirani and Vazirani [192] shows that the log N least-significant bits can be safely used. Vazirani and Vazirani also proves the RNG as secure as factoring N. Kranakis [95] gives number theory particularly directed toward cryptography, including the x^2 mod N generator.

For those number theorists who have been bored up to now, things are about to get more interesting, since both N and x[0] must be specially selected, as described in the main paper [21]:

N is to be the product of two large distinct primes, P and Q.
Both P and Q are to be congruent to 3 mod 4,
*and* must also be
*special* (p. 378). Prime P is
*special* if P = 2P1 + 1 and P1 = 2P2 + 1
where P1 and P2 are odd primes. The paper gives 2879, 1439, 719, 359,
179, and 89 as examples of special primes (but 179 and 89 appear to
*not*
be special, while 167, 47 and 23 should be). As yet another
condition,
*only one* of P1, Q1 may have 2 as a quadratic residue (P1,
Q1 are the intermediate values computed during the "special"
certification). If we mark such
*particular* special primes with an
asterisk ("*"), we get, for example: 23, 47*, 167, 359, 719*,
1439*, 2039, 2879*, 4079*, 4127*, etc. Accordingly, N = 719 * 47
fails the additional condition, because both special primes are
*particular*. Presumably, these detailed conditions guarantee
the existence of long cycles, but they do not banish short ones.

The x^2 mod N generator is not
*perfect* in the sense of this paper:
it is not a permutation generator. As an illustration, consider the
x^2 mod N system of P = 23, Q = 47 (N = 1081), a system specifically
given as an example "of the prescribed form" (p. 378): Starting with
x[0] = 46 we get 1035, then 1035 repeatedly; a degenerate cycle.
Starting with x[0] = 47, we get 47 again; another degenerate cycle.
Starting with x[0] = 48, we get 142, 706, 95, 377, 518, 236, 565, 330,
800, and 48; a 10-state cycle. And starting with x[0] = 24, we get 576,
990, 714, 645, 921, 737, 507, 852, 553, 967, and 24; an 11-state cycle.
Other cycles include another 10-state cycle (x[0] = 94), three more
11-state cycles (x[0] = 437, 484 and 529), and a couple of much more
desirable 110-state cycles (x[0] = 2 and 3). However, no matter what
value of x[0] is selected, this system cannot hope to generate all
possible states, nor even the full set of quadratic residue states,
but is instead limited to those states within a particular cycle.

Because an x^2 mod N generator generally defines multiple cycles
with various numbers of states, the initial value x[0] must
be specially selected to be sure that it is not on a short cycle
(p. 377). The paper says to select x[0] such that the
"order" of x mod N (that is, the length of that cycle) is a
particular value, specifically Lambda(N)/2, where Lambda is
"Carmichael's Lambda-function." The function Lambda(M) can be
computed using
the least common multiple (lcm) of the factors of M. However,
computation of ordN(x[0]) for a particular x[0] (p. 379) would
seem to require a substantial amount of work. Experiments by L'Ecuyer
and Proulx
[99: 472]
suggest that finding large special primes and an element in a long
cycle may require on the order of 10^5 fairly-involved
test-certifications; they report 155 hours of CPU time (on a
MicroVax II) for an
*improper* 128-bit design.

I had assumed that finding *N* would be a configuration
problem, and thus generally irrelevant to frequent use. But
L'Ecuyer and Proulx
[99: 473]
assert that *N* "must remain random," and that *N*
"is part of the seed." The penalty for violating this restriction is
apparently the loss of guaranteed polynomial time unpredictability,
which is the whole reason for using this generator. Consequently,
special prime certification seemingly cannot be an off-line process,
but instead must be in the critical path of seed generation, a path
which must be traversed prior to enciphering. (Both the chosen
*N* and *x[0]* would presumably be transferred securely
to the deciphering system without further computation.)

The worrisome part of all this is that we would normally expect
the "seed" value, *x[0]* (and now *N*), to be some
almost-arbitrary function of an arbitrary user key
[e.g., 24: 854],
and such will not be the case with the x^2 mod N generator.
Of course, we might simply choose to accept the risk of being on a
short cycle, but this hardly seems consistent with the goal of
a "cryptographically secure" RNG. Another possibility would be
to use some sort of RNG to step through values, from an initial
arbitrary value, until some acceptable x^2 mod N seed is found; this
would naturally require a reasonable real-time cycle-length
certification routine. The paper does prove the existence of an
algorithm to allow random access within a cycle (p. 379); if this
could be done in real (user) time, yet another possibility
would be to use the arbitrary key to position the RNG arbitrarily
within a certified long cycle. For *N* of the correct form,
it may be that the value 2 is always part of such a cycle.

For cryptographic work, both *x* and *N* will be very
large quantities; the multi-precision multiplication and division
required for each RNG step would be slow, without even mentioning
configuration and initialization. To form *N* we will likely
apply some sort of probabilistic primality test on very large random
numbers
[e.g., 91, 69],
implying RSA-like computational capabilities for real time use.

Log2(N) or fewer bits are output on any step, thus normally
operating "Class C." Since the x^2 mod N generator does so much
work for so little output, it is tempting to ask how other RNG
methods would fare if they, too, produced just a few bits per step
[192].
Apparently, simple RNG's which discard
*lower* order bits
[179, 25],
or even *higher* order bits
[75]
can be insecure; perhaps the
*number* of bits produced per step is
more important than their position. Or perhaps the particular bits
to be used could be selected dynamically.

The x^2 mod N generator is thought to be a "one-way" function under the "discrete logarithm assumption" [21], and its secrecy properties are further developed in Blum and Micali [24], Long and Wigderson [107], Alexi, Chor, Goldreich and Schnorr [4], and Chor, Goldreich and Goldwasser [32]. Vazirani and Vazirani [191] shows x^2 mod N to be a "trapdoor" one-way function. And Shamir [167], Levin [103], Allender [6], Goldreich, Krawczyk and Luby [67] and Nisan [130] extend one-way functions into pseudorandom generators. However, in using this work we must not forget that these are academic papers, and the details of the x^2 mod N design are known from Blum, Blum, and Shub [21] (also Kranakis [95] and now L'Ecuyer and Proulx [99]); none of the other papers even mention the fairly complex details which are necessary to design and operate this generator securely.

The x^2 mod N RNG is claimed to be "unpredictable" (when properly
designed), but even this is no absolute guarantee of secrecy. An
attack on RNG repetition does not require "prediction." Even a
brute force attack has the
*possibility* of succeeding quickly. An
inference attack could be practical if some way could be found to
efficiently describe and select only those states which have a
particular output bit-pattern from the results of previous such
selections; that we currently know of no such procedure is not
particularly comforting.

(Also see the x^2 mod N experimental results in Section 7.)

The linear congruential generator (LCG) is one of the oldest, and still the most common type of random number generator implemented for programming language commands. The reason for this is that it uses a relatively simple iterative formula,

X[n+1] = (aX[n] + c) mod m,which is relatively fast and easy to compute. The values

The simple formula means that the LCG is relatively easy to
program, but selecting appropriate parameter values for *a*,
*c*, and *m* is not easy. The current level of analysis
seems insufficient to predict the parameters for best randomness,
so the design of a statistically acceptable LCG involves much
trial-and-error and expensive randomness testing
[91: 38-113 §3.3].
Moreover, LCG's regularly fail successively-more-precise analysis
[e.g., 112, 203,
132],
which can thus require yet another complete design session to
find some parameters which will pass all the tests.

Guinier
[73]
does give a method for making LCG design almost trivial. In this
scheme, the modulus (*m*) is prime and the constant (*c*)
is zero, which apparently implies a period of one less than the value
of the modulus (the value zero is prohibited). The product of the
multiplier and modulus is also limited to the range of the available
positive integer arithmetic (e.g., 31 bits), with the multiplier
being the square root of the modulus. This assures that the result
is always computable without overflow.

In a Guinier design, multiple LCG's are used, each with a different prime modulus. The output values from the various LCG's are additively combined, producing an extremely long sequence. The result may also be "more random" than a single LCG, since any bad subsequences are likely to be hidden by good output from other LCG's. Guinier suggests using as many as 1024 separate LCG's, thus producing an "astronomical" sequence length; naturally, such a design would also require 1024 times the computational effort of a single LCG.

LCG's can also be designed as permutation generators, either of
period *m - 1* (in which case the zero value may need to be
inserted in the output somewhere at random), or of perfect period
*m*
[91: 15-20 §3.2.2].
However, it is not clear that all *m* factorial possible
permutations could be achieved in this way, nor what characteristics
the achievable permutations might have in common.

If randomness, by itself, were sufficient for cryptographic use, perhaps a "good enough" LCG could be found. But the real problem with most LCG's is their tiny amount of internal state, simple step formula, and complete exposure. If even a few values from the pseudo-random sequence become available for analysis, the formula can be deduced, the sequence reproduced, and the cryptosystem penetrated [147, 190, 92]. Consequently, LCG's cannot be considered secure, unless strongly isolated, or perhaps combined with other generators [109, 200, 202, 113, 98, 203, 73]. Because it is difficult to find a good set of LCG parameters, LCG's are normally difficult to customize.

A
*shift register* (SR) is a set of storage elements in which the
values in each element may be "shifted" into an adjacent element.
(A new value is shifted into the first element, and the value in
the last element is normally lost.) There are several different
ways of implementing the same logical concept, both in hardware
and software.

In an *n*-element SR, if the last element is connected to
the first element, a set of *n* values can circulate around
the SR in *n* steps. But if two element values in an
*n*-element SR are combined by exclusive-OR and that result
connected to the first element, it is possible to get an
almost-perfect
*maximal length* sequence of 2^*n* - 1 steps.
(The all-zeros state will produce another all-zeros state, and so
the system will "lock up" in a degenerate cycle.) Because there
are only 2^*n* different states of *n* binary values, every
state value but one must occur exactly once, which is a
statistically-satisfying result (for the entire cycle, of course).
Moreover, this is a perfect permutation of the "natural number"
state values (1..2^*n* - 1). (Actual permutation applications
may need all "counting" values 0..2^*n* - 1; in these cases,
it may be sufficient to insert the zero state somewhere at random.)

The mathematical basis for these sequences was described by Tausworthe [184] as a "linear recursion relation":

a[k] = c[1]*a[k-1] + c[2]*a[k-2] + ... + c[n]*a[k-n] (mod 2)where a[k] is the latest bit in the sequence,

The general analysis of
*linear feedback shift registers* (LFSR's)
is based on the algebra of finite fields
[e.g., 14, 120],
and is available in a magnificent work by Golomb
[71],
a text by MacWilliams and Sloane
[111],
and a small book by de Visme
[46];
there is also an interesting short introduction in Simmons
[175: 328-329].
A cryptographic view is available in Beker and Piper
[12],
related topics can be found in Berlekamp
[17],
and there is an interesting general paper by MacWilliams and Sloane
[110].
(A technique for producing longer cycles, basically by cyclically
changing the feedback polynomial, is investigated by Reed and Turn
[146].)

It turns out that an LFSR mechanizes a finite field multiplication
operation
[111: 89],
and is also closely related to finite field division
[111: 210].
(Also, each LFSR has a "dual," which is arranged differently, but
which produces the same sequence.) A maximal length sequence will
occur if the SR "taps" form a polynomial which is *primitive*.
(A primitive is a special kind of *irreducible* or prime in the
given finite field.) A degree-*n* primitive mod 2 polynomial
actually has *n*+1 bits and is used with an *n*-bit SR;
the extra bit represents the feedback result or input to the SR.
Different
primitives produce different sequence permutations; although not all
*n factorial* sequences are available, there can be *many*
primitives.

The statistical performance of an LFSR with a primitive feedback polynomial really is quite luxurious (e.g., Golomb [71], or the interesting analysis by Horowitz and Hill [81: 655-664]); when we look at the sequence of bits produced by the feedback polynomial we find:

- there is only one major cycle, with length 2^n-1 steps (the all-zeros state is an isolated and degenerate cycle);
- over the whole major cycle, the counts of 1's and 0's almost exactly balance (there is one more 1), so 1's and 0's are almost equally likely; and
- over the whole major cycle, every possible subsequence of
*n*bits (except all-zeros) occurs exactly once, so each of these subsequences is also equally likely.

Tausworthe
[184]
was principally concerned with
*decimating* or collecting periodic
bits from an LFSR, and interpreting each collection as a binary
value; statistics computed over many such values are expected to
correspond to a random sequence. Further statistical analysis was
undertaken by Tootill, Robinson and Adams
[188],
Tootill, Robinson and Eagle
[189],
and an improvement suggested by Fushimi
[59].

Despite these favorable statistical results, an LFSR output can nevertheless apparently exhibit "nonrandom higher-order correlations." Compagner and Hoogland [38] present some convincing graphics which illustrate such relationships.

The desirable statistical performance of the LFSR is guaranteed
for any primitive polynomial, so the design of maximal-length
sequence generators reduces to finding a primitive feedback
polynomial. There are "lots" of primitives, but there are also
about *n* random polynomials for each primitive of degree
*n*, so it can take some work to find primitives in
large-degree polynomials. (There is a later section on finding
primitive polynomials.)

The feedback result of the LFSR is generally used as the output;
thus, the mechanism is normally operated "Class B." Consequently,
given a sufficient quantity of the pseudo-random output, the LFSR
length and feedback connections can easily be solved (only 2*n*
bits are needed), and the sequence reproduced
[123, 166,
157, 134].
Of course, the LFSR can be made arbitrarily large (and thus more
difficult to solve), and is also easily customized, but really needs
additional isolation in cryptographic use.

Since LFSR sequences can be predicted from a small subset of their
sequence, it has been proposed
[e.g., 72, 155]
to use a
*non*-linear feedback mechanism to produce a pseudo-random
sequence. The resulting sequence may be more difficult to analyze,
but a guarantee of a long cycle length seems to be a problem.
It is not at all unusual for an arbitrary non-linear feedback
system to get caught in a short cycle, instead of the long cycles
needed for cryptography.

There has been a lot of work on non-linear SR's, including Golomb [71], Key [89], Hemmati [78], and Etzion and Lempel [54], and Beker and Piper [12] presents a cryptographic viewpoint as usual. But an interesting paper by Siegenthaler [171] may be taken to indicate that non-linearity, by itself, is insufficient to prevent cryptanalysis, and may actually aid it. In addition, the required design restrictions conspire to limit customization, and speed is certainly no better than the LFSR.

A shift-register normally "shifts" in response to a regular electronic signal (or instruction sequence) called a "clock." Between clock pulses, the shift-register is stopped and the data inside neither change nor move.

Instead of just changing the feedback network, it is also
possible to enable or disable the clock signal. In some sense
this has no effect on the generated sequence, which must continue,
step-by-step, whatever the delay between clock pulses. However,
*systems*
of multiple SR's, in which some LFSR's enable or disable
the clock to other LFSR's, clearly might produce a complex result.
The question of whether such a sequence is actually as complex as
it might seem apparently needs further research.

There has been some work in this area, including Günther [74], and there is a great review in Gollmann [70].

One of the problems with an LFSR is speed; although each "step" may take just a few instructions, the result is but a single bit. A significant insight, however, allows better efficiency:

The logical concept of a SR does not require data to actually
*move*
within storage; it is sufficient to read "shifted" or "delayed"
data at offsets from the "current" position within a circular queue,
and then place new data at a new "current" position. This implies
that it is possible to build a sort of "vertical" LFSR in which
multiple computer storage "words" of delayed output are combined
to produce the new output. Such a system consists of several
one-bit-wide SR's in parallel; each "column" of bits is a separate
and independent LFSR arranged "vertically." Since these systems can
use word-wide computer instructions to process multiple SR's at once,
they can produce much more pseudo-random data in a little more time.
In the GFSR historical main line, this innovation is ascribed to
Lewis and Payne
[91: 30; 106].

Using the Tausworthe [184] notation, the GFSR can be described as a very similar "linear recursion relation":

a[k] = c[1]*a[k-1] + c[2]*a[k-2] + ... + c[n]*a[k-n] (mod 2)where a[k] is the latest

The resulting pseudo-random distribution has been a major GFSR
topic since the original paper: Clearly, we have multiple LFSR's
in parallel (each bit of the result value), all using the same
feedback polynomial. Clearly, each LFSR will represent a particular
delay within the one major sequence defined by a single polynomial.
Clearly each LFSR is
*absolutely* correlated to the others with
respect to its individual delay. Surely this correlation must
affect the output, so how should the GFSR be initialized for best
statistical performance?

The need for GFSR initialization constraints has also been a
topic of considerable interest since the original paper: Lewis and
Payne note that in order to generate every "p-tuple" before any
repetition, the columns must be
*linearly independent*. They also
note that this is guaranteed if each column is a delayed replica of
the initial column. They thus suggest filling the leftmost column
with 1-bits, and the rest of the generator with 0's, and running
the SR for some number of steps. This produces a complex result
in the leftmost column which can be shifted to the right by one
column, the leftmost column again filled with 1's, and the SR run
again. Eventually, all columns will have been filled with values
only distantly related to one another, but this initialization
process will take a substantial number of RNG steps.

Lewis and Payne suggest that individual columns should have a
delay no less than about 100*p* for polynomials of degree
*p*, but they also use an additional 5000*p* to allow
the first step of "all 1's" to "die out"; Bright and Enison
suggest 20,000*p*. Kirkpatrick
[90]
suggests using a linear congruential generator to initialize GFSR
state, about half of which is then zeroed to force linear
independence (a good idea, but perhaps cryptographically unwise).
Fushimi and Tezuka
[58]
actually illustrate a short linearly-related GFSR, and suggest a
complex initialization; Collings
[36]
suggests initializing with a corresponding LFSR. Fushimi
[60]
gives another substantial construction, and also
[61]
shows an additional requirement in order to ensure
"*k*-distributivity."
All this work on initialization is inherently involved with the
statistics of the results. For other theoretical work on GFSR
statistics, see Tezuka
[185, 186,
187],
and Niederreiter
[129];
Koopman
[94]
provides an empirical analysis of GFSR
*subsequences*. The major
result of all this is that it is not easy to initialize a GFSR
correctly.

Like the LFSR, the GFSR is normally operated "Class B," and thus requires additional isolation in cryptographic use. The software execution time of a GFSR is independent of the degree of the feedback polynomial, being instead nearly proportional to the number of terms in that polynomial. Consequently it is flexible, easily customized, may be made as long as desired, and even as wide as desired (using multiple operations).

(Also see the GFSR experimental results in Section 7.)

Prominent within Knuth
[91: 26-31 §3.2.2]
is a description of the (unpublished) Mitchell and Moore
*Additive*
generator (Marsaglia calls this a lagged-Fibonacci generator).
While not deeply treated in Knuth, the Additive RNG is important
because it seems to be a generalization of the LFSR and an
improvement over the GFSR, both of which are currently better
understood. Marsaglia
[113]
is a major empirical reference, and Marsaglia and Tsay
[114]
develops the sequence length using matrix algebra techniques.

The Additive generator uses the same "vertical" arrangement as
the GFSR, but uses normal arithmetic addition (with internal "carry"
operations) instead of GFSR exclusive-OR (no carry) operations.
(The Additive generator may also be seen as a vertical LFSR with
*m*-bit element values and mod 2*m* arithmetic.) This
guarantees a longer sequence than the GFSR, and a sequence which
may also be more secure
[160].
Although an LFSR generates a permutation of the possible values
(except zero), the Additive generator does not seem to be so
constrained.

Using the Tausworthe [184] notation, the Additive generator can be described by a similar "linear recursion relation":

a[k] = c[1]*a[k-1] + c[2]*a[k-2] + ... + c[n]*a[k-n] (mod 2m)where a[k] is the latest

Marsaglia proves period ((2^r) - 1)*(2^(n-1)) for degree
*r*
and width *n* and
*every* initial vector of integers (at least
one odd). Consequently, the initialization anxiety which so
pervades the GFSR papers seems completely unnecessary in the
additive generator. It might be possible to achieve an even longer
sequence, approaching (2^rn)-1, using arithmetic modulo a prime
modulus
[100].
However, with a suitably-large polynomial (degree 1279 or larger),
the Marsaglia sequence length is "long enough," and a requirement
for explicit modular arithmetic would be a significant execution
overhead.

Like the LFSR and GFSR, Additive generators are usually operated
"Class B," and thus require additional isolation in cryptographic
use. (It is not presently known what information is actually
required for a complete external analysis.) The software execution
time of an Additive RNG is virtually length-independent, but nearly
proportional to the number of feedback taps, the same as the GFSR.
It is interesting that this "mod 2^*m* arithmetic" system may be
customized by selecting feedback delays corresponding to primitive
mod 2 polynomials.

(Also see the Additive RNG experimental results in Section 7.)

Most RNG designs may be penetrated if a cryptanalyst comes up with enough of their output sequences. Naturally, the designer will try to arrange the system so the cryptanalyst never has any confusion sequence with which to work. However, in case these precautions fail, most RNG's need additional protection for their sequences. This protection can occur in the form of added randomizer and isolator mechanisms.

The basic idea behind the multiple mechanism approach has a long and prestigious history. The classic paper by Shannon [169: 711-713] touches on this in the context of "mixing transformations," now more often described as product ciphers [45]. In a product cipher, the ciphertext result of one cipher is enciphered again by another cipher, and so on. Clearly, if a particular cipher were "completely secure," there would be no reason for other encipherings; the additional encipherings act to obscure the weaknesses of the preceding ciphers. (Also see the related work in Wagner, Putter and Cain [196].)

Rather than deal with multiple complete ciphers as independent entities, it seems reasonable to apply multiple transformations to a single data stream. This is the conceptual basis for substitution-permutation (S-P) ciphers, such as DES. Multiple transformations can often be applied equally well either to streams of message data or confusion data, although the purposes of this paper are obviously oriented toward the generation and isolation of confusion streams.

One-way functions are easy to compute but hard to invert
[e.g., 49; 45: 161-164;
4];
that is, they make it difficult to find the generating value
*even* when given *both*
the result and the function which produced it.
Examples of one-way functions include "the exponential in some
finite field: y = a^x in GF(q), or the power function in the ring
of integers modulo a composite number *n*, the factorization
of which is kept secret: y = x^a mod n"
[133: 140].
In a sense, every strong cryptographic system is a one-way
function
[124: 351].

One-way functions are an integral part of the new theoretical work in cryptography, including Shamir [167], Winternitz [205], and Levin [103]; (there is also a significant paper by Yao [208], which I have not seen). One-way functions are closely related to "unpredictable" RNG's, as developed in Blum, Blum and Shub [21], Blum and Micali [24], Vazirani and Vazirani [192] and Goldreich, Krawczyk and Luby [67], among others.

It might seem that even a simple counting sequence into a one-way function must produce a sequence of pseudo-random values, and so be yet another way to construct an RNG. Unfortunately, Shamir [167] shows that while a one-way function may be difficult to invert for individual values, the same does not necessarily apply to sequences (his example is the RSA encryption function [154], and he does give a different construction for a good RNG using RSA). A similar proposal is sometimes mentioned with respect to DES [e.g., 124: 315-316], as is an iterative RNG technique [124: 316-317]. But it seems unlikely that we will ever be able to provide a theoretical guarantee of the minimum cycle length produced by such a complex mechanism.

A one-way function clearly requires some sort of driving
sequence. But if the next driving value is taken from the preceding
result, we have yet another iterative mechanism which needs a theory
of operation with respect to short cycles. If the next driving
value comes from a table, we would have to generate a huge ciphering
table for the longest possible message, a table which must be
transported and held in secrecy for deciphering. And if the next
driving value is generated in real-time, there must be some sort of
driving value generator; that generator cannot be trivial, for we
assume that the generator structure, the one-way function itself,
and a long sequence of results, are all known to a cryptanalyst.
A counting sequence of driving values is unlikely to resist
cryptanalysis for long, unless it comes from an extremely large
counter (at least 64 bits wide) *and* all the counter bits are
used by the one-way function. Note that an exhaustive search for the
start of a counter-generated driving sequence would seem to be the
*ideal* application for a system with massive parallel search
hardware; such a system might speed up a software search by a factor
of a million or more. A reasonable alternative to a counter would be
a large LFSR with a customized primitive polynomial.

There is at least one more possibility for driving a one-way
function, specifically, to use ciphertext (combined plaintext and
one-way function output), or some function partially including
ciphertext. This is the basis for an autokey cipher
[88, 45],
which will be discussed again later with respect to PKZIP. In an
*autokey* cipher, the cryptanalyst necessarily has direct access
to the sequence which is generating the keying sequence, since this is
(or is some function of) the ciphertext. This is worrisome, since
the one-way function in an autokey cipher thus carries virtually the
entire burden of cryptographic strength.

A one-way function would seem to be the ideal randomizer and isolator to protect another RNG, but the one-way functions in the literature tend to be slow. Of course, this problem may be more related to the use of functions based on arithmetic (where centuries of work have built a substantial basis for development), than the lack of existence of other types of one-way functions.

Some functions are designed to produce a short result value from a large amount of data or a message; these are known as "checksum" or "fingerprint" algorithms. Such schemes are clearly impossible to invert simply because there is not enough information in the result to do so. On the other hand, it may be possible to find a different message which has the same fingerprint.

Common "checksum" algorithms, such as CRC, are good for detecting data errors, but not so good for authentication; it may be possible to deliberately generate a message with a particular CRC value. In contrast, Message Authentication Codes (MAC's) [e.g., 176] and Message Detection Codes (MDC's) [e.g., 86] are intended to make it difficult to generate a message with a particular fingerprint; MAC's generally use a secret key, while MDC's are completely public. For example, one MAC uses DES in cipher block chaining mode [176]. An interesting table technique is proposed in Pearson [135].

A Cyclic Redundancy Check (CRC)
[e.g., 143]
is a shift-register mechanism closely related to the LFSR except
that external data are fed into the mechanism. A CRC implements
a mod 2 polynomial division
[111: 210]
or
*modulo* operation, producing only the remainder as a result.
Normally, CRC's are used for error-detection, since they can
generate a small value which is a function of a large amount of
data (such as an entire file, or perhaps a disk or data
communications block). The resulting CRC value is stored or sent
with the original data; another CRC is computed when the data are
recovered or received, and if the CRC's match the data are assumed
correct. If the CRC's do not match, the equipment can arrange to
re-read or re-send the original data. The same idea can be used
to check computer files for unauthorized modification, such as
might occur from a virus program.

A CRC can also be used to process a user's key phrase into a particular arbitrary value. Multiple different polynomials can be employed to generate different CRC results, and the entire set of such results might be used to initialize a large RNG. CRC mechanisms can apparently also be used as randomizers.

Presumably, the intent of a randomizer mechanism would be to convert a known or related sequence into a more complex or less related sequence, thus improving its "randomness." Obviously, such a scheme might well provide a substantial amount of isolation as well.

Originally, randomizers were proposed to improve the statistical distribution of simple LCG RNG's; these schemes generally used a table which collected random values and released those values after some delay. MacLaren and Marsaglia [91: 31-32 §3.2.2; 109] used one sequence to fill the table and another to select the output values. Bays and Durham [91: 32-33 §3.2.2; 11] used a value from a single sequence to both select the output value and replace the selected value. The MacLaren and Marsaglia scheme is especially interesting since it has actually been used in a cryptographic design, a design which was completely penetrated by Retter [149, 150].

An alternate technique, an extension of the work by Chaitin [30], would be to use one or more data-compression techniques to "compress" a pseudo-random sequence. Since the resulting data would not later be un-compressed, there need be no indication in the data of the compression technique used, and certainly no expansion table need be sent with the data. Presumably the resulting output would be more complex, and thus, even more random, than the original.

An interesting paper by Santha and Vazirani [165] deals with increasing the randomness of sequences; the paper directly addresses the topic of physical semi-random sources (e.g., zener diodes, geiger counters). In general, sequences are combined with the parity function (exclusive-OR), and the result is shown to be less predictable than any of the sequences considered independently. The result certainly seems reasonable and is extended by Chor and Goldreich [33].

However, as David Lewis at the University of Toronto described in an article on Usenet, if the semi-random sources are statistically unbalanced, exclusive-ORing them will not produce a balanced result. Consider two sources, with a "1's" probability of 0.3 and 0.4 respectively: We get a '1' when both sources are '1' (0.3 * 0.4 = 0.12), or both '0' (0.7 * 0.6 = 0.42), for a resulting "1's" probability of 0.54. Much better, of course, than 0.3 or 0.4, but still not exactly 0.50. Can we ever be sure that a physical semi-random source will produce balanced results? Lewis also pointed out that exclusive-ORing is inefficient in its use of randomness.

An earlier paper by Blum [23] extends an idea by von Neumann [195] to a more general mechanism. von Neumann was interested in getting an unbiased coin flip from a biased coin; his trick was to toss the coin twice until either heads-then-tails or tails-then-heads was finally obtained. Arbitrarily, one of these combinations is called "heads" and the other "tails." Because an occurrence of each of the two possible elemental actions is required to produce a final result, the effect of unbalanced probabilities is seemingly negated. Blum generalizes the idea to multi-state mechanisms, showing that the obvious extension does not work, although he provides another form which does. Such a mechanism might provide a strong amount of randomization and isolation (but see Rudich [159]), although it does require some computation. In addition, the von Neumann trick depends upon the independence of the individual trials; if they are in some way "correlated," the trick is probably invalid. Some amount of correlation seems likely in an RNG.

Randomizers are currently in use in computer ciphers for
converting ciphertext into a pseudo-random sequence, as in PKZIP
[138].
PKZIP is a file compression and archiving program which includes an
encryption option. In PKZIP encryption (attributed to Roger
Schlafly), the ciphertext data are randomized by three successive
mechanisms to produce the pseudo-random confusion sequence which is
used in a Vernam combiner; it is thus a form of
*autokey* cipher
[e.g., 88, 45].
These randomizers seem to depend upon outputting only a portion of
their state, an amount equal to their unknown input data. Even if
the information in the output was properly interpreted, the input
data would seem to increase the internal information by an amount
equal to the best possible analysis.

Two of the three PKZIP randomizers are based on the well-known CRC-32 algorithm [e.g., 182, 143], in which an 8-bit data value is combined into a 32-bit LFSR. In one mechanism, only the least-significant 8 bits are used as output; in the other, the most-significant 8 bits are used. Since each input value is randomized by the CRC operation, and since only a part of the CRC value is output, an analysis of any particular complete CRC state (on the way to finding the input value) would seem difficult. Despite the fact that this is a linear system, if the values which complicate the system on each step are unknown, the system would apparently be hard to penetrate.

The other PKZIP randomizer seems based on a simple LCG, and consists of multiplication by a large value (which will truncate mod 2^32) plus an addition; only the least-significant 8-bits are used as output. Again, since it receives as much information as it produces, this system may be difficult to analyze, despite having only a small amount of internal state. It is tempting to consider the general idea that any form of RNG could be converted to a randomizer by using external data to additionally transform the internal RNG state after each RNG step.

Since the very worth of a randomizer depends upon making a given sequence more difficult to analyze, such mechanisms really need substantial mathematical analysis. I am not aware of any work on the PKZIP-type mechanisms; are they "one-way" functions?

A mechanism used mainly to complicate an external analysis of an
RNG may be called an
*isolator*. In contrast to a randomizer, an
isolator need not deal with the concept of randomness; its purpose
is to hide information or confuse a sequence in order to complicate
any attempt at external analysis. This limited role would seem to
be amenable to an eventual theoretical analysis. Some approaches
include:

**Use a subset of RNG bits**[e.g., 192, but see 75]. In particular, an Additive RNG includes a substantial amount of carry information (the carry into higher bits of the result), and any particular bit of the result can be wildly affected by lower bits. If the lower bits are not available for analysis, the system should be more difficult to solve. In fact, hidden bits would seem to make the RNG exponentially (2^*n*times, for*n*hidden bit-columns) more complex. The unused data need not increase execution time by much if the extra bits are gained by widening a "vertical" system.**Use a pseudo-random delete filter or**. (An oscilloscope display which is only partially synchronized is said to*jitterizer*to create a discontinuous sequence*jitter*[e.g., 84: 357].) Such a mechanism might occasionally delete values from the pseudo-random stream, thus allowing an analyst to see only aperiodic batches of the sequence. The number of values skipped and the number allowed before the next skip could be dynamic and pseudo-random; this should complicate a simultaneous-equation attack.**Use deleted values**(see 2, above)**to provide an additive offset for jitterizer output values**. Not only would such a sequence be discontiguous, each contiguous segment would have a different value offset. This should not change the value distribution and would also be fast.**Use polyalphabetic substitution to hide the RNG sequence**. The idea would be to use a few output bits to select an alphabet, and then translate the rest of the output bits through that alphabet. Although simple substitution is generally thought to be weak, that is in the context of messages which normally have an uneven and predictable symbol distribution. In contrast, an RNG should have a good pseudo-random symbol distribution, which should make even simple substitution tough to crack. The substitution system could be fairly quick.**Use a randomizer**. If a randomizer further randomizes an already random sequence, it should also hide the original sequence and protect it from analysis.**Use "polyalphabetic" randomizers**. In the same way that polyalphabetic substitution selects between multiple substitution maps, the RNG could select between multiple randomizer mechanisms. This would be almost as quick as a single randomizer, but should be much more difficult to penetrate.**Use different polynomials to develop the feedback and output values**. Simultaneous equations would seem to require knowledge of the internal states in order to solve the output equation, or vise versa; multiple polynomials may prevent such attacks. The output polynomial could even be non-linear [72, 174; but see 172]. The use of dual polynomial evaluations for each step would seem to at least double the computational effort.**Split the RNG values into two parts and combine the parts with a cryptographic combiner**. If a combiner can be considered a good way to hide plaintext, it should be far stronger when hiding pseudo-random data. This should be quick, but would require a pseudo-random value of typically twice the required output width.

No doubt there are many possible isolation mechanisms, some of which may provide only the illusion of protection. It is difficult not to see a message in the apparently effective technique described by Geffe [64], and its eventual analysis by Siegenthaler [171]. (Also see other "correlation attack" papers by Mund, Gollmann and Beth [126], and Meier and Staffelbach [121].) A significant theoretical analysis of various isolation mechanisms is sorely needed.

In addition to the RNG's of the previous section, various related techniques can be useful in cryptography. For example, "really random" numbers are useful as message keys. Short cycle detection can prevent repetition when a design cannot preclude short cycles. Issues of polynomial degree, number of terms, and primitive polynomials become important for mod 2 shift register systems. The output from any two RNG's can be combined into a more complex result, and a pseudo-random sequence can be used to create random permutations.

In the design of cryptographic systems, it is often useful to have a "really random" value, one not produced by a possibly-weak pseudo-random mechanism. A really random value is easily protected by encryption, and can be safely transported even with a weak cipher. The result is a secure arbitrary value, which can be quite large, and which can be used to initialize an RNG; this is a form of a message key [e.g., 12].

Special hardware (such as multiple asynchronous oscillators [e.g., 101], oscillators in chaos [e.g., 183, 5], or integrated circuit capacitor "dark current" comparisons [1]) can be developed to produce "true random" values. Alternately, "semi-random" physical events (such as geiger-counter pulses, or zener diode noise) can be made "more random" [e.g., 165, 33]. (As noted earlier, even quantum events -- such as radioactive decay -- may actually represent a complex internal logic, and so may not be "essentially" random [53].) Another possibility is to use randomized precision timing measurements of human physical actions [e.g., 42: 148].

Since the repeated use of a short RNG sequence is a serious concern, it may be reasonable to try to detect such a cycle. For tiny RNG's it is possible to keep a list of each encountered state (we may have started on an arc and only later join a cycle) and check for re-use on each step, but real RNG's are much too large for this. Of course it is easy to detect a degenerate cycle, since it is only necessary to save the one immediately-previous state and ensure that each step differs from the last, but it is usually difficult to guarantee that degenerate cycles are the only problem.

Another possibility is an idea attributed to Floyd [91: 7 §3.1.6(b); 40]: Two identical RNG's are used, set to the same initial state, and one is stepped twice for each step of the other, which produces the cryptographic sequence. The two RNG's should again have the same state only when the faster RNG has stepped through a cycle and has caught up with the first RNG. By comparing the RNG states after each value is produced, it should be possible to detect a repetition without a huge amount of storage.

Naturally, performing
*three* RNG steps for each random value just
to detect an impending short cycle is a serious additional cost.
Moreover, even the comparison operation between the complete states
of two large RNG's may be expensive.

Then, supposing the system does detect an impending cycle, what is to be done? Presumably such a cryptosystem design would include a family of initializations, of which only the first is normally used, but with others which could be used to restart the RNG's in the event of a repetition.

Because of the particular form of shift register used in the GFSR and Additive RNG designs, the exact same mechanism and storage can accommodate a wide range of polynomial lengths. Since sequence length is a function of the polynomial degree, in general we want as large a polynomial as possible. In practice, computer memory will rarely limit the desired degree of the RNG, so the degree will typically be limited by the availability of a primitive polynomial.

Checking whether large-degree polynomials are primitive can involve a large amount of computation. Nevertheless, some degree 1279 primitive is almost certain to be found over a continuous 64-hour weekend using an old 8088 system, and a degree 4253 primitive should be well within the range of a modern 80386. If the polynomials do not need to be user-customized, even degree 11213 may be practical, so there could easily be 11,213 * 32 = 358,816 bits involved in RNG operations. This amount of state is quite a contrast to the common 32-bit LCG, or even a 400 decimal digit x^2 mod N generator (which would have a total internal state of about 1400 bits). To the extent that cryptanalysis is complicated by the amount of internal state, this is a substantial difference.

A degree 1279 primitive can produce an incredibly long sequence. How long? Well, suppose our design becomes popular, and by the end of the century it occupies 1 billion (10^9 = 2^29.9) channels, each madly sending out 100 million (10^8 = 2^26.6) bytes per second. Assuming a "vertical" design, using a single step per enciphered byte, a century (3.2 x 10^9 = 10^9.5 = 2^31.5 seconds) of such use will cover about 10^26.5 = 2^88 elements, out of the total of 2^1279-1. Due to the "birthday paradox" some repetition may occur, but such overlaps will be very rare and plenty hard to find. Thus, a degree 1279 RNG produces a "long enough" sequence (although a long sequence by itself certainly does not eliminate all avenues of attack).

Naturally, the state of the RNG must be initialized prior to the production of random numbers, and the more state there is, the more time this will take. However, the same state which must be initialized is also that which must be recovered through cryptanalysis in order to fully penetrate the RNG, so the more state there is, the better the secrecy should be. RNG's with large amounts of internal state also support large keys; 256 bits (32 bytes) may be a reasonable minimum for keys in serious new systems [77].

Any linear shift register RNG can easily be customized simply by selecting any one of the many possible primitive polynomials as a feedback system. Primitive trinomials (3-term polynomials) are popular in the literature [e.g., 26, 211, 212]. Of course, if RNG customization is to be used as a key, it is necessary that there be a large number of customizing polynomials, or the customization has not helped much.

For example, at degree 1279 there are only 1278 possible
trinomials which
*might* be primitive, and probably just two will be.
If a system requires a trinomial of some particular degree, a
cryptanalyst could just pre-verify the relatively few possibilities,
then simply try each one. In contrast, there are about 10^18 "odd"
9-nomials of degree 1279, and so about 10^15 primitives (a 51-bit
value), which should at least complicate a brute force attack on the
polynomial. (There are about 10^22 "odd" 9-nomials of degree 4253,
and so about 10^18 primitives, a 62-bit value.) In a real sense,
the polynomial will be a sort of main key, required, along with
initialization, to generate a particular sequence.

A 9-nomial will also imply that each pseudo-random value will be the combination of 8 unknown elements, which should further complicate an external analysis [160]. And there is some reason to believe that the resulting sequence would be more random than one generated by a trinomial [38: 419, 421].

In order to support user customization of the various
maximal-length RNG's, it is necessary to find primitive mod 2
polynomials. Most methods start out by finding an
*irreducible* mod 2
polynomial. Normally, only
*some* irreducibles are primitive, but for
polynomials of a degree which is a Mersenne prime,
*all* irreducibles
are primitive. Therefore, we choose a degree which is a Mersenne
prime, and end up with a primitive.

Finding an irreducible mod 2 polynomial is closely related to the factorization of polynomials over finite fields, as discussed in Berlekamp [17] and Knuth [91]. Almost any such technique will suffice for tiny polynomials (at least through degree 31). For example, a polynomial form of the ever-popular "Sieve of Eratosthenes" [e.g., 91: 394 §4.5.4.8] can reach degree 31 by using a table of irreducibles through degree 16 (also produced by the sieve); while slow, this can provide a simple validation of other techniques.

Of course, large polynomials do require efficient processing. Most of the efficient primitive-finding techniques are generally based on the evaluation of (x^2)^n mod p. In some cases, part of the evaluation is traded for other computation, and some other details may be necessary depending on the specific technique and application. A brief history of primitive-finding algorithms includes Swift [181], Watson [197], Stahnke [178], Rabin [142], Calmet and Loos [28], Knuth [91: 438 §4.6.2.16], Ben-Or [16], and Herlestam [79]. The approach described by Watson is reasonable and still competitive, although the technique described by Ben-Or may be somewhat better for high-level implementations. Thus we have Ben-Or's "Algorithm A" [16], here cast into a sort of math/computer pseudo-code:

Algorithm A 1. Generate a monic random polynomial gx of degree n over GF(q); 2. ux := x; 3. for k := 1 to (n DIV 2) do 4. ux := ux^q mod gx; 5. if GCD(gx, ux-x) <> 1 then go to 1 fi; 6. od

The result of the algorithm (completing all steps) is a certified
irreducible polynomial (as opposed to the "probably prime" result
from probabilistic prime-finding algorithms). GF(q) represents the
Galois Field to the prime base *q*; for mod 2 polynomials,
*q* is 2. These computations require mod 2 polynomial arithmetic
operations for polynomials of large degree; "*ux^q*" is a
polynomial squared, and "*mod gx*" is a polynomial division.
A monic polynomial has a leading coefficient of 1; this is a natural
consequence of mod 2 polynomials of any degree. The first step
assigns the polynomial "x" to the variable *ux*; the polynomial
"x" is x^1, otherwise known as "10".

The squaring and reduction of step 4 represent fairly complex mod 2 polynomial operations (instead of conventional computer language features which operate on tiny integer values). But the real expense is the greatest-common-divisor (GCD) operation of step 5, since this implies repeated polynomial division by large-degree polynomial divisors. (For discussions on polynomial arithmetic, see, for example, Knuth [91: 399-416 §4.6], Arazi [8], Blahut [19], Swift [181], MacWilliams and Sloane [111], and Berlekamp [17].)

Note that the time-to-success for algorithm A is random, in the
sense that an arbitrary polynomial is formed and then checked; the
first value may succeed, or the process may
*never* succeed. But over a
*large* number of trials, about two primitives should be obtained
for each "*n*" random "odd" polynomials examined (it makes
sense to check only the "odds"); thus, if 12,800 random polynomials
of degree 1279 are examined, about 20 primitives should be found.
In practice, the time to find a single primitive ranges from (rarely)
amazingly fast through (often) diabolically slow.

It is certainly *not* necessary to use just a single RNG alone;
the outputs from multiple RNG's may be
*combined* to produce a more-complex
sequence. Examples include MacLaren and Marsaglia
[109],
Westlake
[200],
Groth
[72],
Wichmann and Hill
[202],
Sloane
[177: 91-93],
Wichmann and Hill again
[203],
Rueppel and Staffelbach
[162],
andrGunie
[73],
and Wikramaratna
[204].
Of course, RNG sequences can be combined in a complex cryptographic
combiner, but, normally, combination RNG designs use a simple additive
combiner like exclusive-OR. Experiments by Marsaglia
[113]
indicate that combinations of two RNG's of different types seem to
perform statistically better than either of the RNG's alone. Both
Collings
[37]
and Guinier
[73]
report success with multiple instances of similar types of generator.
But Zeisel
[210]
shows that the three additively-combined LCG's of Wichmann and Hill
[202]
is effectively the same as one huge LCG.

For a combination of RNG's to make sense cryptographically, it is
*absolutely vital*
that the cryptanalyst not be able to be work on the
various generators independently, and this can be a great deal
trickier than one might expect. (Again, see Geffe's influential
early technique for combining RNG's
[64],
which seems quite strong, then see the way it was broken
[171];
also note the disquieting parallels to Günther
[74].)
Commonly used combiner mechanisms include exclusive-OR and integer
addition
[160].
(Alternately, see
[170, 173,
152, 153].)

Some cryptographic systems make use of the ability to create a
random permutation of values. (Some applications of a permutation
sequence are given in Mellen
[122],
Levine and Brawley
[104],
and Levine and Chandler
[105].)
A special LCG can be designed to generate a perfect permutation,
and a different LCG or any LFSR can generate an *almost* perfect
permutation of the (2^n)-1 values 1..2^n, missing only zero, and
the missing zero could be inserted at random.

More generally, a "random" permutation can be created with a pseudo-random sequence which operates on some original state. The common method is the "shuffle" algorithm [50; 91: 139 §3.4.2.P]: For each element in the set, pick one, select some element "at random" (from those elements not yet picked) and exchange the contents of those two elements. Surprisingly, Robbins and Bolker [156] indicates that seemingly-similar algorithms ("students'" versions) which continue to select from all possible elements are somewhat "biased"; it is not clear how this would affect a cryptographic system. See Sloane [177] for an excellent overview of random permutations, and also Diaconis and Shahshahani [48].

Discussion of the creation and randomness-measurement of permutations seems surprisingly muted in Knuth [91], and an explicit proof of the effectiveness of the shuffle algorithm seems hard to find. Durstenfeld [50], apparently the original source for shuffle, gives just an algorithm, without proof or references. Page [131] seemingly gives the same algorithm, also without proof, but does suggest the alternative of associating an original order with random values, then sorting the random values.

Sandelius [164] gives a different "multistage randomization procedure (MRP)," with proofs, in which he references Rao [144]. MRP appears to be a distributed form of the sorting technique: One random bit per element sorts a set into two subsets, one "before" the other; the resulting subsets can then be sorted recursively until all elements are ordered. Descriptions and comparisons of MRP and other randomization methods (but not shuffle) are available in Plackett [139]. Diaconis and Graham [47] provides a welcome discussion of the measurement of the "disarray" of permutations. Knuth [91: 64 §3.3.2.P] provides an algorithm to convert a permutation to a unique value, so that distribution statistics can be applied to a set of permutations.

I conducted exhaustive state
*experiments* on a variety of sizes
of four candidate cryptographic RNG's: Cellular Automata, x^2 mod N,
GFSR, and Additive. The analysis was directed at finding the length
and quantity of the state-sequence cycles which are inevitable in a
finite-state RNG. In each case, *every possible* RNG state was
investigated and classified as part of a cycle or an arc; the number
of cycle-joins and degenerate (single-state) cycles were also counted.

Any computer RNG will be a
*finite state machine* with a limited
number of distinct states; the different states include every
possible initialization and every possible
*state-transition* or step.
In order to gain some insight on the way each RNG technique uses its
allotted states,
*every possible state* can be examined (in
tractable-size implementations), and statistics collected. Obviously,
the examined RNG's will have to be very small to support such an
analysis, but it is reasonable to expect that the various
possibilities found in small RNG's might also be found in large
RNG's, which can never be completely examined. Thus, the technique
provides insight into the design.

Exhaustive state analysis is fairly simple: The RNG is initialized in some state, and then stepped to its next state; a record is kept of all encountered states. This continues until every possible state has been examined.

It is convenient to define every state to be either part of a cycle, or part of an arc leading into a cycle. Exhaustive state analysis can detect cycles (because they re-use states within a single path) and thus identify cycle-states. Statistics can be collected about the number of states in cycles, and thus, the average cycle length, etc. The total number of possible states is known, and after the cycle-states have been identified, the remaining states must be arc-states. The state where an arc joins a cycle can also be identified, and so a primitive sort of average arc states per join measure can be developed. (In practice, arcs often occur in branch structures, where arcs join other arcs in a common trunk; thus the average arc "length" -- the distance from its terminal cycle -- may be far below the average arc states per join value. However, since cycle length, rather than arc length, is generally the weak point of a design, this imprecision may not matter.)

Exhaustive state analysis can yield insights into the functioning of an RNG, especially for those designs which do not have a formal theory of operation. Moreover, since RNG output values may be an arbitrary function of the RNG state, the description of RNG state trajectories seems to be more fundamental than an analysis of output values. Exhaustive state analysis is applicable to any discrete RNG, which is to say any computer RNG, including floating-point based designs (although a special tractable-size floating-point may need to be implemented for such tests).

Some results from Cellular Automata experiments are tabulated in Figure 1. Here there are two design variables: length (the number of elements), and width (the number of bits in each element). Note the wide variation in average cycle length, with no clear correlation to the design variables.

Figure 1. Exhaustive State Experiments: Cellular Automata Total Cycle Pct Degen Min Avg Avg Len Wid States States Cycles Cycles Cycle Cycle Arc 4 1 16 11 68.8% 3 8 2.75 1.00 4 2 256 121 47.3% 9 8 5.26 1.00 4 3 4096 1331 32.5% 27 8 7.01 1.00 4 4 65536 14641 22.3% 81 8 7.70 1.00 5 2 1024 36 3.5% 1 5 4.50 9.15 5 3 32768 216 0.7% 1 5 4.91 21.5 6 2 4096 9 0.2% 9 - 1.00 583.9 7 2 16384 8464 51.7% 1 4 29.2 1.75 8 2 65536 2601 4.0% 9 8 30.6 24.4

The configuration with
length 6 and width 2 presents an interesting case where virtually
the entire state-space is located on arcs; the problem with this is
that, within a finite state-space, any arc must eventually lead to
a cycle. In this particular case, all the cycles are degenerate,
and an arbitrary initialization may start out arbitrarily close to
such a cycle. The
*minimum* cycle length is our normal concern, for
if an RNG is initialized arbitrarily, it may come up in a state
within a minimum-length cycle, or anywhere on an arc leading to
such a cycle. The minimum cycle length of CA RNG's seems rather
short.

Some results of the
x^2 mod N
experiments are tabulated in Figures
2 and 3. The value of N is the only design variable. N is supposed
to be the product of two large primes (*P* and *Q*); tiny
primes were used to make exhaustive analysis practical. These
systems are not permutation generators. The proportion of states
in cycles seems fairly consistent: About 3 out of 4 of the total
states are arc states, and each of these joins a cycle in just a
single step. There are always 4 degenerate cycles. Because
the x^2 mod N design might be configured for a particular cycle,
maximum cycle length is also tabulated (instead of cycle percentage).

Figure 2. Exhaustive State Experiments: Improperly Designed X^2 mod N Total Cycle Degen Min Avg Max Avg P Q States States Cycles Cycle Cycle Cycle Arc 107 163 17441 4428 4 2 201.3 1404 1.00 107 211 22577 5724 4 2 73.4 156 1.00 127 131 16637 4224 4 2 11.4 12 1.00 127 139 17653 4480 4 2 35.0 66 1.00 139 167 23213 5880 4 2 245.0 902 1.00 139 211 29329 7420 4 2 50.1 132 1.00 151 199 30049 7600 4 2 30.4 60 1.00 151 211 31861 8056 4 2 24.0 60 1.00 163 191 31133 7872 4 2 49.2 108 1.00

For the
*improper* x^2 mod N designs which are covered in Figure 2,
*P* and *Q* are "Blum integers"
[4; 96: 8],
that is, they are primes congruent to 3 mod 4, but at most one is
*special* as defined in
Blum, Blum and Shub
[21: 378].
Note the case of *P* = 127, *Q* = 131, which generates
a sizable system with maximum cycle length of 12, and so is
extraordinarily weak. In an improper design, a small increase in
the value of one of the primes can result in a drastic
*decrease* in strength.

Figure 3. Exhaustive State Experiments: Properly Designed X^2 mod N Total Cycle Degen Min Avg Max Avg P Q States States Cycles Cycle Cycle Cycle Arc 23 47 1081 288 4 10 24.0 110 1.00 23 167 3841 1008 4 10 100.8 410 1.00 23 359 8257 2160 4 10 216.0 890 1.00 23 719 16537 4320 4 10 360.0 1790 1.00 23 1439 33097 8640 4 10 720.0 3590 1.00 47 167 7849 2016 4 11 168.0 902 1.00 47 359 16873 4320 4 11 360.0 1958 1.00 47 719 33793 8640 4 11 540.0 1969 1.00 167 359 59953 15120 4 82 1512.0 7298 1.00

For the
*proper* x^2 mod N designs covered in Figure 3, *P* and
*Q* are "Blum integers" but they are also both *special*
and developed as described in Blum, Blum and Shub. For a given
system size they have longer minimum, maximum, and average cycle
lengths than the improper designs of Figure 2. The minimum cycle
length still seems rather short, but if we assume that the operational
cycle is a configuration selection (instead of a key-related arbitrary
setup), this may not be a problem. Alternately, there appears to be a
formula for the period of the cycle including state 2, so if we use
that particular cycle, it may be possible to increase the size of the
system until the period is "long enough." The case of P = 47, Q = 719
is specifically prohibited in Blum, Blum and Shub
[21: 378],
yet gives no experimental indication of being "bad"; perhaps some
other experiment would reveal a problem in this design.

Some results from the
GFSR
experiments are tabulated in Figure 4.
Here there is an additional design variable, the selection of a
primitive polynomial, although we are now constrained to use degrees
which are Mersenne primes. Each experiment was performed using
*every* primitive polynomial of the given degree, and the same
results were obtained in each case.

Figure 4. Exhaustive State Experiments: General Feedback Shift Register Polys Pct Degen Min Avg Avg Deg Tested Wid States Cycles Cycles Cycle Cycle Arc 5 6 1 32 100.0% 1 31 16.0 0.00 5 6 2 1024 100.0% 1 31 30.1 0.00 5 6 3 32768 100.0% 1 31 30.97 0.00 7 18 1 128 100.0% 1 127 64.0 0.00 7 18 2 16384 100.0% 1 127 126.0 0.00

The degenerate cycle is the all-zeros
case, which is prohibited; the rest of the states are part of a
single cycle, and there are no arcs. Of course, each independent
column
*should* have at least one 1-bit, but cycle length is determined
by any
*one* non-zero column. Any such initialization yields the same
cycle length, thus supporting
*almost* arbitrary initialization (with
respect to cycle length only, of course). The cycle length is set
by the polynomial degree, and does not change as we widen the system.
Consequently, if the width were to exceed the degree, only a subset
of the possible output values could be produced. This would be an
abnormal design, but it would seem that this worrisome concept must
apply to some unknown extent in normal designs as well.

Some results from the
Additive RNG
experiments are tabulated in
Figure 5. Again, each experiment was performed using
*every* primitive
polynomial of the given degree, and the same results were obtained
in each case.

Figure 5. Exhaustive State Experiments: Additive Generator Polys Pct Degen Min Avg Avg Deg Tested Wid States Cycles Cycles Cycle Cycle Arc 5 6 1 32 96.9% 1 31 31.0 0.00 5 6 2 1024 96.9% 32 62 62.0 0.00 5 6 3 32768 96.9% 1024 124 124.0 0.00 7 18 1 128 99.2% 1 127 127.0 0.00 7 18 2 16384 99.2% 128 254 254.0 0.00

Here there is an initialization rule which eliminates degenerate cycles (a typically small part of the total). The remaining states form a number of isolated closed cycles with no arcs, again supporting almost-arbitrary initialization. The number of independent cycles varies with the width. However, since each cycle is equally long, this should be just as acceptable as a single long cycle. The cycle length also varies with the width, which is helpful.

The Cellular Automata RNG contains cycles of various lengths, so its performance will vary, depending upon its initial state. Since cryptographic RNG's should ideally be initialized arbitrarily, CA RNG's may apparently come up in a weak short cycle, or on a short arc into a short cycle. Moreover, a larger CA RNG does not necessarily produce a stronger RNG; instead, particular special values for width and length may produce the strongest RNG. This evokes the realistic nightmare of a new search for the "best" such values after every new statistical analysis.

The x^2 mod N RNG is a special case: On the one hand, most of
the comments on the CA RNG could also apply here; on the other, the
extensive theory of operation seems to avoid the weakest designs,
and should also allow the selection of a long operating cycle.
Certainly an x^2 mod N design
*must* follow the many intricate design
requirements of Blum, Blum and Shub to avoid very significant
weaknesses. Customization might consist of finding large special
primes *P* and *Q*, or just the selection of a particular
operating cycle within the context of a fixed value of *N*.
(The number of usable states, here N/4, should be far larger than
the total random numbers used by all fielded units over all
installed time.)

The x^2 mod N generator seems to inherently include both short
and degenerate cycles, so we cannot risk initializing x[0]
arbitrarily. Thus, it is normally necessary to validate any
x[0] "seed" to guarantee that it resides in a cycle which
is "long enough." Alternately, user key initialization might
select an arbitrary start state within a single
configuration-selected cycle, if this can be done in real (user)
time. Ultimately, such initialization would not be much different
than that for a normal LFSR (since an arbitrary LFSR state is just
a different start-state within the single maximal length cycle),
but it is clearly
*far* more complex than simply using arbitrary
data as a convenient initialization state.

Both the GFSR and Additive RNG's were easy to design (even with primitive mod 2 polynomial selection), and were well behaved; there was no significant variation in performance with respect to initial state. Thus, an almost-arbitrary initialization will always produce similar performance. In these designs, a longer polynomial always produced longer cycles; in the Additive RNG, a wider register also always produced longer cycles. In both designs, all of the states were in cycles, and there were no dangerous short cycles. There were also no arcs, and thus no arcs into short or degenerate cycles. Both of these designs can easily be customized through the use of a new primitive polynomial, and the customized design will carry the same performance guarantees.

Certainly, the CA and x^2 mod N designs would have to be
considered more secure
*as they are normally proposed*; both of these designs are
"Class C" RNG's in that the designer is urged to expose only a
portion of their state change on every step. But the Additive RNG
could be similarly restricted (especially since it is so easily
expanded), and both the GFSR and Additive designs are clearly usable
with any other form of isolation mechanism.

A great deal of work remains to be done to establish the cryptographic performance of the various random number generators.

Currently, the Additive RNG seems attractive since it is easily initialized from a user key, easily expanded to huge amounts of internal state, easily customized, reasonably efficient, and has a guaranteed minimum cycle length. The Additive RNG will remain attractive precisely until a much better mechanism is found or a fatal flaw discovered in this one.

The x^2 mod N generator may also be expanded and customized, but seems to require far more computational effort at every stage of the process.

Other RNG techniques could also be attractive, if a good theoretical basis for their minimum cycle lengths could be found, and the design made "long enough." Implementation difficulty and computational efficiency could then be compared to make a reasonable choice.

Because most RNG's can be cryptanalyzed, steps must usually be taken to prevent penetration, often through the use of some sort of isolation mechanism. Here again, much more theoretical work is needed on the ability of various mechanisms to protect an RNG from analysis.

First, much of the modern theoretical work seems oriented at solving "the problem of cryptography" in a single step; this work often implies systems which are slow and complex. One alternative is to design individual mechanisms or processes which solve one aspect of a cryptographic system to some known extent; then multiple such devices might be arranged to completely solve the whole problem. Such a design might be fast, and also better partitioned to support a deep understanding of the overall design. This approach should also be more amenable to deep mathematical analysis than trying to solve the whole problem at once.

Next, both mathematicians and engineers seek simple systems.
However, as we have seen, a simple
*formula* in no way implies a simple
*system*: Clearly, the complexity of the lexical mathematical
representation is not isomorphic to the complexity of the
realization. Systems based on apparently trivial equations can
place surprisingly massive requirements on an actual implementation.
Even simple integer arithmetic represents a fairly complex system
at the binary gate level
[e.g., 2: 23];
perhaps systems based on integer arithmetic are inherently complex
(even the successful period analysis of the simple Additive RNG
seems rather difficult
[114]).
As a goal, mathematicians might strive to work with lexical
representations which are more closely related to the complexity of
the resulting system. The ultimate system must be relatively simple
if we are to avoid dangerous hidden problems; consequently, even
non-mathematicians should be able to understand those systems.

Finally, almost any encryption or random number implementation
has some mathematical claim, if only a hand-waving "there are a
large number of possibilities, so this must be secure." More formal
mathematical models may indeed imply strength, but *only* if the
resulting mechanism implements the mathematical model completely
and exactly. Unfortunately, it is easy to make an implementation
mistake in a complex design: Some errors of understanding do
withstand review, some errors of design do result in "working"
systems, and even massive testing can miss various types of problems.
Both correct and incorrect implementations can look and perform
remarkably alike, differing only in small but crucial details.

It would certainly be a benefit for system builders if the mathematicians, as part of the original work, would define a set of tests which would be sufficient to completely validate the implementation of their mathematical model. Because of the deep mathematical background often assumed in the original work, it is not always possible for a non-mathematician to do this correctly.

What would the mathematicians get out of such validation? Well, the goal would be to establish a correlation between a theoretical and a real system; the real system could then be used for experiments, in ways similar to non-linear dynamics experiments. Small systems could be exhaustively tested for conformance to predicted results; results could provide direct insight into the math. Such experiments might reveal entire new classes of relationship, perhaps some that could otherwise be found only with great difficulty. There can be serious advantages to having a validated realization to play with.

1. Agnew, G. 1986. Random Sources for Cryptographic Systems.
*Advances in Cryptology: CRYPTO '85 Proceedings.* 77-81.
Springer-Verlag: Berlin / New York.

2. Aho, A., J. Hopcroft and J. Ullman. 1974. *The Design and
Analysis of Computer Algorithms.* Addison-Wesley: Reading,
Massachusetts.

3. Akl, S. and H. Meijer. 1984. A Fast Pseudo Random Permutation
Generator. *Advances in Cryptology: CRYPTO '84 Proceedings.*
269-275. Springer-Verlag: Berlin / New York.

4. Alexi, W., B. Chor, O. Goldreich, and C. Schnorr. 1984.
RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure (Extended Abstract).
*25th IEEE Symposium on the Foundations of Computer Science.*
449-457.

5. Allen, T. 1983. Controlled, but Rational, Phase-Locking
Responses of a Simple Time-Base Oscillator. *IEEE Transactions
on Circuits and Systems.* CAS-30: 627-632.

6. Allender, E. 1987. Some Consequences of the Existence of
Pseudorandom Generators. *Proceedings of the Nineteenth Annual
ACM Symposium on Theory of Computing.* 151-159.

7. Anderson, R. 1990. Solving a Class of Stream Ciphers.
*Cryptologia.* 14: 285-288.

8. Arazi, B. 1988. *A Commonsense Approach to the Theory of
Error Correcting Codes.* MIT Press: Cambridge, Mass.

9. *Artificial Life.* 1989. Editor: C. Langton.
Addison-Wesley: New York.

10. Arvillias, A. and D. Maritsas. 1978. Partitioning the Period
of a Class of *m*-Sequences and Application to Pseudorandom
Number Generation. *Journal of the Association for Computing
Machinery.* 25: 675-686.

11. Bays, C. and S. Durham. 1976. Improving a Poor Random
Number Generator. *ACM Transactions on Mathematical Software.*
2: 59-64.

12. Beker, H. and F. Piper. 1982. *Cipher Systems.* John
Wiley: New York.

13. Beker, K. and M. Dorfler. 1989. *Dynamic systems and
fractals.* Cambridge University Press, New York.

14. Bell, E. 1951. *Mathematics, Queen and Servant of
Science.* Microsoft Press: Redmond, Washington.

15. Bell, T. 1986. Better OPM/L Text Compression. *IEEE
Transactions on Communications.* COM-34: 1176-1182.

16. Ben-Or, M. 1981. Probabilistic algorithms in finite fields.
*Proceedings of the 22nd IEEE Foundations of Computer Science
Symposium.* 394-398.

17. Berlekamp, E. 1984. *Algebraic Coding Theory.* Aegean
Park Press: Laguna Hills, CA.

18. Berlinski, D. 1988. *Black Mischief: Language, Life,
Logic, Luck.* 2nd Edition. Harcourt Brace Jovanovich:
Boston / New York.

19. Blahut, R. 1983. *Theory and Practice of Error Control
Coding.* Addison-Wesley: Reading, Mass.

20. Blum, L., M. Blum and M. Shub. 1983. Comparison of Two
Pseudo-Random Number Generators. *Advances in Cryptology:
CRYPTO '82 Proceedings.* Plenum Press: New York. 61-78.

21. Blum, L., M. Blum and M. Shub. 1986. A Simple
Unpredictable Pseudo-Random Number Generator. *SIAM Journal on
Computing.* 15: 364-383.

22. Blum, M. 1982. Coin flipping by telephone. *Proceedings
of the 24th IEEE Spring COMPCON.* 133-137.

23. Blum, M. 1984. Independent unbiased coin flips from a
correlated biased source: a finite state markov chain. *25th
IEEE Symposium on the Foundations of Computer Science.* 425-433.

24. Blum, M. and S. Micali. 1984. How to Generate
Cryptographically Strong Sequences of Pseudo-Random Bits. *SIAM
Journal on Computing.* 13: 850-864.

25. Boyar, J. 1989. Inferring Sequences Produced by Pseudo-
Random Number Generators. *Journal of the ACM.* 36: 129-141.

26. Bright, H. and R. Enison. 1979. Quasi-Random Number
Sequences from a Long-Period TLP Generator with Remarks on Application
to Cryptography. *ACM Computing Surveys.* 11: 357-370.

27. Burks, A. 1970. *Essays on Cellular Automata.*
University of Illinois Press: Urbana / Chicago / London.

28. Calmet, J. and R. Loos. 1980. An Improvement of Rabin's
Probabilistic Algorithm for Generating Irreducible Polynomials over GF(p).
*Information Processing Letters.* 11: 94-95.

29. Campbell, J. 1982. *Grammatical Man: Information, Entropy,
Language and Life.* Simon and Schuster: New York.

30. Chaitin, G. 1975. Randomness and Mathematical Proof.
*Scientific American.* 232(5): 47-52.

31. Chaitin, G. 1987. *Algorithmic Information Theory.*
Cambridge University Press: Cambridge / New York.

32. Chor, B., O. Goldreich and S. Goldwasser. 1985. The Bit
Security of Modular Squaring Given Partial Factorization of the Modulos.
*Advances in Cryptology: CRYPTO '85 Proceedings.* 448-457.
Springer-Verlag: Berlin / New York.

33. Chor, B. and O. Goldreich. 1988. Unbiased Bits from Sources
of Weak Randomness and Probabilistic Communication Complexity.
*SIAM Journal on Computing.* 17: 230-261.

34. Ciarcia, S. 1986. Build a Hardware Data Encryptor.
*Byte.* September. 97-111.

35. Cleary, J. and I. Witten. 1984. Data Compression Using
Adaptive Coding and Partial String Matching. *IEEE Transactions
on Communications.* COM-32: 396-402.

36. Collings, B. and G. Hembree. 1986. Initializing Generalized
Feedback Shift Register Pseudorandom Number Generators. *Journal of
the ACM.* 33: 707-711, 34: 1001.

37. Collings, B. 1987. Compound Random Number Generators.
*Journal of the American Statistical Association.* 82 (398):
525-527.

38. Compagner, A. and A. Hoogland. 1987. Maximum-Length
Sequences, Cellular Automata, and Random Numbers. *Journal of
Computational Physics.* 71: 391-428.

39. Cormack, G. and R. Horspool. 1984. Algorithms for Adaptive
Huffman Codes. *Information Processing Letters.* 18: 159-165.

40. Costas, J. 1979. Cryptography in the Field, Part 2: Using the
Pocket Calculator. *Byte.* March 1979. 157.

41. *Cryptology Yesterday, Today, and Tomorrow.* 1987.
Editors: C. Deavours, D. Kahn, L. Kruh, G. Mellen and B. Winkle.
Artech House: Norwood, Mass.

42. Davies, D. and W. Pierce. 1984. *Security for Computer
Networks.* John Wiley: New York.

43. Davis, W. 1966. Automatic Delay Changing Facility for
Delayed *m*-Sequences. *Proceedings of the IEEE.*
54: 913-914.

44. Deavours, C. 1977. Unicity Points in Cryptanalysis.
*Cryptologia.* 1(1). (Also in
[41: 359-378].)

45. Denning, D. 1982. *Cryptography and Data Security.*
Reading, Mass: Addison-Wesley.

46. de Visme, G. 1971. *Binary Sequences.* The English
Universities Press: London.

47. Diaconis, P. and R. Grahm. 1977. Spearman's Footrule as a
Measure of Disarray. *Journal of the Royal Statistical
Society.* Series B. 39: 262-268

48. Diaconis, P. and M. Shahshahavi. 1981. Generating a Random
Permutation with Random Transpositions.
*Z. Wahscheinlichkeitstheorie.* 57: 159-179.
(Springer-Verlag.)

49. Diffie, W. and M. Hellman. 1976. New Directions in
Cryptography. *IEEE Transactions on Information Theory.*
IT22: 644-654.

50. Durstenfeld, R. 1964. Algorithm 235, Random Permutation,
Procedure SHUFFLE. *Communications of the ACM.* 7: 420.

51. Erber, T., P. Everett and P. Johnson. 1979. The Simulation
of Random Processes on Digital Computers with Cebysev Mixing
Transformations. *Journal of Computational Physics.*
32: 168-211.

52. Erber, T., T. Rynne, W. Darsow and M. Frank. 1983. The
Simulation of Random Processes on Digital Computers: Unavoidable
Order. *Journal of Computational Physics.* 49: 349-419.

53. Erber, T. and S. Putterman. 1985. Randomness in quantum
mechanics -- nature's ultimate cryptogram? *Nature.*
318: 41-43.

54. Etzion, T. and A. Lempel. 1984. Algorithms for the
Generation of Full-Length Shift-Register Sequences. *IEEE
Transactions on Information Theory.* IT-30: 480-484.

55. Feldman, F. 1988. Fast Spectral Tests for Measuring
Nonrandomness and the DES. *Advances in Cryptology: CRYPTO '87
Proceedings.* 243-254. Springer-Verlag: Berlin / New York.

56. Fischer, E. 1981. A Theoretical Measure of Cryptographic
Performance. *Cryptologia.* 5(1). (Also in
[41: 421-426].)

57. Fischer, E. 1981. Measuring Cryptographic Performance with
Production Processes. *Cryptologia.* 5(3). (Also in
[41: 421-426].)

58. Fushimi, M. and S. Tezuka. 1983. The *k*-Distribution
of Generalized Feedback Shift Register Pseudorandom Numbers.
*Communications of the ACM.* 26(7): 516-523.

59. Fushimi, M. 1983. Increasing the Orders of Equidistribution
of the Leading Bits of the Tausworthe Sequence. *Information
Processing Letters.* 16: 189-192.

60. Fushimi, M. 1988. Designing a Uniform Random Number
Generator Whose Subsequences are *k*-Distributed. *SIAM
Journal on Computing.* 17: 1988.

61. Fushimi, M. 1989. An Equivalence Relation between
Tausworthe and GFSR Sequences and Applications. *Applied
Mathematics Letters.* 2(2): 135-137.

62. Gallager, R. 1978. Variations on a Theme by Huffman. *IEEE
Transactions on Information Theory.* IT-24: 668-674.

63. Gardner, M. 1983. *Wheels, Life and Other Mathematical
Amusements.* W. H. Freeman: New York.

64. Geffe, P. 1973. How to protect data with ciphers that are
really hard to break. *Electronics.* 46(1): 99-101.

65. Gleick, J. 1987. *Chaos: Making a New Science.* Viking
Penguin: New York.

66. Goldreich, O., S. Goldwasser and S. Micali. 1984. How to
Construct Random Functions (Extended Abstract). *25th IEEE
Symposium on the Foundations of Computer Science.* 464-479.

67. Goldreich, O., H. Krawczyk and M. Luby. 1988. On the
Existence of Pseudorandom Generators (Extended Abstract). *29th
IEEE Symposium on the Foundations of Computer Science.* 12-24.

68. Goldwasser, S. and S. Micali. 1984. Probabilistic Encryption.
*Journal of Computer and System Sciences.* 28: 270-299.

69. Goldwasser, S. and J. Kilian. 1986. Almost All Primes Can be
Quickly Certified. *18th Symposium on the Theory of
Computing.* 316-329.

70. Gollmann, D. and W. Chambers. 1989. Clock-Controlled Shift
Registers: A Review. *IEEE Journal on Selected Areas in
Communications.* 7: 525-533.

71. Golomb, S. 1982 (original publication 1967). *Shift Register
Sequences,* Revised Edition. Aegean Park Press: Laguna Hills, CA.

72. Groth, E. 1971. Generation of Binary Sequences With
Controllable Complexity. *IEEE Transactions on Information
Theory.* IT-17: 288-296.

73. Guinier, D. 1989. A Fast Uniform "Astronomical" Random
Number Generator. *SIGSAC Review* (ACM Special Interest Group
on Security Audit & Control). 7(1): 1-13. ACM Press: New York.

74. Günther, C. 1987. Alternating Step Generators Controlled by
De Bruijn Sequences. *Advances in Cryptology: EUROCRYPT '87
Proceedings.* 5-14. Springer-Verlag: Berlin / New York.

75. Hastad, J. and A. Shamir. 1985. The Cryptographic Security
of Truncated Linearly Related Variables. *17th ACM Symposium on
Theory of Computing.* 356-362.

76. Hellman, M. 1977. An Extension of the Shannon Theory
Approach to Cryptography. *IEEE Transactions on Information
Theory.* IT-23: 289-294.

77. Hellman, M. 1982. Cryptographic Key Size Issues.
*Proceedings of the (24th) IEEE Spring COMPCON 1982.* 130-137.

78. Hemmati, F. 1982. A Large Class of Nonlinear Shift Register
Sequences. *IEEE Transactions on Information Theory.*
IT-28: 355-359.

79. Herlestam, T. 1983. On Using Prime Polynomials in Crypto
Generators. *Cryptography. Proceedings, Burg Feuerstein
1982.* Springer-Verlag: Berlin / New York.

80. Hofstadter, D. 1979. *Gödel, Escher, Bach: an Eternal
Golden Braid.* Basic Books: New York.

81. Horowitz, P. and W. Hill. 1989. *The Art of Electronics,*
2nd Edition. Cambridge University Press: New York.

82. Hosack, J. 1986. The Use of Cebysev Mixing to Generate
Pseudo-random Numbers. *Journal of Computational Physics.*
67: 482-486.

83. Huffman, D. 1952. A Method for the Construction of
Minimum-Redundency Codes. *Proceedings of the IRE.*
40: 1098-1101.

84. Jay, F., ed. 1977. *IEEE Dictionary of Electrical and
Electronics Terms,* 2nd Ed. IEEE / John Wiley: New York.

85. Johnsen, V. and K. Kjeldsen. 1973. Loop-free Compositions
of Certain Finite Automata. *Information and Control.*
22: 303-319.

86. Jueneman, R. 1987. A High Speed Manipulation Detection
Code. *Advances in Cryptology: CRYPTO '86 Proceedings.*
327-346. Springer-Verlag: Berlin / New York.

87. Jueneman, R. 1987. Electronic Document Authentication.
*IEEE Network Magazine.* 1(2): 17-23.

88. Kahn, D. 1967. *The Codebreakers.* Macmillan: New York.

89. Key, E. 1976. An Analysis of the Structure and Complexity of
Nonlinear Binary Sequence Generators. *IEEE Transactions on
Information Theory.* IT-22: 732-736.

90. Kirkpatrick, S. and E. Stoll. 1981. Note: A Very Fast
Shift-Register Sequence Random Number Generator. *Journal of
Computational Physics.* 40: 517-526.

91. Knuth, D. 1981. *The Art of Computer Programming,*
Vol. 2, *Seminumerical Algorithms.* 2nd ed. Addison-Wesley:
Reading, Massachusetts.

92. Knuth, D. 1985. Deciphering a Linear Congruential
Encryption. *IEEE Transactions on Information Theory.*
IT-31: 49-52.

93. Kolmogorov, A. 1965. Three approaches to the quantitative
definition of information. *Problems of Information
Transmission.* 1: 1-7.

94. Koopman, R. 1986. The Orders of Equidistribution of
Subsequences of Some Asymptotically Random Sequences.
*Communications of the ACM.* 29: 802-806.

95. Kranakis, E. 1986. *Primality and Cryptography.*
John Wiley: New York.

96. Landau, S. 1988. Zero Knowledge and the Department of
Defense. *Notices of the American Mathematical Society.*
35: 5-12.

97. Langdon, G. 1983. A Note on the Ziv-Lempel Model for
Compressing Individual Sequences. *IEEE Transactions on
Information Theory.* IT-29: 284-286.

98. L'Ecuyer, P. 1988. Efficient and Portable Combined Random
Number Generators. *Communications of the ACM.*
31(6): 742-749, 774.

99. L'Ecuyer, P. and R. Proulx. 1989. About Polynomial-Time
"Unpredictable" Generators. *Proceedings of the 1989 Winter
Simulation Conference.* 467-476. IEEE Press: New York.

100. L'Ecuyer, P. 1990. Random numbers for simulation.
*Communications of the ACM.* 33(10): 86-97.

101. Letham, L., D. Hoff and A. Folmsbee. 1986. A 128k EPROM
Using Encryption of Pseudorandom Numbers to Enable Read Access.
*IEEE Journal of Solid-State Circuits.* SC-21: 881-888.

102. Lempel, A., and J. Ziv. 1976. On the Complexity of Finite
Sequences. *IEEE Transactions on Information Theory.*
IT-22: 75-81.

103. Levin, L. 1985. One-Way Functions and Pseudorandom
Generators. *17th ACM Symposium on Theory of Computing.*
363-365.

104. Levine, J. and V. Brawley. 1977. Some Cryptographic
Applications of Permutation Polynomials. *Cryptologia.*
1: 76-92.

105. Levine, J. and R. Chandler. 1987. Some Further Cryptographic
Applications of Permutation Polynomials. *Cryptologia.*
11: 211-217.

106. Lewis, T. and W. Payne. 1973. Generalized Feedback Shift
Register Pseudorandom Number Algorithm. *Journal of the ACM.*
20: 456-468.

107. Long, D. and A. Wigderson. 1983. How Discreet is the
Discrete Log? *15th ACM Symposium on Theory of Computing.*
413-420.

108. Lu, S. 1979. The Existence of Good Cryptosystems for Key
Rates Greater than Message Redundancy. *IEEE Transactions on
Information Theory.* IT-25: 475-477.

109. MacLaren, M. and G. Marsaglia. 1965. Uniform Random
Number Generators. *Journal of the Association for Computing
Machinery.* 12: 83-89.

110. MacWilliams, F. and N. Sloane. 1976. Pseudo-Random
Sequences and Arrays. *Proceedings of the IEEE.*
64: 1715-1729.

111. MacWilliams, F. and N. Sloane. 1977. *The Theory of
Error-Correcting Codes.* North Holland: Amsterdam / New York.

112. Marsaglia, G., and T. Bray. 1968. One-Line Random
Number Generators and Their Use in Combinations. *Communications
of the ACM.* 11: 757-759.

113. Marsaglia, G. 1984. A current view of random number
generators. *Proceedings of the Sixteenth Symposium on the
Interface Between Computer Science and Statistics.* 3-10.

114. Marsaglia, G. and L. Tsay. 1985. Matrices and the Structure
of Random Number Sequences. *Linear Algebra and its
Applications.* 67: 147-156.

115. Marsaglia, G. and A. Zaman. 1990. Toward a Universal
Random Number Generator. *Statistics and Probability Letters.*
8: 35-39.

116. Martin-Lf, P. 1966. The Definition of Random Sequences.
*Information and Control.* 9: 602-619.

117. Massey, J. 1969. Shift-Register Synthesis and BCH
Decoding. *IEEE Transactions on Information Theory.*
IT-15: 122-127.

118. Massey, J. 1988. An Introduction to Contemporary
Cryptology. *Proceedings of the IEEE.* 76: 533-549.

119. Matthews, R. 1989. On the Derivation of a "Chaotic"
Encryption Algorithm. *Cryptologia.* 13: 29-42.

120. McCoy, N. 1972. *Fundamentals of Abstract Algebra.*
Allyn and Bacon: Boston.

121. Meier, W. and O. Staffelbach. 1988. Fast Correlation
Attacks on Stream Ciphers (extended abstract). *Advances in
Cryptology: EUROCRYPT '88 Proceedings.* 301-314.
Springer-Verlag: Berlin / New York.

122. Mellen, G. 1973. Cryptology, Computers, and Common
Sense. *Proceedings of the National Computer Conference.*
1973: 569-579.

123. Meyer, C. and W. Touchman. 1972. Pseudorandom codes
can be cracked. *Electronic Design 23.* (Nov): 74-76.

124. Meyer, C. and S. Matyas. 1982. *Cryptography: A New
Dimension in Computer Data Security.* John Wiley: New York.

125. Mitchell, D. 1990. Nonlinear Key Generators.
*Cryptologia.* 14: 350-354.

126. Mund, S., D. Gollmann, and T. Beth. 1987. Some Remarks
on the Cross Correlation Analysis of Pseudo Random Generators.
*Advances in Cryptology: EUROCRYPT '87 Proceedings.* 25-35.
Springer-Verlag: Berlin / New York.

127. Nichols, E., J. Nichols, and K. Musson. 1982. *Data
Communications for Microcomputers.* McGraw-Hill: New York.

128. Nicolis, G. and I. Prigogine. 1989. *Exploring
Complexity.* W. H. Freeman and Company: New York.

129. Niederreiter, H. 1987. A Statistical Analysis of Generalized
Feedback Shift Register Pseudorandom Number Generators. *SIAM
Journal on Scientific and Statistical Computing.* 8: 1035-1051.

130. Nisan, N. and A. Wigderson. 1988. Hardness vs.
Randomness (Extended Abstract). *29th IEEE Symposium on
Foundations of Computer Science.* 2-11.

131. Page, E. 1967. A note on generating random permutations.
*Applied Statistics.* 16: 273-274.

132. Park, S. and K. Miller. 1988. Random Number Generators:
Good Ones Are Hard To Find. *Communications of the ACM.*
31: 1192-1201.

133. Patterson, W. 1987. *Mathematical Cryptology.* Rowan &
Littlefield: Totowa, N.J.

134. Pearson, P. 1988. Cryptanalysis of the Ciarcia Circuit Cellar
Data Encryptor. *Cryptologia.* 12: 1-9.

135. Pearson, P. 1990. Fast Hashing of Variable-Length Text
Strings. *Communications of the ACM.* 33: 677-680.

136. Pickover, C. 1988. Pattern Formation and Chaos in
Networks. *Communications of the ACM.* 31: 136-151.

137. Pierce, J. 1980. *An Introduction to Information
Theory.* 2nd Ed. Dover Publications: New York.

138. PKZIP110.EXE, *APPNOTE.TXT* (shareware file compression
utility documentation). 1989. PKWARE: Glendale, WI.

139. Plackett, R. 1968. Random Permutations. *Journal of the
Royal Statistical Society.* Series B. 30: 517-534.

140. Pless, V. 1977. Encryption Schemes for Computer
Confidentiality. *IEEE Transactions on Computers.*
C-26: 1133-1136.

141. Poundstone, W. 1985. *The Recursive Universe.*
Contemporary Books: Chicago.

142. Rabin, M. 1980. Probabilistic Algorithms in Finite Fields.
*SIAM Journal on Computing.* 9: 273-280.

143. Ramabadran, T. and S. Gaitonde. A Tutorial on CRC
Computations. *IEEE Micro.* August: 62-75.

144. Rao, C. 1961. Generation of Random Permutations of
Given Number of Elements Using Random Sampling Numbers.
*Sankhya.* Series A. 23: 305-307.

145. Rasband, S. 1990. *Chaotic Dynamics of Nonlinear
Systems.* John Wiley & Sons: New York.

146. Reed, I. and R. Turn. 1969. A Generalization of
Shift-Register Sequence Generators. *Journal of the Association
for Computing Machinery.* 16: 461-473.

147. Reeds, J. 1977. "Cracking" a Random Number Generator.
*Cryptologia.* 1(1). (Also
[41: 509-515].)

148. Reif, J. and D. Tygar. 1988. Efficient Parallel
Pseudorandom Number Generation. *SIAM Journal on Computing.*
17: 404-411.

149. Retter, C. 1984. Cryptanalysis of a MacLaren-Marsaglia
System. *Cryptologia.* 8:97-108. Also see letters,
8: 374-378.

150. Retter, C. 1985. A Key Search Attack on MacLaren-Marsaglia
Systems. *Cryptologia.* 9: 114-130.

151. Rietman, E. 1989. *Exploring the Geometry of Nature.*
Windcrest Books, Blue Ridge Summit, PA.

152. Ritter, T. 1990. Substitution Cipher with Pseudo-Random
Shuffling: The Dynamic Substitution Combiner. *Cryptologia.*
14(4): 289-303.

153. Ritter, T. 1991. Transposition Cipher with Pseudo-Random
Shuffling: The Dynamic Transposition Combiner. *Cryptologia.*
15(1):1-17.

154. Rivest, R, A. Shamir, and L. Adleman. 1978. A Method for
Obtaining Digital Signatures and Public Key Cryptosystems.
*Communications of the ACM.* 21: 120-126.

155. Rivest, R. 1980. "Forwards and Backwards" Encryption.
*Cryptologia.* 4(1). (Also
[41: 433-437].)

156. Robbins, D. and E. Bolker. 1981. The bias of three pseudo-
random shuffles. *Aequationes Mathematicae.* 22: 268-292.

157. Rubin, F. 1978. Computer Methods for Decrypting
Random Stream Ciphers. *Cryptologia.* 2(3). (Also
[41: 493-508].)

158. Rubin, F. 1979. Decrypting a Stream Cipher Based on J-K
Flip-Flops. *IEEE Transactions on Computers.* C28: 483-487.
(Also *Cryptologia* 5(1), and
[41: 283-293].)

159. Rudich, S. 1985. Inferring the structure of a Markov Chain
from its output. *26th IEEE Symposium on the Foundations of
Computer Science.* 321-326.

160. Rueppel, R. 1985. Correlation Immunity and the
Summation Generator. *Advances in Cryptology: CRYPTO '85
Proceedings.* 260-272. Springer-Verlag: Berlin / New York.

161. Rueppel, R. 1987. Linear Complexity and Random
Sequences. *Advances in Cryptology: CRYPTO '86 Proceedings.*
167-188. Springer-Verlag: Berlin / New York.

162. Rueppel, R. and O. Staffelbach. 1987. Products of Linear
Sequences with Maximal Complexity. *IEEE Transactions on
Information Theory.* IT-33: 124-131.

163. Rueppel, R. 1988. When Shift Registers Clock Themselves.
*Advances in Cryptology: EUROCRYPT '87 Proceedings.* 53-64.
Springer-Verlag: Berlin / New York.

164. Sandelius, M. 1962. A simple randomization procedure.
*Journal of the Royal Statistical Society.* Series B.
24: 472-481.

165. Santha, M. and U. Vazirani. 1986. Generating Quasi-random
Sequences from Semi-random Sources. *Journal of Computer and
System Sciences.* 33: 75-87.

166. Sastri, K. 1975. Specified sequence linear feedback shift
registers. *International Journal of Systems Science.*
6: 1009-1019.

167. Shamir, A. 1981. On the generation of cryptographically
strong pseudo-random sequences. *8th International Colloquium on
Automata, Language, and Programming.* 544-550.

168. Shannon, C. and W. Weaver. 1949. *The Mathematical
Theory of Communication.* University of Illinois Press:
Urbana, Chicago.

169. Shannon, C. 1949. Communication Theory of Secrecy
Systems. *Bell System Technical Journal.* 28: 656-715.

170. Siegenthaler, T. 1984. Correlation-Immunity of Nonlinear
Combining Functions for Cryptographic Applications. *IEEE
Transactions on Information Theory.* IT-30: 776-780.

171. Siegenthaler, T. 1985. Decrypting a Class of Stream
Ciphers Using Ciphertext Only. *IEEE Transactions on Computers.*
C34: 81-85.

172. Siegenthaler, T. 1986. Cryptanalysts Representation of
Nonlinearly Filtered ML-Sequences. *Advances in Cryptology:
EUROCRYPT '85 Proceedings.* 103-110. Springer-Verlag:
Berlin / New York.

173. Siegenthaler, T. 1986. Design of Combiners to Prevent
Divide and Conquer Attacks. *Advances in Cryptology: CRYPTO '85
Proceedings.* Springer-Verlag: Berlin / New York.

174. Siegenthaler, T., R. Forre, and A. Kleiner. 1987. Generation
of Binary Sequences with Controllable Complexity and Ideal
*r*-Tupel Distribution. *Advances in Cryptology: EUROCRYPT
'87 Proceedings.* 15-23. Springer-Verlag: Berlin / New York.

175. Simmons, G. 1979. Symmetric and Asymmetric Encryption.
*Computing Surveys.* 11: 305-330.

176. Simmons, G. 1988. A Survey of Information
Authentication. *Proceedings of the IEEE.* 76: 603-620.

177. Sloane, N. 1983. Encrypting by Random Rotations.
*Cryptography. Proceedings, Burg Feuerstein 1982.* 71-128.
Springer-Verlag: Berlin / New York.

178. Stahnke, W. 1973. Primitive Binary Polynomials.
*Mathematics of Computation.* 27: 977-980.

179. Stern, J. 1987. Secret Linear Congruential Generators are
Not Cryptographically Secure. *28th Annual Symposium on
Foundations of Computer Science.* 421-426.

180. Storer, J. and T. Szymanski. 1982. Data Compression via
Textual Substitution. *Journal of the ACM.* 29: 928-951.

181. Swift, J. 1960. Construction of Galois Fields of
Characteristic Two and Irreducible Polynomials. *Mathematics of
Computation.* 14: 99-103.

182. Tanenbaum, A. 1981. *Computer Networks.* Prentice-Hall:
Englewood Cliffs, NJ.

183. Tang, Y., A. Mees and L. Chua. 1983. Synchronization and
Chaos. *IEEE Transactions on Circuits and Systems.* CAS-30:
620-626.

184. Tausworthe, R. 1965. Random Numbers Generated by
Linear Recurrence Modulo Two. *Mathematics of Computation.*
19: 201-209.

185. Tezuka, S. 1987. Walsh-Spectral Test for GFSR Pseudorandom
Numbers. *Communications of the ACM.* 30: 731-735.

186. Tezuka, S. 1987. On the Discrepancy of GFSR
Pseudorandom Numbers. *Journal of the Association for Computing
Machinery.* 34: 939-949.

187. Tezuka, S. 1988. On Optimal GFSR Pseudorandom
Number Generators. *Mathematics of Computation.* 50: 531-533.

188. Tootill, J., W. Robinson, and A. Adams. 1971. The Runs
Up-and-Down Performance of Tausworthe Pseudo-Random Number
Generators. *Journal of the Association for Computing
Machinery.* 18:381-399.

189. Tootill, J., W. Robinson, and D. Eagle. 1973. An
Asymptotically Random Tausworthe Sequence. *Journal of the
ACM.* 20: 469-481.

190. Vahle, M. and L. Tolendino. 1982. Breaking a Pseudo
Random Number Based Cryptographic Algorithm. *Cryptologia.*
6: 319-328.

191. Vazirani, U. and V. Vazirani. 1983. Trapdoor Pseudo-random
Number Generators with Applications to Protocol Design. *24th
IEEE Symposium on the Foundations of Computer Science.* 23-30.

192. Vazirani, U. and V. Vazirani. 1985. Efficient and Secure
Pseudo-Random Number Generation. (extended abstract) *Advances
in Applied Cryptology: Proceedings of CRYPTO 84.* 193-202.
Springer-Verlag: Berlin / New York.

193. Vazirani, U. 1985. Towards a Strong Communication
Complexity Theory or Generating Quasi-Random Sequences from Two
Communicating Slightly-Random Sources. *Proceedings of the 17th
Annual ACM Symposium on the Theory of Computing.* 366-378.

194. Vernam, G. 1926. Cipher Printing Telegraph Systems.
*Transactions of the AIEE.* 45: 295-301.

195. von Neumann, J. 1963. Various techniques used in
connection with random digits. *John von Neumann, Collected
Works.* 5: 768-770. A. H. Taub, Ed. MacMillan: New York.

196. Wagner, P., P. Putter and M. Cain. 1987. Large-Scale
Randomization Techniques. *Advances in Cryptology: CRYPTO '86
Proceedings.* 394-404. Springer-Verlag: Berlin / New York.

197. Watson, E. 1962. Primitive Polynomials (Mod 2).
*Mathematics of Computation.* 16: 368-369.

198. Wayner, P. 1987. Building an Encryption System.
*Computer Language.* December: 67-72.

199. Welch, T. 1984. A Technique for High-Performance Data
Compression. *Computer.* June, 1984: 8-19.

200. Westlake, W. 1967. A Uniform Random Number Generator
Based on the Combination of Two Congruential Generators. *Journal
of the Association for Computing Machinery.* 14: 337-340.

201. Wheeler, D. 1989. Problems with Chaotic Cryptosystems.
*Cryptologia.* 13: 243-250.

202. Wichmann, B. and I. Hill. 1982. An Efficient and Portable
Pseudo-Random Number Generator. Applied *Statistics.*
33: 706-711. (Also see comments and responses 33: 123,
34: 198-200 and 35: 89.)

203. Wichmann, B. and D. Hill. 1987. Building a Random-Number
Generator. *Byte.* March, 1987. 127-128.

204. Wikramaratna, R. 1989. ACORN -- A New Method for
Generating Sequences of Uniformly Distributed Pseudo-random Numbers.
*Journal of Computational Physics.* 83: 16-31.

205. Winternitz, R. 1984. A Secure One-Way Hash Function
Built from DES. *1984 IEEE Symposium on Secrecy and
Privacy.* 88-90.

206. Wolfram, S. 1985. Cryptography with Cellular Automata
(extended abstract). *Advances in Cryptology: CRYPTO '85
Proceedings.* Springer-Verlag, 1986. 429-432.

207. Wolfram, S. 1986. Random Sequence Generation by
Cellular Automata. *Advances in Applied Mathematics.*
7: 123-169.

208. Yao, A. 1982. Theory and Applications of Trapdoor
Functions. *Proceedings of the 23rd IEEE Symposium on Foundations
of Computer Science.* 80-91.

209. Yuen, C. 1977. Testing Random Number Generators by
Walsh Transform. *IEEE Transactions on Computers.*
C-26: 329-333.

210. Zeisel, H. 1986. A Remark on Algorithm AS 183. An
Efficient and Portable Pseudo-random Number Generator. *Applied
Statistics.* 35: 89.

211. Zierler, N. and J. Brillhart. 1968. On Primitive Trinomials
(Mod 2). *Information and Control.* 13: 541-554.

212. Zierler, N. and J. Brillhart. 1969. On Primitive Trinomials
(Mod 2), II. *Information and Control.* 14: 566-569.

213. Ziv, J. and A. Lempel. 1977. A Universal Algorithm for
Sequential Data Compression. *IEEE Transactions on Information
Theory.* IT-23: 337-343.

Terry Ritter is a registered Professional Engineer, a member of IEEE and ACM, with a background in computer architecture, hardware, software, and now, library research. He has spent the last few years being Blue Jean Software and Blue Jean Computer Engineering.