Skip to main content

Questions tagged [lfsr]

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

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19 votes
0 answers

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 ...
b degnan's user avatar
  • 4,880
4 votes
0 answers

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
3 votes
0 answers

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
0 answers

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
2 votes
0 answers

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
2 votes
0 answers

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: ...
forest's user avatar
  • 15.3k
2 votes
0 answers

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 ...
Gabi Tulba Lecu's user avatar
2 votes
0 answers

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 $...
Timo Junolainen's user avatar
2 votes
0 answers

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 ...
AttributedTensorField's user avatar
1 vote
0 answers

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
1 vote
0 answers

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 ?
Akash's user avatar
  • 71
1 vote
0 answers

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 ...
Ken's user avatar
  • 91
1 vote
0 answers

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$...
Hughtwo's user avatar
  • 71
1 vote
0 answers

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 ...
bkoodaa's user avatar
  • 629
1 vote
0 answers

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 ...
Zapho Oxx's user avatar
1 vote
0 answers

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 ...
Nils Q.'s user avatar
  • 43
1 vote
2 answers

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 ...
Learner's user avatar
  • 61
0 votes
0 answers

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 ...
niloufar hz's user avatar
0 votes
0 answers

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
0 votes
0 answers

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
0 votes
0 answers

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
0 votes
0 answers

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
0 votes
0 answers

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: For example ...
Moody Lover's user avatar