A weighted sum multiplies values by coefficients and adds the resulting terms. In Boolean LFSRs, multiplication becomes AND and addition becomes XOR, producing each new state bit from tapped prior bits. section 4.2.2
Equation 4.4
\[s_{n+1} = a_{0}s_{n-L} + ... + a_{L-1}s_{n-1} + a_{L}s_{n} \label{equation:lfsr}\]The LFSR recurrence writes the next bit as a weighted sum of earlier sequence values and tap coefficients. section 4.2.2
A weighted sum supports LFSR tap recovery through these operations:
- Arrange observed sequence bits into a state matrix S and collect subsequent bits in X. section 4.2.2
- Model the recurrence as X = SA, where A contains the unknown tap coefficients. section 4.2.2
- Recover the taps with A = S⁻¹X when S is invertible; Boolean matrix operations use XOR and AND. section 4.2.2
Recovering an LFSR from known plaintext
A known prefix reveals keystream bits by XORing plaintext with ciphertext. The recovery code tests candidate LFSR lengths, clones a valid recurrence, and decrypts the remaining ciphertext; the test obtains the original timestamped message.
