1
$\begingroup$

Trying to write a C program that implements the DES standard (FIPS 46-3). I am unsure about how the standard should be interpreted when computing the various permutations specified in the document, with regard to the external data that is loaded in the algorithm.

For example, the IP (Initial Permutation) takes the 64 bits of input and arranges them so that the result has bit 58 of the input as its first bit, bit 50 as its second bit, and so on.

Assuming (is this correct?) that "first bit" of output means MSB, the problem still remains with what is meant by "bit 58" of input. Where do we start counting?

For example, if the input is read from a file in a buffer (C array) of 8 bytes, where is the 58th bit to be found: in buffer[0] or in buffer[7]? Both seem plausible: in buffer[0] (because logically is the last in the row, assuming it was read first) and in buffer[7] (assuming we believe we are reading an integer starting with its MSB).

What is the community consensus about this issue?

Thank you.

$\endgroup$
  • $\begingroup$ This can be proven to be one way or the other given the existing applications and test vectors; we don't need a consensus, especially if fgrieu is doing the answering :P $\endgroup$ – Maarten Bodewes Jan 30 at 21:16
2
$\begingroup$

All standard literature on DES, including FIPS 46-3, number data bits starting from 1 for the most significant bit of the first word in reading order, incrementing by 1 as we go to lower-order bit, and moving to the next word after each multiple of the word size in bit. Here word can be 8-bit (for data and key), 32-bit (state formed by L/R), 28-bit (internal key formed by C/D).

For an implementer manipulating an array of 8 bytes at indexes 0 to 7 as input of IP, bit $i$ is for byte at index $\left\lfloor(i-1)/8\right\rfloor$ and has weight $2^{(-i)\bmod 8}$. In C, it might be testable as

Buffer[(i-1)>>3] & (128>>((i-1)&7))

Bit 58 belongs to the last of 8 bytes, Buffer[7], with weight 64 ( 0x40 ).

$\endgroup$
  • 1
    $\begingroup$ FWIW, the programming language PL/I, (also) designed by IBM about a decade before DES, supported bit strings with elements numbered from 1 at the top bit of the first byte on S/360, which was 8-bit-byte addressable big-endian. Also character strings from 1 as the first byte, and both either fixed or variable length. $\endgroup$ – dave_thompson_085 Jan 31 at 2:34
1
$\begingroup$

The DES Standard is an interoperability standard describing compatibility with the hardware implementation found in IBM's patent.

Initial and Inverse Initial Permutations

The initial permutation describes taking 8 input bytes bit ordered 1 to 8 with 1 having the greatest binary weight and providing an initial LR Block comprised of even and odd input byte bits.

The binary weight of an input byte bit in the 1 to 8 ms to ls notation would be expressed as (1 << 8 - x) where x a value in the range 1 to 8 and the - operator is higher precedence than the << operator.

Note that in the programming language C for instance, bits in a char of byte size would be labelled 7 down to 0 and not 1 to 8 as here.

The inverse initial permutation does the obverse while also including the output block reordering to RL. Note the IP-1 table appears rotated 90 degrees clockwise here.

From a hardware perspective you can load 8 successive bytes in the Left and Right registers by shifting them in serially where the two 32 bit registers are comprised of four 8 bit shift registers. (For the simplest DES implementation these registers also parallel load.)

The Inverse Initial Permutation serially shifts the result out to a byte wide interface. Both permutations consist of 8 wires when implementing a byte wide interface.

Permuted Choice 1 does something similar for the key which is loaded into the 28 bit C and D blocks.

Permuted Choice 1

Where we again get 8 wires to describe the permutation using 7 input byte bits. The PC-1 table is re-aligned to an 8 successive input bytes here. Note that input byte bit 4 is shifted into the concatenated last 4 bits of both C and D blocks.

For your question on the initial permutation, "...where is the 58th bit to be found: in buffer[0] or in buffer[7]?" the answer would be buffer[7], corresponding to the 8th input byte in sequence assuming buffer is an array of char values.

As commented it's not a matter of consensus. The standard is specific. There are also published known triplet values (test vectors) as well as known conforming implementations. See the answer to 64 DES full example with all the stages describing a conforming implementation which can be used for direct comparison and a source for triplet values.

$\endgroup$
  • $\begingroup$ +1 for the patent $\endgroup$ – fgrieu Feb 3 at 21:16
  • $\begingroup$ Perhaps, undelete your answer there. Even as is, it is the most useful, and I have to assign the bounty Real Soon Now. $\endgroup$ – fgrieu Nov 14 at 11:25

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.