Finite Subsequences of Shift Register Sequences
CHRISTINE BOURNE, Fred C. Piper · IMA Journal of Applied Mathematics · 1985
In a stream cipher a cryptogram is produced from a binary data stream by modulo-2-adding it to a keystream sequence. The security of the system relies on the inability of an interceptor to determine this keystream sequence. One obvious requirement for such a system is that there should be sufficiently many possibilities for the keystream sequence that the interceptor cannot possibly try them all. In this paper we consider the likelihood of an interceptor being able to decipher the cryptogram correctly even though he may be trying the wrong keystream sequence. This possibility arises because the length of any particular message is likely to be considerably shorter than the period of the keystream sequence, and thus only a comparatively small section of the keystream sequence is used. Hence, if the interceptor tries a sequence which intersects (i.e. agrees) with the keystream sequence in the appropriate positions, he will deduce the message correctly. A number of the standard methods for generating keystream sequences use shift registers as ‘building blocks’. So we look in considerable detail at the number of intersections (of various lengths) for sequences generated by two different shift registers. We also show that if a keystream sequence has linear equivalence n, then the local linear equivalence of any subsequence of length at least 2n is n. This means that if the message has length at least 2n and the keystream sequence has linear equivalence n, then there is no other sequence of linear equivalence less than n+1 which can be used to decipher correctly.