# 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. 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? 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

I will try to not directly answer your question, but this exercise is so simple that it gets hard to help you without doing that.

You are going to use a symmetric cipher (One-Time Pad - OTP), thus your initial step is to compute your key. This is given by the execution of the LFSR as you described, until a key-stream of the length of the message is obtained. Then, simply apply the OTP decryption step (*) into your pair (key, ciphertext).

(*) I hope you know what the OTP decryption step looks like! ;-)

• I'm afraid that I don't know what the OTP decryption step looks like... Sep 28 '14 at 22:31
• Hint: OTP uses the same computational instruction to perform both encryption and decryption. Sep 28 '14 at 22:35
• What exactly do the "n's" in the problem refer to? Sep 29 '14 at 16:58
• The variable 'n' is used to define the recurrence rule for the LFSR algorithm. It is an abstraction, but for your case: n \in [0, 12], since you need a key of length 16. Sep 29 '14 at 17:17
• @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