0
$\begingroup$

I am trying to understand the difference between permutation and transposition. I have seen a similar question in the forum but I would like to ask you for proper definitions and examples of each. I'm trying to understand the DES algorithm and I'd like to understand if the halving of the initial block and eventual swapping of the halves would be permutation or transposition. Thank you in advance.

$\endgroup$
1
  • 2
    $\begingroup$ First of all, it is better to link the similar question that doesn't resolve your issue with the reasons. Second, Stack Overflow is not a forum, it is a question and answer site. Finally, your title is quite broad that one may consider the question is about classical ciphers as you tagged! transposition is a permutation. In DES, it is called the network ( a permutation) and whole aim is to create a Pseudo-Random Permutation (PRP) $\endgroup$
    – kelalaka
    Nov 27 '21 at 19:11
2
$\begingroup$

This answer focuses on bit permutations as used in the context of DES for bit permutations IP, IP-1, and E. It numbers bits starting from $1$, as in DES.


A bit permutation is a function $g$ on the set $\{0,1\}^n$ of $n$-bit bistrings. It's entirely defined by a vector of $n$ distinct integers $p_i$ with $1\le p_i\le n$, and the property that for any bitstring $x$ and any integer $i$ with $1\le i\le n$, bit number $i$ of the image of bitstring $x$ by function $g$ is bit number $p_i$ of $x$.

In other word, each input bit goes to it's uniquely assigned output bit, and output bit $i$ is input bit $p_i$.

Every bit permutation is a bijection on the set $\{0,1\}^n$. Equivalently: every bit permutation is a permutation of the set of $n$-bit bistrings. There are $n!$ such bit permutations, versus the much larger $(2^n)!$ such permutations. The subset of bit permutations is closed under function composition: applying any two fixed bit permutations yields a bit permutation.

Note: some authors use bit transposition or even transposition to designate a bit permutation as defined above, and distinguish it from a permutation. That's not what I'll do in the following, but it could be what the OP has in mind.


A bit transposition is a particular bit permutation of $n$-bit bitstrings, entirely defined by two integers $\ell$ and $c$ with $n=\ell\cdot c$. It's $n$ integers $p_i$ are $p_i=1+((i-1)\bmod c)\cdot c+\lfloor (i-1)/c\rfloor$, for $1\le i\le n$.

In other words, when we write the input bits as $\ell=n/c$ lines and $c$ columns, and the output bits as $c$ lines and $\ell$ columns, output column $j$ comes from input line $j$.

For example, with $\ell=3$ and $c=2$, the bit transposition has $p_1=1$, $p_2=3$, $p_3=5$, $p_4=2$, $p_5=4$, $p_6=6$, which is best represented as

     1   3   5
     2   4   6

Sometime, the bit permutation with $p_i=\ell\cdot c-((i-1)\bmod c)\cdot c-\lfloor (i-1)/c\rfloor$ is also considered an alternate bit transposition. With $\ell=3$ and $c=2$, the alternate bit transposition has $p_i$

     6   4   2
     5   3   1

When $n$ is a square and $\ell,c$ are unspecified, they are assumed to be $\sqrt n$, and such square bit transpositions are involutions.


Would the halving of the initial block and eventual swapping of the halves be a permutation or a transposition?

In DES, the transformation (consisting of IP followed by halving) from 64-bit input to LR is a bit permutation (thus a permutation of the set $\{0,1\}^n$, but that's much less specific). It's $p_i$ are given in the IP table:

    58  50  42  34  26  18  10   2
    60  52  44  36  28  20  12   4
    62  54  46  38  30  22  14   6
    64  56  48  40  32  24  16   8
    57  49  41  33  25  17   9   1
    59  51  43  35  27  19  11   3
    61  53  45  37  29  21  13   5
    63  55  47  39  31  23  15   7

A very regular swapping of lines makes it

    64  56  48  40  32  24  16   8
    63  55  47  39  31  23  15   7
    62  54  46  38  30  22  14   6
    61  53  45  37  29  21  13   5
    60  52  44  36  28  20  12   4
    59  51  43  35  27  19  11   3
    58  50  42  34  26  18  10   2
    57  49  41  33  25  17   9   1

which is the alternate square bit transposition for $n=64$. Thus IP is nearly a bit transposition.

When seen as operating on LR, the swapping of the halves is a bit permutation, which $p_i$ are given by:

    33  34  35  36  37  38  39  40
    41  42  43  44  45  46  47  48
    49  50  51  52  53  54  55  56
    57  58  59  60  61  62  63  64
     1   2   3   4   5   6   7   8
     9  10  11  12  13  14  15  16
    17  18  19  20  21  22  23  24
    25  26  27  28  29  30  31  32

It's not a bit transposition, but it's a very regular bit permutation (as bit transpositions are), and an involution (which square bit transpositions are).

$\endgroup$
2
  • $\begingroup$ permutation is a bijective function from a set S to S i.e., ${\phi:S \mapsto S }$, it performs more than one transposition. Hence Transposition is changing a position of two elements. for ex. transposing (12) effectively means send 1 to 2 and 2 to 1. $\endgroup$
    – SSA
    Nov 28 '21 at 8:54
  • $\begingroup$ @SSA: the definition that you give is that of a permutation. When applied to the set $\{0,1\}^n$, it yields $(2^n)!$ possible permutations. That's not the definition used in DES when it comes to IP and E, which are bit permutations. I clarified the answer focuses on the later kind. $\endgroup$
    – fgrieu
    Nov 28 '21 at 10:48

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.