Questions tagged [lfsr]
Linear Feedback Shift Register, a pseudorandom bit generator which can be efficiently implemented in hardware.
164
questions
0
votes
0
answers
42
views
Finding LFSR Tap bits. The question is below please help me out with the correct answer [closed]
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
...
- 1
0
votes
0
answers
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 ...
- 1
2
votes
0
answers
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
0
votes
0
answers
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 ...
0
votes
0
answers
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
2
votes
1
answer
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
2
votes
1
answer
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 ...
- 21
0
votes
2
answers
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$$...
- 1
0
votes
1
answer
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 ...
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?
- 459
0
votes
0
answers
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 ...
4
votes
2
answers
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
0
answers
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
3
votes
1
answer
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 ...
2
votes
0
answers
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
1
answer
119
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 $...
- 11
-1
votes
1
answer
130
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
4
votes
2
answers
306
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 ...
- 2,625
3
votes
1
answer
238
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
68
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 ...
- 171
0
votes
0
answers
293
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....
- 123
6
votes
3
answers
269
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,...
3
votes
1
answer
362
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 ...
- 171
1
vote
1
answer
297
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 ...
1
vote
3
answers
727
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
852
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 ...
- 145
1
vote
1
answer
111
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 ...
- 147
0
votes
0
answers
108
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 ...
2
votes
2
answers
195
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, ...
- 51
1
vote
2
answers
724
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 ...
- 147
4
votes
0
answers
410
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 ...
- 453
4
votes
1
answer
550
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 ...
- 41
5
votes
1
answer
752
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?
- 1,241
3
votes
1
answer
225
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 (...
- 49.3k
6
votes
1
answer
300
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?
...
- 49.3k
2
votes
0
answers
88
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 ...
- 147
4
votes
2
answers
1k
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 ...
- 453
4
votes
2
answers
921
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 ...
- 453
1
vote
1
answer
375
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-...
- 31
0
votes
0
answers
345
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 ...
3
votes
1
answer
60
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$
...
- 171
3
votes
1
answer
906
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)}$....
- 51
1
vote
1
answer
574
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 ...
- 2,262
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 ...
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 ...
- 2,262
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 ...
- 2,262
2
votes
1
answer
132
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 $...
- 121
6
votes
1
answer
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
3
votes
0
answers
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
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 ...
- 189