3
$\begingroup$

How can I calculate the polynomial and state of a LFSR given 2n (or more) non-consecutive keystream bits? It is known to be n bit. If they were consecutive, I could use the Berlekamp–Massey algorithm.

Simple example: n is 7 and I know the keystream is 0...0...1...0...1...0...1...1...1...0...1...0...1...0 where the . is an unknown bit

Any explanation or reference to paper or text book with algorithm will be greatly appreciated.

$\endgroup$
3
$\begingroup$

We are given the sequence $b_i$ for $i$ multiple of $m>1$ with $0\le i<2n\,m$.

  • If all the given $b_i$ are identical, we can't compute any missing $b_i$ (beyond a wild guess they are all $b_0$), stop.
  • Build the sequence of $2n$ known bits $c_j=b_{(j\,m)}$ with $0\le j<2n$.
  • Use Berlekamp–Massey to find a LFSR (polynomial $P$ of degree $k$ and $k$-bit initial state) matching $c_j$.
  • Find some period $p$ of the $c_j$. For small degree $k$, we can simulate operation of the LFSR until the state repeats (OK to say $k\le40$ on a PC) or we can use baby-step/giant-step (OK to say $k\le75$ on a PC, see final section of this former revision). But more generally, if $P$ factors into a product of irreducible polynomials of degrees $k_r$ (thus with $k=\sum k_r$), then a period is $p=\prod(2^{k_r}-1)$.
    Note: For large polynomial, we can still efficiently compute $c_j$ for large arbitrary $j$ (see this), once we have $P$ and starting state.
  • If $\gcd(m,p)=1$, then $b_i$ also has period $p$, thus $\forall j\in\Bbb N,\ c_j=b_{(j\,m\bmod p)}$ ; it follows that $\forall i\in\Bbb N, b_i=c_{(i\,m^{-1}\bmod p)}$
    Note: $m^{-1}\bmod p$ needs to be computed only once, e.g. with the half extended Euclidean algorithm.
    Note: with $p=\prod(2^{k_r}-1)$ and $m$ a power of two as in the question, $\gcd(m,p)=1$ always holds. If $\gcd(m,p)\ne1$, it might be possible to find a smaller period, by factoring $p$ and iteratively removing those factors that leave what remains a period, until finding the smallest period $p_\text{min}$ (which depends on the irreducible factors of $P$ being primitive or not, and on the starting point). $\gcd(m,p_\text{min})=1$ allows to conclude without guesswork.

Once $2k$ consecutive $b_j$ are found, an easy option to find the LFSR yielding them is to use Berlekamp–Massey again. The initial state of the LFSR for the $b_j$ (in Fibonacci form) is of course the first $k$ bits $b_i$.

Not covered (yet?): polynomial arithmetic would allow to directly derive the LFSR for the $b_j$ from the one for the $c_j$; and conclude when $\gcd(m,p_\text{min})\ne1$ and partial information on the $b_j$ is available.

$\endgroup$
  • $\begingroup$ Thank very much. I think I understand now. My initial example did not work as it failed in the gcd-step. I have changed it to one that is solvable. $\endgroup$ – PurpleTree Jun 7 '18 at 18:33
  • $\begingroup$ how does one "efficiently compute c_j for large arbitrary j"? $\endgroup$ – Les Jul 9 '18 at 1:19
  • $\begingroup$ @fgrieu - I'm confused. In #1 for example, let j=9, the binary expression for J is b1001 or 2^3 + 2^0, then "step the generator 2^i for each i"? Isn't that 9 steps? What if j=2305843009213693952 (mod (2^64-1)). To step the generator that many times would take years, wouldn't it? $\endgroup$ – Les Jul 9 '18 at 11:20
  • $\begingroup$ @fgrieu - I have opened a new question on efficiently finding $c_j$ for large $j$ - crypto.stackexchange.com/questions/60634/… $\endgroup$ – Les Jul 9 '18 at 11:23
  • $\begingroup$ @fgrieu - what are the parameters to the baby-step-giant-step if I've computed a non-primitive P, order K in field GF($2^K$)? Am i correct in assuming Alpha = P and Beta is $2^K$-1, with the goal of finding $x$ where $a^x = beta$ ? $\endgroup$ – Les Jul 12 '18 at 14:56

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.