# DES: How to find the Inverse of the Initial Permutation?

I am doing a DES problem by hand and I want to know how you calculate the inverse of the initial permutation. I know what the permutation is, but how do you find it based off the given initial permutation?

• Make a table of all possible $(i,P(i))$. Then sort by the second value (i.e. $P(i)$). This new table can be read as $(i,P^{-1}(i))$. Expected run-time: $O(2^n\cdot n)$ for an n-bit permutation – SEJPM Dec 14 '15 at 19:28
• i, being what eactly? – Ryan Weaver Dec 14 '15 at 19:34
• $i$ being a bit string taking all possible inputs to the permutation function. This means for an n-bit permutation $0\leq i\leq2^{n}-1$. – SEJPM Dec 14 '15 at 19:37
• So for instance, the initial permutation for DES is a 64 bit permutation. Would that not be ridiculous to do all i for 0 <= i <= 2^64-1? I am trying to get this wrapped around my head so thank you for you time. – Ryan Weaver Dec 14 '15 at 19:46
• This is feasible (although very costly). The easier approach would be to just consider the bit permutation used by DES which is a 6-bit permutation (mapping bit 0 to bit 58, bit 1 to bit 50, ...). See Wikipedia for more data. – SEJPM Dec 14 '15 at 19:52

Ryan, the permutation IP is fixed so it is a table of only 64 entries, mapping the $$i$$-th position to the $$P(i)$$th position. Each entry $$i$$ (and $$P(i)$$) of the table is in the range $$1,\ldots,64,$$ so 6 bits are enough to represent each, but a byte can also be used.