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?
$\begingroup$
$\endgroup$
7
-
$\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$– SEJPMCommented Dec 14, 2015 at 19:28
-
$\begingroup$ i, being what eactly? $\endgroup$– Ryan WeaverCommented Dec 14, 2015 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$– SEJPMCommented Dec 14, 2015 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 WeaverCommented Dec 14, 2015 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$– SEJPMCommented Dec 14, 2015 at 19:52
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
0
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.
