10 - Pseudo-random sequence generators using structured noise

Summary

Stream ciphers use the output of a Pseudo-Random (PR) generator to mask the information stream. The security of these cipher systems ultimately depends on the structure of the PR generator. There are some minimum necessary criteria such as long period, flat statistical distribution and high linear complexity that the PR generator of a stream cipher system should satisfy to resist the basic cryptanalytic attacks on such systems. We propose a class of PR generators using the coset elements of a Reed-Muller code. The linear complexity of these generators is analysed and conditions that assure the highest possible linear complexity for them are specified. It is shown that the above mentioned criteria do not gurantee the security of a stream cipher system and the proposed PR generator, although it satisfies all of them, is not secure.

Introduction

Stream ciphers assimilate the one time pad, the only provably perfect secure system. However with the replacement of the random generator by a pseudo-random (PR) one, the perfect security of the system vanishes. It is easy to see that the assessment of the security of these systems is directly related to the properties of the PR generator. There are some necessary criteria which must be satisfied by the PR generator of a secure stream cipher. It is recognised that these generators should satisfy Golomb's criteria and have high linear complexity [1], [3].