geo909
Reputation
Top tag
Next privilege 100 Rep.
Edit community wikis
 Jun15 awarded Self-Learner May12 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? They cite something for those proofs: R. Rueppel, Analysis and design of Stream Ciphers, 1986 May12 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? @sarwate Yes, that's right, to my understanding. Now, about the "pairwise coprime" thing: they say without proof that for pairwise coprime LFSR lengths (tapped to give maximal sequences), we get a keystream period equal to $\prod_{i=1}^m 2^{L_i}-1$ (easy to see) and linear span $f(L_1,\dots,L_m)$ (evaluated as we discussed). From their wording I assume that the "pairwise coprime" assumption applies to the latter, too.. May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? Good point! "[...] the linear complexity is [...] $L=f(L_1,\cdots,L_m)$ [...] with the latter Boolean function transformed by evaluating the addition and multiplication operations in the function over the integers rather than over $GF(2)$" (Dawson, Simpson, Analysis and Design issues for Synchronous Stream Ciphers). Also this applies when the $L_i's$ are pairwise coprime. May11 accepted Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? It seems that ideally one would like linear complexity almost equal to the period of the keystream (and of course, a large period) May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? So, that's another good reason not to use combinations of LFSRs.. After reading your answer I looked a bit more carfully and confirmed that if the combiner function is $f$ and the lengths of the $m$ LFSRs are $L_1,\cdots,L_m$, then the linear complexity of the output sequence is $f(L_1,\cdots,L_m)$; in our case that's the sum of the $L_i's$ as you said. So, for lengths that add up to 128 (so we have a 128-bit key), one needs only $2\times 128=256$ bits of the keystream sequence and the Berlekamp-Massey algorithm to break the system. May11 awarded Commentator May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? You're right! By the reccurent nature of the LFSRs, every output bit of every LFSR can be expressed as a linear combination of the initial state! Then we end up with a system of linear equations and we can perform Gaussian elimination. May11 revised Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? see my comment May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? @rphv I think there is another issue about the edit: one needs $2n$ bits if the tap positions are not known. If they are known, one needs $n$ bits. May10 asked Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? Feb19 awarded Teacher Feb19 comment Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR That's clear; I added an answer with an example demonstrating your answer. If you ever have time you maybe could have a look at my LFSR-related question here? Feb19 revised Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR added 108 characters in body Feb19 accepted Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Feb19 answered Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Feb17 comment Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Thanks a lot for your answer.. There are still some parts that I don't get though. You say in your last sentence that this LFSR will typically not be of length L and the feedback polynomial will typically differ from that of the LFSR of length L that is known to generate (S0,S1,…,Sn−1). But doesn't $L$ refer to the shortest LFSR anyway? That's what you say in the beginning too. Maybe I need to read again 'cause there are lots to absorb but this part is a bit fuzzy.. Thanks! Feb17 revised Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR added 31 characters in body Feb16 comment Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Due to my low reputation I couldn't add the non-existing tags "LFSR", maybe it makes sense that somebody does that..