Chapter 10: Processes of Perception and Analysis

Section 10: Cryptography and Cryptanalysis

LFSR cryptanalysis

Given a sequence obtained from a length n LFSR (see page 975)

Nest[Mod[Append[#, Take[#, -n].vec], 2] &, list, t]

the vector of taps vec can be deduced from

LinearSolve[Table[Take[seq, {i, i + n-1}], {i, n}], Take[seq, {n + 1, 2n}], Modulus->2]

(An iterative algorithm in n taking about n2 rather than n3 steps was given by Elwyn Berlekamp and James Massey in 1968.) The same basic approach can be used to deduce the rule for an additive cellular automaton from vertical sequences.

From Stephen Wolfram: A New Kind of Science [citation]