# Questions tagged [lfsr]

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

164 questions
Filter by
Sorted by
Tagged with
42 views

Note: The notation from this problem is from Understanding Cryptography by Paar and Pelzl. Suppose you have an LFSR with 6 state bits. The first 12 bits of output produced by this LFSR are ...
27 views

### Can I get the taps and the initial state of an lfsr, just knowing a part of the final keystream?

So, imagine you have an lsr sequence like this: 1101 0111 1000 1001 That has been obtained from the initial sequence: 1011 ...
32 views

### Sequences over groups and multiplicative recurrences

Feedback shift registers (FSRs) with nonlinear feedback function produce recurring sequences which satisfy polynomial recurrence relations defined by the feedback function. If the register cells are ...
• 171
84 views

### Proof of theorem by Lin and Costello

I want to prove the following theorem in LFSR: If $f(x)$ is a polynomial in $\text{GF}(2)$ with exponent $e$, which means $f(x) \mid x^e + 1$. I want to prove that $e \le 2^n -1$. I had some attempts ...
37 views

### Why is firmware implementation not preferred for more lfsr based encryption schemes?

Given that an algorithmic implementation of a linear feedback shift register based encryption scheme is (much?) more secure against side channel attacks; why are hardware platforms usually used? I get ...
• 1
221 views

### How to identify if a legacy encryption algorithm used in my programming language is secure?

I used an open-source programming language called Lucee / Cfscript that is closely related to Adobe Coldfusion. The default function that developers use to encrypt and decrypt data (usually for ...
• 123
413 views

### Decrypting 3 Binaries | LFSR

I have three binary arrays each one representing the pixels of an image. For example, if the picture size is 100 pixels X 100 pixels. Then the binary array would be 100×100×8×3 bits. These files are ...
176 views

### Finding the polynomial for LFSR given it's length and output

Let's say that i know that the output of an LFSR with length 4 is 1,1,1,0,0,1,1. Constructing the 3 equations modulo 2: $$s_{4} = \sum\limits_{i=1}^{4}c_{i}s_{4-i} \Leftrightarrow c_{2}+c_{3}+c_{4}=0$$...
308 views

### Determining the coefficients of a binary LFSR

I am currently leaning about LFSRs. I was told that a binary LFSR with length m has a form of $s_m=a_0s_0+a_1s_1+\ldots+a_{m-1}s_{m-1}$ are binary numbers. $a_0\ldots a_{m-1}$ are hidden and we are ...
1k views

### Why do Mersenne Twister use Mersenne prime but not regular prime numbers

I'm trying to figure out why Mersenne Twister use exactly Mersenne prime numbers but not regular primes. What makes Mersenne prime numbers more appropriate for this role than regular primes?
• 459
81 views

### Distinct sequences in a Fibonacci LFSR

How many distinct sequences can a $128$-bit Fibonacci LFSR (considering $4$ taps set for the maximum period) generate? Will all $2^{128} - 1$ distinct seeds produce distinct sequences? Also, let's say ...
161 views

### Is there a standard for LFSRs to test against for use in a stream cipher?

I am trying to implement a stream cipher that uses an LFSR PRNG. I have found resources online that give good primitive polynomials, but I am struggling to find resources with the initial states as ...
• 101
1 vote
41 views

### Find Linear Complexity of sequence beginnings

I know that in order to find the linear complexity of the two sequence beginnings (1,-1,0,-1,0,0,0,0,1,0,\dots)\in\mathbb{Z}_3^\mathbb{N}\\ (2,0,-1,-2,0,0,-2,2,-1,-2,\dots)\in\mathbb{Z}_5^\mathbb{N},...
• 111
129 views

### What is the result of not connecting the 1st register to the xor gate in LFSR?

I designed 8 bit lfsr in vhdl. According to mathematical theory, I xor processed the outputs of registers 1, 4, 5, 6 and 8 and connected them to the input of register 1. theory says that if I give the ...
44 views

### How to find linear complexity of non binary prime fields using berlekamp_massey algorithm in Sagemath?

I am having a prime field of large size (assume it of the type GF(2**18)) and I need to find linear complexity of a sequence (of some specified length) defined on ...
1 vote
119 views

• 121
718 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 ...
• 163
189 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 ...
• 31