Computer Security and Cryptography

9.19 GENERATING THE SYMMETRIC GROUP

Product block ciphers acting on plaintext on are often constructed from certain primitives; for example, XOR, addition-with-carry, and circular-shift. DES, LUCIFER, and IDEA (defined in Chapter 17) are examples. The symmetric group of is the group containing the 2ⁿ! permutations of the elements of . It is the richest possible cryptographic family; to specify an element of this symmetric group requires log₂ 2ⁿ! ≈ n2ⁿ bits

In the design of a product block cipher it seems reasonable to ask if the components of the cipher generate the symmetric group or as large as possible group.

        Proposition 9.8: The group generated by the following two operators acting on the n-vectors in

9.8a α: addition (with carry) on elements of and

9.8a ρ [ρ⁻¹]: shift-left [-right] circular

is the symmetric group of permutations of .

        Proof: This result does not