Score:0

Relationship between LCGs and LFSRs

tf flag
Tom

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?

kodlu avatar
sa flag
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.
kodlu avatar
sa flag
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)
Score:1
sa flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.