On binary sequences generated by self-clock controlled LFSR
Michele Elia, Guglielmo Morgari, Maria Spicciola · PORTO Publications Open Repository TOrino (Politecnico di Torino) · 2010
The paper considers some peculiar proper- ties of binary sequences generated by self-clocked linear feedback shift registers of maximum length, and compares these properties with those of truly random sequences. In particular it examines their periods, their 0-1 distributions, and their linear complexity profiles. I. INTRODUCTION The cryptographic qualities of stream ciphers depend on the mechanisms used to generate long binary se- quences starting from short blocks of bits. These mech- anisms are usually described in terms of finite state machines. The literature concerning the generation of binary sequences is vast and wide-ranging with many profound and elegant results, see (1), (4), (6), (12) and the references therein, however, the quest for finite state machines that generate sequences demonstrated to sat- isfy all cryptographic requirements is far from being complete. In (13), Rueppel investigated the properties of self-decimated sequences produced by Linear Feed- back Shift Registers (LFSR), and drew the conclusion that these sequences may have some applications in cryptography and spread spectrum communication. A slightly different approach to studying self-decimation is described in (3), where emphasis is set on the decimation of the LFSR states, rather than of the se- quence itself; these two approaches are closely related, but not totally equivalent. This paper focus on state decimation, looking at its interplay with linear codes and their puncturing, and compares some peculiar properties of self-clocked binary generated sequences with those of truly random sequences. In particular it examines their period, their 0-1 distributions, and their linear complexity profile (LCP), which is defined as the length of the shortest LFSR that generates the sub- sequence up to length n for every n.