Re: DES implementation questions (FinalPermutation code)

From: Brian Ross (brian.ross.x_at_rogers.com)
Date: 06/15/05 

Date: Tue, 14 Jun 2005 23:18:13 -0400

"Richard Outerbridge" <outer@interlog.com> wrote in message
news:outer-CB7858.21241214062005@news.bellglobal.com...
> In article <xpOdndeqlIHkzjLfRVn-hg@rogers.com>,
> "Brian Ross" <brian.ross.x@rogers.com> wrote:
>
>> Hi,
>>
>> I am trying to understand some DES implementation code I have.
>>
>> For the most part, I think I have finally figured out how everything
>> works
>> from the InitialPermutation code to the DES rounds. The problem is that I
>> don't quite understand the final permutation code.

[...]

>> The problem is that when I walk through the code and how the bits are
>> repositioned I can not come up with anything that resembles the final
>> permutation table in the standard (and I tried verifying my steps many
>> times). It certainly isn't as clear as the InitialPermutation seemed to
>> work
>> out.
>>
>> Can someone help me understand this? It's pretty much the last part that
>> I
>> do not understand. Is there some trick I am missing for this last part?
>
> Please post the IP function. It should be almost the reverse. This
> translation into portable C works for me.
>
> Again, for the record, IP and IP-1 are due to Dan Hoey.

Here is the IntialPermutation code (below with some comments I added
regarding the output bit positions):

I understand the InitialPermutation code and that it produces the expected
output matching the DES standard IP table (with an extra rotate 1 bit to the
left and I understand why this rotate is necessary).

My problem is that I don't really understand the FinalPermutation code.
Isn't the FinalPermutation code supposed to be the complete inverse of the
InitialPermutation code? This doesn't really seem to be the case when I run
tests?

ie.. if I do:

    InitialPermutation(Left, Right)
    FinalPermutation(Left, Right)

I do not end up with the same result as I started with - yet my DES test
vectors indicate the complete encrypt/decrypt code is functioning correctly.

It 'looks' like there is some sort of Left/Right swap taking place in the FP
code as well as some of the inner bits pairs are swapped. I don't see how
this even remotely resembles the standard final permutation but it must be
correct since the overall code functions correctly. As far as I can tell the
output from the DES rounds is normal with the exception of the rotate left 1
bit still present and (I think) an extra L/R swap.

Can you provide the little hint that I need to complete my understanding?

Thanks 

---
void CBlockCipherDES::DoInitialPermutation(UnsignedInteger32& Left, 
UnsignedInteger32& Right) throw()
{
    // Left  = |01|02|03|04|05|06|07|08| |09|10|11|12|13|14|15|16| 
|17|18|19|20|21|22|23|24| |25|26|27|28|29|30|31|32|
    // Right = |33|34|35|36|37|38|39|40| |41|42|43|44|45|46|47|48| 
|49|50|51|52|53|54|55|56| |57|58|59|60|61|62|63|64|
    UnsignedInteger32 Temp = 0;
    Right = RotateLeft32(Right, 4);
    Temp = ( Left ^ Right ) & 0xF0F0F0F0;
    Left ^= Temp;
    Right = RotateRight32( Right ^ Temp, 20 );
    Temp = ( Left ^ Right ) & 0xFFFF0000;
    Left ^= Temp;
    Right = RotateRight32( Right ^ Temp, 18 );
    Temp = ( Left ^ Right ) & 0x33333333;
    Left ^= Temp;
    Right = RotateRight32( Right ^ Temp, 6 );
    Temp = ( Left ^ Right ) & 0x00FF00FF;
    Left ^= Temp;
    Right = RotateLeft32( Right ^ Temp, 9 );
    Temp = ( Left ^ Right ) & 0xAAAAAAAA;
    Left = RotateLeft32( Left ^ Temp, 1 );
    Right ^= Temp;
    // Left  = |50|42|34|26|18|10|02|60| |52|44|36|28|20|12|04|62| 
|54|46|38|30|22|14|06|64| |56|48|40|32|24|16|08|58|
    // Right = |49|41|33|25|17|09|01|59| |51|43|35|27|19|11|03|61| 
|53|45|37|29|21|13|05|63| |55|47|39|31|23|15|07|57|
    // Note: Left, Right are rotated left by 1 bit compared with standard 
InitialPermutation table
}
---

Relevant Pages

  • DES implementation questions (FinalPermutation code)
    ... I am trying to understand some DES implementation code I have. ... don't quite understand the final permutation code. ... UnsignedInteger32 Temp = 0; ... I am pretty sure that the output from the DES rounds is still rotated left ...
    (sci.crypt)
  • Re: DES implementation questions (FinalPermutation code)
    ... > I am trying to understand some DES implementation code I have. ... > don't quite understand the final permutation code. ... On an architecture which somehow guarantees a clean 32-bit rotate (no ...
    (sci.crypt)