Editing Linear-feedback shift register (section)

=== Uses in cryptography ===
LFSRs have long been used as [[pseudo-random number generator]]s for use in [[stream cipher]]s, due to the ease of construction from simple [[electromechanical]] or [[electronic circuits]], long [[periodic function|periods]], and very uniformly [[probability distribution|distributed]] output streams. However, an LFSR is a linear system, leading to fairly easy [[cryptanalysis]]. For example, given a stretch of [[known-plaintext attack|known plaintext and corresponding ciphertext]], an attacker can intercept and recover a stretch of LFSR output stream used in the system described, and from that stretch of the output stream can construct an LFSR of minimal size that simulates the intended receiver by using the [[Berlekamp-Massey algorithm]]. This LFSR can then be fed the intercepted stretch of output stream to recover the remaining plaintext.

Three general methods are employed to reduce this problem in LFSR-based stream ciphers:
* [[Non-linear]] combination of several [[bit]]s from the LFSR [[state (computer science)|state]];
* Non-linear combination of the output bits of two or more LFSRs (see also: [[shrinking generator]]); or using [[Evolutionary algorithm]] to introduce non-linearity.<ref>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]</ref>
* Irregular clocking of the LFSR, as in the [[alternating step generator]].

Important: LFSR-based stream ciphers include [[A5/1]] and [[A5/2]], used in [[GSM]] cell phones, [[E0 (cipher)|E0]], used in [[Bluetooth]], and the [[shrinking generator]]. The A5/2 cipher has been broken and both A5/1 and E0 have serious weaknesses.<ref>{{Citation
 | last1 = Barkam
 | first1 = Elad
 | last2 = Biham
 | first2 = Eli
 | last3 = Keller
 | first3 = Nathan
 | title = Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication
 | journal = Journal of Cryptology
 | volume = 21
 | issue = 3
 | year = 2008
 | pages = 392–429
 | url = https://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf
 | doi = 10.1007/s00145-007-9001-y
 | s2cid = 459117
 | access-date = 2019-09-15
 | archive-date = 2020-01-25
 | archive-url = https://web.archive.org/web/20200125081932/http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/2006/CS/CS-2006-07.pdf
 | url-status = dead
 }}</ref><ref>{{cite book
 | first = Yi | last = Lu |author2=Willi Meier |author3=Serge Vaudenay
 | title = Advances in Cryptology – CRYPTO 2005 | chapter = The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption | year = 2005 | location = Santa Barbara, California, USA
 | url = http://www.terminodes.org/micsPublicationsDetail.php?pubno=1216 | volume = 3621 | pages = 97–117 | doi=10.1007/11535218_7
| series = Lecture Notes in Computer Science | isbn = 978-3-540-28114-6 | citeseerx = 10.1.1.323.9416 }}</ref>

The linear feedback shift register has a strong relationship to [[linear congruential generator]]s.<ref>
RFC 4086
section 6.1.3 "Traditional Pseudo-random Sequences"
</ref>