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!

  • 4
    $\begingroup$ 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. $\endgroup$ – Stephen Touset Sep 28 '14 at 22:56
  • $\begingroup$ 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. $\endgroup$ – fgrieu Sep 29 '14 at 7:49
  • $\begingroup$ 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. $\endgroup$ – fgrieu Sep 29 '14 at 10:42
  • $\begingroup$ @fgrieu: does changing the condition for n change how I would approach the problem? $\endgroup$ – Jok3r Sep 29 '14 at 17:03
  • $\begingroup$ @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. $\endgroup$ – 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! ;-)

  • $\begingroup$ I'm afraid that I don't know what the OTP decryption step looks like... $\endgroup$ – Jok3r Sep 28 '14 at 22:31
  • $\begingroup$ Hint: OTP uses the same computational instruction to perform both encryption and decryption. $\endgroup$ – mczraf Sep 28 '14 at 22:35
  • $\begingroup$ What exactly do the "n's" in the problem refer to? $\endgroup$ – Jok3r Sep 29 '14 at 16:58
  • 1
    $\begingroup$ 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. $\endgroup$ – mczraf Sep 29 '14 at 17:17
  • $\begingroup$ @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). $\endgroup$ – fgrieu Sep 30 '14 at 5:21

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.