meta user
network profile
| bio | website | |
|---|---|---|
| location | ||
| age | ||
| visits | member for | 6 months |
| seen | May 12 at 15:52 | |
| stats | profile views | 3 |
|
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 |
