# Questions tagged as ['lfsr']

Linear Feedback Shift Register, a pseudorandom bit generator which can be efficiently implemented in hardware.
Score: 2
Linear Complexity of two dimensional finite patterns such as QR codes

Two dimensional patters are omnipresent in information transactions. QR codes, images are most common. I want to know if there is a concept analogous to the well known concept of Linear Complexity of periodic sequences, for two dimensional patterns?

Score: 1
Berlekamp massey possibly wrong SAGEMATH

This is in context with the inbuilt berlekamp_massey function in SAGEMATH.

While computing the minimal polynomial of the sequences using the Berlekamp Massey function, I have felt that the Berlekamp Massey function in Sagemath is so designed that it requires the periodic sequence to be repeated twice for correct results. Considering the problem of computing the linear complexity of the periodic s ...

Score: 1
Berlekamp–Massey input sequence length

For a given periodic sequence of length $$N$$ for which minimal polynomial is being constructed. Does the Berlekamp-Massey algorithm take the input of $$2N$$, i.e., the repeated input sequence or just the input sequence itself? The doubt arise because by taking the original sequence $$S$$ of length $$N$$, and the sequence $$S \| S$$ (concatenation) of length $$2N$$, I found that the minimal polynomial value c ...

Score: 0
Why LFSR stream code is not suitable for encryption?

Why LFSR stream code is not suitable for encryption? Is there a special attack for LFSR?

Score: 1
Polynomial notation of LFSR

I was following along with Christof Paar's lecture on Linear Feedback Shift Registers. He explains the structure coherently as a set of flip flops where the 'taps' are defined by a bit vector (0 for no tap on that flip flop, 1 for a tap on that flip flop). This makes perfect sense to me.

But then he brings up the point that people describe an LFSR not as a set of flip flops and a bit vector to define ...

Score: 0
Can the Berlekamp-Massey algorithm falsely detect an LFSR?

Is it possible that the BMA detects an irreducible polynomial from a sequence that was not generated by an LFSR? I am feeding a sequence into the BMA under the assumption that it was generated by an LFSR. It detects a polynomial of a certain length, but the sequence can’t be reconstructed from that polynomial. I don’t want to assume that the implementation of the BMA has a bug. If the question above ...

Score: 0
Finding initial key of Fibonacci LFSR knowing only polynomial and output stream-cipher

I need to know whether it is possible to find the initial key of a Fibonacci LFSR knowing only length and taps and output stream-cipher bit sequence?

Plaintext is not ASCII, nor some other sort of printable characters. It's also a bit sequence.

LFSR: 15bit $$X^{15}+X^{14}+1$$

Score: 2
Discrepancy \$δ\$ in the Berlekamp-Massey Algorithm

I have a question regarding to the Berlekamp–Massey algorithm. Can someone guide me to understand the idea/intuition of this algorithm?

According to the explanation in Wikepedia, in each iteration, the algorithm is trying to calculate the discrepancy $$δ$$.

If $$δ≠0$$, the algorithm will update the error locator polynomial using an update polynomial $$B(x)$$. However, at this point, I know that the r ...

Score: 1
What tools are there to reverse-engineer an LFSR besides the BMA?

I have a certain timecode which I can’t seem to figure out. We gave successfully decoded other codes for the same purpose with the Berlekamp-Massey algorithm, but this code seems to have a linear complexity of 110, which is not practical in any way. It can also not be reconstructed with the 110-bit irreducible polynomial the BMA finds. Just the first few bits are as expected and then the bits seem to  ...

Score: 4
Use of scrambler LFSR for randomness extraction of semi-random source

I am using a linear feedback shift register (LFSR) in a scrambler configuration as a randomness extractor for a weakly random source. This source is semi-random (aka. Santha-Vazirani source): the bits are correlated and biased (with a min-entropy of ~0.5 per bit). Here is an example of a LFSR in a scrambler configuration (this one is 12-bit while I am using a 32-bit register) with a downsampler:

Score: 4
What vulnerabilities does the LFSR filter generator have?

As the title suggests, I wonder what kinds of attacks there are in the LFSR filter generator. The most representative attack is the fast correlation attack and inversion attack. I wonder what other attacks are possible.