Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [lfsr]

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

2
votes
1answer
60 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 ...
0
votes
0answers
44 views

How many bits needed for the LFSR to generate a specific number of sequences

I need to generate 64bit data sequences for 16 times pseudo randomly. How many bits should the linear feedback shift register have to be able to do so? I mean what is the number of bits for the ...
1
vote
0answers
59 views

Explaining Berlekamp-Massey Algorithm in simple/layman term?

My foundation in Mathematics is not great. But I would like to understand how Berlekamp-Massey Algorithm works and how it is used in lay-man terms. The only thing I find out there is the emphasis on ...
2
votes
0answers
45 views

Understanding LFSRs and Berlekamp-Massey Algorithm [duplicate]

I have a tutorial question which focuses on LFSRs and Berlekamp-Massey Algo (which is totally out of my syllabus). Please forgive me if my questions seem stupid. I'm given these information: {"...
1
vote
2answers
118 views

Berlekamp Massey Algorithm

I am trying to solve the BM algorithm to find the shortest LFSR and the feedback polynomial but i keep getting stuck. Is there anybody who could solve any binary code so the steps could be little ...
3
votes
2answers
208 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?
1
vote
2answers
84 views

Can a LFSR has more than one repeat cycle?

It's clear that an LFSR has finite states and eventually will end up with repeating cycle. However, is it possible for an LFSR to have more than one repeating cycle? For example, with initial state $A$...
5
votes
1answer
652 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) ...
2
votes
1answer
100 views

Attack on stream cipher that XOR's the output of two LFSRs

There are two LFSRs of different lengths: LFSR-17 and LFSR-25. LFSR-17 Initially contains a two byte seed, with a 1 injected into the fourth bit, for a total of 17 bits. LFSR-25 operates in the same ...
1
vote
0answers
29 views

Why does the Content Scrambling System have two different length LFSRs

CSS uses two LFSRs of length 17 and 25. If we have two periodic functions $f(t)$ and $g(t)$ and consider the function $h(t) = (f(t), g(t))$, then $h$ will have period $pq/\gcd(p, q)$ where $p$ and $q$...
1
vote
0answers
93 views

How to use Galois LFSR to find multiplicative inverses

My question is how can a Galois Linear Feedback Shift Register be used to discover multiplicative inverses of polynomials? This is a homework assignment. Here is a list of things I did before asking ...
1
vote
1answer
90 views

LFS Kolmogorov Randomness

Consider following LFS register (where + denotes addition modulo 2) I have found the output sequence as 1,0,1,1. I know that The K(s) of a string s is defined as the length of the shortest computer ...
0
votes
1answer
68 views

Expected Linear Complexity of a sequence

Let (s) be a sequence of length n. What are the expected linear complexities of (s) and $(s)^{\infty}$ (meaning that the periodic version of s)? I have no idea of the answer to this question? What ...
1
vote
1answer
100 views

Confused by the definition of Linear Complexity of an LFSR sequence?

