## Feedback with carry shift register ciphers

In 1991 G. Marsaglia and A. Zaman [MZ] introduced a new class of pseudo-random number sequences. The shift register analogs of these have been investigated by A. Klapper and M. Goresky in several papers (see [GK1], for example).

The general idea is very simple. Let be any integer and let be positive integers with no factors in common with or each other. If you take any rational number then the coefficients in the -adic expansion

are eventually periodic. Like decimal expansions and unlike power series expansions, the coefficients are NOT in general unique (for example, in the case we have ). There is an analog of the Berlekamp-Massey decryption method [GK2]. What is worst (depending on your point of view) is that if you add two such sequences then the sequence (defined using the carry operation) can be decrypted using at most terms, where is the -adic span of . In particular, the stream cipher, when viewed from the perspective of FCSR's is even less secure than previously thought.

Example 1.7.26   Let , so

whose coefficients are .

The coefficients in the -adic expansion of are very easy to determine from the following algorithm:

• Find the least such that is divisible by (the is the order of (mod )) and let .
• Write as a polynomial in powers of with coefficients in .
• Using the geometric series expansion compute

as a power series in (this converges in the -adic norm and represents the -adic expansion of ).

Theorem 1.7.27   When is a power of a prime and when is primitive mod (i.e., generates the cyclic group ) then the coefficients of the -adic expansion of satisfy analogs of Golomb's randomness conditions.

For a proof, see [GK2].

david joyner 2008-04-20