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. [1]
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).
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; [2] but the construction of other large NLFSRs with guaranteed long periods remains an open problem. [3] Using bruteforce methods, a list of maximum-period n-bit NLFSRs for n ≤ 25 has been made as well as for n=27. [4] [1]
New methods suggest usage of evolutionary algorithms in order to introduce non-linearity. [5] 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, [6] effectively.
- ^ a b Rachwalik, Tomasz; Szmidt, Janusz; Wicik, Robert; Zabłocki, Janusz (3 June 2012). Generation of Nonlinear Feedback Shift Registers with special-purpose hardware (PDF). Military Communication Institute (Warsaw). p. 1. Retrieved 3 May 2017.
- ^ 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
- ^ On analysis and synthesis of (n, k)-non-linear feedback shift registers, 2008.
- ^ E. Dubrova, "A List of Maximum Period NLFSRs", Cryptology ePrint Archive, Report 2012/166, March 2012, http://eprint.iacr.org/2012/166.
- ^ 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 [1]
- ^ NIST. " A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications". NIST, Special Publication April 2010
 | This cryptography-related article is a stub. You can help Wikipedia by expanding it. |
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. [1]
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).
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; [2] but the construction of other large NLFSRs with guaranteed long periods remains an open problem. [3] Using bruteforce methods, a list of maximum-period n-bit NLFSRs for n ≤ 25 has been made as well as for n=27. [4] [1]
New methods suggest usage of evolutionary algorithms in order to introduce non-linearity. [5] 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, [6] effectively.
- ^ a b Rachwalik, Tomasz; Szmidt, Janusz; Wicik, Robert; Zabłocki, Janusz (3 June 2012). Generation of Nonlinear Feedback Shift Registers with special-purpose hardware (PDF). Military Communication Institute (Warsaw). p. 1. Retrieved 3 May 2017.
- ^ 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
- ^ On analysis and synthesis of (n, k)-non-linear feedback shift registers, 2008.
- ^ E. Dubrova, "A List of Maximum Period NLFSRs", Cryptology ePrint Archive, Report 2012/166, March 2012, http://eprint.iacr.org/2012/166.
- ^ 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 [1]
- ^ NIST. " A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications". NIST, Special Publication April 2010
|
| This cryptography-related article is a stub. You can help Wikipedia by expanding it. |