(Last Mod: 27 November 2010 21:38:01 )
As the name implies, a substitution operation involves replacing one thing with something else. In cryptography, it generally involves replacing one symbol (or group of symbols) with another symbol (or group of symbols). For example, in the Caesar Shift Cipher, each letter of the plaintext is replaced by the letter three places further down in the alphabet (wrapping back to the beginning if the end of the alphabet is reached).
A transposition operation merely involves swapping the places of two things, which are said to have thus been transposed. A strict definition requires that exactly two items are swapped and that all other things in the set remain in place. However, in practice, a transposition is frequently used less rigorously to refer to any reordering of the members of a set, although this is more properly referred to as a permutation.
A permutation is an arbitrary reordering of the members of a set. While not glaringly obvious, any permutation can be accomplished by the proper sequence of transpositions (using the strict definition, i.e., swap exactly two members).
Permutations can be described by several simple and easy to understand notations. One way to define the permutation is to simply write a list that indicates which member from the old set occupies that spot in the new set. Thus, one permutation of a 9-element set could be described by:
P = (4,7,10,3,5,9,1,8,6,2)
This merely tells us that the first element in the new set is the fourth element from the old set while the second element of the new set is the seventh element from the old set, and so forth. Hence this permutation working on the set {HELLOWORLD} would be {LODLOLHRWE}. Note that, if the elements of the old set are simply an ordered set of integers from 1 to 10, then the new set is the same as the description of the permutation itself (except that we are using curly braces to denote a set and parentheses to denote a permutation instruction.
While the above description is simple and completely general, it merely describes the final result and fails to capture any underlying structure of the permutation itself. For example, a permutation that simply swaps two members is, in many respects, "simpler" than a permutation in which all of the members are shuffled. To capture this information is a way that makes it readily apparent, we use the concept of a "cycle", which will evolve naturally as we refine our notation.
Another way to describe the permutation is as a list of moves. For instance, in the permutation above the first item in the list is replaced by the fourth item in the list, which could be written as (1<=4). Note that we have not said that the fourth element is replaced by the first; in other words, we are not performing a transposition. This notation simply means that the fourth element from the old set becomes the first element of the new set, nothing more. Using this notation, our permutation could be defined as:
P = (1<=4)(2<=7)(3<=10)(4<=3)(5<=5)(6<=9)(7<=1)(8<=8)(9<=6)(10<=2)
Now observe two things about the above description. First, the fact that the 5th and 8th elements are not touched becomes readily apparent. Also, note that there is no requirement that the operations be performed in the order shown since they are independent (don't forget that, in each case, we are talking about taking an item from the old list and placing it in the new list). Hence we could write this as:
P = [(1<=4)(4<=3)(3<=10)(10<=2)(2<=7)(7<=1)][(5<=5)][(6<=9)(9<=6)][(8<=8)]
Here all we have done is to rearrange things so that the next operation moves something into the position that the previous operation moved something out of. At some point, we can't continue doing this because the position that we need has already been used -- for instance, after (7<=1) we would like to use (1<=4), but it has already been used. So instead we pick one the next unused operation and continue on. The square brackets indicate the groupings that result. We can think of each grouping as a "cycle" of positions that rotate one place within the group. With this interpretation, we can simplify our notation as a list of cycles and write it as:
P = (1,4,3,10,2,7)(5)(6,9)(8)
Which, you might have noticed, simply involves keeping the left hand side from each operation within each cycle. Next, we can order the cycles from smallest to largest and, within each group of cycles of the same size, list them in the order of the smallest index within each cycle. It might not be apparent, but a given cycle, such as (6,3,4,8), can be performed starting at any element, hence any rotation of the cycles, such as (4,8,6,3), is the same thing. Thus, before we order the cycles, we rotate each one so that it begins with the lowest index within the cycle. Thus the cycle here would be (3,4,8,6). After we perform the ordering, our final permutation is defined as:
P = (5)(8)(6,9)(1,4,3,10,2,7)
From this notation, the structure of the permutation becomes readily apparent. Namely that we have two 1-cycles (cycle of length 1), meaning that those elements remain in place, one 2-cycle, which is a simple swap or transposition, and one 6-cycle. Note that, to be valid, a permutation must include every index exactly once somewhere in the list.
For the sake of completeness, we mentioned initially that any permutation can be performed as a sequence of simple transpositions. We are now in a position to see how to do that since, from here, it is fairly easy to see that any cycle can be expressed as a sequence of transpositions performed one after another. For instance, the cycle (1,4,6) can be accomplished by performing the transposition (1,4) and then, on the set that resulted, performing the transposition (4,6) and then, on the set that resulted from that, performing the transposition (6,1). Hence the permutation we have been working with could be accomplished by the following sequence of transpositions:
P = (6,9)[(1,4)(4,3)(3,10)(10,2)(2,7)(7,1)]
Note that this is not so much a definition of a permutation as much as it is an expression of a series of transposition operations. Although the ordering of the operations within each cycle (indicated by the square brackets) is critical (they can be rotated, but nothing more) and must be performed sequentially, the operations for different groups can be done in any order and can even be intermixed.