Questions tagged [lfsr]
Linear Feedback Shift Register, a pseudorandom bit generator which can be efficiently implemented in hardware.
154
questions
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?
- 207
0
votes
0
answers
60
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
111
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 ...
- 91
1
vote
0
answers
27
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
114
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
35
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
85
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
89
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
259
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,554
2
votes
1
answer
167
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
58
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 ...
- 141
0
votes
0
answers
229
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
223
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
352
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 ...
- 141
1
vote
1
answer
242
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
568
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
346
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
83
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
87
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
149
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
417
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
348
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
383
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
588
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,211
3
votes
1
answer
203
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 (...
- 46.4k
6
votes
1
answer
232
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?
...
- 46.4k
2
votes
0
answers
72
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
1
answer
801
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
725
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
242
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
261
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
57
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$
...
- 141
3
votes
1
answer
560
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
374
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,167
1
vote
1
answer
1k
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
745
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,167
3
votes
1
answer
1k
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,167
2
votes
1
answer
116
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
629
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
145
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
1k
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
0
votes
1
answer
125
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 ...
4
votes
1
answer
112
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,...
- 143
1
vote
1
answer
131
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?
- 81
1
vote
1
answer
138
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 ...
- 45
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 ...
- 45
1
vote
1
answer
1k
views
Understanding LFSR stream ciphers and the content scrambling system
I'm a little confused over how exactly Linear Feedback Shift Registers (LFSR) work, I kind of get it, but not really, can someone help me understand it? I know it XORs bits in a loop against some mask,...
- 65
3
votes
2
answers
257
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 ...
- 15k
2
votes
0
answers
86
views
Known-plaintext attack against E0 with 2745 bits per frame instead of 24
In the paper The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption, an attack against the E0 cipher is described which can break it efficiently in a known-plaintext attack:
...
- 15k
1
vote
0
answers
58
views
MULalpha and DIValpha operations in SNOW 3G
I'm not able to appreciate the importance of mul alpha and div alpha operations in feedback polynomial of LFSR in SNOW 3G. What problems or weakness do they help in mitigating and how ?
- 71