Finite Subsequences of Shift Register Sequences

In a stream cipher a cryptogram is produced from a binary datastream by modulo-2-adding it to a keystream sequence. The securityof the system relies on the inability of an interceptor to determinethis keystream sequence. One obvious requirement for such asystem is that there should be sufficiently many possibilitiesfor the keystream sequence that the interceptor cannot possiblytry them all. In this paper we consider the likelihood of an interceptor beingable to decipher the cryptogram correctly even though he maybe trying the wrong keystream sequence. This possibility arisesbecause the length of any particular message is likely to beconsiderably shorter than the period of the keystream sequence,and thus only a comparatively small section of the keystreamsequence is used. Hence, if the interceptor tries a sequencewhich intersects (i.e. agrees) with the keystream sequence inthe appropriate positions, he will deduce the message correctly. A number of the standard methods for generating keystream sequencesuse shift registers as ‘building blocks’. So welook in considerable detail at the number of intersections (ofvarious lengths) for sequences generated by two different shiftregisters. We also show that if a keystream sequence has linearequivalence n, then the local linear equivalence of any subsequenceof length at least 2n is n. This means that if the message haslength at least 2n and the keystream sequence has linear equivalencen, then there is no other sequence of linear equivalence lessthan n+1 which can be used to decipher correctly.