Hot answers tagged

10 votes
Accepted

Algorithm or closed form solution that lets me directly compute the $n^{\text{th}}$ state of an LFSR?

If the initial state is $b_0,b_1,\dots,b_{k-1}$ and the recurrence relation is $b_k = \sum_{i = 0}^{k-1} a_ib_i$, then in linear-algebraic terms we have $$ \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_k \...
fkraiem's user avatar
  • 8,112
10 votes
Accepted

Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights?

The obvious way to do this is to generate N words, and use logical operations to combine them in a single word such that each bit of the output word is a 1 with probability approximately 0.1 (and the ...
poncho's user avatar
  • 146k
9 votes

How secure is the E0 stream cipher used in Bluetooth?

Bluetooth has gone through a few transitions in protocol. Bluetooth BR/EDR uses E0/SAFER for a cipher and Bluetooth LE uses AES-CCM. Fundamentally, when you write a specification as an engineer, ...
b degnan's user avatar
  • 4,722
9 votes
Accepted

Are ciphertext-only attacks on LFSRs possible?

For text known to be ASCII encoded as octets with high-order bit of octets at zero, that reveals one bit of the output of the LFSR out of 8. It allows finding the original state of the LFSR from (say) ...
fgrieu's user avatar
  • 140k
7 votes

Relationship between Fibonacci LFSR and Galois LFSR

Consider a Galois LFSR with feedback polynomial $x^3 + x + 1$ and initialization $1 + 0x + 0x^2$, that is, the shift register shifts its initial content $(1,0,0)$ rightwards, and the output bit (the ...
Dilip Sarwate's user avatar
7 votes
Accepted

Is there a library that output LFSR images given parameters?

Yes, there is a python library LFSR-Automatic-Draw that can output $\LaTeX$ Tikz code and that can be converted to PNG images by pdflatex -shell-escape lfsr.tex ...
kelalaka's user avatar
  • 48.3k
7 votes
Accepted

Why do Mersenne Twister use Mersenne prime but not regular prime numbers

A Mersenne Twister is a Linear-Feedback Shift Register with other characteristics, including period a Mersenne prime¹. In essence, the question asks why that is desirable. A LFSR with $n$-bit state ...
fgrieu's user avatar
  • 140k
6 votes
Accepted

LFSR Jump Ahead Algorithm

Galois LFSR In a Galois LFSR with polynomial $P$ of degree $n$, the state is a vector of $n$ bits assimilated to the binary coefficients of terms of degree $n-1$ to $0$ of a polynomial; we note both ...
fgrieu's user avatar
  • 140k
6 votes

Why are stream ciphers based on linear-feedback shift registers so popular?

There were popular once upon a time; They were very easy to implement in the hardware. Think about you only need latch and $\oplus$. For combining functions some $\wedge$ operation. Their periodic ...
kelalaka's user avatar
  • 48.3k
6 votes
Accepted

Linear Feedback Shift Registers analysis

First of all, LFSR's are not secure when they are used alone. They have good statistical properties and one can calculate their period given the feedback polynomial. The LFSR is maximal-length if and ...
kelalaka's user avatar
  • 48.3k
6 votes
Accepted

Why are LFSRs represented as polynomials?

why are LFSRs represented as polynomials? Because it gives useful insights into the behavior of the LFSR. If the feedback terms are represented by the polynomial $P$, and if the initial state of the ...
poncho's user avatar
  • 146k
6 votes
Accepted

Reversed Fibonacci LFSR taps

Are the taps placed correctly on the above figure? No. That's acknowledged in the errata to the second edition, on the section for page 375 (AFAIK the 20th anniversary edition is essentially the ...
fgrieu's user avatar
  • 140k
5 votes
Accepted

Galois LFSR Subsequence Periodicity

Although I cannot speak to the first part of your question, I can answer the second part. Also, I have never seen a formal explanation of how to map polynomials to a LFSR. In retrospect, I honestly ...
b degnan's user avatar
  • 4,722
5 votes
Accepted

Would A5/1 with a much larger state be a good choice of stream cipher for hardware?

I have argued so 15 years ago, and not been proven wrong since. Basically, A5/1, with a $n$-bit state, offers a resistance of roughly $2n/3$ bits of security. With $n = 64$, the resistance is very low,...
Thomas Pornin's user avatar
5 votes
Accepted

Attack on LFSR key stream generator

The number of consecutive plaintext-ciphertext pairs $(x_i,y_i)$ of bits necessary is 256 if we know the LFSR taps (equivalently: the reduction polynomial) in advance, for the reason explained in the ...
fgrieu's user avatar
  • 140k
5 votes

XOR LFSR and all zero state

how does one prevent a LFSR from getting to an all zero state? One method is to not initialize the LFSR to the all-zero state, and use a feedback polynomial with a constant term (the $1$ in the ...
fgrieu's user avatar
  • 140k
5 votes
Accepted

Is a LFSR sufficient for post-processing a biased TRNG?

I'll assume the right 16 in the question's figure is to tell that the LFSR is unloaded 16 bits at a time; and unless otherwise stated I'll assume that's done every 16 clock cycles of the LFSR. Is the ...
fgrieu's user avatar
  • 140k
5 votes
Accepted

What does that mean, that A5/1 is clocked?

The clock term comes from electronic engineering; in each clock, the cells of LFSRs ( flip-flops) are clocked and the data moves. In the shift registers, the data moves from one to another in one ...
kelalaka's user avatar
  • 48.3k
5 votes
Accepted

Can the Berlekamp-Massey algorithm falsely detect an LFSR?

No. Given an arbitrarily long sequence $(x_1,\ldots,x_t,\ldots)$ consider its initial segments. Any (finite) sequence $$x^{(n)}:=(x_1,\ldots,x_n)$$can be generated by a circulating LFSR of the same ...
kodlu's user avatar
  • 22k
4 votes

Non primitive lfsr sequence

A binary sequence of period $105$ will have characteristic polynomial that is a divisor of $x^{105}-1$. Since $x^{105}-1$ has irreducible factors of degrees $12, 4, 3$, and $1$, it is possible to ...
Dilip Sarwate's user avatar
4 votes

How to design a balanced LFSR with period 1023 and linear span 55?

The polynomial factorisation of $X^{2^L-1}+1$ into irreducible factors gives you all the polynomials $g_i(X)$ that can be used as LFSR polynomials in generating any sequence of period $2^L-1.$ Say ...
kodlu's user avatar
  • 22k
4 votes
Accepted

Period, correlation and auto-correlation of non-linear feedback shift registers based sequences

The reason such generators are used is to avoid the Berlekamp Massey attack by introducing high linear complexity. However, even though there are many publications on these, the theory is far from ...
kodlu's user avatar
  • 22k
4 votes
Accepted

How to convert a Galois LFSR to a Fibonacci LFSR?

In this answer I will consider the Galois LFSR mentionned at this question: Sequence output by a Galois type LFSR see the image below. First we assume that the 5 positions of bits are numbered from ...
Biv's user avatar
  • 9,979
4 votes
Accepted

Sequence output by a Galois type LFSR

You made a mistake in the propagation of the feedback. If you follow the LFSR very slowly this is what you get: ...
Biv's user avatar
  • 9,979
4 votes

Is it possible to crack a LFSR encrypted file without using bruteforce?

First up: a 5 bit LFSR is horribly small, so getting the initial seed which was used is a piece of cake. But indeed, it’ll basically boil down to a (rather quick) brute-force job where – unless that ...
e-sushi's user avatar
  • 17.9k
4 votes
Accepted

Decrypting Ciphertext with partial Key Fragment using LFSR and Berlekamp-Massey

TL;DR: If you have a similar question, then use the online Berlakamp-Massey algorithm to get the minimal polynomial by providing the given keystream, then get the C++ code from github and then replace ...
kelalaka's user avatar
  • 48.3k
4 votes

Why are stream ciphers based on linear-feedback shift registers so popular?

A complement to @kelalaka's excellent answer. Here are a few LFSR (and NLFSR for Trivium) based stream ciphers that have not been broken. Trivium Self shrinking generator. Also, some stream ...
kodlu's user avatar
  • 22k
4 votes
Accepted

Explanation of $z^{-1}$ and $T_{1,2}$ within E0 Bluetooth encryption algorithm

This article Cryptanalysis of the Bluetooth Stream Cipher by Canniere et al. explains in details; \begin{align} T_1 : \mathbb Z^2_2 &\mapsto \mathbb Z^2_2\\ (x_1, x_0) &\to (x_1, x_0)\\ \end{...
kelalaka's user avatar
  • 48.3k
4 votes

Multiplication of two LFSR

TL;DR: It's complicated. Intuitively, the idea that all roots of the two polynomials contribute to the linear complexity of the product sequence, which can sometimes result in very high linear ...
kodlu's user avatar
  • 22k
4 votes
Accepted

What is the result of not connecting the 1st register to the xor gate in LFSR?

OK, it is a question of what the connection polynomial is, the figure helps clarify what you are doing. In both cases the polynomial is degree 8. Originally, your connection polynomial is $1+x+x^4+x^5+...
kodlu's user avatar
  • 22k

Only top scored, non community-wiki answers of a minimum length are eligible