10.1 Types of operations

All block cipher operations are actually made up of conceptually simpler building blocks. Usually, the elements of V are represented as strings of a fixed length n out of an alphabet A, while elements of K are also represented as strings of some length k in the same alphabet (k < n).

There is one obvious way to obtain a permutation of V and that is to apply a permutation in Perm_n to permute the elements of the string. Such an operation is called a ``Transposition'' (which is confusing for group theorists familiar with the notion of transpositions as elements of the permutation group that interchange two elements!). Another obvious way to obtain a permutation on V is apply a permutation in Perm(A). Such an operation is called a ``Substitution'' since it substitutes one letter of the alphabet with another. It is clear that Substitutions and Transpositions commute with one another and form the subgroup Perm_n×Perm(A) of Perm(V). Thus, a cryptanalyst (or ``code cracker'') could try to solve the problem of finding the Substitution and Transposition independently, thus weakening the cryptosystem. Thus we need another operation that ``mixes'' the Substitutions with the Transpositions; appropriately this is known as ``Mixing''. One method used for mixing is ``Polyalphabetic'' Substitution; different substitutions rules are applied to different portions of the string; in addition a Transposition of these different portions can also be performed. A different procedure is break the string into ``words'' of m ``letters'' in the alphabet and directly find a nice permutation that performs ``Word substitution'' (using a ``code book'' for example).

Now only some of these operations need to depend on the key and the operations can be repeated in multiple ``rounds'' since the new collection is not commutative anymore (because of Mixing).