Crypto-IT

Pseudorandom generators (PRG) are used to create random sequences of numbers in deterministic devices. All computer algorithms are strictly deterministic. PRGs allow encryption of many data blocks using data generated from secret keys which have only few bits.

Pseudorandom generator has to be unpredictable. There must not be any efficient algorithm that after receiving the previous output bits from PRG would be able to predict the next output bit with probability non-negligibly higher than 0.5.

Pseudorandom generators are used for creating pseudorandom functions and permutations, which are widely used in cryptography (for example, for implementation of block ciphers).

Nowadays, pseudorandom generators are implemented in most operating systems (for example /dev/random in Linux) and in many libraries for various programming languages. In general, their behaviour is similar.

First, the algorithm initializes the internal state of the generator based on some external information (for example, the current time or temperature). Then, all bytes of the state are mixed for the whole time when the generator works. The changes are based on various external and random input data - the frequency and the way of using the keyboard and mouse by the user, network traffic, hardware interrupts and other kinds of information from outside the deterministic environment where the algorithm works.

The pseudorandom generator algorithm continuously changes its internal state. The internal state is then used to generate output sequences of numbers, which should be as random as possible. All the modifications of the state are performed in a way that is supposed to provide the best possible protection against sequence analysis of the produced output data.

There are many standards that describe requirements, which should be fulfilled by pseudorandom generators. For example, the American National Institute of Standards and Technology is the author of several norms, like NIST SP 800-90.

There exist many different statistical tests that can be used to assess the quality of pseudorandom generators. They check if received sequences are random and unpredictable. Some statistical test examples include:

• a number of 1 bits in the produced sequence is similar to the number of 0 bits
• a number of 00 pairs in the produced sequence is more or less equal to one-fourth of all bits
• a length of the longest sequence of zeros or ones is similar to its mathematical estimation