Analysis On Feedback With Carry Shift Register Sequences

Feedback with carry shift registers(FCSR) are a type of nonlinear sequence generators suitable for stream cipher design. Compared with traditional linear feedback shift registers, FCSRs implement the arithmetic of 2-adic addition by introducing several carry registers, and so their outputting sequences have very good nonlinear properties. Since A. Klapper and M. Goresky proposed FCSRs, FCSR sequences, especially maximal length FCSR sequences(l-sequences), and 2-adic complexity have gained much attention.In terms of cryptographic applications, l-sequences are the most important FCSR sequences. As for l-sequences, this thesis mainly studies such problems as combined l-sequences, autocorrelations, crosscorrelations, distinctness of decimations, linear relations and carry sequences.1. Although it is widely accepted that bitwise exclusive ors of l-sequences have good cryptographic properties, few of their theoretical results have been published yet and even their periods are not determined. It is proved that the period of a termwise exclusive or of several l-sequences generated by FCSRs with distinct nonprime connection integers either attains the maximum or half of it.2. For an l-sequence based on a prime number p > 11, it is proved that its nontrivial maximal autocorrelation is the largest even number less than p/3. Moreover, the sufficient and necessary conditions for autocorrelations of l-sequences based on primes attaining such nontrivial maximal value are also given.3. It is shown that if the connection integers of two l-sequences have a common prime factor, then every crosscorrelation between them can be converted into some autocorrelation of the sequence with smaller period. As a result of it, previous results proved for autocorrelations can be used to estimate the expectation and variance of such kind of crosscorrelations.4. Since the distinctness conjecture of decimations of l-sequences was proposed in 1997, no complete proof has been reported in the literature so far. A sufficient condition for l-sequences based on primes whose decimations are pairwise distinct is given. On the basis of convincing experimental data, the sufficient condition seems to ensure that more than 79% of l-sequences based on different primes satisfy the conjecture. In particular, a complete proof is provided for l-sequences based on primes of the form 2r + 1, where r is an odd prime number.5. Linear properties of l-sequences are identified based on the 2-adic expansion of their connection integers. It is shown that for an l-sequence with connection integer q (not necessary the least connection integer), if wt(q +1) is a small odd number, then a linear relation with large bias exists.6. When an FCSR outputs a sequence from its main register, its carry register also produces a sequence called carry sequence. Generally speaking, the period of a carry sequence is a factor of that of the FCSR outputting sequence. Let a be an l-sequence generated by an FCSR with connection integer pe. It is proved that if 2 p-1 -1 is not divisible by p2, then the period of the carry sequence corresponds to a attains the period of a. Furthermore, it is proved that the element distribution of carry sequences corresponds to l-sequences has very similar complementarity with l-sequences.2-Adic complexity measures the difficulty of outputting a binary sequence using an FCSR. Since FCSRs were proposed, 2-adic complexity becomes an important security measure for pseudorandom sequences like traditional linear complexity. This thesis studies 2-adic complexity of m-sequences and the expected value for 2-adic complexity of finite sequences.7. It is proved that for a binary m-sequence of order n, its 2-adic complexity attains the maximum, i.e., log2 ( 2 2 n-1-1), which implies that no FCSR with connection integer less than 2 2 n-1-1 can generate m-sequences of order n. Thus, m-sequences are the first class of sequences whose 2-adic complexities are completely determined through their linear complexities.8. To faciliate the study of 2-adic complexity of finite sequences, the concept of rational complexity is introduced and the expected value for rational complexity of finite sequences is estimated. Furthermore, based on the algebraic relation between rational complexity and 2-adic complexity, it is proved that the expected value for the 2-adic complexity of finite sequences of length n is upper bounded by 0.7716n.