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
35 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 ...
Me2's user avatar
  • 1
2 votes
1 answer
169 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 ...
ialexander's user avatar
2 votes
1 answer
390 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 ...
Ahmed Diyaa's user avatar
0 votes
2 answers
104 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$$...
Prothean 's user avatar
0 votes
1 answer
241 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 ...
rin ichinose's user avatar
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
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 ...
vibhav950's user avatar
4 votes
2 answers
144 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
1 vote
0 answers
35 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},...
stack_math's user avatar
3 votes
1 answer
125 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
2 votes
0 answers
40 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 ...
Mathpdegeek497's user avatar
1 vote
1 answer
101 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 $...
Grigoriy's user avatar
-1 votes
1 answer
119 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 (-> ...
Mike's user avatar
  • 1
4 votes
2 answers
288 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,595
2 votes
1 answer
217 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 ...
Julian Fusco-Wright's user avatar
1 vote
2 answers
63 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 ...
Viren Sule's user avatar
0 votes
0 answers
288 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....
KetDog's user avatar
  • 123
6 votes
3 answers
251 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
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 ...
Viren Sule's user avatar
1 vote
1 answer
277 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 ...
Mathpdegeek497's user avatar
1 vote
3 answers
674 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 ...
Mathpdegeek497's user avatar
1 vote
1 answer
608 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 ...
user3556757's user avatar
1 vote
1 answer
99 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 ...
neolith's user avatar
  • 147
0 votes
0 answers
102 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 ...
RobotVerter's user avatar
2 votes
2 answers
175 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, ...
ytj_banana's user avatar
1 vote
2 answers
579 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 ...
neolith's user avatar
  • 147
4 votes
0 answers
395 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
4 votes
1 answer
481 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
5 votes
1 answer
698 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
3 votes
1 answer
216 views

What is the linear complexity of a modified LFSR sequence with a fixed length of zeroes inserted between every pair of successive terms

There was a deleted question that asked; We know that if $n$ zeros are inserted between every pair of successive terms of the sequence in LFSR (variable changed $x$ to $x^n$) then linear complexity (...
kelalaka's user avatar
  • 48.5k
6 votes
1 answer
274 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.5k
2 votes
0 answers
80 views

Is there a way to find the two generator polynomials of a JPL sequence?

I am decoding a binary sequence that was detected as an unpractically long LFSR by the Berlekamp-Massey algorithm. First of all, the generated sequence is far longer than it needs to be and since it ...
neolith's user avatar
  • 147
4 votes
1 answer
923 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
835 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
1 vote
1 answer
336 views

Listing first 8 bits generated by LFSR

Consider the primitive polynomial P(x) = x^4 + x^3 + 1, initialized with the bit string (shifting occurs from left to right, were the right-most bit represents the LFSR output): 1101. List the first 8-...
hollyjolly's user avatar
0 votes
0 answers
324 views

How to find the matrix of LFSR output?

I am trying to find polynomial , but don't know how to get matrix matrix must look something like this:https://www.oreilly.com/library/view/computer-security-and/9780471947837/sec8.8.html For example ...
Moody Lover's user avatar
3 votes
1 answer
58 views

Is there a way to bound linear complexity of a sequence less than its period

Linear complexity of a sequence $s_0,s_1,\ldots$ over a finite field is the shortest length $n$ of linear recurrence of the sequence such that $s_{n+j}=\sum_{i=0}^{n-1}a_is_{i+j}$ for $j=0,1,2,\ldots$ ...
Viren Sule's user avatar
3 votes
1 answer
802 views

How to interpret Berlekamp-Massey algorithm?

I'm trying to find a way to understand the process of the Berlekamp-Massey Algorithm. But I'm struggling in understanding the fourth step of the process, which is $B^{(r+1)}(x) = A^{(r)}/\delta^{(r)}$....
ytj_banana's user avatar
1 vote
1 answer
512 views

Breaking the 40 bit DVD CSS stream cipher

This is from the transcript of Dan Boneh's Coursera Crypto course https://www.coursera.org/learn/crypto/lecture/mQAkP/real-world-stream-ciphers So it turns out this is easy to break in time roughly ...
user93353's user avatar
  • 2,201
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 ...
Ataberk Özbay's user avatar
1 vote
2 answers
985 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 ...
user93353's user avatar
  • 2,201
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,201
2 votes
1 answer
126 views

autocorrelation of non-linear shift register with the period of $2^n$ (full period)

throughout the question I will talk about sequences in bipolar alphabet, meaning, over {1,-1}. I have read in the book Shift Register Sequences by Solomon W. Golomb that sequences with the period of $...
Mr.O's user avatar
  • 121
6 votes
1 answer
694 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
3 votes
0 answers
180 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 ...
math4ev's user avatar
  • 31
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 ...
Trey's user avatar
  • 189
0 votes
1 answer
155 views

What does "Clocked" mean in alternating step generators

In the wiki article, it says "An ASG comprises three linear-feedback shift registers, which we will call LFSR0, LFSR1, and LFSR2 for convenience. The output of one of the registers decides which of ...
ZazzyCola's user avatar
4 votes
1 answer
119 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
1 vote
1 answer
149 views

Forward Security of Symmetric Encryption Schemes with LFSR based PRNG

Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?
Surya's user avatar
  • 91
1 vote
1 answer
155 views

M-Sequence Properties in LFSR

I test this law with a 7-bits primitive polynomial LFSR. and the run property could be found according to output. Is there any theoretical to prove m-sequence property, I could just find some ...
Asdeasdfs's user avatar