NON-LINEAR PSEUDORANDOM BIT GENERATION BY COMBINING BLUM BLUM SHUB AND LINEAR FEEDBACK SHIFT REGISTER SEQUENCES

The purpose of this thesis is to analyze the cryptographic properties of a pseudorandom bit generator that combines Blum Blum Shub and linear feedback shift register sequences using a shrinking generator configuration. We sought to answer the questions: (1) What are the strengths and weaknesses of this type of combiner? (2) What constraints must be placed on the input parameters to ensure good cryptographic properties of the output sequence? We generated sequences using variations of this combiner. We then evaluated their cryptographic suitability with the National Institute of Standards and Technology (NIST) statistical test suite. We identified lower bounds on the input parameters to increase the probability that the combiner would perform well under the NIST test suite. Our scheme produced consistently excellent results under NIST testing but is computationally too slow for many practical uses as a stream cipher. Future work could focus on methods to increase the speed of the generator without a loss of excellent cryptographic properties.Major, United States ArmyApproved for public release. distribution is unlimite