Cryptography Stack Exchange
Cryptography Stack Exchange

Questions tagged [lfsr]

Linear Feedback Shift Register, a pseudorandom bit generator which can be efficiently implemented in hardware.

160 questions
5
votes
1 answer

Algorithm or closed form solution that lets me directly compute the $n^{\text{th}}$ state of an LFSR?

I have a large linear feedback shift register with a known state and taps. Now I want to compute the state of the LFSR after $n$ iterations. The problem: $n$ is in the order of $2^{256}$ so just brute forcing is not an option. Is there an algorithm…
Nils Pipenbrinck
  • 218
  • 1
  • 6
4
votes
1 answer

Reversed Fibonacci LFSR taps

In the classic book "Applied Cryptography" (20th anniversary edition) from Bruce Schneier, there is an illustration of a maximal-length LFSR: According to the book, this LFSR uses the tap sequence from the polynomial $x^{32}+x^7+x^5+x^3+x^2+x+1$…
DurandA
  • 453
  • 5
  • 17
4
votes
1 answer

How to convert a Galois LFSR to a Fibonacci LFSR?

I have just found the sequence output by the Galois type LFSR, seen here. Now I know there exists a Fibonacci-type LFSR capable of outputting this same sequence but how could I find what the first six states of this LFSR would be?
harry55
  • 139
  • 1
  • 7
4
votes
1 answer

Period, correlation and auto-correlation of non-linear feedback shift registers based sequences

Use of Linear Feedback Shift Registers(LFSR) is discouraged due to complexity of order of it's length. Recently Non-Linear LFSR has been talked about. I am curious how the properties of LFSR based m-sequence generators hold in this…
Jay
  • 195
  • 10
4
votes
1 answer

Maximal-length LFSR with $n$ bits when the factorization of $2^n-1$ is unavailable?

There's a classical method to efficiently test if a LFSR with $n$ bits is maximal-length (or equivalently, if the feedback polynomial is primitive), when the factorization of $2^n-1$ is available. Do we have an efficient method working when that…
fgrieu
  • 140,762
  • 12
  • 307
  • 587
4
votes
2 answers

Multiplication of two LFSR

Let $a_n$, and $b_n$ two sequences generated by two LFSR with connection polynomials $P$, and $Q$. How to show the sequence $(a_n \cdot b_n)$ can be generated by a LFSR wit connection polynomial of degree upper bounded by $\deg(P)\cdot \deg(Q)$?
Ievgeni
  • 2,585
  • 1
  • 10
  • 32
3
votes
1 answer

What is the linear complexity of a modified LFSR sequence with a fixed length of zeroes inserted between every pair of successive terms

There was a deleted question that asked; We know that if $n$ zeros are inserted between every pair of successive terms of the sequence in LFSR (variable changed $x$ to $x^n$) then linear complexity (shortest LFSR which produces the given seq) will…
kelalaka
  • 48,443
  • 11
  • 116
  • 196
3
votes
1 answer

How to interpret Berlekamp-Massey algorithm?

I'm trying to find a way to understand the process of the Berlekamp-Massey Algorithm. But I'm struggling in understanding the fourth step of the process, which is $B^{(r+1)}(x) = A^{(r)}/\delta^{(r)}$. I found this algorithm from this paper, "VLSI…
ytj_banana
  • 51
  • 2
3
votes
1 answer

XOR LFSR and all zero state

I read this in a description of Linear Shift Feedback Registers Note that the allzero state must be excluded. If an LFSR assumes this state, it will get “stuck” in it, i.e., it will never be able to leave it again". I can understand why an all…
user93353
  • 2,191
  • 3
  • 23
  • 43
3
votes
0 answers

Period of LFSR sequence with reducible polynomial

I want to prove the following theorem: Let's assume a LFSR(Linear feedback shift register) sequence with a reducible characteristic polynomial of degree $n$ over the finite field $\mathbb{F}_q$. Under those assumptions, the minimal period of this…
math4ev
  • 31
  • 1
3
votes
1 answer

Linear Feedback Shift Registers analysis

Cryptanalysis of Linear Feedback Shift Registers. From this site I found that lfsr could be break by Berlekamp-Massey algorithm. What is the specific progress of this algorithm? And if there is any other way to do it
Asdeasdfs
  • 45
  • 8
3
votes
1 answer

Sequence output by a Galois type LFSR

I have provided a diagram of a Galois type LFSR. I am told it outputs a sequence of period 31. Find the sequence output by this LFSR. By applying the shifts I got the seemingly trivial answr of $0,0,0,0,1$ which I know must be wrong since it has a…
harry55
  • 139
  • 1
  • 7
3
votes
2 answers

Reverse output of general Fibonacci LFSR

Suppose we have some Fibonacci LFSR, and it outputs some sequence. How to change starting LFSR so, that it outputs exactly same sequence, but in reverse order?
Timo Junolainen
  • 235
  • 1
  • 10
3
votes
2 answers

Period of pseudo random sequence generated from (5, 2, 0) LFSR

I was reading about the Linear Feedback Shift Registers and I am confused about the technique to find the period of a primitive polynomial. Consider the polynomial $x^5 + x^2 + 1$. As this is a primitive polynomial, it should be a maximal period…
CryptoNovice
  • 31
  • 3
3
votes
1 answer

Nonlinearity of the J-K Flip Flop

In Encryption Schemes for Computer Confidentiality, Pless describes how to use the J-K flip flop as a nonlinear combiner for linear feedback shift registers. This generator was broken because the J-K flip flops are not correlation immune but my…
William Hird
  • 501
  • 1
  • 5
  • 18
1
2 3