A state matrix records consecutive internal bits of a linear feedback shift register (LFSR). For an LFSR of length L, each row shifts the observed sequence by one position, exposing the recurrence that produces later bits. section 4.2.2
Equation 4.6
\[\begin{aligned} \begin{bmatrix} s_{3} \\ s_{4} \\ s_{5} \end{bmatrix} &= \begin{bmatrix} s_{0} & s_{1} & s_{2} \\ s_{1} & s_{2} & s_{3} \\ s_{2} & s_{3} & s_{4} \end{bmatrix} \begin{bmatrix} a_{0} \\ a_{1} \\ a_{2} \end{bmatrix} \notag\\ X &= SA \label{equation:lfsr-matrix} \end{aligned}\]The matrix equation expresses the next L observed bits as the state matrix S multiplied by the tap vector A using Boolean arithmetic: multiplication is AND and addition is XOR. section 4.2.2
Recovering an LFSR from observed output follows these implementation steps:
- Compute the tap vector with A = S⁻¹X; inversion failure indicates an unsuitable sequence or incorrect length. section 4.2.2
Known-plaintext recovery
Known plaintext reveals corresponding keystream bits by XORing plaintext with ciphertext. Trying candidate lengths, recovering taps, and decrypting the remainder can expose the original timestamped message.
