J.Cryptology(1997)10:111–147
©1997International Association for
Cryptologic Rearch
Feedback Shift Registers,2-Adic Span,and
Combiners with Memory∗
Andrew Klapper
763H Anderson Hall,Department of Computer Science,University of Kentucky,
Lexington,KY40506-0047,U.S.A.
klapper@cs.uky.edu
Mark Goresky
School of Mathematics,Institute for Advanced Study,
Princeton,NJ,U.S.A.
Communicated by Rainer Rueppel and Gilles Brassard
Received27January1995and revid1July1996
Abstract.Feedback shift registers with carry operation(FCSRs)are described,im-
plemented,and analyzed with respect to memory requirements,initial loading,period,
and distributional properties of their output quences.Many parallels with the theory of
linear feedback shift registers(LFSRs)are prented,including a synthesis algorithm
(analogous to the Berlekamp–Masy algorithm for LFSRs)which,for any pudo-
random quence,constructs the smallest FCSR which will generate the quence.
The techniques are ud to attack the summation cipher.This analysis gives a unified
approach to the study of pudorandom quences,arithmetic codes,combiners with
memory,and the Marsaglia–Zaman random number generator.Possible variations on
the FCSR architecture are indicated at the end.
Key words.Binary quence,Shift register,Stream cipher,Combiner with memory,
Cryptanalysis,2-Adic numbers,Arithmetic code,1/q Sequence,Linear span.
1.Introduction
Pudorandom quences,with a variety of statistical properties(such as high linear span, low autocorrelation and pairwi cross-correlation values,and high pairwi hamming distance)are important in many areas of communications and computing(such as cryp-tography,spread spectrum communications,error correcting codes,and Monte Carlo
∗Andrew Klapper was sponsored by the Natural Sciences and Engineering Rearch Council under Oper-ating Grant OGP0121648,the National Security Agency under Grant Number MDA904-91-H-0012,and the National Science Foundation under Grant Number NCR9400762.The United States Government is autho-rized to reproduce and distribute reprints notwithstanding any copyright notation hereon.Mark Goresky was partially supported by the Ellentuck Fund and National Science F
oundation Grant Number DMS9304580.
111
112 A.Klapper and M.Goresky
存钱利息
池莉小说
Fig.1.Linear feedback shift register.
integration).Binary pudorandom periodic quences are often generated in hardware,
using linear feedback shift registers(LFSRs),and are referred to as“linear recurrence
quences.”Certain register cells are“tapped,”their contents are added modulo2,and
ampoulethe sum is returned to thefirst cell of the shift register.(See Fig.1.The q i∈{0,1} indicate existence or nonexistence of a tap.The symbol⊕refers to addition modulo2.)
Many modern stream ciphers are designed by combining the output of veral LFSRs
in various nonlinear ways(and hence ultimately depend on a deep understanding of
the linear feedback architecture).Since1955,an enormous amount of effort has been
directed toward the study of other(“nonlinear”)feedback ,[13],[44],
and[6])which would give ri to fundamentally new or different kinds of pudoran-
dom quences.However,the other architectures have proven extremely resistant to
analysis:even simple properties such as the period of nonlinear feedback shift register
quences are esntially unknown.Despite40years of rearch,it is still the ca that
only the linear feedback architecture is adequately understood.
擞怎么读
In this paper we introduce a new but very simple feedback architecture for shift
register generation of pudorandom quences,which we call“feedback with carry”
shift registers(FCSR).The are the shift register analogues of the Marsaglia–Zaman
pudorandom number generators[36].It turns out that quences generated by an FCSR
share many of the important properties enjoyed by linear recurrence quences.However,
the analysis of FCSR quences involves a completely different mathematical toolkit:
instead of arithmetic infinitefields,we u arithmetic in the2-adic numbers.Although
some of the results in this paper may be proven without the u of the2-adic numbers,
we have been unable tofind any alternate approach to the main results(Theorems4.1,
9.5,10.1,and10.2).
An FCSR is a feedback shift register together with a small amount of auxiliary memory.
In its simplest form,the cells in the register consist of bits(0or1),while the memory
contains a nonnegative integer(e Fig.2).
The contents(0or1)of the tapped cells of the shift register are added as integers
to the current contents of the memory to form a sum,σ.The parity bit(σ(mod2))of σis fed back into thefirst cell,and the higher-order bits( σ/2 )are retained for the new value of the memory.(More details of the feedback procedure and simple hardware implementation are described in Section3).
The results in this paper are best described by exploiting the many parallels between
冬时令Feedback Shift Registers,2-Adic Span,and Combiners with Memory 113
Fig.2.Feedback with carry shift register.
properties of LFSR quences and tho of FCSR quences.Let us first recall the salient features of the LFSR theory.Note :Throughout this paper,Z denotes the integers, x denotes the greatest integer ≤x , x denotes the least integer ≥x ,and log denotes log 2.
Properties of LFSR Sequences
1.The r taps q 1,q 2,...,q r on the cells of an r -stage LFSR correspond to a connection polynomial
q (X )=q r X r +q r −1X r −1+···+q 1X −1
with coefficients q i in Z /(2).The period (and many other properties)of the LFSR quence may be expresd in terms of the Galois theory of this polynomial.
2.Suppo a =(a 0,a 1,a 2,...)is a periodic quence of bits obtained from a lin-ear feedback shift register of length r with connection polynomial q (X ).If q (X )is irreducible,and if γ∈GF (2r )is a root of q (X ),then for all i =0,1,2,...we have
a i =Tr (A γi )
for some A ∈GF (2r )(which corresponds to the choice of initial loading of the shift register).Here,Tr :GF (2r )→GF (2)denotes the trace function.3.Any infinite binary quence a =(a 0,a 1,a 2,...)may be identified with its gener-ating function,A (X )= ∞i =0a i X i which is an element of the ring Z /(2)[[X ]]of formal power ries with coefficients in the integers modulo 2.It is well known (e [13])that the quence a is eventually periodic if and only if its generating function is equal to a quotient of two polynomials ,
A (X )=r (X )q (X )
∈Z /(2)[[X ]],in which ca the denominator q (X )is the connection polynomial for a linear feedback shift register which generates the periodic part of the quence a .The quence a is strictly periodic if and only if deg (r )<deg (q ).
4.The size of the smallest LFSR that generates a given periodic quence a is called the linear complexity or equivalent linear span of a ;it is an important measure of
114 A.Klapper and M.Goresky the cryptographic curity of the quence.Such a shift register (of minimum size)may be found in an efficient way using the Berlekamp–Masy algorithm,which may be interpreted as the continued fraction expansion of the fraction r (X )/q (X )in the ring Z /(2)[[X ]]of formal power ries.This algorithm is optimal in two ns:(a)it determines the smallest LFSR who output coincides with a ;and (b)it does so with minimal information:only the first 2·span (a )bits of the quence a are needed.
5.The generating function of the bitwi sum of two binary pudorandom quences a =(a 0,a 1,a 2,...)and b =(b 0,b 1,b 2,...)is given by addition C (X )=A (X )+B (X )∈Z /(2)[[X ]]in the ring of formal power ries.If a and b are periodic,then so is the bitwi sum c ,and its equivalent linear span is no greater than the sum of the linear spans of a and b .
6.An m -quence is a LFSR quence of maximum possible period T =2r −1(where the shift register has r stages).It is a remarkable but well-known fact that the m -quences are exactly tho quences generated by LFSRs who taps correspond to primitive connection polynomials.Such s
equences are balanced and have the de Bruijn property:in any single period of an m -quence,every nonzero binary string of length r occurs exactly once.The autocorrelation function of an m -quence is two-valued;the out-of-pha values are all equal to −1.
7.The 2n −1cyclic permutations of a single period of an m -quence form the nonzero codewords of a (“punctured”)first-order cyclic Reed–Muller code.The codes are of fundamental importance in coding theory and are prototypes of the general “finite geometry”codes.
Properties of FCSR Sequences
We now describe the main definitions and results of this paper.
1 .The r taps q 1,q 2,...,q r on the cells of an r -stage FCSR define a connection integer (e Definition 3.1)
q =q r 2r +q r −12r −1+···+q 12−1.
The period (and many other properties)of the FCSR quence may be expresd in terms of number-theoretic properties of this integer.
2 .In Section 6we prove that if a periodic quence a =(a 0,a 1,a 2,...)is generated by an FCSR with connection integer q ,and if γ=2−1∈Z /(q )is the (multiplicative)inver of 2in the ring of integers modulo q ,then there exists A ∈Z /(q )such that for all i =0,1,2,...we have
a i =(A γi (mod q ))(mod 2).
3 .Any infinite binary quence a =(a 0,a 1,a 2,...)may be identified with the formal power ries,α= ∞i =0a i 2i which is an element of the ring Z 2of 2-adic numbers (e Section 2).The quence a is eventually periodic if and only if the 2-adic number αis ,if there exist integers r ,q such that
α=r q
∈Z 2.
Feedback Shift Registers,2-Adic Span,and Combiners with Memory 115In this ca,the denominator q is the connection integer for an FCSR which generates the periodic part of the quence a (e Theorem 4.1.)The quence a is strictly periodic if and only if α<0and |r |<|q |(e Corollary 4.2).
4 .The size of the smallest FCSR that generates a given periodic quence a we call the 2-adic span of a (e Definition 9.1).Such a shift register (of minimum size)may be found in an efficient way usin
g 2-adic approximation theory (e Section 10).Our algorithm is optimal in both of the above ns:it determines the smallest FCSR who output coincides with a ,and it does so with knowledge of only 2M +2log (M )bits of the quence a (where M denotes the 2-adic span of a ).Although our algorithm is bad on de Weger’s theory [47]of approximation lattices,it differs from de Weger’s algorithm in that ours is adaptive :each time a new bit is determined (say,by a known plaintext attack),it is ud to quickly update the previously determined FCSR.Thus,the number of bits need not be known ahead of time.
5 .Suppo two infinite,periodic quences a =(a 0,a 1,a 2,...)and b =(b 0,b 1,b 2,...)are added with the carry operation.This process is called the sum-mation combiner;it was invented by Masy and Rueppel [37],[44],and was suggested as a means for generating cryptographically cure binary quences from incure ones.
The resulting quence c =(c 0,c 1,c 2,...)is given by addition γ=α+β∈Z 2in the ring of 2-adic integers (where γ= ∞i =0c i 2i )(e Section 2).In Theorem 9.5we prove
that the 2-adic span of the quence c is approximately bounded by the sum of the 2-adic spans of a and b .
6 .An -quence is an FCSR quence of maximum possible period T =q −1(where q is the connection integer of the FCSR).The -quences are generated by FCSRs with connection integers q for which 2is a primitive root .A single period of an quence is a cyclic shift of the quence formed by reversing a single period of the binary expansion of the fraction 1/q .The quences have been studied since the time of Gauss [12],[3,Theorem 1],[44,p.219].They have remarkable distribution and correlation properties (e Section 13)which are parallel to tho of m -quences.
7 .The q −1cyclic permutations of a single period of an -quence form the nonzero codewords of a Barrows–Mandelbaum [2],[33]arithmetic code.The generation of the codes using FCSR circuitry is new.
In Section 11we prent a method for attacking the summation cipher.Suppo two periodic binary quences a and b are summation-combined to give a binary quence c .Although the linear span of c approaches the product of the linear spans of a and b ,it follows from (5 )above that the 2-adic span of c is only of the order of the sum of the 2-adic spans of a and b .Furthermore,the rational approximation algorithm (4 )above will find an FCSR which generates the quence c with knowledge (approximately)2·span 2(c )bits.There is a huge variety of possible variations on the “feedback with carry”theme,some of which we prent at the end of this paper.
It is remarkable that quences generated with the FCSR architecture can be analyzed at all (although there still remains a number of interesting questions).It is even more remarkable that this simple feedback circuitry leads immediately to a variety of deeper number-theoretic issues.We believe that FCSR quences (and their generalizations)are likely to find many applications in stream cipher technology.
116 A.Klapper and M.Goresky
Related Literature
The authors have published announcements(with sketch of proofs,or with no proofs at
all)of some of the results,in various conference proceedings[23],[24],[25],[26].Our
shift registers are nicely described in§17.4and§17.5of[45],where various architectures
for combining them with other shift register quences are suggested.See also[10](to
appear).We also wish to draw the reader’s attention to the subquent developments
[22],[27].
The cloly related paper of Marsaglia and Zaman[36](e[35])was recently brought
to our attention:their random number generator may be described as an FCSR with two
taps,who cells contain integers modulo b(rather than modulo2).(Here,b is some
large integer.)Thus there is some overlap between their analysis and ours.In particular,
Marsaglia and Zaman prove:(a)that the period of their generator is given by the order
of b modulo q=b r+b s−1(where the taps occur on cells number r and s);and(b) that the output quence of their generator may be identified with the b-adic expansion
of a certain rational number a/q.The are the analogues of our Corollary2.2and
Theorem4.1,respectively.
We also learned of the(apparently unpublished)manuscript[1]in which the Euclidean
algorithm is propod as a possible method for the efficient prediction of the Marsaglia–
Zaman generator.We have relied heavily on the p-adic approximation theory of[47]三天打鱼
and[32].Related results appear in[14],[30],[34].
Another important measure of(nonlinear)complexity is the“maximum order com-
plexity”[19],[20],[21]and its determination using the Blumer algorithm[4].This is
discusd briefly in Section9,however,we do not understand the relationship between
打雪仗看图写话2-adic complexity and maximum order complexity.
The summation combiner was previously shown to be vulnerable to the“correlation
元旦手抄报一等奖attack”of Meier and Staffelbach[38],[39].
2.Review of2-Adic Numbers
In this ction we briefly review some basic facts about2-adic numbers,andfix a notation
for the2-adic numbers;the interested reader may wish to consult one of the many
excellent references on p-adic numbers,for example,[11],[29],or[28,Section4.1,
Example31].
A2-adic integer is a formal power riesα= ∞
i=0
a i2i,with a i∈{0,1}.Such a
power ries does not converge in the usual n,but it can nevertheless be manipulated
as a formal object;the collection of all such power ries forms the ring Z2of2-adic
integers.The main difference between the ring Z2and the ring Z/(2)[[X]]of formal
power ries in X,is that addition in Z2is performed by“carrying”overflow bits to
higher-order terms,so that2i+2i=2i+1.Multiplication is defined by shift and add. Using the operations,Z2becomes a ring with additive identity0and multiplicative
identity1=1·20.(Some readers mayfind it less confusing to think of formal power ries in some indeterminate,Y,rather than2,and to u the rule Y i+Y i=Y i+1.It turns out that the u of the number
2instead of Y facilitates many computations and comparisons between the2-adic integers and the usual integers.)
