# Tagged Questions

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

73 views

### How to design a balanced LFSR with period 1023 and linear span 55?

I am trying various combination of LFSR's to try to design sequence of period 1023. The linear span should be 55 and the output 1023 bits has to be balanced. I have tried with five LFSR's with degree ...
47 views

### How do you do a linear feedback shift register?

I saw a video on YouTube by Daniel Rees. The video was about stream ciphers and showed how to do a linear feedback shift register. The example that was used to demonstrate how to do it is was like ...
89 views

### Finding all polynomials up to a given degree to generate a bit sequence

Consider the following bit sequence: 00100000110 Using Berlekamp-Massey algorithm we can find the following minimal degree polynomial: $P(x)=x^6 + x^5 + x^4 + 1$ Now, is there a way to find all ...
101 views

### How to prove a function is pseudorandom function?

I am currently enrolled in a cryptography course, which uses the book by Katz and Lindell. I am using a function having $F_{k}$ = $A_{k}(B_{k}(r,m),r)$, the random number is generated using the ...
16 views

### Testing the first 40 bit sequence for A5/1 if all registers initialized to 1

I have an assignment where my instructor asked to generate the first 40 bits for an A5/1 algorithm if all registers are initialized to '1' initially . I have implemented the algorithm successfully ...
36 views

### Would A5/1 with a much larger state be a good choice of stream cipher for hardware?

Would A5/1 with a much larger state be a good choice of stream cipher for hardware? Assume that a reasonable choice of MAC is made such as GMAC, with the first 128 bits of the stream cipher output ...
29 views

### Multiplexed stream cipher

Consider the stream cipher that consists of 3 LFSRs, with the output of one coming being used to determine which of the other 2 is used that clock cycle. Both the IV and the polynomials are secret. ...
77 views

### Non primitive lfsr sequence

Given a non-primitive LFSR sequence (i.e number of states is less than $2^n - 1$); how do we find out the the characteristic polynomial? Will Berlekamp-Massey algorithm work in this case? for example;...
47 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 ...
33 views

### References for combining LFSRs with different lengths and taps? [closed]

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 ...
91 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 ...
82 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?
25 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$ ...
165 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?
91 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?
19 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 (...
45 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 ...
82 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 ...
215 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. ...
251 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., ...
431 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 ...
187 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$ ...
487 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 ...
119 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$?
455 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 ...
410 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 ...
129 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 ...
77 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 ...
286 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 ...
309 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 ...
570 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 ...
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 ...
623 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 ...
1k 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 ...
115 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)
148 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 ...
266 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 ...
233 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 ...
672 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 ...
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 ...
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 ...
551 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 ...
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. ...