Questions tagged as ['lfsr']

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?

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 ...

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 ...

Why LFSR stream code is not suitable for encryption? Is there a special attack for 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 ...

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 ...

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$

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 ...

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  ...

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:

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.