Questions tagged [lfsr]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
337 views

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 ...
1
vote
1answer
77 views

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 ...
1
vote
3answers
154 views

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 ...
0
votes
0answers
34 views

Why LFSR stream code is not suitable for encryption? [duplicate]

Why LFSR stream code is not suitable for encryption? Is there a special attack for LFSR?
1
vote
1answer
94 views

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 ...
0
votes
1answer
45 views

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 ...
0
votes
0answers
43 views

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 ...
2
votes
2answers
99 views

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, ...
1
vote
2answers
88 views

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 ...
4
votes
1answer
208 views

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 ...
4
votes
1answer
123 views

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 ...
5
votes
1answer
351 views

What does that mean, that A5/1 is clocked?

What does that mean, that A5/1 is clocked? What happens if the clocking bit agrees with the majority bit?
3
votes
1answer
124 views

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 (...
6
votes
1answer
116 views

Is there a library that output LFSR images given parameters?

I'm looking for a library that given parameters; feedback polynomial, initial values then it will produce $\LaTeX$ / Tikz codes to include in Latex documents or LFSR images. Is there such a library? ...
2
votes
0answers
45 views

Is there a way to find the two generator polynomials of a JPL sequence?

I am decoding a binary sequence that was detected as an unpractically long LFSR by the Berlekamp-Massey algorithm. First of all, the generated sequence is far longer than it needs to be and since it ...
4
votes
1answer
349 views

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 ...
4
votes
2answers
416 views

Is a LFSR sufficient for post-processing a biased TRNG?

I am building a TRNG on a FPGA based on ring oscillators. I found out that Linear Feedback Shift Registers (LFSRs) are commonly used for the post-processing of TRNGs. Here is my initial design: Let's ...
1
vote
1answer
77 views

Listing first 8 bits generated by LFSR

Consider the primitive polynomial P(x) = x^4 + x^3 + 1, initialized with the bit string (shifting occurs from left to right, were the right-most bit represents the LFSR output): 1101. List the first 8-...
0
votes
0answers
75 views

How to find the matrix of LFSR output?

I am trying to find polynomial , but don't know how to get matrix matrix must look something like this:https://www.oreilly.com/library/view/computer-security-and/9780471947837/sec8.8.html For example ...
3
votes
1answer
45 views

Is there a way to bound linear complexity of a sequence less than its period

Linear complexity of a sequence $s_0,s_1,\ldots$ over a finite field is the shortest length $n$ of linear recurrence of the sequence such that $s_{n+j}=\sum_{i=0}^{n-1}a_is_{i+j}$ for $j=0,1,2,\ldots$ ...
3
votes
1answer
127 views

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)}$....
1
vote
1answer
147 views

Breaking the 40 bit DVD CSS stream cipher

This is from the transcript of Dan Boneh's Coursera Crypto course https://www.coursera.org/learn/crypto/lecture/mQAkP/real-world-stream-ciphers So it turns out this is easy to break in time roughly ...
1
vote
1answer
547 views

Decrypting LFSR, knowing the beginning of the cyphertext, and nothing else

I have a cipher-text in binary, I know the beginning of the plain-text. I know that it is encrypted using LFSR, and I know nothing else. How can I attack, and decrypt it? What I have tried; I ...
0
votes
2answers
246 views

Why are LFSRs represented as polynomials?

Disclaimer: I am neither an electronics engineer nor am I a mathematician. I understand what an LFSR is. I can derive the periodic sequence if an LFSR is described by it's taps. My question is - why ...
2
votes
1answer
480 views

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 ...
2
votes
1answer
90 views

autocorrelation of non-linear shift register with the period of $2^n$ (full period)

throughout the question I will talk about sequences in bipolar alphabet, meaning, over {1,-1}. I have read in the book Shift Register Sequences by Solomon W. Golomb that sequences with the period of $...
5
votes
1answer
545 views

Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights?

I am in need of a non-uniform random number generator where each n-bit output has a hamming weight with a certain binomial distribution. For example, I would like a non-uniform PRNG which generates ...
3
votes
0answers
97 views

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 ...
2
votes
2answers
598 views

Attack on LFSR key stream generator

Alright this is a question I found on one of my books: Given is a stream cipher which uses a single LFSR as key stream generator. The LFSR has a degree of 256. How many plaintext/ciphertext bit ...
0
votes
1answer
75 views

What does "Clocked" mean in alternating step generators

In the wiki article, it says "An ASG comprises three linear-feedback shift registers, which we will call LFSR0, LFSR1, and LFSR2 for convenience. The output of one of the registers decides which of ...
3
votes
1answer
84 views

Explanation of $z^{-1}$ and $T_{1,2}$ within E0 Bluetooth encryption algorithm

