The first widely used technology for generating a random number was the algorithm proposed by Lechmer, which is known as the linear congruent method. This algorithm is parameterized by four numbers as follows:

Subsequence random numbers(X n) is obtained using the following iterative equality:

X n +1 = (a X n + c) mod m

If m, a and c are integers, then a sequence of integers in the range 0 X n is created< m.

The choice of values ​​for a, c, and m is critical to developing a good random number generator.

Obviously, m must be very large to be able to generate many random numbers. It is believed that m should be approximately equal to the maximum positive integer for of this computer. So usually m is close to or equal to 2 31 .

There are three criteria used when choosing a random number generator:

1. The function must create a complete period, i.e. all numbers between 0 and m before the numbers generated start repeating.

2. The generated sequence must appear randomly. The sequence is not random since it is generated deterministically, but the various statistical tests that may be applied should show that the sequence is random.

3. The function must be effectively implemented on 32-bit processors.

The values ​​of a, c and m must be chosen so that these three criteria are met. In accordance with the first criterion, it can be shown that if m is simple and c = 0, then for a certain value of a the period, created by a function, will be equal to m-1. For 32-bit arithmetic, the corresponding prime value is m = 2 31 - 1. So the creation function pseudorandom numbers has the form:

X n +1 = (a X n) mod (2 31 - 1)

Only a small number of values ​​of a satisfy all three criteria. One such value is a = 7 5 = 16807, which was used in the IBM 360 family of computers. This generator is widely used and has passed more than a thousand tests, more than all other pseudorandom number generators.

The power of the linear congruent algorithm is that if the factor and modulus (base) are appropriately chosen, then the resulting sequence of numbers will be statistically indistinguishable from a sequence that is random from the set 1, 2, ..., m-1. But there can be no randomness in the sequence obtained using the algorithm, regardless of the choice of the initial value X 0 . If a value is selected, the remaining numbers in the sequence will be predetermined. This is always taken into account in cryptanalysis.

If the adversary knows that the linear congruent algorithm is being used, and if its parameters are known (a = 7 5, c = 0, m = 2 31 - 1), then if one number is revealed, the entire sequence of numbers becomes known. Even if the adversary only knows that a linear congruent algorithm is being used, knowing a small part of the sequence is enough to determine the parameters of the algorithm and all subsequent numbers. Let's assume that the enemy can determine the values ​​of X 0, X 1, X 2, X 3. Then:

X 1 = (a X 0 + c) mod mX 2 = (a X 1 + c) mod mX 3 = (a X 2 + c) mod m

These equalities allow us to find a, c and m.

Thus, although the algorithm is good generator pseudo-random sequence of numbers, it is desirable that the actual sequence used be unpredictable, since in this case knowledge of part of the sequence will not allow determining its future elements. This goal can be achieved in several ways. For example, using the internal system clock to modify the random number stream. One way to use the clock is to restart the sequence after N numbers, using the clock's current value modulo m as the new starting value. Another way is to simple addition current time values ​​to each random number modulo m.

Generating random sequences with a given probabilistic law and checking their adequacy are some of the the most important problems modern cryptology. Random sequence generators are used in existing cryptosystems to generate key information and set a number of cryptosystem parameters. The scientific and practical significance of this problem is so great that separate monographs in the field of cryptology are devoted to it, sections are organized in scientific journals "Journal of Cryptology", "Cryptologia" and special sessions at international scientific conferences "Eurocrypt", "Asiacrypt", "Crypto" and etc.

At the beginning of the 20th century, random sequences were simulated using the simplest random experiments: throwing a coin or dice, drawing balls from an urn, laying out cards, roulette, etc. In 1927, L. Tippett first published tables containing over 40,000 random numbers , “randomly extracted from census reports.” In 1939, using a specially designed mechanical device- random number generator, M. J. Kendall and B. Babington-Smith created a table containing 10 5 random numbers. In 1946, American mathematician John von Neumann first proposed a computer algorithm for generating random numbers. In 1955, the RAND Corporation published widely popular tables containing 10 6 computer-generated random numbers.

Currently, the demand for random sequence generators with given probability distributions, as well as for random sequences themselves, has increased so much that research and production companies have appeared abroad, producing and selling large arrays of random numbers. For example, since 1996, the compact disc “The Marsaglia random number CDROM” has been distributed around the world, which contains 4.8 billion “truly random” bits.

The vast majority of modern cryptographic systems use either stream or block algorithms based on various types substitution and permutation ciphers. Unfortunately, almost all algorithms used in stream cryptosystems are intended for use in military and government communications systems, as well as, in some cases, for protecting commercial information, which quite naturally makes them secret and inaccessible for review. The only standard algorithms for stream symmetric encryption are the American DES standard (CFB and OFB modes) and the Russian GOST 28147-89 standard (gamma mode).

The basis for the functioning of stream cryptosystems are generators of random or pseudorandom sequences. Let's consider this issue in more detail.

2 Pseudo-random number generator

