1
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 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
    Commented Sep 28, 2014 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 ♦
    Commented Sep 29, 2014 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 ♦
    Commented Sep 29, 2014 at 10:42
  • $\begingroup$ @fgrieu: does changing the condition for n change how I would approach the problem? $\endgroup$
    – Jok3r
    Commented Sep 29, 2014 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 ♦
    Commented Sep 29, 2014 at 18:38

1 Answer 1

Reset to default
1
$\begingroup$

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! ;-)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.