In our Discrete Mathematics class, the way the textbook introduces the transposition cipher is as follows:
As
a key we use a permutation $\sigma$ of the set $\{1, 2, \ldots , m\}$ for some positive integer $m$, that is, a one-to-one function from $\{1, 2, \ldots, m\}$ to itself. To encrypt a message we first split its letters into blocks of size $m$. We encrypt the block $p_1p_2\ldots p_m$ as $c_1c_2\ldots c_m = p_{\sigma(1)}p_{\sigma(2)}\ldots, p_{\sigma(m)}$. To decrypt a ciphertext block $c_1c_2, \dots c_m$, we transpose its letters using the permutation $\sigma^{−1}$, the inverse of $\sigma$.
And then an example is brought up, where a transposition cipher is done.
Using the transposition cipher based on the permutation $\sigma$ of the set $\{1, 2, 3, 4\}$ with $\sigma(1) = 3$, $\sigma(2) = 1$, $\sigma(3) = 4$, and $\sigma(4) = 2$, encrypt the plaintext message PIRATE ATTACK…We first split the letters of the plaintext into blocks of four letters. We obtain PIRA TEAT TACK. To encrypt each block, we send the first letter to the third position, the second letter to the first position, the third letter to the fourth position, and the fourth letter to the second position. We obtain IAPR ETTA AKTC.
The confusion arises because given the notation $c_1c_2\ldots c_m = p_{\sigma(1)}p_{\sigma(2)}\ldots p_{\sigma(m)}$, wouldn't the ciphered text be in the form $p_3p_1p_4p_2$ (rather than the suggested $p_2p_4p_1p_3$)? I've looked online and it may be that the difference is caused because the permutation is an active permutation, not a passive one, but I still find this to not make sense.
Best Answer
I think the most intuitive explanation of a transposition cipher is that we move the letter in position $k$ to position $\sigma(k).$ That is how the example is done.
But you're right, this contradicts the way the transposition for a permutation $\sigma$ was defined earlier. In order to be consistent with the example, the definition should have been
$$ c_1c_2\ldots c_m = p_{\sigma^{-1}(1)}p_{\sigma^{-1}(2)},\ldots,p_{\sigma^{-1}(m)}.$$