72 reputation
6
bio website
location
age
visits member for 1 year, 5 months
seen May 12 '13 at 15:52

May
12
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
May
12
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..
May
11
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.
May
11
accepted Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?
May
11
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)
May
11
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.
May
11
awarded  Commentator
May
11
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.
May
11
revised Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?
see my comment
May
11
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.
May
10
asked Combining LFSRs for Stream Ciphers: Why do we need high non-linearity?
Feb
19
awarded  Teacher
Feb
19
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?
Feb
19
revised Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR
added 108 characters in body
Feb
19
accepted Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR
Feb
19
answered Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR
Feb
17
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!
Feb
17
revised Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR
added 31 characters in body
Feb
16
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..
Feb
16
asked Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR