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

learn more… | top users | synonyms

0
votes
0answers
23 views

how to prove sequence y uphold golomb's third axiom

given $\{ x_k \}$ is a m-seq of order $n$, we define $\{ y_k \}$ to be a $m$ digits number: $$ y_i=x_ix_{i+1}...x_{i+m-1} $$ for every integer $n \ge m \ge 1$ how can I show that $\{ y_k \}$ upholds ...
1
vote
0answers
27 views

References for combining LFSRs with different lengths and taps?

I started learning streams ciphers with the use of LFSRs. Therefore, I tried to simulate what I am learning in a C sourcecode, which combines three registers and ...
1
vote
1answer
66 views

Degree of M and Max Sequence Length for LFSR

For the LFSR mod 2, determine the degree of m and maximum sequence length s_(i+3)≡ s_i+s_(i-2)+s_(i-4) mod 2 determine the degree of m and the maximum ...
2
votes
2answers
65 views

Profile Complexity LFSR

I try to understand how Complexity of an LSFR calculated. For example I have a bit sequence 110101 and it's profile 1 1 2 2 3 3. Is there any easy way in order to produce the profile?
1
vote
0answers
21 views

LFSR, different bits from different initial states

Suppose we useLFSR, which gives output $x_1x_2x_3\dots$ from some particular initial state. From another state, different from previous, same LSFR though, it gives sequence $y_1y_2y_3\dots$ ...
2
votes
1answer
71 views

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?
1
vote
1answer
62 views

Finding Galois LFSR and its initial configuration

Suppose recursion for output of Galois LFSR is $u_1=u_3=u_4=0$ What kind of taps are here, and initial state? How to uncover this information?
0
votes
1answer
16 views

Fibonacci LFSR, recovering previous bits

Suppose somewhere is Fibonacci LFSR, we know that it has 7 cells and feedback taps are cell 2 and 7. We intercepted part of a stream, and part intercepted is 1010101. Is it possible to recover ...
4
votes
1answer
39 views

Given occasional LFSR samples can the next sample be computed?

