Skip to main content

Questions tagged [lfsr]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
221 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
1 answer
284 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
0 answers
84 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
2 answers
878 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 ...
5 votes
2 answers
196 views

Rueppel's example of self-clocking LFSR

Consider the following excerpt from Rueppels paper, titled When Shift Registers Clock Themselves: His example includes $C(D) = 1 + D + D^2 + D^3 + D^4 + D^5$ as a primitive connection polynomial. ...
1 vote
1 answer
361 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
0 answers
335 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
1 answer
58 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
1 answer
846 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
1 answer
544 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 ...
5 votes
1 answer
3k views

Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey

Edit Does the state register (the LFSR) always have to remain with 16 bits (I'm assuming yes). If so, are we shifting the register right by one (lfsr>>1) ...
2 votes
1 answer
130 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 $...
6 votes
1 answer
706 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 ...
0 votes
1 answer
157 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
0 answers
183 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 ...
4 votes
1 answer
126 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,...
5 votes
1 answer
4k 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 ...
3 votes
1 answer
1k 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
1 answer
161 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 ...
1 vote
1 answer
151 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?
6 votes
1 answer
2k views

LFSR Jump Ahead Algorithm

A related question has been asked and answered here. My question is specifically about figuring out C for very large J. I have searched the web and found many scholarly articles on "jump ahead" and ...
1 vote
1 answer
1k 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,...
1 vote
1 answer
99 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?
2 votes
0 answers
95 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: ...
4 votes
1 answer
125 views

Difference between one-level and two-level E0 encryption

I am trying to understand the practical security implications of the way E0 is used in Bluetooth 2.1 devices. In reading up on the subject, I am seeing that encrypting a large amount of data with E0 ...
2 votes
1 answer
193 views

LFS Kolmogorov Randomness

Consider following LFS register (where + denotes addition modulo 2) I have found the output sequence as 1,0,1,1. I know that The K(s) of a string s is defined as the length of the shortest computer ...
1 vote
0 answers
58 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
1 answer
971 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 ...
0 votes
1 answer
2k views

Cipher feedback mode with shift registrers

Can someone please explain to me how the Cipher Feedback Mode works? From what I have read some examples have a shift register in its explanation but some examples don't. Is there two versions of CFB ...
3 votes
1 answer
597 views

iOS Data Protection: What is the Input of the LFSR?

Every time a file on the data partition is created, Data Protection creates a new 256-bit key (the “per-file” key) and gives it to the hardware AES engine, which uses the key to encrypt the file ...
0 votes
1 answer
185 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
1 answer
468 views

Upper bound Linear Feedback Shift Register

It is clear that when we have any output stream $x_0,x_1,...$ produced by linear-feedback shift register, then this output has to be periodic. Now I was wondering if we can find an upper bound for ...
4 votes
2 answers
959 views

When does a feedback shift register count as non-linear?

It seems that a feedback shift register is counted as a linear feedback shift register whenever it only includes XOR operations. This leads me to believe that a non-linear feedback shift register is ...
11 votes
2 answers
4k views

Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?

Linear Feedback Shift Registers (LFSRs) can be excellent (efficient, fast, and with good statistial properties) pseudo-random generators. Many stream ciphers are based on LFSRs and one of the possible ...
2 votes
0 answers
74 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
1 answer
1k 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 ...
-1 votes
1 answer
4k 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 ...
2 votes
0 answers
185 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
0 answers
251 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 ...
1 vote
2 answers
694 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 ...
5 votes
2 answers
2k views

Why are stream ciphers based on linear-feedback shift registers so popular?

I was conducting research on stream ciphers and LFSRs was a subtopic of my research and I was wondering why are LFSRs so popular?
1 vote
2 answers
543 views

Can a LFSR has more than one repeat cycle?

It's clear that an LFSR has finite states and eventually will end up with repeating cycle. However, is it possible for an LFSR to have more than one repeating cycle? For example, with initial state $A$...
3 votes
2 answers
1k views

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

period of the lfsr sequence after some manipulations

Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate: Given 3 maximum length (max period) LFSR's of lengths L1,...
2 votes
1 answer
693 views

Attack on stream cipher that XOR's the output of two LFSRs

There are two LFSRs of different lengths: LFSR-17 and LFSR-25. LFSR-17 Initially contains a two byte seed, with a 1 injected into the fourth bit, for a total of 17 bits. LFSR-25 operates in the same ...
1 vote
0 answers
258 views

Why does the Content Scrambling System have two different length LFSRs

CSS uses two LFSRs of length 17 and 25. If we have two periodic functions $f(t)$ and $g(t)$ and consider the function $h(t) = (f(t), g(t))$, then $h$ will have period $pq/\gcd(p, q)$ where $p$ and $q$...
1 vote
0 answers
406 views

How to use Galois LFSR to find multiplicative inverses

My question is how can a Galois Linear Feedback Shift Register be used to discover multiplicative inverses of polynomials? This is a homework assignment. Here is a list of things I did before asking ...
3 votes
1 answer
904 views

Find a LFSR given 2n (or more) non-consecutive keystream bits

How can I calculate the polynomial and state of a LFSR given 2n (or more) non-consecutive keystream bits? It is known to be n bit. If they were consecutive, I could use the Berlekamp–Massey algorithm. ...
0 votes
1 answer
218 views

Expected Linear Complexity of a sequence

Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)? I have no idea of the answer to this question? What ...
1 vote
1 answer
1k views

Confused by the definition of Linear Complexity of an LFSR sequence?

The Linear Complexity of a sequence is defined as the length of the shortest LFSR that produces this sequence. It also corresponds to the degree of the minimal polynomial ( i.e. the smallest ...