Computer Security and Cryptography

6.6 THE DISPLACEMENT SEQUENCE OF A PERMUTATION

Are some rotor wirings better than others? As the intent of rotor encipherment is to encipher plaintext using a large number of different 1-gram substitutions and to change the plaintext letters as much as possible, this might be used as a design paradigm. For example, if a rotor θ is wired according to a Caesar substitution C_k, the rotor's substitution is the same in each position, which might explain the weakness of C_k as a rotor.

Edward Hebern suggested that rotors should be wired so as to produce the largest number of different substitutions. Can the rotor's substitutions be different in each position? The displacement sequence of an m-letter substitution θ is the vector d_θ = (d_θ (0), d_θ (1),…, d_θ (m − 1)) defined by

What displacement sequences are possible?

Proposition 6.1:

6.1a
6.1b	If θ = θ1θ2, then dθ(i) = dθ1 (θ2(i)) + dθ1 (i) for 0 ≤ i < m.
6.1c	dθ-1 = m – d.
6.1d	dC−kθ Ck = σkdθ where σk is the left-cyclic shift of dθ by k places. σkdθ = (dθ(k), dθ(k + 1),…, dθ(m − 1), dθ(0), dθ(1), …, dθ(k − 1))

Proof: 6.1a is obvious; for 6.1b, write

Using 6.1a and 6.1b

which implies 6.1c. To prove 6.1d, use 6.1b

Proposition ...