How to look up permutation tables in DES?

Question

For finding out the final permutation or initial permutation in DES Encryption, we need to look up permutation tables.

Taking an example: Find the output of the initial permutation box when the input is given in hexadecimal as: 0x0000 0080 0000 0002. After reading the solution, I am not able to understand:

1. How is the bit 25 and bit 64 1s?

2. How does in final permutation bit 25 becomes, bit 64 and bit 63 becomes bit 15?

Please explain the outcomes.

Answer 1

DES is specified in FIPS 46-3, which is a rather old standard that uses a somewhat uncommon numbering of bits within bytes. Namely, they start at 1, and count bits from left to right.

So, in the following sequence of bytes:

00 00 00 80 00 00 00 02

First byte is bits 1 to 8, second byte is bits 9 to 16, third byte is bits 17 to 24, fourth byte (the one with value 80) is bits 25 to 32, and so on. If you consider that 80 is written in binary 10000000, and that these bits are thus numbered from 25 to 32 left-to-right, then bit 25 has value 1. Similarly, the last byte (02) contains bits 57 to 64; bit 63 has value 1.

The "solution" in the document you link to contains the sentence:

Given the hex input, when we expand it to binary, we find that only bit 64 and bit 25 are 1s and the other bits are 0s.

which is wrong, and probably a typographic error. It should read "only bit 63 and bit 25 are 1s".

The "initial permutation" is specified on page 10 of FIPS 46-3; it lists the bits of the output of the permutation, and says where they come from (this is a "comes from" table, not a "goes to" table). The input bit 25 goes to output bit 37 (the value "25" is the 37th in the table), while input bit 63 goes to output bit 57. This should yield:

00 00 00 00 08 00 00 80

which is not at all what the document lists as "solution". Indeed, the solution talks about the "final permutation" (while the question was about the "initial permutation"). If we suppose that the question also has a typographic error (the author wrote "initial" but thought "final") then we can try the final permutation, whose table is also on page 10 of FIPS 46-3. In that table, bit 25 of the input goes to bit 64 of the output (the number "25" appears as 64th, i.e. last, element of the table of IP^-1), while bit 63 of the input goes to bit 15 of the output (the number "63" appears as 15th element in the table). In that case, this would yield this output:

00 02 00 00 00 00 00 01

which is what the "solution" gives as correct answer.

Summary: the document contains two errors:

• In the question, it says "initial permutation" but it should be "final permutation".
• In the solution, it says "bit 64 and 25" but it should be "bit 63 and 25".

With these two fixes, the question and the solution now match each other.

I have not looked at the other questions/solutions, but two such errors in the first question shed a poor light on the document quality.