Secret keys represent the basis of cryptographic transformations, for which, according to Kerkhoffs' rule, the strength of the cryptosystem is determined only by the secrecy of the key. The main problem of classical cryptography for a long time has been the difficulty of generating a secret key. Physically modeling randomness using physical phenomena such as radioactive radiation or shot noise in a vacuum tube is quite difficult and expensive, and the use of keystrokes and mouse movements requires user effort and also does not provide completely true random processes. Therefore, instead of physical modeling, methods of mathematical modeling of randomness and generation of random sequences in the form of computer programs or specialized devices are used.

These programs and devices, although called random number generators, actually generate deterministic sequences that only appear random in their properties and are therefore called pseudo-random sequences. They are required to ensure that, even knowing the law of formation, but without knowing the key in the form of given initial conditions, no one would be able to distinguish the generated sequence from a random one, as if it were obtained by throwing ideal dice.

Pseudo-random number generator(PRNG, English Pseudorandom number generator, PRNG) - an algorithm that generates a sequence of numbers, the elements of which are almost independent of each other and obey a given distribution (usually uniform).

It is possible to formulate three main requirements that cryptographically strong generators of pseudo-random sequences or gammas must satisfy.

1. The gamma period must be large enough to encrypt messages of varying lengths.

2. Gamma should be difficult to predict. This means that if the type of generator and a piece of gamma are known, then it is impossible to predict the gamma bit that follows this piece or the gamma bit that precedes this piece.

3. Generating a range should not be associated with major technical and organizational difficulties.

The most important characteristic of a pseudorandom number generator is the information length of its period, after which the numbers will either simply repeat or can be predicted. This length practically determines the possible number of keys in the cryptosystem. The longer this length, the more difficult it is to find the key.

The second of the above requirements is related to next problem: On what basis can we conclude that the gamma of a particular generator is truly unpredictable? So far in the world there are no universal and practically verifiable criteria for checking this property. Intuitively, randomness is perceived as unpredictability. For a gamma to be considered random and unpredictable, at a minimum, its period must be very large, and various combinations of bits of a certain length must be evenly distributed along its entire length. This requirement can be statistically interpreted as the complexity of the law for generating a pseudo-random sequence of numbers. If from a sufficiently long segment of this sequence it is impossible to determine this generation law either statistically or analytically, then in principle one can be satisfied with this.

And finally, the third requirement must guarantee the possibility of practical implementation of pseudo-random sequence generators, taking into account the required speed and ease of practical use. Let us now consider some practical methods for obtaining pseudorandom numbers.

3 Methods for obtaining pseudorandom numbers

One of the first such methods was the method proposed in 1946 by D. von Neumann. This method was based on the fact that each subsequent number in a pseudo-random sequence was formed by squaring the previous number and discarding the digits at both ends. However, this method proved unreliable and was quickly abandoned. Another method is the so-called congruent method.

3.1 Linear congruent method

The linear congruent method is one of the algorithms for generating pseudorandom numbers. Applicable in simple cases and does not have cryptographic strength. Included in the standard libraries of various compilers.

This algorithm consists of iteratively applying the following formula:

where a>0, c>0, m>0 are some integer constants. The resulting sequence depends on the choice of starting number X 0 and for different values ​​of it, different sequences of random numbers are obtained. At the same time, many properties of the sequence X j are determined by the choice of coefficients in the formula and do not depend on the choice of starting number. It is clear that the sequence of numbers generated by such an algorithm is periodic with a period not exceeding m. In this case, the length of the period is equal to m if and only if:

· GCD (c, m) = 1 (that is, c and m are coprime);

· a - 1 multiple of p for all prime p - divisors of m;

· a - 1 is a multiple of 4 if m is a multiple of 4.

The statistical properties of the resulting sequence of random numbers are completely determined by the choice of constants a And c at a given bit depth e. For these constants, conditions are written that guarantee satisfactory quality of the resulting random numbers.

The table below shows the most commonly used parameters of linear congruent generators, in particular in the standard libraries of various compilers (rand() function).

3.2 Fibonacci method

An interesting class of pseudorandom sequence generators is based on the use of Fibonacci sequences. Classic example such a sequence (0,1,1,2,3,5,8,13,21,34...) - with the exception of its first two members, each subsequent member is equal to the sum of the previous two.

The distribution features of random numbers generated by the linear congruent algorithm make it impossible to use them in statistical algorithms that require high resolution.

In this regard, the linear congruent algorithm gradually lost its popularity, and its place was taken by the family of Fibonacci algorithms, which can be recommended for use in algorithms that are critical to the quality of random numbers. In the English-language literature, Fibonacci sensors of this type are usually called “Subtract-with-borrow Generators” (SWBG).

Fibonacci sensors have gained the greatest popularity due to the fact that the speed of performing arithmetic operations with real numbers has become equal to the speed of integer arithmetic, and Fibonacci sensors are naturally implemented in real arithmetic.

One of the widely used Fibonacci sensors is based on the following iterative formula:

Where X k- real numbers from range)