Suppose I have access to an LFSR generator output used in a radio communications system, with the LFSR being used to authenticate devices. The system cycles an internal unknown length LFSR (greater ...
1
vote
1answer
65 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 ...
1
vote
1answer
165 views

Split 32-bit LFSR into two 16-bit LFSR which xor to same sequence [duplicate]

Today I was thinking about exactly this. Is it possible, for a 32-bit LFSR e.g. ...
2
votes
0answers
248 views

Difference between statistical PRNG and cryptographic PRNG? [duplicate]

What's the difference between a statistical pseudorandom number generator (PRNG) and a cryptographic-strength PRNG? I've seen a lot of PRNGs that are proposed for statistical uses -- e.g., ...
1
vote
1answer
416 views

Attack an stream cypher using 2 XORed LFSRs

We know that the Key were generated by 2 16Bit LFSRs (output of both is XORed together -> key) I already extracted a 64 Bit key sequence, but how can I calculate the polynom of the LFSRs (and the ...
2
votes
2answers
183 views

Are LFSRs enough for this?

Consider the following experiment: Let there be a machine which runs (ie. continually clocks) an LFSR of size (ie. number of bits) $b$, having a button that, when pressed, extracts the next $t$ ...
1
vote
1answer
344 views

Message encrypted with a LFSR based stream cipher

I am learning about LFSR sequence and I came across this question: A 16-bit message consists of two ASCII characters. This message was encrypted with a one-time pad, and the key for the one-time pad ...
1
vote
2answers
115 views

Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$? [closed]

Is there an efficient way to map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?
6
votes
2answers
394 views

Determine LFSR phase quickly?

I know it's possible with work backwards from the output bits of an LFSR to determine its feedback polynomial in a O(n) fashion. I'm also curious if, given an LFSR state and polynomial, is it ...
2
votes
1answer
314 views

LFSR Output Sampling for Berlekamp-Massey

Looking at the use of Linear Feedback Shift Registers in cryptographic algorithms, I have learned that the Berlekamp-Massey algorithm can be used to find the (shortest) LFSR that generates a given ...
1
vote
1answer
120 views

LFSR and Markov chain question [closed]

This may seem an elementary question about LFSRs, and their link to Markov chains. LFSRs show Markov chain behaviour in that there can be a transition matrix defined over the LFSR, this follows from ...
1
vote
0answers
67 views

Berlekamp-Massey algorithm, correct stepping

I'm trying to use the Berlekamp-Massey algorithm on the following bit sequence: 0 1 0 0 1 0 0 1 0 1 I have the correct answer and most of the approach to get there, but I'm unable to fill in what I ...
2
votes
1answer
211 views

Berlekamp-Massey to construct minimal LFSR

Given the sequence 0010001111 (or any other, not homework, but exam practice), how do you use the Berlekamp-Massey algorithm to construct a minimal LFSR? I have read several definitions of how ...
3
votes
1answer
293 views

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 ...
3
votes
1answer
341 views

Convert m-Sequence into a de Bruijn Sequence

In his paper Alternating Step Generator Controlled by de Bruijn Sequence, C.G. Günther states on page three that a de Bruijn sequence (..) can easily be obtained from an m-sequence (maximal length ...
3
votes
1answer
1k views

LFSR get output from characteristic polynomial?

Say you have a characteristic polynomial of an LFSR: $$f(X) = X^4 + X^3 + 1$$ How can I use this function f to get the output of the LFSR, given some initial state? Obviously I can create the LFSR ...
3
votes
1answer
550 views

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

Can a LFSR be cryptographically secure?

I have been looking at an embedded microcontroller which has a cryptographic hardware engine (in particular the PIC32MZ family). These devices have what they advertise as a cryptographically secure ...
-4
votes
1answer
112 views

What is the best (thoroughly covering) textbook for application of LFSRs in cryptography? [closed]

What is the best (thoroughly covering) textbook for application of LFSRs in cryptography? (Beside Cipher Systems by Beker & Piper)
2
votes
1answer
144 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 than this output has to be periodic. Now I was wondering if we can find an upper bound for ...
2
votes
1answer
258 views

How to prove this LFSR equation?

I am having difficulty solving part (ii) of Excercise 5.17 from Becker's Cipher Systems. Exercise 5.17 $\quad$If $f(x),g(x)$ are any two polynomials over $GF(2)$ with $f(0)=g(0)=1$ show that ...
3
votes
1answer
214 views

Feasibility of using a base 26 LFSR for cryptography by hand

I have been playing with base 26 LFSRs (i.e. using the alphabet) and noticed that the XOR operation for base 26 is just the tabula recta and so can be done very quickly. This made me wonder whether a ...
2
votes
1answer
576 views

LFSR using words

If I've got an LFSR, let's say a 16-bit Fibonacci LFSR as shown in the corresponding wikipedia article, which generates maximum length sequences, could I use it to create word sequences instead of bit ...
5
votes
2answers
1k 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
2answers
1k views

Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR

Suppose that we have a sequence of $N$ digits which is produced by a Linear Feedback Shift Register (LFSR) and the shortest such LFSR is of length $L$. A very important tool in cryptanalysis of stream ...
3
votes
2answers
535 views

Number of states in a LFSR

Do all $2^{\ell}$ (where $\ell$ is the bit length of the shift register) states always occur in a LFSR or can I choose my taps badly so some states are skipped and the period is shortened? If so is ...
4
votes
2answers
2k views

Cryptanalysis of Linear Feedback Shift Registers

It is well known that simple m-sequence linear feedback shift registers have a linear algebraic structure and therefore the generator seed can easily be deduced using the Berlekamp-Massey algorithm. ...
4
votes
1answer
280 views

LFSR dynamic mutation

In normal LFSR, the state is a function of the initial seed, taps positions and time, nothing else. I've seen a modification of LFSR that works like this: ...
3
votes
1answer
728 views

Linear Feedback Shift Register Taps

Linear feedback shift register tap charts are availale for registers of length 3 to 168. Does anyone have a chart for register lengths from 168 to 256 or beyond? Thank you.