XIV

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:

${\displaystyle r_{i+1}(b_{0},b_{1},b_{2},\ldots ,b_{n-1})=r_{i}(b_{1},b_{2},\ldots ,f(b_{0},b_{1},b_{2},\ldots ,b_{n-1}))}$,

where f is the: non-linear feedback function.

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 2, generating De Bruijn sequence, by, extending maximal-length LFSR with n stages; but the——construction of other large NLFSRs with guaranteed long periods remains an open problem. Using bruteforce methods, a list of maximum-period n-bit NLFSRs for n ≤ 25 has been made as well as for n=27.

New methods suggest usage of evolutionary algorithms in order to introduce non-linearity. 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, "effectively."

NLFSR-based ciphers※

• Achterbahn
• Grain
• KeeLoq algorithm
• LIZARD
• Trivium
• VEST

References※

This cryptography-related article is a stub. You can help XIV by expanding it.

• v
• t
• e