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 $p$ be any integer and let $a,b$ be positive integers with no factors in common with $p$ or each other. If you take any rational number $a/b$ then the coefficients ${\bf c} ={\bf c}(a,b)$ in the $p$-adic expansion

$${a\over b}=c_{-N}p^{-N}+...+{c_{-1}\over p} +c_0+c_1p+...\ ,$$

are eventually periodic. Like decimal expansions and unlike power series expansions, the coefficients are NOT in general unique (for example, in the case $p=10$ we have $1=.999999...$). 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 ${\bf c}+{\bf c'}$ (defined using the carry operation) can be decrypted using at most $S+S'$ terms, where $S=S({\bf c})= \log_2(\max\{\vert a\vert _2,\vert b\vert _2\})$ is the $2$-adic span of ${\bf c} ={\bf c}(a,b)$. 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 $a=10,b=3$, so

$${10\over 3}=2+2^2+2^3+2^5+2^7+2^9+2^{11}+...$$

whose coefficients are $0, 1, 1, 1, 0, 1, 0, 1, 0, 1, ...$.

The coefficients in the $2$-adic expansion of $a/b$ are very easy to determine from the following algorithm:

• Find the least $k$ such that $2^k-1$ is divisible by $b$ (the is the order of $b$ (mod $2$)) and let $2^k-1=bd$.
• Write $ad$ as a polynomial in powers of $2$ with coefficients in $\{0,1\}$.
• Using the geometric series expansion ${1\over 1-x}=1+x+x^2+...$ compute
  $${a\over b}={ad\over bd}={ad\over 2^k-1}$$
  as a power series in $2$ (this converges in the $2$-adic norm and represents the $2$-adic expansion of $a/b$).

Theorem 1.7.27   When $b$ is a power of a prime and when $2$ is primitive mod $b$ (i.e., $2$ generates the cyclic group $(\mathbb{Z}/b\mathbb{Z})^\times$) then the coefficients of the $2$-adic expansion of $1/b$ satisfy analogs of Golomb's randomness conditions.

For a proof, see [GK2].