Questions tagged [lfsr]
Linear Feedback Shift Register, a pseudorandom bit generator which can be efficiently implemented in hardware.
22
questions with no upvoted or accepted answers
19
votes
0
answers
464
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 ...
- 4,820
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 ...
- 453
3
votes
0
answers
181
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
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 ...
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 ...
- 147
2
votes
0
answers
94
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:
...
- 15.3k
2
votes
0
answers
72
views
LFSR expected period
What is the expected value of the length of the period of a n-bit linear-feedback shift register with a random tap?
I am asking because I am curious what security issues would appear if the tap would ...
2
votes
0
answers
173
views
LFSR, different bits from different initial states
Suppose we use an LFSR, which gives output $x_1x_2x_3\dots$ from some particular initial state. From another state, different from the previous one, using the same LFSR though, it gives sequence $...
- 235
2
votes
0
answers
236
views
Berlekamp-Massey algorithm, correct stepping
I'm trying to use the Berlekamp-Massey algorithm on the following bit sequence:
0 1 0 0 1 0 0 1 0 1
I have the correct answer and most of the approach to get there, but I'm unable to fill in what I ...
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},...
- 111
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
1
vote
0
answers
247
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 ...
- 91
1
vote
0
answers
257
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$...
- 71
1
vote
0
answers
401
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 ...
- 629
1
vote
0
answers
85
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 ...
- 23
1
vote
0
answers
1k
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 ...
- 43
1
vote
2
answers
674
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 ...
- 61
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 ...
- 1
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 ...
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....
- 123
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 ...
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 ...