I am trying to understand how E0 Bluetooth algorithm exactly works. I know that $y_t$ is the sum of $x_1$ to $x_4$ and can take values $0, 1, 2, 3, 4$. Also $S_{t+1}$ = $(y_t + c_t)/2$ and can be $\{0,...
1
vote
1answer
80 views

Forward Security of Symmetric Encryption Schemes with LFSR based PRNG

Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?
1
vote
1answer
84 views

M-Sequence Properties in LFSR

I test this law with a 7-bits primitive polynomial LFSR. and the run property could be found according to output. Is there any theoretical to prove m-sequence property, I could just find some ...
3
votes
1answer
759 views

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 ...
1
vote
1answer
717 views

Understanding LFSR stream ciphers and the content scrambling system

I'm a little confused over how exactly Linear Feedback Shift Registers (LFSR) work, I kind of get it, but not really, can someone help me understand it? I know it XORs bits in a loop against some mask,...
2
votes
1answer
162 views

Are there any LFSR-based ciphers with variable feedback polynomials?

All LFSR-based stream ciphers that I know of use a fixed feedback polynomial (i.e. the taps are always in the same position). I know that, at least for non-trivial output lengths, it is necessary to ...
2
votes
0answers
68 views

Known-plaintext attack against E0 with 2745 bits per frame instead of 24

In the paper The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption, an attack against the E0 cipher is described which can break it efficiently in a known-plaintext attack: ...
1
vote
0answers
52 views

MULalpha and DIValpha operations in SNOW 3G

I'm not able to appreciate the importance of mul alpha and div alpha operations in feedback polynomial of LFSR in SNOW 3G. What problems or weakness do they help in mitigating and how ?
2
votes
1answer
327 views

How to perform the lfsr scrambling used in PCIe for 2 byte input?

In PCIe Gen 3 on-wards there is 128b/130b encoding used which scrambles incoming bit using a LFSR with polynomial: $$G(X) = X^{23} + X^ {21} + X^{16} + X^{8} + X^5 + X^2 + 1.$$ Is there any way to ...
1
vote
1answer
76 views

About LFSR based M209 Cipher Machine

Can some one please express M209 Cipher Machine in terms of LFSR with Diagram or any simple method?
0
votes
1answer
175 views

Mixing Cipher Lower Bounds

Let Z be a cipher system consisting of three m-sequence linear feedback shift registers (LFSR) of length 128 bits each which are assumed to be not cryptographically secure and the registers are seeded ...
2
votes
0answers
60 views

LFSR expected period

What is the expected value of the length of the period of a n-bit linear-feedback shift register with a random tap? I am asking because I am curious what security issues would appear if the tap would ...
1
vote
1answer
698 views

LFSR: finding the period for an irreducible Polynomial

From what I understand an LFSR produces a maximal length sequence if its characteristic polynomial $p(x)$ of degree $n$ is irreducible, i.e. if it cannot be factored and the smallest integer $k$ for ...
2
votes
1answer
163 views

Building an LFSR logical bitmap using characteristic polynomials

How would one build an LFSR logical map, with a characteristic polynomial such as $$P(x) = x^4 + x^3 + 1$$? Also, how would you interpret it, and what would you do to do the reverse it in order to ...
-2
votes
1answer
2k views

How to crack LFSR with known plain text attack?

I'm learning stream ciphers and I'm at LFSR cipher, and I've been trying to solve the question that states if given a 5th degree lfsr with the cipher text ...
5
votes
1answer
2k views

Relationship between Fibonacci LFSR and Galois LFSR

I'm studying about LFSR and have some troubles understanding LFSRs. For Galois LFSR, it is clear that LFSR just multiplies $x$, the primitive element of $GF(2^n)$, so that it makes all the elements ...
1
vote
1answer
932 views

How many bits are needed for an LFSR to generate a specific number of sequences?

I need to generate 64-bit data sequences 16 times pseudorandomly. How many bits should the linear-feedback shift register (LFSR) have in order to do so? That is, what is the number of bits for the ...
1
vote
0answers
175 views

Explaining Berlekamp-Massey Algorithm in simple/layman term?

My foundation in Mathematics is not great. But I would like to understand how Berlekamp-Massey Algorithm works and how it is used in lay-man terms. The only thing I find out there is the emphasis on ...
2
votes
0answers
170 views

Understanding LFSRs and Berlekamp-Massey Algorithm [duplicate]

I have a tutorial question which focuses on LFSRs and Berlekamp-Massey Algo (which is totally out of my syllabus). Please forgive me if my questions seem stupid. I'm given these information: {"...
1
vote
2answers
498 views

Berlekamp Massey Algorithm

I am trying to solve the BM algorithm to find the shortest LFSR and the feedback polynomial but i keep getting stuck. Is there anybody who could solve any binary code so the steps could be little ...