Slovak University of Technology, Bratislava

Faculty of Electrical Engineering and Information Technology

Degree Course: INFORMATICS

Author: Bc. Peter Vadovič

Diploma thesis: Cryptanalysis of parity generator based on LFSR a FCSR

Supervisor: Ing. Milan Vojvoda

December 2001

The main purpose of this project is to implement and analyse a keystream parity generator based on LFSR and FCSR.

The most significant theoretical facts dealing with LFSR a FCSR as well as sequences they produce are described. There is implemented parity generator based on LFSR and FCSRs, Berlekamp-Massey algorithm for linear complexity analysis, 2RA algoritm for 2-adic complexity analysis and a package of statistical tests published in NIST Special Publication 800-22 in this project.

A conjecture that the linear complexity of the FCSR is approximately half of its connection integer emerged while applying Berlekamp-Massey algorithm on sequences produced by FCSRs with connection integer less than 5000. The linear complexity of sequence produced by this generator is about the sum of linear complexities of its registers. Experiments based on 2RA algorithm shown results leading to hypothesis about 2-adic complexities of binary sequences produced by LFSRs and parity generator that are worthy of remark.

Results of statistical tests did not detect any deviation from randomness. Thus the further study of this generator is reasonable.