The Linear Complexity of a sequence is defined as the length of the shortest LFSR that produces this sequence. It also corresponds to the degree of the minimal polynomial ( i.e. the smallest ...
2
votes
1answer
102 views

period of the lfsr sequence after some manipulations

Here is the question I am dealing with. I have some sort of a solution but I need more specific results. If someone can help I'd appreciate: Given 3 maximum length (max period) LFSR's of lengths L1,...
3
votes
2answers
392 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 ...
2
votes
1answer
71 views

Unbalanced Feistel network only generates complete permutations with square lengths

I'm generating permutations with a generalized Feistel network which will output integer values $r_j$ in a specified range $[0,period]$ pseudo-randomly, according to the counter input, which will then ...
2
votes
1answer
129 views

Reproducable pseudorandom permutation

I there a way to calculate two similar pseudorandom periodic sequences by exchanging some sort of initial value and generator polynomial? Like a linear-feedback shift register but with a finite ...
7
votes
0answers
144 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 ...
1
vote
1answer
67 views

Looking for title of encryption machines book

I am looking for a title of book in the field of stream crypography. I vaguely remember, that I saw this book at online shop (maybe amazon) near 5-10 years ago. This book is devoted to electronic ...
3
votes
1answer
279 views

Find a LFSR given 2n (or more) non-consecutive keystream bits

How can I calculate the polynomial and state of a LFSR given 2n (or more) non-consecutive keystream bits? It is known to be n bit. If they were consecutive, I could use the Berlekamp–Massey algorithm. ...
1
vote
0answers
48 views

Can I deduce the info such as the bitsize of an LFSR from multiple ciphertext messages?

If I encrypt the same message multiple times (>10000 times) with the same LFSR can I then somehow retrieve some information on the LFSR? I'm looking for information like bit size, polynomial used. The ...
1
vote
2answers
57 views

is it correct that for a nbit LFSR (galois algorithm in particular) the maximum number of unique 32byte keys can only be 255?

In fact I have more than just the one question as I try to better understand the whole topic. for a CTF challenge I am currently reading up on LSFR. The code the challenge provides as an example is a ...
1
vote
2answers
365 views

Is it possible to crack a LFSR encrypted file without using bruteforce?

Let's say I was given a file from which I know that it is encrypted using a 5 bit LFSR with a given poly. I already know that it is possible to deduce the state of an LFSR and thus all future outputs ...
5
votes
1answer
518 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 ...
3
votes
1answer
68 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 ...
0
votes
1answer
118 views

Finding non-zero coefficients in 8 bit polynomial LFSR

I have a following crypto problem and I have been struggling with for some time An 8-bit linear feedback shift register with connection polynomial C(X) = 1+aX +bX^2 +cX^3 +dX^4 +eX^5 + fX^6 +gX^7 +hX^...
1
vote
1answer
303 views

Finding max period of 8-bit LFSR

I am a bit stuck there and trying to figure out the approach for given problem. What is the maximim period of a pseudo-random sequence generated by the 8-bit LFSR with connection polynomial C(X) = 1+...
1
vote
1answer
142 views

Linear Feedback shift register over integers

The Solina's paper Generalized Mersenne Numbers contains a Linear Feedback shift register I am not able to understand. Here it is: It is supposed to be a normal Linear Feedback shift register but it ...
3
votes
1answer
420 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?
1
vote
1answer
98 views

In what way is KeeLoq a block cipher?

I'm just going by this diagram of KeeLoq encryption and it resembles these diagrams of Crypto-1 and Hitag2. I'm wondering how it is a block cipher. If it is one and that diagram represents most or all ...
0
votes
2answers
507 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
1answer
1k views

Attack on stream cipher

I am trying to decrypt a message, which was encrypted using a stream cipher and 8 bit LFSR. First two letters of plain text are given: K and ...
-1
votes
2answers
151 views

LFSR, polynomial , finite field

I'm having a hard time understanding the concept of LFSR, polynomials and finite field and how to solve exercises like picture below. Could anyone give me some pointer on where to start?
3
votes
1answer
236 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 ...
5
votes
0answers
74 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. ...
1
vote
1answer
212 views

Linear-Feedback Shift Register in Mod 3

I have an exercise for a crypto class that I'm working on and trying to understand. In the problem I have a Linear-Feedback shift register working in mod 3 with digits {0, 1, 2}. The LFSR is using ...
0
votes
1answer
174 views

An (N)LFSR…but for bytes!

A linear feedback shift register can be thought of as an array of bits where NEW_BIT is calculated using F(REGISTERS). ...
3
votes
1answer
2k 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 ...
2
votes
1answer
513 views

Sequence output by a Galois type LFSR

I have provided a diagram of a Galois type LFSR. I am told it outputs a sequence of period 31. Find the sequence output by this LFSR. By applying the shifts I got the seemingly trivial answr of $0,0,...
-1
votes
1answer
683 views

How to find output sequence for LFSR from its polynomial? [duplicate]

LFSR characterized by $p_2 = 1$, $p_1 = 0$, $p_0 = 1$. I've computed that, the corresponding polynomial is $P(x) = x^3 + x^2 + 1$ What is the sequence generated from the initialization vector $s_2 = ...
6
votes
1answer
510 views

Galois LSFR 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 $\...
7
votes
2answers
483 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 $...
3
votes
1answer
151 views

Why is the state of an LFSR not output?

According to Wikipedia LFSRs are used as PRGs but due to their linearity they are easy to cryptanalyze. Also, using Berlekamp-Massey consecutive output bits allow reconstruction of the internal LFSR ...
3
votes
1answer
505 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-...
-1
votes
0answers
99 views

Is Galois theory used to analyze LFSR ciphers?

Is it true that in the analysis of LFSR ciphers, Galois theory is used ?
2
votes
2answers
375 views

Finding the cycle set of specific polynomial

I have a school assignment where the problem lies in finding the cycle set of two different polynomials. I tried to look up different tools on how to solve these problems, but I have a hard time ...
1
vote
0answers
333 views

Find the initial state of LFSR with n non-consecutive output bits

Let's say I have (e.g.) $32$ output bits of an $128$ bit LFSR whose period length is $2^{128} - 1$. Those output bits are chosen arbitrarily, so I do not have any consecutive bits. Let us call the ...
1
vote
1answer
466 views

Linear feedback shift register combination, secure?

I am currently working on a project which consist in the encryption of image using the GPU of a raspberry. I would like to use LFSR to generate a stream cypher in each Core of the GPU. In the ...
3
votes
1answer
157 views

Generating dataset for LFSR stream cipher

I have implemeneted the code for cryptanalysis of LFSR stream cipher . But I have a problem with generation of dataset i.e to get valid pairs using LFSR stream cipher. In the stinson book it is ...