The linear complexity of a periodic sequence ( s) is just the "length" of the shortest linear recurrence which generates ( s), i.e., the degree of the corresponding characteristic polynomial. We employ the notation s for a finite sequence of bits and ( s) for the periodic sequence obtained by appending copies of s. Linear complexity is useful in the search for cryptographically strong pseudo-random sequences.ĭefinition 3.1 The linear complexity of a sequence is the minimum number of stages of an LFSR that generates the sequence. (However, certain nonlinear combinations of m-sequences do have desirable cryptographic properties see. It follows that intuitive concepts of randomness do not insureĬryptographic strength. These properties make m-sequences useful in many applications where pseudo-random bits are required, but in the next section we show that m-sequences are cryptographically weak. Rueppel has shown that Colomb's randomness postulates almost exclusively describe m-sequences. Golomb proposes three "randomness postulates" and suggests that sequences which satisfy these postulates are statistically random. It is well-known that the characteristic polynomial of an m-sequence is necessarily primitive. The maximum possible period for an n-stage LFSR is 2 n - 1 and any sequence which attains this upper bound is referred to as an m-sequence (or pseudo-noise sequence). The output from any LFSR is eventually periodic in the sense that there exists a k such that The characteristic polynomial of the sequence (2.1) is (0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1) (2.1)Īnd any other choice of initial values-with the obvious exception of the zero vector-produces a cyclic shift of (2.1). It is easy to construct a 4-stage LFSR which realizes the linear recurrenceĪs initial values, this recurrence generates the periodic sequence The element inserted into stage n - 1 is calculated from the linear feedback function. An LFSR is controlled by a clock and at each clock pulse the element in stage i is shifted into stage i - 1, with the element in stage 0 taken as the output. Linear feedback shift registers (LFSR's) satisfy these requirements.Īn LFSR consists of n storage units, or stages, and a linear feedback function. The pseudo-random sequence generator employed in a stream cipher must be capable of rapidly producing bits and it must be analyzable. Below we use the term cryptographically strong as a synonym for unpredictable. Our approach follows this second line of attack. Authors such as Shamir and Blum and Micali insist that determining the next element of the sequence based on the previous elements be provably as difficult as inverting a one-way function, while Groth, Key, and Rueppel emphasize linear complexity as the primary measure of unpredictability. There are at least two approaches to this concept of unpredictability. For a stream cipher to be secure against this type of attack, the pseudo-random sequence must be unpredictable, i.e., it must be computationally infeasible to recover more of the sequence from a short, captured segment. It is assumed that a persistent eavesdropper will obtain some segment of the text and thereby obtain a segment of the pseudo-random sequence. Stream ciphers have received considerable attention in the literature-an excellent source is the book by Rueppel. By simply reversing the process, the receiving party recovers the original message. The resulting bit string is presumably difficult to decipher and hence may be transmitted over insecure lines. In a stream cipher, a binary message is encrypted by adding (element-wise modulo 2) a pseudo-random sequence of bits. †Supported in part by NASA grant NAG2-89, NSF Grant DMS 8905334 and NSA Grant MDA904-90-H-4009 *Supported in part by NSA Grant MDA904-90-H-4009Ĭurrent Address: Mathematical Sciences, Worcester Polytechnic Institute, Worcester, MA 01609 Keywords: linear complexity, k-error linear complexity, algorithm This new algorithm generalizes an algorithm due to Games and Chan. A generalized linear complexity which has application to the security of stream ciphers is proposed and an efficient algorithm is given for the case where the sequence is binary with period 2 n. It is shown that linear complexity is useful in determining such sequences. An Algorithm for the k-Error Linear Complexity of Binary Sequences with Period 2 nĬertain applications require pseudo-random sequences which are unpredictable in the sense that recovering more of the sequence from a short segment must be computationally infeasible.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |