Nonlinear-feedback shift register
{{Short description|Type of shift register}}
A nonlinear-feedback shift register (NLFSR) is a shift register whose input bit is a non-linear function of its previous state.
For an n-bit shift register r its next state is defined as:
,
where f is the non-linear feedback function.{{cite book|first1=Tomasz|last1=Rachwalik|first2=Janusz|last2=Szmidt|first3=Robert|last3=Wicik|first4=Janusz|last4=Zabłocki|title=Generation of Nonlinear Feedback Shift Registers with special-purpose hardware|date=3 June 2012|publisher=Military Communication Institute (Warsaw)|page=1|url=https://eprint.iacr.org/2012/314|access-date=3 May 2017|language=en|format=PDF}}
Applications
Nonlinear-feedback shift registers are components in modern stream ciphers, especially in RFID and smartcard applications. NLFSRs are known to be more resistant to cryptanalytic attacks than Linear Feedback Shift Registers (LFSRs).
Generating
It is known how to generate an n-bit NLFSR of maximal length 2n, generating a De Bruijn sequence, by extending a maximal-length LFSR with n stages;C.G. Günther, "Alternating Step Generator Controlled by de Bruijn Sequence", Advances in Cryptology – EUROCRYPT '87, {{doi|10.1007/3-540-39118-5_2}} but the construction of other large NLFSRs with guaranteed long periods remains an open problem.[http://portal.acm.org/ft_gateway.cfm?id=1403686&type=pdf&CFID=21663688&CFTOKEN=35521752 On analysis and synthesis of (n, k)-non-linear feedback shift registers], 2008. Using bruteforce methods, a list of maximum-period n-bit NLFSRs for n ≤ 25 has been made as well as for n=27.E. Dubrova, "A List of Maximum Period NLFSRs", Cryptology ePrint Archive, Report 2012/166, March 2012, http://eprint.iacr.org/2012/166.
New methods suggest usage of evolutionary algorithms in order to introduce non-linearity.A. Poorghanad, A. Sadr, A. Kashanipour" Generating High Quality Pseudo Random Number Using Evolutionary Methods", IEEE Congress on Computational Intelligence and Security, vol. 9, pp. 331–335, May 2008 [http://www.computer.org/csdl/proceedings/cis/2008/3508/01/3508a331.pdf] In these works, an evolutionary algorithm learns how to apply different operations on strings from LFSR to enhance their quality to meet the criteria of a fitness function, here the NIST protocol,NIST.[http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf " A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications"]. NIST, Special Publication April 2010 effectively.