An Equivalence Preserving Transformation from the Fibonacci to the Galois NLFSRs ElenaDubrova RoyalInstituteofTechnology(KTH),Electrum229,16446Kista,Sweden 8 [email protected] 0 0 2 Abstract. ConventionalNon-LinearFeedbackShiftRegisters(NLFSRs)usethe n a Fibonacci configuration in which the value of the first bit is updated accord- J ing to some non-linear feedback function of previous values of other bits, and 0 eachremainingbitrepeatsthevalueofitspreviousbit.Weshow how totrans- 3 formthefeedbackfunctionofaFibonacciNLFSRintoseveralsmallerfeedback functionsofindividualbits.Suchatransformationreducesthepropagationtime, ] thusincreasingthespeedofpseudo-random sequencegeneration.Thepractical R significance of thepresented technique isthat ismakes possible increasing the C keystreamgenerationspeedofanyFibonacciNLFSR-basedstreamcipherwith . nopenaltyinarea. s c [ Keywords: Fibonacci NLFSR, Galois NLFSR, pseudo-randomsequence, keystream, 2 streamcipher. v 9 7 1 Introduction 0 4 . Non-LinearFeedbackShiftRegisters(NLFSRs) havebeenproposedasan alternative 1 0 to LinearFeedbackShiftRegisters(LFSRs) forgeneratingpseudo-randomsequences 8 forstreamciphers.NLFSR-basedstream ciphersincludeAchterbahn[1],Dragon[2], 0 Grain[3],Trivium[4],VEST[5],and[6].NLFSRshavebeenshowntobemoreresis- v: tanttocryptanalyticattacksthanLFSRs[7,8].However,constructionoflargeNLFSRs i with guaranteed long periods remains an open problem. A systematic algorithm for X NLFSR synthesis has not been discoveredso far. Only some special cases have been r considered[9,10,11,12,13,14,15,16,17]. a Ingeneral,therearetwowaystoimplementanNLFSR:intheFibonacciconfigu- ration,orintheGaloisconfiguration.TheFibonacciconfiguration,showninFigure1, is conceptuallymoresimple. The Fibonaccitype of NLFSRs consists of a numberof bitsnumberedfromlefttorightasn−1,n−2,...,0withfeedbackfromeachbittothe n−1thbit.Ateachclockinginstance,thevalueofthebitiismovedtothebiti−1.The valueofthebit0becomestheoutputoftheregister.Thenewvalueofthebitn−1is computedassomenon-linearfunctionofthepreviousvaluesofotherbits. IntheGaloistypeofNLFSR,showninFigure2,eachbitiisupdatedaccordingto its ownfeedbackfunction.Thus,in contrastto the FibonacciNLFSRs in whichfeed- back is applied to the n−1th bit only, in the Galois NLFSRs feedback is potentially appliedtoeverybit.SincethenextstatefunctionsofindividualbitsofaGaloisNLFSR feedbackfunction ... n−1 n−2 n−3 0 output Fig.1.AnFibonaccitypeofNLFSR. are computedin parallel, the propagationtime is reducedto thatof smaller functions ofindividualbits.ThismakesGaloisNLFSRsparticularlyattractiveforstreamciphers applicationinwhichhighkeystreamgenerationspeedisimportant. However,GaloisNLFSRsalsohavethefollowingtwodrawbacks: 1. Ann-bitGaloisNLFSRwiththe periodof2n−1doesnotnecessarilysatisfythe 1st and the 2nd postulates of Golomb [18]. An n-bit Fibonacci NLFSR with the periodof2n−1alwayssatisfybothpostulates[9]. 2. TheperiodoftheoutputsequenceofaGaloisNLFSRisnotnecessarilyequaltothe lengthofthelongestcyclicsequenceofitsconsecutivestates[18].Theperiodofa FibonacciNLFSRalwaysequalsto thelongestcyclicsequenceofitsconsecutive states[9]. These drawbacks do not create any problems in the linear case because, for LF- SRs, there exist a one-to-one mapping between the Fibonacci and Galois configura- tions.AGaloisLFSRgeneratingthesameoutputsequenceasagivenFibonacciLFSR (andthereforepossessingnoneoftheabovementioneddrawbacks)canbeobtainedby reversing the order of the feedback taps and adjusting the initial state. For example, Figure 3 showsthe Fibonacciand Galois configurationsforthe generatorpolynomial x3+x+1. If the FibonacciLFSR is initialized to the state 001 and the Galois one is initializedtothestate101,thentheygeneratethesameperiodicsequence1001011. Inthenon-linearcase,however,nomappingbetweentheFibonacciandtheGalois configurationshas been known until now. The problem of finding such a mapping is addressedinthispaper.Weshowthat,foreachFibonacciNLFSR,thereexistaclassof equivalentGaloisNLFSRswhichproducethesameoutputsequence.Weshowhowto transformagivenFibonacciNLFSRintoanequivalentGaloisNLFSR. Themostsignificantcontributionofthe paperis a sufficientconditionforequiva- lenceoftwoNLFSRsbeforeandafterthetransformation.Itisformulatedandproved forthegeneralcasewhichcoversnotonlytheequivalencebetweenaFibonaccianda GaloisNLFSRs,butonlytheequivalencebetweentwoGaloisNLFSRs. Thepaperisorganizedasfollows.Section2describesmainnotionsanddefinitions used in the sequel. Section 3 formulatesa sufficientconditionfor existence of a non- linear recurrence describing the output sequence of an NLFSR. Section 4 presents a sufficientconditionfortheequivalenceoftwoNLFSRs.InSection5,wedefineaGalois NLFSR which is unique for a given Fibonacci NLFSR and show how to compute it. Section6concludesthepaperanddiscussesopenproblems. ... ... ... f n−1 f n−2 ... f 0 n−1 n−2 0 output Fig.2.AGaloistypeofNLFSR. 2 Preliminaries Inthissection,wedescribebasicdefinitionsandnotationusedinthesequel. Thealgebraicnormalform (ANF) of a Booleanfunction f :{0,1}n→{0,1}is a polynomialinGF(2)oftype 2n−1 f(x ,...,x )= (cid:229) c ·xi0·xi1·...·xin−1, 0 n−1 i 0 1 n−1 i=0 wherec ∈{0,1}and(i i ...i )isthebinaryexpansionofiwithi beingtheleast i 0 1 n−1 n−1 significantbit. Thedependenceset(orsupportset)ofaBooleanfunction f isdefinedby dep(f)={i| f| 6= f| }, xi=0 xi=1 where f| = f(x ,...,x ,j,x ,...,x )for j∈{0,1}. xi=j 0 i−1 i+1 n−1 Leta (f)(a (f))bethesmallest(largest)indexofvariablesindep(f). min max Let f :{0,1}n→{0,1}beafeedbackfunctionofthebiti,i∈{0,1,...,n−1},of i anNLFSR.AllresultsinthispaperasderivedforNLFSRswhosefeedbackfunctions aresingularfunctionsoftype f =x ⊕g(x ,...,x ), (1) i i+1 i 0 n−1 whereg :{0,1}n−1→{0,1},i+16∈dep(g),andthesign“+”ismodulon.Singularity i i guarantees that the state transition graph of an NLFSR is “branchless”, i.e. that each statebelongstooneofthestatecycles[9]. Let s(t) denote the value of the bit i at time t. The sequence of states an n-bit i NLFSR with the singular feedbackfunctionscan be described by a system of n non- linearequationsoftype: s (t)=s (t−1)⊕g (s (t−1),s (t−1),...,s (t−1)) n−1 0 n−1 1 2 n−1 s (t)=s (t−1)⊕g (s (t−1),s (t−1),...,s (t−1)) n−2 n−1 n−2 0 1 n−2 (2) ... s (t)=s (t−1)⊕g (s (t−1),s (t−1),...,s (t−1)). 0 1 0 0 2 n−1  2 1 0 2 1 0 Fig.3.TheFibonacciLFSR(left)andtheGaloisLFSR(right)forthegeneratorpoly- nomialx3+x+1. 3 A Condition forExistence ofa Non-Linear Recurrence In this section, we formulate a condition for existence of a non-linear recurrence de- scribingtheoutputsequenceofanNLFSR.First,weintroducesomedefinitionswhich arenecessaryforthepresentationofmainresults. Definition1. Two NLFSRs are equivalentif there are initial states, possibly different foreachNLFSR,fromwhichtheygeneratethesameoutputsequences. Definition2. ThefeedbackgraphofanNLFSRhasnverticesv ,...,v representing 0 n−1 thebits0,...,n−1.Thereisanedgefromv tov ifi∈dep(f ),i,j∈{0,1,...,n−1}. i j j Definition3. Theterminalbitofann-bitNLFSRisthebitwiththelargestindexiwhich satisfiesthefollowingcondition:Forallbits jsuchthati> j≥0,thefeedbackfunction f isoftype f =x ,i,j∈{0,1,...,n−1}. j j j+1 Definition4. Theoperationsubstitution,denotedbysub(v,v ),isdefinedforanyver- i j tex v which hasa uniquepredecessorv . Thesubstitutionsub(v,v )removesv from i j i j i thefeedbackgraphand,foreachsuccessorv ofv,replacestheedge(v,v )byanedge k i i k (v ,v ),i,j,k∈{0,...,n−1}. j k Definition5. GivenafeedbackgraphG, thereducedfeedbackgraphofG isagraph obtained by subsequently applyingthe substitution to all vertices of G with the input degree1. Sincesubstitutionmergesavertexwithitsuniquepredecessor,theorderofapplying thesubstitutiondoesnotinfluencetheresultingreducedfeedbackgraph,i.e.itisunique foragivenG. Lemma1. Ifthefeedbackgraphofann-bitNLFSRcanbereducedtoasinglevertex v,i∈{0,1,...,n−1},thenthereexistanon-linearrecurrencedescribingthesequence i ofvaluesofthebitioftype 2n−1 n−1 si(t)= (cid:229) (aj·(cid:213) sjk(t−n+k)), (3) j=0 k=0 wherea ∈{0,1},(j j ...j )isthebinaryexpansionof jwith j beingtheleast j 0 1 n−1 n−1 significantbit,andsjk(t−n+k)isdefinedasfollows s(t−n+k),fori=1, sjk(t−n+k)= (cid:26)1, fori=0. 3 3 3 0 2 2 3 2 1 1 (a) (b) (c) (d) Fig.4.ReductionstepsforthefeedbackgraphoftheFibonacciNLFSRfromtheexam- ple:(a)initialgraph;(b)aftersub(v ,v );(c)aftersub(v ,v );(d)aftersub(v ,v ). 0 1 1 2 2 3 Proof:Letv beavertexofthefeedbackgraphwhichhasauniquepredecessorv andm i j successorsv ,...,v , j,k ∈{0,1,...,n−1},p∈{0,1,...,m}.ByDf.2,thisimplies k1 km p thats(t)=s (t−1)and,foreach p,s (t)dependsons(t−1). i j kp i The substitution sub(v,v ) is equivalent to replacing the variable s(t−1) in the i j i equationofeachs (t)bys (t−2).Thisreducesthenumberofvariablesintheequa- kp j tions(2)byoneandreducesthenumberofequationsbyone. IfthefeedbackgraphofanNLFSRcanbereducedtoasinglevertex,sayv ,thenthe r substitutioncanbeappliedn−1times.So,thenumberofvariablesintheequations(2) canbereducedtoasinglevariableandthenumberofequationscanbereducedtoasin- gleequation.Thisequationcorrespondstothenon-linearrecurrencerelationdescribing thesequenceofstatesofthebitroftheNLFSR. 2 Example1:Asanexample,considera4-bitFibonacciNLFSRwiththefeedbackfunc- tion f =x ⊕x ⊕x ⊕x x . Itssequenceofstatescanbedescribedbythefollowing 3 0 1 2 1 3 equations: s (t)=s (t−1)⊕s (t−1)⊕s (t−1)⊕s (t−1)s (t−1), 3 0 1 2 1 3 s2(t)=s3(t−1), s1(t)=s2(t−1), s (t)=s (t−1). 0 1  ThisNLFSRgeneratesthefollowingoutputsequencewiththeperiod15: 111011000101001... ThefeedbackgraphofthisNLFSRisshowninFigure4(a).Itcanbereducedtoa singlevertexasfollows: 1. sub(v ,v )reducesthegraphtoFigure4(b).Thisisequivalenttosubstitutings (t) 0 1 0 bys (t−1)intotheequationofs (t): 1 3 s (t)=s (t−2)⊕s (t−1)⊕s (t−1)⊕s (t−1)s (t−1). 3 1 1 2 1 3 2. sub(v ,v )reducesthegraphtoFigure4(c).Thisisequivalenttosubstitutings (t) 1 2 1 bys (t−1)intotheequationofs (t): 2 3 s (t)=s (t−3)⊕s (t−2)⊕s (t−1)⊕s (t−2)s (t−1). 3 2 2 2 2 3 3. sub(v ,v )reducesthegraphtoFigure4(d).Thisisequivalenttosubstitutings (t) 2 3 2 bys (t−1)intotheequationofs (t): 3 3 s (t)=s (t−4)⊕s (t−3)⊕s (t−2)⊕s (t−3)s (t−1). 3 3 3 3 3 3 This gives us a non-linear recurrence describing the sequence of values of the bit 3. Sinceotherbitsrepeatthecontentofthe3rdbit,therecurrenceisidenticalforallbits, andthusfortheoutputoftheNLFSR. Itis easy to see thatthe feedbackgraphof a FibonacciNLFSR can always be re- duced to a single vertex v . Therefore,for a FibonacciNLFSR, a non-linearrecur- n−1 renceoftype(3)alwaysexists.Itscoefficientsa,i∈{0,1,...,2n−1},areequaltothe i coefficientsc oftheANFofthefeedbackfunction f . i n−1 ForGaloisNLFSRs,anon-linearrecurrenceoftype(3)mayormaynotexist.Ifit exists,itmaybedifferentfordifferentbits. Example2:Asanotherexample,consideraGaloisNLFSRwiththefollowingfeedback functions: f =x ⊕x x , 3 0 1 3 f =x , 2 3 f =x , 1 2 f =x ⊕x ⊕x . 0 1 2 3 Itsfeedbackgraphcanbereducedtothevertexv ,givingusthefollowingrecurrence: 3 s (t)=s (t−4)⊕s (t−3)⊕s (t−2)⊕s (t−3)s (t−1). 3 3 3 3 3 3 This recurrenceis the same as the one of the FibonacciNLFSR fromthe Example1. Bits2 and1repeatthesamerecurrenceasthebit3,however,thevalueofthebit0 is theXORofthebits1,2and3.Thus,itssequenceofvaluesdiffersfromtheoneofthe 3rd bit. Therefore, the output sequence of this Galois NLFSR, is different the output sequenceoftheFibonacciNLFSRfromtheExample1. 4 A Transformationfrom the Fibonacci to the GaloisNLFSRs Inthissection,weshowhowtotransformaFibonacciNLFSRintoanequivalentGalois NLFSR. LetP denotethe set of all product-termsof the ANF of a function f :{0,1}n→ f {0,1}. Given an ANF product-term p∈P , the notation p means that the index of f −k eachvariablex of pischangedtox ,where“−”ismodulon. i i−k Forexample,ifn=4,and p=x x x then 0 1 3 p =x x x , p =x x x , p =x x x . −1 3 0 2 −2 2 3 1 −3 1 2 0 p Definition6. Theoperationshifting,denotedby f → f , p∈P ,a,b∈{0,1,...,n− a b fa 1}, b<a, removes the product-term p from the ANF of the function f and addsthe a product-term p totheANFofthefunction f . −(a−b) b Aswecanseeformthedefinition,shiftingsubtracts(a−b)fromtheindexofeach variableintheshiftedproduct-term(modulon).Forexample,ifinitially f =x ⊕x x 3 0 1 3 f =x 2 3 then,after f −x1→x3 f ,weget 3 2 f =x 3 0 f =x ⊕x x . 2 3 0 2 Definition7. Ann-bitNLFSRisuniformif: (a) allitsfeedbackfunctionsareoftype(1),and (b) forallitsbitsisuchthatn−1≥i>t ,thefollowingconditionholds: a (g)≤t , (4) max i wheret istheterminalbitoftheNLFSR,t ∈{0,1,...,n−1}. NotethatanyFibonacciNLFSRisuniform. Lemma2. IfanNLFSRisuniform,thenitsfeedbackgraphcanbereducedtoasingle vertex. Proof:SupposethatanNLFSRN isuniform.Weshowthatthenwecanalwayreduce thefeedbackgraphofN tothevertexvt correspondingtotheterminalbitt ofN. By Df. 3, for i∈{0,1,...,t −1}, each vertex v of the feedback graph has input i degree1.So, foreachi∈{0,1,...,t −1}, wecan applythe substitutionsup(v,v ) i i+1 to removev fromthe feedbackgraph,and,foreach successor v of v, to replacethe i k i theedge(vi,vk)byanedge(vt ,vk).Therefore,byapplyingasequenceofsubstitutions sup(v0,v1),sup(v1,v2),...,sup(vt −1,vt )wecanremovev0,v1,...,vt −1fromthefeed- backgraphandchangetheoriginofalloutgoingedgesofv0,v1,...,vt −1tovt . Sincethecondition(4)holdsandtheoriginofalloutgoingedgesofv0,v1,...,vt −1 ischangedtovt ,eachoftheverticesvifori∈{t +1,t +2,...,n−1}hasnomorethan twoincomingedges:onefromvi+1andonefromvt .Thisimpliesthateachofthemhas theoutputdegree1. Clearly, vn−1 has only one incoming edge, from vt . By applying the substitution sup(vn−1,vt ),wecanremovevn−1andreplacetheedge(vn−1,vn−2)bytheedge(vt ,vn−2). This make the input degree of v one. Continuing similarly with the sequence of n−2 substitutionssup(vn−2,vt ),...,sup(vt +1,vt )weremovevn−2,...,vt +1 andreducethe graphtoonevertex,vt . 2 Theaboveconditionissufficient,butnotnecessary.Forexample,theNLFSRfrom theExample2isnotuniform,butitcanbereducedtoasinglevertex. Thefollowingtheoremisthemainresultofthepaper.Itpresentsasufficientcon- ditionforequivalenceoftwoNLFSRs.Note,thatitisformulatedforshiftingsonsub- functions g of the singular feedback functions f (see the expression 1), because the i i variablex shouldnotbeshiftedinordertopreservetheregisterstructure. i+1 p Theorem1. GivenauniformNLFSR,ashiftingg →g ,a,b∈{0,1,...,n−1},b<a, a b P⊆P ,preservestheequivalenceifthetransformedNLFSRisuniformaswell. ga Proof:SeeAppendix. The condition of the Theorem 1 is sufficient, but not necessary. For example, the followingNLFSR canbe obtainedfromthe NLFSRfromthe Example1 byapplying theshifting f −x1→x3 f , f −x→1 f and f −x→2 f : 3 0 3 1 3 1 f =x , 3 0 f =x , 2 3 f =x ⊕x ⊕x , 1 2 0 3 f =x ⊕x x . 0 1 0 2 ThisNLFSRisnotuniform,however,itisequivalenttotheNLFSRfromtheExample 1. Next,we formulatea conditionwhichshouldbe satisfied inorderto obtaina uni- formNLFSRaftershifting. p Theorem2. GivenauniformNLFSRN,anNLFSRobtainedfromNbyashiftingg → a g ,a,b∈{0,1,...,n−1},b<a,P⊆P ,isuniformonlyif b ga b≥a−a (p). (5) min Proof:Ifb<a−a (p),thena (p)<a−b.Therefore,aftertheshiftingg →p g , min min a b a (p)becomesa (p)+n−(a−b)=a (p)+b+(n−a).ByDf.6,b<a,thus min min min aisalwaysgreaterthan0.So,foranya∈{1,2,...,n−1},aftershiftingthefeedback functiong containsa product-termwhoseindexisgreaterthanb byn−a.Sincethe b terminalbitoftheNLFSRissmallerorequaltob,thecondition(4)ofDf.7isviolated. 2 Often an equivalentGalois NLFSR can be obtained from a FibonacciNLFSR by shifting product-termsone-by-one.Sometimes, however,morethan one product-term has to be shifted in order to preserve the equivalence. For example, if the feedback function g has more than one product-term containing the variable x , then all n−1 n−1 suchproduct-termshavetobeshifted.TheLemmabelowdescribestwocasesinwhich theproduct-termscanbeshiftedone-by-one. Lemma3. GivenauniformNLFSRwiththeterminalbitt andasiftingg →p g ,a,b∈ a b {0,1,...,n−1},b<a,P⊆P ,thefollowingholds: ga (a) Ifb≥t ,theng →p g preservestheequivalenceforany p∈P whichsatisfiesthe a b ga condition(5). (b) Ifb<t anda (g)≤bforalli∈{n−1,n−2,...,b},theng →p g preserves max i a b theequivalenceforany p∈P whichsatisfiesthecondition(5). ga Proof:Case(a):ByDf.6,aftertheshiftinga (p)becomesa (p)−(a−b).Since min min thecondition(5)issatisfied,a (p)≥a−b,i.e.aftershiftingtheindexesofvariables min of p are reduced by some value between 1 and a (p). Therefore,after the shifting, min none of the product-termsof p violates the condition (4). Since the initial NLFSR is uniform and the terminal bit is not changed, the transformed NLFSR is uniform as well,andtherefore,byTheorem1,theequivalenceispreserved. Case (b): Similarly to the case (a) we can show that, after the shifting, none of the product-termsofpviolatesthecondition(4).Sincea (g)≤bforallibyassumption, max i the transformed NLFSR is uniform and therefore, by Theorem 1, the equivalence is preserved. 2 TheaboveLemmaimpliesthat,foranyFibonacciNLFSR,shiftingcanalwaysre- duce the index of the initial terminal bit n−1 at least by 1. It reduces the index of the terminalbitexactlyby1if g ofthe FibonacciNLFSR containsa productwith n−1 a (g)=n−1anda (g )=1.Thesmallerthedifferencebetweena (g ) max i min n−1 max n−1 anda (g ),themoretheindexoftheinitialterminalbitcanbereduced. min n−1 5 Fully Shifted GaloisNLFSRs Usually,therearemultiplewaystotransformaFibonacciNLFSRintoaGaloisNLFSR. Next,wedefinea“fullyshifted”GaloisNLFSRwhichisuniqueforagivenFibonacci NLFSRandshowhowtocomputeit. Definition8. An NLFSR is fully shifted if no product-term of any function g can be i shifted to a function g with the index j<i withoutviolating the condition(4), i,j∈ j {0,1,...,n−1}. In the linear case, a fully shifted NLFSR reduces to a Galois LFSR, i.e. it is a generalizationoftheGaloisLFSR.NotethatthisisnotthecaseforNLFSRswhichare notfullyshifted. Algorithm 1: Given a uniform n-bit FibonacciNLFSR N, the fully shifted Galois NLFSRNˆ whichisequivalenttoN isobtainedasfollows. First,theterminalbitt ofNˆ iscomputedas: t = max (a (p)−a (p)), max min ∀p∈P (6) gn−1 with|p|>1 where|p|denotesthenumberofvariablesintheproduct-termp. Then,eachproduct-termp∈Pgn−1witha min(p)≤(n−1)−t isshiftedtogn−1−a min(p): p gn−1−→gn−1−a min(p). andeachproduct-termp∈Pgn−1 witha min(p)>(n−1)−t isshiftedtogt : p gn−1−→gt . Theorem3. Algorithm1correctlycomputesthefullyshiftedGaloisNLFSRforagiven FibonacciNLFSR. Proof:Foreachproduct psuchthata (p)≤(n−1)−t ,theindexesarereducesby min a (p). So, after the shifting, the smallest indexbecomes0 and the largestbecomes min a (p)−a (p).Byequation(6),a (p)−a (p)≤t . max min max min For each product p such that a (p)>(n−1)−t , the indexes are reduces by min (n−1)−t . Since a (p)<a (p)≤n−1, the largest index after the shifting is min max 0<a (p)−((n−1)−t )≤t . Since(n−1)−t <a (p)<a (p),thesmallest max min max indexaftertheshiftingis0<a (p)−((n−1)−t )<t . min So,thetransformedNLFSRNˆ isuniformandtherefore,byTheorem1,twoNLFSRs areequivalent.ItremainstoprovethatNˆ isfullyshifted. ByDf6,indexofeachvariableof pisreducedbya (p)aftertheshifting.There- min fore, for each product-term p∈P such that a (p)≤t , p after the shifting con- gn−1 min tainsa variablex0. If p isshiftedfurtherfromgn−1−a min(p) to gn−1−a min(p)−i forsome 1≤i≤n−1−a (p), the indexof x increasesto n−i.For everyvalueof iin the min 0 range1≤i≤n−1−a (p),n−i>n−1−a (p),sothecondition(4)isviolated min min andtheresultingNLFSRisnotequivalenttotheinitialFibonacciNLFSR. Eachproduct-term p∈P suchthata (p)>t isshiftedtotheterminalbitt . gn−1 min If pisshiftedtosomei<t ,then,accordingtotheequation(6),thereisaproduct-term p∗ which has a (p∗)>i after shifting. Thus, the condition (4) is violated and the max resultingNLFSRisnotequivalenttotheinitialFibonacciNLFSR. 2 Example4: Asan example,considerthe following32-bitFibonacciNLFSR which is usedintheNLFSR-basedstreamcipherfrom[6]: f = x ⊕x ⊕x ⊕x ⊕x ⊕x ⊕x ⊕x ⊕x ⊕x x ⊕ x x ⊕x x x 31 0 2 6 7 12 17 20 27 30 3 9 12 15 4 5 16 Its correspondingfully shifted Galois NLFSR has the terminalbit t =12 and the followingfeedbackfunctions: f =x 31 0 f =x ⊕x 29 30 0 f =x ⊕x x 28 29 0 6 f =x ⊕x x x 27 28 0 1 12 f =x ⊕x 25 26 0 f =x ⊕x 24 25 0 f =x ⊕x ⊕x x 19 20 0 0 3 f =x ⊕x 14 15 0 f =x ⊕x ⊕x ⊕x 12 13 1 8 11