3
$\begingroup$

I know how initial permutation works, but I've never heard of this part. People say it's Richard Outerbridge's initial permutation and that it's faster than usual IP (initial permutation) and simple.

How does this IP work? I've only the source to work with:

work   = ((leftt >>  4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);

work   = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);

work   = ((right >>  2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);

work   = ((right >>  8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);
right  = (right << 1) | ((right >> 31) & 1);

work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;
leftt  = (leftt << 1) | ((leftt >> 31) & 1);
Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Hint: the IP of DES essentially transposes a square matrix of 8x8 bits, except for putting even lines first (otherwise keeping their order). Richard Outerbridge's technique uses that regularity to greatly reduce the number of operations compared to a bit-by-bit selection. $\endgroup$
    – fgrieu ♦
    May 12, 2018 at 13:56
  • $\begingroup$ thanks for the hint. but still confused, can you explain more details of that?? $\endgroup$
    – yogoyogo
    May 12, 2018 at 15:05
  • 1
    $\begingroup$ Hint2: Show that each group of three instructions calculating work then performing two ^= has merely exchanged 16 bits of lefttand right, as selected by the mask, moving them right and left by the shift count. The technique is sort of an extension of the idiomx^=y; y^=x; x^=y; swapping integer variables xand y, with added selection of bits, and shifts. Hint3: Track what each 32 bits of lefttand rightcontains: initially, after the last in said group of three instructions, and after the additional two instructions. And when you get it, answer your own question! $\endgroup$
    – fgrieu ♦
    May 12, 2018 at 15:25
  • 1
    $\begingroup$ You can find this technique to implement permutations in the first chapter "Bitwise Tricks & Techniques" of Volume 4 of D.E.Knuth "The Art of Computer Programming". $\endgroup$
    – j.p.
    May 14, 2018 at 5:14
  • 2
    $\begingroup$ "My" IP is mostly MIT Hacker Dan Hoey's, to be honest, rotated by one bit, as admirably explained below. I can't remember where I found it. He's mentioned in the comments. __outer /ps yes, I was Googling myself :) $\endgroup$
    – outer
    Jan 26, 2019 at 4:53

1 Answer 1

Reset to default
6
$\begingroup$

By definition, applying the initial Permutation of DES is shuffling bits per

01 02 03 04 05 06 07 08           58 50 42 34 26 18 10 02
09 10 11 12 13 14 15 16           60 52 44 36 28 20 12 04
17 18 19 20 21 22 23 24      \    62 54 46 38 30 22 14 06
25 26 27 28 29 30 31 32   ----\   64 56 48 40 32 24 16 08
33 34 35 36 37 38 39 40   ----/   57 49 41 33 25 17 09 01
41 42 43 44 45 46 47 48      /    59 51 43 35 27 19 11 03
49 50 51 52 53 54 55 56           61 53 45 37 29 21 13 05
57 58 59 60 61 62 63 64           63 55 47 39 31 23 15 07

where the left table represents, in reading order, bits of the 64-bit input from first (most significant) to last; and the right table represents, in reading order, the Left then Right 32-bit registers, per that same convention.

That transformation has great regularity: each line of the output (in reading order) is a column of the input (from bottom to top). That's a property of a transpose except for inverted order. IP is a mirror of the input according to the / diagonal, followed by a regular shuffling of lines (lines 1 2 3 4 5 6 7 8 go to lines 4 8 3 7 2 6 1 5).

This structure of IP has a hardware rationale: the transpose allows an implementation with Left and Right registers implemented each as four 8-bit shift registers, with 1 bit entering in each of the 8 shift registers for each plaintext octet sequentially fed into the DES hardware. And the shuffling brings next to each others the bits that interact when XORing the Left and Right registers.

The question's code makes use of 5 "Half-Butterfly Permutations" (as I name them by analogy with the butterfly diagram) indexed with $k$ taking all values from 0 to 4. Each splits the 32-bit lleft and right registers into $2^{5-k}$ segments each $2^k$-bit, and exchanges odd-numbered segments of one register with the higher (even-numbered) segment of the other, with thus a shift by $2^k$-bit.

One general HBP is implemented with 3 instructions involving a total of 6 bitwise operations directly supported by C. It uses XOR in a way similar to exchanging x and y with the idiom x^=y; y^=x; x^=y; taking advantage of associativity and commutativity to avoid a work value; but uses one due to the shifting and masking.

There are some irregularities in the code to perform the prescribed shuffling of lines. Also, the code wants to end with the 32-bit lleft and right pre-rotated on the left by 1 bit, because then the low-order 6 bits of these registers are properly aligned to serve as index in an S-box (after XOR with sub-key); and the HBP with $k=0$ is performed between these two rotations, because that removes the shifts in that HBP.

Here is how it goes step by step. We start from

01 02 03 04 05 06 07 08     most  significant byte of lleft
09 10 11 12 13 14 15 16     :
17 18 19 20 21 22 23 24     :
25 26 27 28 29 30 31 32     least significant byte of lleft
33 34 35 36 37 38 39 40     most  significant byte of right
41 42 43 44 45 46 47 48     :
49 50 51 52 53 54 55 56     :
57 58 59 60 61 62 63 64     least significant byte of right

then perform the Half-Butterfly Permutation with $k=2$

work   = ((leftt >> 4) ^ right) & 0x0f0f0f0f;
right ^= work;
leftt ^= (work << 4);

giving

37 38 39 40 05 06 07 08     most  significant byte of lleft
45 46 47 48 13 14 15 16     :
53 54 55 56 21 22 23 24     :
61 62 63 64 29 30 31 32     least significant byte of lleft
33 34 35 36 01 02 03 04     most  significant byte of right
41 42 43 44 09 10 11 12     :
49 50 51 52 17 18 19 20     :
57 58 59 60 25 26 27 28     least significant byte of right

then perform the HBP with $k=4$

work   = ((leftt >> 16) ^ right) & 0x0000ffff;
right ^= work;
leftt ^= (work << 16);

giving

49 50 51 52 17 18 19 20     most  significant byte of lleft
57 58 59 60 25 26 27 28     :
53 54 55 56 21 22 23 24     :
61 62 63 64 29 30 31 32     least significant byte of lleft
33 34 35 36 01 02 03 04     most  significant byte of right
41 42 43 44 09 10 11 12     :
37 38 39 40 05 06 07 08     :
45 46 47 48 13 14 15 16     least significant byte of right

then perform the HBP with $k=1$

work   = ((right >>  2) ^ leftt) & 0x33333333;
leftt ^= work;
right ^= (work << 2);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
57 58 41 42 25 26 09 10     :
53 54 37 38 21 22 05 06     :
61 62 45 46 29 30 13 14     least significant byte of lleft
51 52 35 36 19 20 03 04     most  significant byte of right
59 60 43 44 27 28 11 12     :
55 56 39 40 23 24 07 08     :
63 64 47 48 31 32 15 16     least significant byte of right

then perform the HBP with $k=3$

work   = ((right >>  8) ^ leftt) & 0x00ff00ff;
leftt ^= work;
right ^= (work << 8);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
51 52 35 36 19 20 03 04     :
53 54 37 38 21 22 05 06     :
55 56 39 40 23 24 07 08     least significant byte of lleft
57 58 41 42 25 26 09 10     most  significant byte of right
59 60 43 44 27 28 11 12     :
61 62 45 46 29 30 13 14     :
63 64 47 48 31 32 15 16     least significant byte of right

then perform the pre-rotation of right by one bit to the left

right  = (right << 1) | ((right >> 31) & 1);

giving

49 50 33 34 17 18 01 02     most  significant byte of lleft
51 52 35 36 19 20 03 04     :
53 54 37 38 21 22 05 06     :
55 56 39 40 23 24 07 08     least significant byte of lleft
58 41 42 25 26 09 10 59     most  significant byte of right
60 43 44 27 28 11 12 61     :
62 45 46 29 30 13 14 63     :
64 47 48 31 32 15 16 57     least significant byte of right

then perform the HBP with $k=0$, eased by the previous rotation

work   = (leftt ^ right) & 0xaaaaaaaa;
leftt ^= work;
right ^= work;

giving

58 50 42 34 26 18 10 02     most  significant byte of lleft
60 52 44 36 28 20 12 04     :
62 54 46 38 30 22 14 06     :
64 56 48 40 32 24 16 08     least significant byte of lleft
49 41 33 25 17 09 01 59     most  significant byte of right
51 43 35 27 19 11 03 61     :
53 45 37 29 21 13 05 63     :
55 47 39 31 23 15 07 57     least significant byte of right

then perform the pre-rotation of leftt by one bit to the left

leftt  = (leftt << 1) | (leftt >> 31) & 1);

giving

50 42 34 26 18 10 02 60     most  significant byte of lleft
52 44 36 28 20 12 04 62     :
54 46 38 30 22 14 06 64     :
56 48 40 32 24 16 08 58     least significant byte of lleft
49 41 33 25 17 09 01 59     most  significant byte of right
51 43 35 27 19 11 03 61     :
53 45 37 29 21 13 05 63     :
55 47 39 31 23 15 07 57     least significant byte of right

Skipping the pre-rotations and accordingly adjusting the HBP with $k=0$ would have given exactly the permutation specified for IP.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.