0
$\begingroup$

Here:

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

they wrote:

The linear feedback shift register has a strong relationship to linear congruential generators

What this relationship is all about? Are they mathematically equivalent in some way? In two cases, we can reach the maximum period. Maybe there are LCGs that generate the same numbers as the LFSRs? As far as I know, the LFSRs also have a problem with the low order bits, just like the LCG mod $2^n$. But do we have any deeper connections here, beyond the similarities?

$\endgroup$
2
  • $\begingroup$ Given most LFSRs used in practice work over $GF(2)$ instead of $GF(2^n)$ I am wondering what your comment "problem with low order bits" may be about. $\endgroup$
    – kodlu
    Sep 14 at 4:51
  • $\begingroup$ or do you just mean don't output the first so many bits since you'd be giving away the "seed" (sometimes used as the key) $\endgroup$
    – kodlu
    Sep 14 at 5:10
1
$\begingroup$

They're both linear which is of course a weakness from the cryptographic point of view. LCG is $$x_{t}\equiv (a x_{t-1}+c) \pmod n \qquad (1) $$ while LFSR is $$x_{t} \equiv (a_1 x_{t-1}+ a_2 x_{t-2}+\cdots+ a_L x_{t-L}) \pmod 2\qquad (2) $$

One could devise an $L$ term LCG $$x_{t}\equiv (a_1 x_{t-1}+a_2 x_{t-2}+\cdots+ a_L x_{t-L}) \pmod n$$ which could then be reduced mod 2 (both the $x_t$s and the $a_i$s reduced mod 2) to correspond to an LFSR, but that's a bit artificial, since one must pick a large size for $n$ and choose its properties (e.g., is $n$ prime, semiprime, is $\gcd(a,n)=1$) to get a relatively strong recurrence. So this would be overkill, with no appreciable gain in strength compared to (1) and a more complicated choice of the constants $a_i$ would be needed.

And the basic attacks on them are based on quite different ideas, for example the truncation attack on LCGs by Lagarias et al has nothing to do with Berlekamp Massey attack.

I am not aware of any other important similarities between them; at least I can't think of any off the top of my head.

$\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.