0
$\begingroup$

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?

| improve this question | |
$\endgroup$
  • $\begingroup$ Welcome to CryptographySE. Is this a homework question? $\endgroup$ – kelalaka Feb 17 '19 at 8:48
  • $\begingroup$ 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. $\endgroup$ – eHH Feb 17 '19 at 8:51
  • 4
    $\begingroup$ 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. $\endgroup$ – kelalaka Feb 17 '19 at 9:20
  • 4
    $\begingroup$ 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. $\endgroup$ – fgrieu♦ Feb 17 '19 at 9:40
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Feb 17 '19 at 9:46
1
$\begingroup$

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).

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.