1
$\begingroup$

In some literature I am reading – where they are explaining the permutation cipher – they have two examples, which encrypt a small block of text. But they seem to contradict each other:

First example:

permutation: ${1\text{ }2\text{ }3 \choose 3\text{ }1\text{ }2}$, plaintext: VEN, ciphertext =NVE

Second example:

permutation: ${1\text{ }2\text{ }3 \choose 2\text{ }3\text{ }1}$, plaintext: TEN, ciphertext = NTE

Am I missing something? The second example makes sense to me, but not the first. Why isn’t the ciphertext for the first example not ENV?

$\endgroup$
4
  • $\begingroup$ Looks like the 2 permutations are different? $\endgroup$ May 31, 2014 at 1:25
  • 1
    $\begingroup$ The first permutation just shifts each letter to the right cyclically. Look at the permutation: (1, 2, 3) => (3, 1, 2). So (1=V, 2=E, 3=N) is mapped to (3=N, 1=V, 2=E), that is, NVE. $\endgroup$
    – Thomas
    May 31, 2014 at 1:47
  • $\begingroup$ I'm afraid i still don't understand, am i not supposed to read the permutation as $\sigma(1)=3,\sigma(2)=1, \sigma(3)=2$? The element in the first position goes to the third position, second to first, third to second? $\endgroup$ May 31, 2014 at 23:41
  • $\begingroup$ The first permutation is a circular left shift, the second is the right shift. $\endgroup$ Jun 1, 2014 at 7:05

2 Answers 2

4
$\begingroup$

The permutations in your question are given in Cauchy's two-line notation, where the upper line gives the input index to the permutation function, and the lower line gives the resulting permuted index.

For example, the definition $$\sigma = {1\ 2\ 3 \choose 3\ 1\ 2}$$ means the same as $$\sigma(1) = 3,\quad \sigma(2) = 1,\quad \sigma(3) = 2.$$ Thus, if we apply this permutation $\sigma$ to a tuple $x = (x_1, x_2, x_3)$, we obtain the permuted tuple $$x_\sigma = \sigma \cdot x = (x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}) = (x_3, x_1, x_2).$$

In particular, if $x = (x_1, x_2, x_3) = (\text{V}, \text{E}, \text{N})$, then $x_\sigma = (x_3, x_1, x_2) = (\text{N}, \text{V}, \text{E})$.

This is easy visualize if you simply replace the indices $1$, $2$ and $3$ in the definition of the permutation with the elements $x_1 = \text{V}$, $x_2 = \text{E}$ and $x_3 = \text{N}$ to be permuted, giving $${x_1\ x_2\ x_3 \choose x_3\ x_1\ x_2} = {\text{V E N} \choose \text{N V E} }.$$


The second example in your question appears to be incorrect: given the permutation $$\sigma' = {1\ 2\ 3 \choose 2\ 3\ 1}$$ and the input $x' = (x'_1, x'_2, x'_3) = (\text{T}, \text{E}, \text{N})$, the output should be $$x'_{\sigma'} = \sigma' \cdot x' = (x'_{\sigma'(1)}, x'_{\sigma'(2)}, x'_{\sigma'(3)}) = (x'_2, x'_3, x'_1) = (\text{E}, \text{N}, \text{T}),$$ not $(x'_3, x'_1, x'_2) = (\text{N}, \text{T}, \text{E})$. It would, however, be correct if we replaced the permutation $\sigma'$ with its inverse $$\sigma'^{-1} = {2\ 3\ 1 \choose 1\ 2\ 3} = {1\ 2\ 3 \choose 3\ 1\ 2}$$ (which, as it happens, equals the first permutation $\sigma$) obtained by swapping the rows and (optionally) re-sorting the columns in the two-line definition of $\sigma'$.

$\endgroup$
1
$\begingroup$

There are two possible explanations.

  1. The literature you are reading swapped the positions of the plaintext and ciphertext in the second example. If you were to permute TEN, the result is ENT.

  2. There is a mistake in either the permutation value or in the resultant ciphertext. If the first example permutation was used, the ciphertext would be correct.

Either is a likely explanation, as the permutations are the inverse of eachother.

EDIT:
I was processing encryption as decryption and vice versa based on a false assumption, which linked the explanations to the wrong examples. This has been fixed.

$\endgroup$
2
  • $\begingroup$ Okay, i wondered that, as i have come across other errors as well, things more obvious. So having to second guess yourself alot is a tiny bit annoying, when you are reading an "introduction" book. But as they progress further, the next example is: > permutation: ${1\text{ }2\text{ }3\text{ }4\text{ }5 \choose 5\text{ }3\text{ }4\text{ }2\text{ }1}$, plaintext: MEETA, ciphertext = AETEM . Should the ciphertext be that or ATEEM? $\endgroup$ Jun 1, 2014 at 17:21
  • 1
    $\begingroup$ My examples were flipped, as is how you are processing the permutation. "Two goes to Three" should actually be "Two goes to position Four" in that example. The ciphertext should be AETEM. $\endgroup$ Jun 1, 2014 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.