Feedback with Carry Shift Registers

In sequence design, a Feedback with Carry Shift Register (or FCSR) is the arithmetic or with carry analog of a Linear feedback shift register (LFSR). If $N>1$ is an integer, then an N-ary FCSR of length $r$ is a finite state device with a state $(a;z)=(a_{0},a_{1},\dots ,a_{r-1};z)$ consisting of a vector of elements $a_{i}$ in $\{0,1,\dots ,N-1\}=S$ and an integer $z$ .^[1]^[2]^[3]^[4] The state change operation is determined by a set of coefficients $q_{1},\dots ,q_{n}$ and is defined as follows: compute $s=q_{r}a_{0}+q_{r-1}a_{1}+\dots +q_{1}a_{r-1}+z$ . Express s as $s=a_{r}+Nz'$ with $a_r$ in $S$ . Then the new state is $(a_{1},a_{2},\dots ,a_{r};z')$ . By iterating the state change an FCSR generates an infinite, eventually period sequence of numbers in $S$ .

FCSRs have been used in the design of stream ciphers (such as the F-FCSR generator), in the cryptanalyis of the summation combiner stream cipher (the reason Goresky and Klapper invented them^[1]), and in generating pseudorandom numbers for quasi-Monte Carlo (under the name Multiply With Carry (MWC) generator - invented by Couture and L'Ecuyer,^[2]) generalizing work of Marsaglia and Zaman.^[5]

FCSRs are analyzed using number theory. Associated with the FCSR is a connection integer $q=q_{r}N^{r}+\dots +q_{1}N^{1}-1$ . Associated with the output sequence is the N-adic number $a=a_{0}+a_{1}N+a_{2}N^{2}+\dots$ The fundamental theorem of FCSRs says that there is an integer $u$ so that $a=u/q$ , a rational number. The output sequence is strictly periodic if and only if $u$ is between $-q$ and $0$ . It is possible to express u as a simple quadratic polynomial involving the initial state and the q_i.^[1]

There is also an exponential representation of FCSRs: if $g$ is the inverse of $N\mod q$ , and the output sequence is strictly periodic, then $a_{i}=(Ag_{i}\mod q)\mod N$ , where $A$ is an integer. It follows that the period is at most the order of N in the multiplicative group of units modulo q. This is maximized when q is prime and N is a primitive element modulo q. In this case, the period is $q-1$ . In this case the output sequence is called an l-sequence (for "long sequence").^[1]

l-sequences have many excellent statistical properties^[1]^[3] that make them candidates for use in applications,^[6] including near uniform distribution of sub-blocks, ideal arithmetic autocorrelations, and the arithmetic shift and add property. They are the with-carry analog of m-sequences or maximum length sequences.

There are efficient algorithms for FCSR synthesis. This is the problem: given a prefix of a sequence, construct a minimal length FCSR that outputs the sequence. This can be solved with a variant of Mahler^[7] and De Weger's^[8] lattice based analysis of N-adic numbers when $N=2$ ;^[1] by a variant of the Euclidean algorithm when N is prime; and in general by Xu's adaptation of the Berlekamp-Massey algorithm.^[9] If L is the size of the smallest FCSR that outputs the sequence (called the N-adic complexity of the sequence), then all these algorithms require a prefix of length about $2L$ to be successful and have quadratic time complexity. It follows that, as with LFSRs and linear complexity, any stream cipher whose N-adic complexity is low should not be used for cryptography.

FCSRs and LFSRs are special cases of a very general algebraic construction of sequence generators called Algebraic Feedback Shift Registers (AFSRs) in which the integers are replaced by an arbitrary ring R and N is replaced by an arbitrary non-unit in R.^[10] A general reference on the subject of LFSRs, FCSRs, and AFSRs is the book.^[4]

References

1 2 3 4 5 6 A. Klapper and M. Goresky, Feedback Shift Registers, 2-Adic Span, and Combiners With Memory, in Journal of Cryptology vol. 10, pp. 111-147, 1997,
1 2 R. Couture and P. L’Ecuyer, On the lattice structure of certain linear congruential sequences related to AWC/SWB generators, Math. Comp. vol. 62, pp. 799–808, 1994, ,
1 2 M. Goresky and A. Klapper, Efficient Multiply-with-Carry Random Number Generators with Optimal Distribution Properties, ACM Transactions on Modeling and Computer Simulation, vol 13, pp 310-321, 2003,
1 2 M. Goresky and A. Klapper, Algebraic Shift Register Sequences, Cambridge University Press, 2012 ISBN 9781107014992
↑ G. Marsaglia and A. Zaman, A new class of random number generators, Annals of Applied Probability, vol 1, pp. 462–480, 1991
↑ B. Schneier, Applied Cryptography. John Wiley & Sons, New York, 1996
↑ K. Mahler, On a geometrical representation of p–adic numbers, Ann. of Math., vol. 41, pp. 8–56, 1940
↑ B. M. M. de Weger, Approximation lattices of p–adic numbers, J. Num. Th., vol 24, pp. 70–88, 1986
↑ A. Klapper and J. Xu, Register Synthesis for Algebraic Feedback Shift Registers Based on Non-Primes, Designs, Codes, and Cryptography vo. 31, pp. 227-250", 2004
↑ A. Klapper and J. Xu, Algebraic Feedback Shift Registers, Theoretical Computer Science, vol. 226, pp. 61-93, 1999,

Stream ciphers

Widely used ciphers

eSTREAM Portfolio

Software	HC-256 Rabbit Salsa20 SOSEMANUK

Hardware	Grain MICKEY Trivium

Other ciphers

Theory

Attacks

Cryptography

History of cryptography Cryptanalysis Outline of cryptography

Symmetric-key algorithm Block cipher Stream cipher Public-key cryptography Cryptographic hash function Message authentication code Random numbers Steganography

Category Portal WikiProject

This article is issued from Wikipedia - version of the 3/14/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.