1

I need to generate 64-bit data sequences 16 times pseudorandomly. How many bits should the linear-feedback shift register (LFSR) have in order to do so?

That is, what is the number of bits for the initial seed? How can I calculate this number? Can we minimize this number? Should it be a fixed number of bits?

Patriot
  • 3,132
  • 3
  • 18
  • 65
eHH
  • 121
  • 2
  • Welcome to CryptographySE. Is this a homework question? – kelalaka Feb 17 '19 at 08:48
  • I don't know alot about LSFRs and Pseudo random bit generators but I need the answer of this question because I have to use it in my research. – eHH Feb 17 '19 at 08:51
  • 5
    An LFSR with $L$ length can generate $2^L-1$ periodic sequence. With a given $2L$ key stream of the generated stream, one can produce the LFSR with its tap position in $\mathcal{O}(n^2)$-time by Berlakamp-Massey Algorithm. Using only LFSR is not a good idea. – kelalaka Feb 17 '19 at 09:20
  • 5
    In the above, $n$ is $L$. Also, if the taps are known, $2L$ becomes $L$, the algorithm becomes more trivial, and the run time drops to $\mathcal{O}(L)$. In most use cases, a lone LFSR only give a false sense of cryptographic security. – fgrieu Feb 17 '19 at 09:40
  • 1
    Yes. $n=L$. If you tell more about your actual problem, like where are you going to use these 16 pseudo bits, you can find more specific help four your cause. – kelalaka Feb 17 '19 at 09:46
  • Related: https://crypto.stackexchange.com/q/5683/54184 – forest Sep 01 '19 at 09:28

1 Answers1

3

An $n$-bit LFSR with a primitive feedback polynomial will cycle through all $2^n-1$ possible non-zero states. You will need an LFSR to generate $16\times 64 = 1024$ bits. An 11-bit LFSR will cycle through $2^{11} - 1 = 2047$ states and output as many bits, so for your purposes, an 11-bit state is sufficient.

If the feedback polynomial is not primitive, then the period will be unpredictable but not maximal. An example primitive polynomial suitable for use in a maximal-length 11-bit LFSR is $x^{11}+x^9+1$.

It's extremely important to know that an LFSR is not cryptographically secure. An $n$-bit LFSR can be broken after only $n$ bits of keystream are known ($2n$ bits if the feedback polynomial is secret).

forest
  • 15,253
  • 2
  • 48
  • 103