Slovak University of Technology, Bratislava
Faculty of Electrical Engineering and Information Technology
Degree Course: INFORMATICS
Author: Bc. Pavol Repčík
Diploma thesis: Cryptanalysis of the majority generator based on the LFSR and FCSR
Supervisor: Ing. Milan Vojvoda
december 2001

The aim of this work was to decide whether a new type of the pseudo-random number generator can be used for stream ciphers. The generator is based on majority function, which combines three registers. We used two types of the registers: the linear feedback shift register (LFSR) and the feedback with carry shift register (FCSR).

We applied the statistical tests on seven generators created with combining three registers of each types to triplets. The set of tests consist of algorithms based on NIST specification. Test shows several flaws on statistical parameters of tested sequences. We study parameters of 2-adic span of sequence produced with this generator type. Results confirmed assumption, that 2-adic span rapidly grows when combination function is used.

The analysis of conventional types of attacks shows that divide-and-conquer and correlation attack can be real threat for this type of generator. Fast correlation attacks can be applied on linear feedback shift registers used in the generator.

We can qualify this type of random generator as unsuitable for use in real applications.