PUBLISHED: Ritter, T. 1991. The Efficient Generation of Cryptographic Confusion Sequences. Cryptologia. 15(2): 81-139.

The Efficient Generation of Cryptographic Confusion Sequences

Terry Ritter

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

1. INTRODUCTION (Prev|Next)

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.

2. BACKGROUND (Prev|Next)

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."

3. BASICS AND TERMINOLOGY (Prev|Next|Down)

3.1 Randomness (Prev|Next)

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].)

3.2 Randomness and Data Compression (Prev|Next)

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]).

3.3 Reasoning about Randomness (Prev|Next)

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.)

3.4 Gödel and Ciphers? (Prev|Next)

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.

3.5 Characteristics of Computer-Based RNG'S (Prev|Next)

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.

3.6 Number of Sequences (Prev|Next)

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.

3.7 Cycles (Prev|Next)

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.

3.8 Some Potential Attacks (Prev|Next)

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.

3.9 Inference Resistance by Exposure Class (Prev|Next)

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."

3.10 Information and Penetration (Prev|Next)

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.

3.11 Inference versus Prediction (Prev|Next)

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.

3.12 Cryptographic RNG Requirements (Prev|Next)

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:

1. allow arbitrary initialization, to support unbiased keys;
2. have a guaranteed long sequence, to make repetition (coincidence) attacks impractical;
3. be easy to customize, so that different users can have different sequences when using exactly the same key;
4. be fast, for an unused system is . . . , well . . . , useless;
5. 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,
6. 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.

4. RNG TECHNIQUES (Prev|Next|Down)

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.

4.1 Chaos (Prev|Next)

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.

4.2 Cebysev Mixing (Prev|Next)

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.

4.3 Cellular Automata (Prev|Next)

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]).

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.)

4.4 x^2 mod N (Prev|Next)

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.)

4.5 Linear Congruential (Prev|Next)

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,

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.

4.6 Linear Feedback Shift Register (LFSR) (Prev|Next)

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)

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:

1. there is only one major cycle, with length 2^n-1 steps (the all-zeros state is an isolated and degenerate cycle);
2. 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
3. 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 2n 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.

Execution time can be modest.

4.7 Non-Linear Shift Register (Prev|Next)

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.

4.8 Clock-Controlled Shift Registers (Prev|Next)

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].

4.9 Generalized Feedback Shift Register (GFSR) (Prev|Next)

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)

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 100p for polynomials of degree p, but they also use an additional 5000p to allow the first step of "all 1's" to "die out"; Bright and Enison suggest 20,000p. 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.)

4.10 Additive RNG (Prev|Next)

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 2m 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)

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.)

5. RANDOMIZERS and ISOLATORS (Prev|Next|Down)

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.

5.1 One-Way Functions (Prev|Next)

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.

5.2 Checksum Algorithms (Prev|Next)

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].

5.3 CRC's (Prev|Next)

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.

5.4 Randomizers (Prev|Next|Down)

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.

5.4.1 Theoretical Randomizers (Prev|Next)

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.

5.4.2 Randomizers in PKZIP (Prev|Next)

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?

5.5 Isolation Techniques (Prev|Next)

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:

1. 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.

2. Use a pseudo-random delete filter or jitterizer to create a discontinuous sequence. (An oscilloscope display which is only partially synchronized is said to 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.

3. 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.

4. 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.

5. Use a randomizer. If a randomizer further randomizes an already random sequence, it should also hide the original sequence and protect it from analysis.

6. 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.

7. 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.

8. 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.

6. OTHER RANDOMNESS TECHNIQUES (Prev|Next|Down)

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.

6.1 "Really Random" Values (Prev|Next)

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].

6.2 Cycle Detection (Prev|Next)

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.

6.3 Polynomial Degree (Prev|Next)

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].

6.4 Sequence Customization and Number of Terms (Prev|Next)

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].

6.5 Finding Primitive Mod 2 Polynomials (Prev|Next)

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.

6.6 Combined RNG's (Prev|Next)

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].)

6.7 Random Permutations (Prev|Next)

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.

7. RNG EXHAUSTIVE STATE EXPERIMENTS (Prev|Next)

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.

7.1 Exhaustive State Analysis (Prev|Next)

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).

7.2 Results (Prev|Next)

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.

7.3 Discussion (Prev|Next)

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.

8. SUMMARY (Prev|Next)

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.

9. COMMENTS (Prev|Next)

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.

10. REFERENCES (Prev|Next)

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-L”f, 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.

BIOGRAPHICAL SKETCH (Prev)

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.