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
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 ...
b degnan's user avatar
  • 4,830
17 votes
1 answer
5k 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 ...
Duncan Drennan's user avatar
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 ...
geo909's user avatar
  • 387
10 votes
2 answers
2k views

Why is the polynomial of an LFSR called so?

As far as I understand, the "polynomial" of the LFSR tells us the positions of the register where taps are situated. However, the natural way to look at the positions would be to think of them as $...
Agnishom Chattopadhyay's user avatar
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 ...
AttributedTensorField's user avatar
7 votes
2 answers
8k 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. ...
William Hird's user avatar
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 $\...
Rohit Khera's user avatar
6 votes
2 answers
1k 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 ...
gct's user avatar
  • 175
6 votes
1 answer
703 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 ...
Ollie's user avatar
  • 163
6 votes
1 answer
280 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? ...
kelalaka's user avatar
  • 48.8k
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,...
Dominic van der Zypen's user avatar
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 ...
Les's user avatar
  • 205
5 votes
2 answers
1k 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 ...
nist's user avatar
  • 153
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?
Learner's user avatar
  • 61
5 votes
1 answer
320 views

Algorithm or closed form solution that lets me directly compute the $n^{\text{th}}$ state of an LFSR?

I have a large linear feedback shift register with a known state and taps. Now I want to compute the state of the LFSR after $n$ iterations. The problem: $n$ is in the order of $2^{256}$ so just ...
Nils Pipenbrinck's user avatar
5 votes
1 answer
965 views

Are ciphertext-only attacks on LFSRs possible?

Reading about LFSR, I know that breaking an LFSR by knowing it's design and having enough (plaintext, ciphertext) pairs is an relatively easy task but let's assume we know the design of LFSR and a ...
Mehran Torki's user avatar
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 ...
Chang Lee's user avatar
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?
Tom's user avatar
  • 1,221
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) ...
Juxhin's user avatar
  • 53
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. ...
Incredible's user avatar
5 votes
1 answer
2k 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 ...
Arjun Londhey's user avatar
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?
Melab's user avatar
  • 3,655
4 votes
2 answers
4k 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 ...
geo909's user avatar
  • 387
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?
pacman's user avatar
  • 429
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 ...
Ievgeni's user avatar
  • 2,605
4 votes
2 answers
864 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 ...
DurandA's user avatar
  • 453
4 votes
1 answer
3k 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 ...
fgrieu's user avatar
  • 142k
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 ...
DurandA's user avatar
  • 453
4 votes
2 answers
946 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 ...
Melab's user avatar
  • 3,655
4 votes
1 answer
124 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,...
František Štrba's user avatar
4 votes
1 answer
3k views

How to convert a Galois LFSR to a Fibonacci LFSR?

I have just found the sequence output by the Galois type LFSR, seen here. Now I know there exists a Fibonacci-type LFSR capable of outputting this same sequence but how could I find what the first ...
harry55's user avatar
  • 139
4 votes
1 answer
942 views

Period, correlation and auto-correlation of non-linear feedback shift registers based sequences

Use of Linear Feedback Shift Registers(LFSR) is discouraged due to complexity of order of it's length. Recently Non-Linear LFSR has been talked about. I am curious how the properties of LFSR based m-...
Jay's user avatar
  • 195
4 votes
1 answer
391 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 ...
Thomas O's user avatar
  • 141
4 votes
1 answer
363 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: ...
qwer's user avatar
  • 177
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 ...
Lachlan's user avatar
  • 101
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 ...
zelda191919's user avatar
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 ...
William Hird's user avatar
4 votes
1 answer
529 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 ...
bradleyjkemp's user avatar
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 ...
forest's user avatar
  • 15.3k
4 votes
1 answer
797 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 ...
usr109876787's user avatar
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 ...
DurandA's user avatar
  • 453
3 votes
1 answer
744 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 ...
Nils Q.'s user avatar
  • 43
3 votes
1 answer
1k 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 ...
Hagge Knar's user avatar
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 ...
Asdeasdfs's user avatar
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?
William Hird's user avatar
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 ...
user93353's user avatar
  • 2,245
3 votes
2 answers
878 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;...
toshi's user avatar
  • 31
3 votes
1 answer
3k 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 ...
cHiMp's user avatar
  • 389
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 ...
Doğukan Karakaya's user avatar
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 ...
forest's user avatar
  • 15.3k