# 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? 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. 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

## 2 Answers

The inverse of the Initial Permutation (IP) of DES is the Final Permutation (FP) (in the Standard (NIST FIPS 46-3) FP is called "IP-1"). Number the 64 bits of the input to IP from 1 to 64. Subject them to IP, so that the 1st 8 bits of the output of IP are bits { 58, 50, 42, 34, 26, 18, 10, 2 } etc. of the input. Renumber (not reorder) the bits of the output of IP from 1 to 64. Treat that as the input to FP.

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.