Code
Reading a text without its key: naming the cipher, peeling off encodings, counting letters, measuring an unknown script, breaking nomenclators, reading messages in depth, replaying the Enigma breaks, checking anagrams.
Shift Registers
Runs a linear feedback shift register from its connection polynomial and initial state, drawn at each unit of time, and gives its period. From a run of bits, Berlekamp and Massey’s algorithm finds the shortest register that makes them; its length is the sequence’s linear complexity, drawn as a profile. The notation and the worked examples are the Handbook of Applied Cryptography’s, §6.2.
Terms
History, how it works, how it was checked, limits
History
A linear feedback shift register is a row of stages, each holding a bit; at every unit of time the last stage’s bit is put out, the rest move one place, and the sum of a fixed set of stages enters at the other end. The Handbook of Applied Cryptography sets out the theory and credits the algorithm that finds the shortest register for a sequence to James Massey, who built it on Elwyn Berlekamp’s algorithm for decoding BCH codes.
How it works
Run a register: the connection polynomial C(D) = 1 + c₁D + … + c_L·D^L and the initial state, written highest stage first, give each further bit as the sum of the earlier bits the polynomial names. The register is run until its state returns, to give its period, and drawn at each of its first 200 units of time. From its keystream: Berlekamp and Massey’s algorithm reads the bits one at a time, keeping the shortest register that gives all of them so far and lengthening it only when it fails. Its final length is the linear complexity; the length after each bit is the profile, drawn against the line L = N/2 that random bits keep to. The register is the only one of its length when the bits are at least twice its stages.
How it was checked
Against the Handbook’s own examples: the register ⟨4, 1 + D + D⁴⟩ from [0, 1, 1, 0] holds the sixteen states of Example 6.10 and has period 15; Table 6.1’s nine rounds give its C(D), L, m and B(D) row by row; the profile of Example 6.26’s sequence is the forty values printed; Example 6.27’s sequence follows ⌊(N + 1)/2⌋. A register of seventeen stages is found again from 34 bits of its keystream. On thirty random runs the linear complexity equals the one Randomness Tests counts.
The tests hold 21 checks of this tool; 8 rest on outside material:
- A print’s own example The Handbook of Applied Cryptography, Example 6.10, p. 196: the register ⟨4, 1 + D + D⁴⟩ from the state [0, 1, 1, 0] holds at each time t = 0 … 15 the stages its table prints
- A print’s own example Example 6.10, p. 196: its output is 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, periodic with period 15
- A print’s own example The Handbook’s Table 6.1, p. 202: Berlekamp and Massey’s rounds on 0, 0, 1, 1, 0, 1, 1, 1, 0 give C(D), L and m as printed, round by round
- A print’s own example Table 6.1, p. 202: the discrepancies d are 0 0 1 1 1 1 0 1 1, T(D) the polynomial each changing round replaced, B(D) 1 until the eighth round and then 1 + D + D²
- A print’s own example Example 6.33, p. 201: the nine bits have linear complexity 5, and ⟨5, 1 + D³ + D⁵⟩ generates them
- A print’s own example The Handbook’s Example 6.26 (Figure 6.6): the linear complexity profile of the 20-periodic sequence begins 1, 1, 1, 3, 3, 3, 3, 5, 5, 5, 6, 6, 6, 8, 8, 8, 9, 9, 10, 10, 11, 11, 11, 11, 14, 14, 14, 14, 15, 15, 15, 17, 17, 17, 18, 18, 19, 19, 19, 19
- A print’s own example The Handbook’s Example 6.27, p. 200: the sequence with a 1 at each place 2ʲ − 1 has L(sᴺ) = ⌊(N + 1)/2⌋ for every N
- A print’s own example Fact 6.19, p. 198: zeros have linear complexity 0, and zeros ending in a 1 as many as their bits
Limits
Binary registers only, of at most 64 stages; 8,192 bits are read. A period is not run out beyond four million units of time, or beyond 65,536 for more than 31 stages, and a register longer than its polynomial’s degree is given none. No polynomial is tested for being primitive: the period is found by running. A low linear complexity shows that a register makes the bits; a high one does not show they are random, as the Handbook’s Example 6.27 warns. Massey’s paper of 1969 is cited from the Handbook, not read.
- A. J. Menezes, P. C. van Oorschot and S. A. Vanstone, Handbook of Applied Cryptography (CRC Press, 1997), chapter 6, §6.2 (the authors’ own copy)
- J. L. Massey, “Shift-register synthesis and BCH decoding”, IEEE Transactions on Information Theory 15 (1), 1969, pp. 122–127 (cited from the Handbook, not read here)