According to Wikipedia LFSRs are used as PRGs but due to their linearity they are easy to cryptanalyze. Also, using Berlekamp-Massey consecutive output bits allow reconstruction of the internal LFSR state (I think the rule was something like $2n$ bits for state size $n$).

Now my question is a much more profane one. Given the following diagram for how an LFSR works doesn't it simply output its state and, therefore become trivially predictable? enter image description here

  • 2
    $\begingroup$ Actually, the Berlekamp-Massey algorithm assumes you don't know the feed back terms. Yes, if you do, it's trivial; if you don't, Berlekamp-Massey makes it trivial $\endgroup$
    – poncho
    Jan 25, 2017 at 17:27
  • $\begingroup$ Wow, they're even more terrible than I could reasonably imagine. ;) $\endgroup$
    – Elias
    Jan 25, 2017 at 17:28
  • 1
    $\begingroup$ "Terrible" isn't very objective. They are certainly unfit for some uses, but they have properties that are desirable for others. $\endgroup$
    – bmm6o
    Jan 25, 2017 at 21:57
  • $\begingroup$ @Elias, do you have any comments on the answer below? $\endgroup$
    – kodlu
    Jan 27, 2017 at 4:39

1 Answer 1


LFSRs are very useful as building blocks of ciphers, with some nonlinearity introduced. For example Trivium is a very strong and fast cipher, which includes a little amount of quadratic nonlinearity in 3 coupled LFSRs.

An example of bad use of LFSRs--and by no means the only one--is the A5 series of ciphers, of GSM fame, where majority clocking does not include enough nonlinearity/unpredictability.

  • $\begingroup$ Well, the feedback function of Trivium is not really linear so it's a little odd. I agree that shift registers can be interesting building blocks as long as sufficient nonlinearity is introduced. $\endgroup$
    – Elias
    Jan 27, 2017 at 8:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.