3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – SEJPM Dec 14 '15 at 19:28
  • $\begingroup$ i, being what eactly? $\endgroup$ – Ryan Weaver Dec 14 '15 at 19:34
  • $\begingroup$ $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$. $\endgroup$ – SEJPM Dec 14 '15 at 19:37
  • $\begingroup$ 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. $\endgroup$ – Ryan Weaver Dec 14 '15 at 19:46
  • $\begingroup$ 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. $\endgroup$ – SEJPM Dec 14 '15 at 19:52
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

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.