A cryptographically secure pseudorandom number generator

We investigate a cryptographically secure pseudorandom number generator based on a Linear Feedback Shift Register (LFSR). The statistical properties of the generator are examined, as well as its resistance to cryptographic analysis. LFSRs are known to produce bit streams that have excellent statistical properties. However, they can be predicted by monitoring their outputs briefly. Many approaches have been tried to modify an LFSR output to preserve its statistical properties but make it unpredictable. These techniques work in a stream-wise manner; for each bit output from the LFSR, one bit is output from the composite generator. All of these approaches have fallen to cryptanalysis. The technique used in this project processes the output of an LFSR with a hash function, converting blocks of M bits into smaller blocks of N bits. Since the hash function maps many input blocks into any given output block, there is no way of determining the LFSR state by knowing the value of an output block. The resulting generator was analyzed using standard statistical tests for randomness, such as chi-square tests on the distribution of blocks of bits, autocovariance of the output bit stream, and the Marsaglia Die-Hard Battery of statistical tests. The Lempel-Ziv data-compression algorithm was used on the output stream to try to discover any structure. In addition, a cryptographic analysis technique, the Berlekamp-Massey algorithm, was used to determine the difficulty of predicting the generator\u27s output