Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [lfsr]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
69 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 ...
0 votes
0 answers
36 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 ...
2 votes
1 answer
181 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 ...
2 votes
1 answer
404 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 ...
0 votes
2 answers
112 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$$...
2 votes
2 answers
420 views

On bent combining functions

Bent functions are Boolean functions with maximum nonlinearity and are widely studied for their potential applications in cryptography. Let's say you want to use a simple $2$-input AND gate as a ...
0 votes
1 answer
270 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 ...
4 votes
1 answer
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?
0 votes
0 answers
73 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 ...
4 votes
2 answers
148 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 ...
1 vote
0 answers
37 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},...
3 votes
2 answers
281 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 ...
3 votes
1 answer
127 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 ...
2 votes
0 answers
41 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 ...
4 votes
0 answers
400 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 ...
1 vote
1 answer
105 views

Size of nonlinear filter sequence to recover LFSR feedback polynomial

Let's suppose that there is a filter generator which based on $n$-size LFSR. Denote a feedback polynomial as $g(x_1, x_2, \dots, x_n)$ and nonlinear filter function as $f(x_1, x_2, \dots, x_n)$. Let $...
-1 votes
1 answer
122 views

Attack on cipher that adds modulo FF output of two LFSRs (LFSR-12 and LFSR-19)

LFSR-12 with poly $x^7+x^2+1$ and LFSR-19 with poly $x^{11}+x^5+1$ are used to produce 8 bit of output each, output is then added together modulo FF (LFSR-12+LFSR19)mod FF I know first 8 bytes (-> ...
1 vote
2 answers
1k 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 ...
4 votes
2 answers
297 views

Multiplication of two LFSR

Let $a_n$, and $b_n$ two sequences generated by two LFSR with connection polynomials $P$, and $Q$. How to show the sequence $(a_n \cdot b_n)$ can be generated by a LFSR wit connection polynomial of ...
4 votes
2 answers
2k views

How secure is the E0 stream cipher used in Bluetooth?

The question is about E0, the stream cipher used to secure Bluetooth communication. The impression I get is that it's more secure than A5/1. Also, why wasn't AES used instead?
3 votes
1 answer
224 views

Streams Ciphers - Linear feedback shift register logic behind design

I’m just seeking a better understanding as to the logic behind design of the A5/1 cipher’s keystream generator. Why are the registers degree chosen in such a fashion (19,22 and 23 bits long ...
1 vote
2 answers
65 views

Linear complexity of real and complex sequences

In cryptography output sequences of stream ciphers are binary valued (or more generally finite field valued). However mathematically sequences over real and complex variables can also be generated by ...
1 vote
1 answer
2k 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 ...
0 votes
0 answers
292 views

Attack against stream cipher (LFSR with ASCII)

I'm reading Understanding Cryptography by Christof Paar and Jan Pelzl. In chapter 2 (Stream Ciphers) there's a question that goes like this: Assume we have a stream cipher whose period is quite short....
3 votes
1 answer
2k 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?
6 votes
3 answers
256 views

Majority-based feedback shift register

Linear feedback shift registers (LFSR's) work by taking a fixed-length bit-string $b\in\{0,1\}^n$, as well as fixed "taps" (bit positions) and applying XOR to the taps, giving one output bit,...
2 votes
2 answers
181 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, ...
19 votes
0 answers
466 views

Adding bit constants to the key schedule to reduce rounds?

Bit constants are often added to the key schedule to reduce slide attacks. I have reviewed David Wagner's work, where he showed that the increased rounds in a Feistel network do not help if you have ...
3 votes
1 answer
358 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 ...
9 votes
1 answer
9k 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 ...
1 vote
3 answers
689 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 ...
1 vote
1 answer
286 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 ...
2 votes
3 answers
2k views

LFSR Tap sequence 15 bit LFSR

I have been asked to create an LFSR with a polynomial of x^15 + x + 1 and i am confused where the tap sequence would go. The examples I was given show a 4 bit tap sequence with two polynomials: x^3 + ...
1 vote
1 answer
679 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 ...
2 votes
1 answer
439 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 ...
1 vote
1 answer
103 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 ...
3 votes
1 answer
1k views

How to clock a linear feedback shift register?

I have some trouble understanding what happens when a LFSR is clocked. I have tried many examples but I do not get the correct result. Can anyone point out my errors? I have the following polynomial: ...
4 votes
1 answer
1k 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 ...
1 vote
1 answer
2k 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 ...
2 votes
2 answers
2k 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 ...
3 votes
1 answer
2k 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 ...
0 votes
0 answers
104 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 ...
1 vote
2 answers
623 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 ...
2 votes
0 answers
173 views

LFSR, different bits from different initial states

Suppose we use an LFSR, which gives output $x_1x_2x_3\dots$ from some particular initial state. From another state, different from the previous one, using the same LFSR though, it gives sequence $...
3 votes
2 answers
200 views

Profile Complexity of an LFSR

I am trying to understand how the linear complexity profile of an LFSR is calculated. For example, I have the bit sequence $110101$ and its profile $1 1 2 2 3 3$. Is there any easy way to produce the ...
1 vote
2 answers
275 views

Is it correct that for a n-bit LFSR (Galois algorithm in particular), the maximum number of unique 32-byte keys can only be 255?

In fact, I have more than one question. For a CTF challenge, I am currently reading up on LFSRs. The code the challenge provides as an example is a 5-bit LFSR, and it generates from its bit sequences ...
4 votes
1 answer
949 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 ...
7 votes
1 answer
1k views

Galois LFSR Subsequence Periodicity

I had the following questions - Concerning generating sequences of bits $\textbf{x} = ( x_{0},x_{1}, ... , x_{n-1})$ where the $x_{i} \in \{0,1\}$ are considered coefficients of a polynomial in $\...
4 votes
1 answer
496 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
1 answer
719 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?