# Message encrypted with a LFSR based stream cipher

I am learning about LFSR sequence and I came across this question: A 16-bit message consists of two ASCII characters. This message was encrypted with a one-time pad, and the key for the one-time pad was an LFSR sequence (mod 2) given by $x_0 = 1$, $x_1 = 0$, $x_2 = 1$ and $x_{n+3} = x_{n+2} + x_n$ for $n \ge 0$. The ciphertext is 1111000000001000. Decode the message.

I'm a lost as where to begin on this one. I am not looking for anyone to just give me the answer, but some guidance (step by step preferably) on what my starting steps should be would be greatly appreciated!

• This is a side point, but the question itself is nonsense. An OTP by definition must use a truly random key — a key generated by an LFSR with an input seed (or any PRNG using a seed) is by definition not truly random. – Stephen Touset Sep 28 '14 at 22:56
• Likely one should read $x_{n+3} = x_{n+2} + x_n$ for $n≥0$; with the original $n≥3$ there was no way to infer $x_3$, $x_4$, $x_5$. I took the liberty to fix it. – fgrieu Sep 29 '14 at 7:49
• Hints: contrary to historical practice in telecommunication, assume big-endian convention when converting a sequence of 8 bits to ASCII (that is: 01001010 is \$4A thus J, not \$52 thus R). $\;$ The message itself could be understood as a provocative invitation. – fgrieu Sep 29 '14 at 10:42
• @fgrieu: does changing the condition for n change how I would approach the problem? – Jok3r Sep 29 '14 at 17:03
• @J0ker: Yes: now you can compute the $x_i$, with $i$ from 0 to 15, which in your problem forms the output of the LFSR, which also is the key of the (pseudo) OTP. Then you can decipher the given ciphertext as you would for a regular OTP, yielding the plaintext. That's basically what you are told by mczraf in that answer. – fgrieu Sep 29 '14 at 18:38

• @J0ker: what is meant is that for all integers $n\ge0$, the equation $x_{(n+3)} = x_{(n+2)} \oplus x_n$ holds, where $\oplus$ is exclusive-OR. You are given $x_0$, $x_1$, $x_2$, and can compute $x_3$ (with $n=0$), $x_4$ (with $n=1$), and so on, up to $x_{15}$, which is the last used term of the LFSR output (also the key of the pseudo-OTP, which really is a stream cipher). – fgrieu Sep 30 '14 at 5:21