Random number generator how to determine. Pseudo-random sequence generators
- Tutorial
Have you ever wondered how Math.random() works? What is a random number and how is it obtained? Imagine an interview question - write your generator random numbers in a couple of lines of code. So, what is it, an accident and is it possible to predict it?
I am very fascinated by various IT puzzles and tasks, and the random number generator is one of these tasks. Usually in my telegram channel I sort out all sorts of puzzles and different tasks from interviews. The random number generator problem has gained great popularity and I wanted to perpetuate it in the depths of one of the authoritative sources of information - that is, here on Habré.
This material will be useful to all those front-end and Node.js developers who are on the cutting edge of technology and want to get into a blockchain project/startup where questions about security and cryptography are at least basic level, they even ask front-end developers.
Pseudo-random number generator and random number generator
In order to get something random, we need a source of entropy, a source of some chaos from which we will use to generate randomness.This source is used to accumulate entropy and then obtain from it an initial value (seed), which is necessary for random number generators (RNG) to generate random numbers.
The Pseudo-Random Number Generator uses a single seed, hence its pseudo-randomness, while the Random Number Generator always generates a random number by starting with a high-quality random variable that is drawn from various sources of entropy.
Entropy is a measure of disorder. Information entropy is a measure of the uncertainty or unpredictability of information.It turns out that in order to create a pseudo-random sequence we need an algorithm that will generate a certain sequence based on a certain formula. But such a sequence can be predicted. However, let's imagine how we could write our own random number generator if we didn't have Math.random()
PRNG has some algorithm that can be reproduced.
RNG is the process of obtaining numbers entirely from some kind of noise, the ability to calculate which tends to zero. At the same time, the RNG has certain algorithms for equalizing the distribution.
We come up with our own PRNG algorithm
Generator pseudorandom numbers(PRNG, English pseudorandom number generator, PRNG) is 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).We can take a sequence of some numbers and take the modulus of the number from them. The simplest example that comes to mind. We need to think about which sequence to take and the module from what. If you just directly from 0 to N and modulus 2, you get a generator of 1 and 0:
Function* rand() ( const n = 100; const mod = 2; let i = 0; while (true) ( yield i % mod; if (i++ > n) i = 0; ) ) let i = 0; for (let x of rand()) ( if (i++ > 100) break; console.log(x); )
This function generates the sequence 01010101010101... and it cannot even be called pseudo-random. For a generator to be random, it must pass the next bit test. But we don’t have such a task. Nevertheless, even without any tests we can predict the next sequence, which means that such an algorithm is not suitable, but we are in the right direction.
What if we take some well-known but non-linear sequence, for example the number PI. And as the value for the module we will take not 2, but something else. You can even think about the changing value of the module. The sequence of digits in Pi is considered random. The generator can operate using Pi numbers starting from some unknown point. An example of such an algorithm, with a PI-based sequence and a variable module:
Const vector = [...Math.PI.toFixed(48).replace(".","")]; function* rand() ( for (let i=3; i<1000; i++) {
if (i >99) i = 2; for (let n=0; n
We got a generator of numbers from 0 to 9, but the distribution is very uneven and it will generate the same sequence every time.
We can take not the number Pi, but time in numerical representation and consider this number as a sequence of numbers, and in order to ensure that the sequence does not repeat each time, we will read it from the end. In total, our algorithm for our PRNG will look like this:
Function* rand() ( let newNumVector = () => [...(+new Date)+""].reverse(); let vector = newNumVector(); let i=2; while (true) ( if ( i++ > 99) i = 2; let n=-1; while (++n< vector.length) yield (vector[n] % i);
vector = newNumVector();
}
}
// TEST:
let i = 0;
for (let x of rand()) {
if (i++ >100) break; console.log(x)
This already looks like a pseudo-random number generator. And the same Math.random() is a PRNG, we’ll talk about it a little later. Moreover, each time we get a different first number.
Actually on these simple examples you can understand how more work complex generators random numbers. And there's even ready-made algorithms. As an example, let’s look at one of them — this is the Linear Congruent PRNG (LCPRNG).
Linear congruent PRNG
Linear congruent PRNG (LCPRNG) is a common method for generating pseudorandom numbers. It is not cryptographically strong. This method consists of calculating the terms of a linear recurrent sequence modulo some natural number m, given by the formula. The resulting sequence depends on the choice of starting number — i.e. seed. At different meanings seed produces different sequences of random numbers. An example of implementing such an algorithm in JavaScript:Const a = 45; const c = 21; const m = 67; var seed = 2; const rand = () => seed = (a * seed + c) % m; for(let i=0; i<30; i++)
console.log(rand())
Many programming languages use LCPRNG (but not exactly this algorithm(!)).
As mentioned above, such a sequence can be predicted. So why do we need PRNG? If we talk about security, then PRNG is a problem. If we talk about other tasks, then these properties can be a plus. For example, for various special effects and graphics animations, you may need to frequently call random. And this is where the distribution of meanings and performance are important! Secure algorithms cannot boast of speed.
Another property is reproducibility. Some implementations allow you to specify a seed, and this is very useful if the sequence must be repeated. Reproduction is needed in tests, for example. And there are many other things that do not require a secure RNG.
How Math.random() works
The Math.random() method returns a pseudo-random floating point number from the range = crypto.getRandomValues(new Uint8Array(1)); console.log(rvalue)
But, unlike the Math.random() PRNG, this method is very resource-intensive. The fact is that this generator uses system calls in the OS to gain access to entropy sources (mac address, CPU, temperature, etc...).Note that to create RRSP, three types of generators are used: tabular, physical generators and PSP generators.
An example of a table generator is a table of 106 random digits published in 1955 by the Rand Corporation.
Physical generators have become widespread after the creation of microprocessors, which are low cost and provide sufficient performance. In Fig. Figure 4.1 presents a physical random data generator ORB, implemented by APA Consulting on a microcontroller of the PIC12C67X family (8-pin SOIC package size 5.3 x 8.1 mm).
Rice. 4.1. ORB Random Number Generator
The operation of this generator is based on the principle of measuring the voltage on a capacitor, which is charged and discharged in accordance with a certain bit stream.
The first two types of generators, along with good statistical properties, have a number of disadvantages, the main of which include the complexity of technical implementation, low performance and high cost.
For these reasons, PSP generators have become widespread in the development of software and hardware for cryptographic information protection.
The simplest software pseudorandom number sensor is linear congruent generator(LKG), which is described by a recurrent equation of the form , where
– random initial value,
– multiplier,
– increment,
– module.
The period of the output sequence of such a generator does not exceed
, the maximum value is achieved with the correct choice of parameters
, namely when:
– numbers
And
are relatively prime: gcd
;
–
multiple of any prime
, dividing
;
–
divisible by 4 if
multiple of 4.
Below is a list of constants for LCG that ensure the maximum period of the sequence and, equally important, the corresponding sequences pass statistical tests.
To implement LCG on personal computers, taking into account their bit grid, the module is often used
. In this case, the highest quality statistical properties of the PSP are achieved for the constant
.
Compared to other types of PSP generators, this type provides high performance due to the small number of operations to create one pseudo-random bit.
The disadvantage of LCGs in terms of their use for creating stream ciphers is the predictability of the output sequences.
Effective attacks on LKG were proposed by Joan Boyar.
She owns methods of attacks on quadratic and cubic generators: and.
Other researchers have generalized Boyar's work to the case of a general polynomial congruent generator. Stern and Boyar showed how to crack the LKG, even if the entire sequence is not known.
Wishmann and Hill, and later Pierre L'Ecuger, studied combinations of LCH. The complications are not cryptographically stronger, but have longer periods and behave better under some randomness criteria.
Linear Feedback Shift Registers(Linear Feedback Shift Registers - LFSR) include the shift register itself and the circuit for calculating the feedback function (tap sequence) - see Fig. 4.2.
Rice. 4.2 Linear Feedback Shift Register (LFSR)
In the diagram, the contents of the register - a sequence of bits - are shifted one bit to the right with the arrival of the clock pulse. The least significant bit is considered the output of the LFSR in a given operating cycle. The value of the most significant digit is the result of adding modulo 2 (XOR function) the digits (reference points) of the feedback. The generated sequence is called a linear recurrent sequence.
In theory,
-bit LFSR can generate a pseudo-random sequence with a period
bit. Such LFSRs are called maximum period registers.
To do this, the shift register must visit all
non-zero internal states.
The same recurrence can be generated by registers of different lengths. Suppose that among similar registers ours
-bit LFSR has a minimum length.
Register feedback functions can be mapped to a polynomial
degree no higher
with coefficients from the field of residues modulo two, consisting of monomials of the form
, Where
- set of numbers of feedback pickup points.
Polynomial
called minimal polynomial corresponding recurrent sequence.
For every finite (or periodic) sequence
one can specify an LFSR which, given some initial padding, generates this sequence.
Among all such registers, there is a register of minimum length
.
Magnitude
called linear complexity sequences
.
Recall that a polynomial is called irreducible if it cannot be expressed as the product of two polynomials of lesser degree that are different constants.
Primitive polynomial degrees
over the field of residues modulo two is an irreducible polynomial that divides
, but does not divide
for any
:
.
Theorem. In order for the sequence generated by LFSR to have a maximum period, it is necessary and sufficient that its minimum polynomial be a primitive polynomial modulo 2.
A list of practically applicable primitive polynomials is given in. For example, a primitive polynomial is .
Set of indicators
means that by taking a shift register of length 32 and generating a feedback bit by adding the 7th, 5th, 3rd, 2nd and 1st bits modulo 2, we get a maximum length LFSR (with
states).
Here is a program in C for the sequence generated by this LFSR:
Static unsigned long ShiftRegister=1; //any non-zero initial padding
ShiftRegister = ((((ShiftRegister>>31)
^(ShiftRegister>>6)
^(ShiftRegister>>4)
^(ShiftRegister>>2)
^(ShiftRegister>>1)
^(ShiftRegister))
| ShiftRegister>>1);
return ShiftRegister & 0x00000001;
Note that if
is a primitive polynomial, then
– also primitive. Moreover, if the polynomial
primitive, then
– primitive. If a polynomial
primitive, then primitive, etc.
Primitive trinomials are especially convenient because Only 2 bits of the shift register are added, but they are also more vulnerable to attacks.
Generally speaking, LFSRs are convenient for technical implementation, but from the point of view of cryptographic strength, they have weaknesses.
Consecutive linear recurrent bits are linearly dependent, making them useless for encryption.
Enough
successive recurrent bits to determine the set of feedback pick-up point numbers.
Large random numbers generated from successive LFSR bits are highly correlated. However, LFSRs are often used as elements of more complex algorithms for generating an encryption key sequence.
There are also a number of PSP generators (including Galois generators), which for a number of reasons have not found wide application in cryptographic systems. The most effective solutions were obtained based on composite generators.
The idea of constructing a compound generator is based on the fact that a combination of two or more simple PSP generators, in the case the right choice combining function (including modulo addition,
etc.), provides a generator with improved randomness properties, and, as a result, with increased cryptographic strength.
In the case of creating a cryptographically strong PSP generator, the issue of creating stream ciphers is easily solved. The output of such PSP is indistinguishable (or rather, should be indistinguishable) from RRSP. Two generators can always be started synchronously from a single initial state vector, which is much shorter than the transmitted message, which distinguishes this scheme from the Vernam cipher.
There are 4 known approaches to designing appropriate generators:
1) system-theoretical approach;
2) complexity-theoretical approach;
3) information-theoretical approach;
4) randomized approach.
These approaches differ in their assumptions about the cryptanalyst's capabilities, the definition of cryptographic success, and the concept of reliability.
In the system-theoretic approach, the cryptographer creates a key stream generator that has verifiable properties, including the period length of the output sequence, the statistical distribution of the bit stream, the linear complexity of the transformation, etc.
Taking into account known cryptanalysis techniques, the cryptographer optimizes the generator against these attacks.
Based on this approach, Rüppel formulated the following set of criteria for stream ciphers.
1.Long period of output sequence, no repetitions.
2. High linear complexity as a characteristic of our generator through a minimum length LFSR register that can generate the same output.
3. Indistinguishability from RRSP according to statistical criteria.
4. Shuffle: Any bit of the key stream must be a complex transformation of all or most of the bits of the initial state (key).
5. Dissipation: Redundancy in all substructures of the generator algorithm must be dissipated.
6. Criteria for nonlinearity of transformations: in accordance with some metric, the distance to linear functions must be large enough; an avalanche-like propagation of errors is required if one bit of the argument changes, etc.
Practice confirms the advisability of applying the specified criteria not only for the analysis and evaluation of stream ciphers created within the framework of a system-theoretical approach, but also for any stream and block ciphers.
The main problem with such cryptosystems is that it is difficult for them to prove any facts about their cryptographic strength, since for all these criteria their necessity or sufficiency has not been proven.
A stream cipher can satisfy all of these principles and still be weak because resistance to a given set of cryptanalytic attacks does not guarantee anything.
An example of a successful construction of a composite generator from the point of view of increasing linear complexity is the Goleman cascade (Fig. 4.3). The Goleman stage includes several LFSR shift registers. The first register moves uniformly in increments of 1. The shift of each subsequent register is controlled by the previous one so that the state of the subsequent register changes in a clock cycle
happens if on beat
1 is removed from the previous register. Otherwise, the state of the subsequent register does not change.
If all LFSRs are lengths
, then the linear complexity of the system with
registers equal
.
Rice. 4.3. Gollman cascade
A typical example of combining shift registers is the Alternating Stop-and-Go Generator circuit.
This generator has a long period and high linear complexity.
The start-stop generator (Figure 4.4) uses three linear shift registers of varying lengths. LFSR-2 changes state if the output of LFSR-1 is 1; LFSR-3 changes state otherwise. The result of the generator is the modulo addition of 2 outputs of registers LFSR-2, LFSR-3.
Rice. 4.4. Alternating start-stop generator
Applying complexity-theoretical approach, the cryptographer tries to prove the strength of the generator using complexity theory.
The basis for solutions in this approach are generators based on the concept Obottom-directionaloh functions.
One-way function value
easy to calculate, but for almost all values
it is almost impossible to determine the appropriate value
. Otherwise, if
– computational complexity of obtaining
, A
– computational complexity of finding
, That
.
There is general agreement that one candidate for a one-way function could be an exponential function in some finite field
, Where
.
It is easy to see that exponentiation can be accelerated due to the properties of associativity. For example,
, which allows you to calculate the degree in four steps instead of eight.
The inverse operation - the problem of finding the exponent from the value of the power function (discrete logarithm), in the general case, cannot yet be solved better than using optimized enumeration methods.
With a correspondingly selected characteristic
and degree of field expansion
With the modern development of computer technology, this problem is computationally insoluble.
An example of a generator based on a one-way function is a generator based on RSA algorithm with parameters
kind. Here
, Where
– secret large, unequal prime numbers,
– exponent of power function, gcd
,
.
The result of one clock cycle of the generator - the least significant bit
. The durability of this generator is not lower than that of RSA. If
large enough, the generator provides practical durability.
BBS is another example of a complexity-based generator (proposed by Blum, Blum and Shub).
This is one of the simple and effective algorithms. The mathematical theory of this generator is quadratic residues modulo composite
.
Generator parameters: secret large, unequal prime numbers,
, such that,
; number
;
– random secret modulo deduction
.
The first step is to calculate the initial state
.
In the main cycle, the PSP element with the number
equal, i.e.
The th pseudorandom number is the least significant bit of the number
.
Note that the algorithm can be used to encrypt random access files if, except
, enter secret parameter
, because then
can be calculated via
, because, where
.
This property allows you to use the BBS generator to work with random-access files.
Number
can be distributed freely so that each network subscriber can independently generate the necessary bits. Moreover, if the cryptanalyst cannot factorize the number
, it will not be able to predict the next bit, even in a probabilistic sense, such as "there is a 51% chance that the next bit is 1".
Note that such generators are very slow; special processors are required for their practical implementation.
The next two approaches information-theoretical And randomized, have not found wide practical application.
From point of view information-theoretical the most the best remedy in the fight against a cryptanalyst who has endless computing resources and time, is a one-time tape or one-time pad.
When randomized approach, the goal is to increase the number of bits that the cryptanalyst needs to work with (without increasing the key). This can be achieved by using large random public strings.
The key will indicate which parts (or bits) of these strings need to be used for encryption and decryption. Then the cryptanalyst will have to use the method of total search of options (brute force) on random strings.
The strength of this method can be expressed in terms of the average number of bits that a cryptanalyst would have to examine before the odds of determining the key become better than simple guessing.
Ueli Maurer described such a scheme. The probability of breaking such a cryptosystem depends on the amount of memory available to the cryptanalyst (but does not depend on his computing resources).
For this scheme to take on a practical form, about 100 bit sequences are required.
bits each. Digitizing the lunar surface is one way to obtain such a number of bits.
In conclusion, we note that to build a PSP generator it is necessary to obtain a few random bits. The easiest way: use the smallest significant bit computer timer.
Using this method, you cannot receive many bits, because Each call to the bit generation procedure can take an even number of timer steps, which will certainly affect the properties of the sequence.
The best way to get a random number is to appeal to the natural randomness of the real world - noise from transients in semiconductor diodes, thermal noise from high-voltage resistors, radioactive decay, etc.
In principle, there is an element of randomness in computers:
– time of day;
– processor load;
- Arrival time network packets and so on.
The problem is not to find the sources of randomness, but to maintain randomness in measurements.
For example, this can be done like this: let’s find an event that happens regularly, but randomly (the noise exceeds a certain threshold).
Let's measure time
between the first event and the second, then time
between the second event and the third.
If
, then we set the output of the generator equal to 1; If
, then the output is 0. If necessary, we will continue the process further.
A significant problem with random data generation systems is the presence of deviations and correlations in the generated sequence. The processes themselves may be random, but problems can arise during the measurement process. How to deal with this?
Let the probability of zero occurrence be shifted by
, i.e. can be written as
.
Addition by
two equally distributed independent bits will give:. When adding four bits we get:
. The process converges to an equally probable distribution of bits.
Another approach. Let the distribution of ones and zeros in the sequence be the quantities
And
respectively.
Let's transform successive pairs of bits:
– if these are identical bits, then discard them and consider the next pair;
– if the bits are different, then we take the first bit as the output value.
This method allows us to solve the bias problem while maintaining the randomness properties of the source (with some loss in data volume).
A potential problem with both methods is that when there is correlation between adjacent bits, these methods increase the offset. One way to avoid this is to use different sources of random numbers and add the bits of sequences signed under each other vertically.
The fact that a random number generator has a bias, generally speaking, does not always mean that it is unsuitable.
For example, let's assume that a zero-biased generator is used to generate a 112-bit key for the Triple DES algorithm (see below):
,
(entropy
0.99277 per key bit compared to 1 for an ideal generator).
In this case, the attacker can optimize the procedure of total search of keys by searching for the key starting from the most probable value
and ending with the least likely
. Due to the presence of bias, we can expect to find the key in an average of
attempts. If there were no displacement, then it would be necessary
attempts.
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:
The sequence of 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. Thus, the function for generating pseudorandom numbers is:
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.
pseudorandom number generation algorithm called BBS algorithm(from the authors' surnames - L. Blum, M. Blum, M. Shub) or generator with quadratic remainder. For cryptography purposes, this method was proposed in 1986.It is as follows. First, two large primes 1 are selected A positive integer greater than one is called simple, if it is not divisible by any other number except itself and one. For more information about prime numbers, see Fundamentals of Number Theory Used in Public Key Cryptography. numbers p and q. Numbers p and q must be both comparable from 3 modulo 4, that is, when p and q are divided by 4, the same remainder 3 should be obtained. Next, the number M = p* q, called the Bloom integer, is calculated. Then another random integer x is chosen that is coprime (that is, has no common divisors other than one) with M. We calculate x0= x 2 mod M. x 0 is called the starting number of the generator.
At each nth step of the generator operation, x n+1 = x n 2 mod M is calculated. The result of the nth step is one (usually the least significant) bit of the number x n+1. Sometimes the result is a parity bit, that is, the number of ones in the binary representation of the element. If the number of ones in the number record is even, the parity bit is taken equal to 0, if the number is odd, the parity bit is taken equal to 1.
For example, let p = 11, q = 19 (we make sure that 11 mod 4 = 3, 19 mod 4 = 3). Then M = p* q = 11*19=209 . Let's choose x that is coprime to M: let x = 3. Let's calculate the starting number of the generator x 0:
x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.
Let's calculate the first ten numbers x i using the BBS algorithm. As random bits we will take the least significant bit in the binary notation of the number x i:
x 1 =9 2 mod 209= 81 mod 209= 81 least significant bit: 1 x 2 =81 2 mod 209= 6561 mod 209= 82 least significant bit: 0 x 3 =82 2 mod 209= 6724 mod 209= 36 least significant bit: 0 x 4 =36 2 mod 209= 1296 mod 209= 42 least significant bit: 0 x 5 =42 2 mod 209= 1764 mod 209= 92 least significant bit: 0 x 6 =92 2 mod 209= 8464 mod 209= 104 least significant bit: 0 x 7 =104 2 mod 209= 10816 mod 209= 157 least significant bit: 1 x 8 =157 2 mod 209= 24649 mod 209= 196 least significant bit: 0 x 9 =196 2 mod 209= 38416 mod 209= 169 least significant bit: 1 x 10 =169 2 mod 209= 28561 mod 209= 137 least significant bit: 1 The most interesting property of this method for practical purposes is that to obtain the nth number of the sequence, you do not need to calculate all the previous n numbers x i. It turns out x n can be immediately obtained using the formula
For example, let's calculate x 10 directly from x 0:
As a result, we actually got the same value as with sequential calculation, – 137 . The calculations seem quite complex, but in fact they are easy to formulate into a small procedure or program and use when necessary.
The ability to “directly” obtain xn allows you to use the BBS algorithm for stream encryption, for example, for random access files or fragments of files with database records.
The security of the BBS algorithm is based on the complexity of the decomposition large number M into factors. It is argued that if M is large enough, it does not even need to be kept secret; Until M is factorized, no one can predict the output of the PNG generator. This is due to the fact that the task of factoring numbers of the form n = pq (p and q are prime numbers) is computationally very difficult if we only know n, and p and q are large numbers consisting of several tens or hundreds of bits ( this is the so-called factorization problem).
In addition, it can be proven that an attacker, knowing a certain sequence generated by the BBS generator, will not be able to determine either the previous bits or the next ones. BBS Generator unpredictable in the left direction And in the right direction. This property is very useful for cryptography purposes and it is also associated with the features of factoring the number M.
The most significant drawback algorithm is that it is not fast enough, which does not allow it to be used in many areas, for example, in real-time calculations, and also, unfortunately, in stream encryption.
But this algorithm produces a really good sequence of pseudo-random numbers with a large period (with an appropriate choice of initial parameters), which allows it to be used for cryptographic purposes when generating encryption keys.
Key terms
Stream cipher– stream cipher.
BBS algorithm– one of the methods for generating pseudorandom numbers. The name of the algorithm comes from the names of the authors - L. Blum, M. Blum, M. Shub. The algorithm can be used in cryptography. To calculate the next number x n+1 using the BBS algorithm, use the formula x n+1 = x n 2 mod M, where M = pq is the product of two large primes p and q.
Pseudo-random number generator (PRNG)- some algorithm or device that creates a sequence of bits that looks like random.
Linear congruent generator pseudorandom numbers - one of the simplest PRNGs, which to calculate the next number k i uses the formula k i =(a*k i-1 +b)mod c, where a, b, c are some constants, a k i-1 is the previous one pseudorandom number.
Fibonacci method with lags– one of the methods for generating pseudorandom numbers. Can be used in cryptography.
Stream cipher– a cipher that encrypts the input message one bit (or byte) per operation. A stream encryption algorithm eliminates the need to split a message into an integer number of blocks. Stream ciphers are used to encrypt data in real time.
Brief summary
A stream cipher is a cipher that encrypts an input message one bit (or byte) per operation. A stream encryption algorithm eliminates the need to split a message into an integer number of blocks. Thus, if a stream of characters is being transmitted, each character can be encrypted and transmitted at once. Stream ciphers are used to encrypt data in real time.
