Fun with map and array slices (was Re: DES in Perl)

[roboticus]

TomY:

Pretty interesting! Since you've put a lot of work into your code, and I've never bothered to look at DES source code before, I spent a bit of time going over your code.

Beginners remarks

I've looked over your code and from a beginner's perspective, and I have only one thing I would mention: Be sure to use strict and warnings in your code to help perl alert you to possible issues. When I added strict and warnings, perl alerted me to a few undefined variables ($blocks, $chunk, etc.) as well as some missing parenthesis on some declarations. Specifically in createRoundKeys you have:

   my $i, $j;

Instead of what you probably wanted:

   my ($i, $j);

The same is true in the des subroutine.

Advanced remarks: the map operator

I realize you're a beginner, but I thought it might be helpful to show you some more intermediate and advanced idioms you can use in perl. Please note that I'm not razzing you or anything. My intent is more like "Hey, here are some nifty tricks you can look forward to using as you get more familiar with perl!".

In the beginner stage, you'll use the heck out of for loops. Later, you'll start seeing opportunities to simplify your code with some more advanced techniques. But until you know these techniques well, you won't notice the opportunity. As I was working though your code, I found a few places where I could simplify things using techniques you're not yet familiar with.

In your createRoundKeys subroutine, you're converting a buffer into a bit array and then ensuring that the values in the array are numeric with code like this:

    my @tempArr = unpack("B64", $key);
    my @keyBitsArr = split("", $tempArr[0]);
    for ($j=0; $j<=$#keyBitsArr; $j++) {
        $keyBitsArr[$j] += 0;
    }

Essentially you're splitting $tempArr[0] into a list, storing it into an array, and then making a simple transformation on the data in the array. Perl has a beautiful operator that can help you here: map It takes a bit of code and a list. For each value in the list, it assigns it to $_, then executes the bit of code, and then puts the result into a new list. So if you replace your for loop with a use of the map operator, your code would look like this:

    my @tempArr = unpack("B64", $key);
    my @keyBitsArr = split("", $tempArr[0]);
    @keyBitsArr = map { $_ + 0 } @keyBitsArr;

So here, it takes the array @keyBitsArr as a list. Then, for each element in the list, it adds 0 to it. Finally the entire list is assigned to @keyBitsArr.

Even nicer is that map doesn't need an array on the right, it just needs a list. So you can save a little more code by converting it to this:

    my @tempArr = unpack("B64", $key);
    my @keyBitsArr = map { $_ + 0 } split("", $tempArr[0]);

Now you're splitting $tempArr[0] into a list of strings, adding 0 to each of them, and then assigning the resulting list of numbers to your @keyBitsArr array.

Another thing I see you doing fairly often is using an array as a list of bit positions you use to permute a bit array into a different order. Let's take a look at one:

my @keyBitsArr56_PC1 = ();
for ($i=0; $i<=$#PC_1; $i++) {
    $keyBitsArr56_PC1[$i] = $keyBitsArr[$PC_1[$i]-1];
}

Normally C-style for loops are a signal that there may be a better way to do things. All you're really needing here is a list of the values 0 to $#PC_1, and you can use the range operator (..) with for to make a perl-style for loop:

my @keyBitsArr56_PC1 = ();
for my $i (0 .. $#PC_1) {
    $keyBitsArr56_PC1[$i] = $keyBitsArr[$PC_1[$i]-1];
}

Now, since we have a list of values 0 .. $#PC_1 and you're loading values into an array in that order and you have a simple expression to convert your value into another value, then the map operator can help you out here as well, giving you:

my @keyBitsArr56_PC1 = map { $keyBitsArr[$PC_1[$_]-1] } 0 .. $#PC_1;

Map's brother grep

It takes time to get comfortable with using map, bit it's worth your time. When you're learning map, you'll probably want to learn grep along with it. It also takes a bit of code and a list. The grep operator will also assign each value in the incoming list to $_ and execute the bit of code. The difference is that if the result is true, then the original input value gets placed in the output list, otherwise the input value is skipped.

Here's a bit of goofy code--the first statement uses map to double the values 0..10 to build a list of even numbers from 0 to 20, and the second line builds a list of even numbers from 0 to 10 by filtering out the odd values.

my @even_from_0_to_20 = map  { $_*2 }        0 .. 10;
my @even_from_0_to_10 = grep { is_even($_) } 0 .. 10;
sub is_even {
    my $val = shift;
    return 0 == $val % 2;
}

You can use map and grep multiple times with each other to accomplish some pretty interesting things. The secret to understanding map and grep is to read from the right to the left. At the right is a list of stuff and a chunk of code that you'll apply to your map or grep operator. Then you may find another bit of code and a map or grep operator. For example:

  
my @foo = map { sprintf "% 4u", $_ }
          grep { is_prime($_) }
          0 .. 1000;

Starting from the end, we find that we have a list of numbers from 0 to 1000. Then using grep we're keeping only the ones that happen to be prime. The result of that is another list that we're sending to map to format them to four-character long strings, and the final result is going into our @foo array.

Joining and splitting arrays

Another thing I see you doing is joining and splitting arrays. You're joining a pair of arrays like this:

for ($k=0; $k<32; $k++) {
   $bitsArray[$k] = $leftBitsArr[$k];
   $bitsArray[$k+32] = $rightBitsArr[$k];
}

Since you simply want all the values in @leftBitsArr followed by all the values in @rightBitsArr, you can do it like this:

@bitsArray = (@leftBitsArr, @rightBitsArr);

perl likes to flatten lists, so on the right side, we're making a list out of two lists and then placing the final list into @bitsArray.

For splitting lists, you're typically splitting them in half, like this:

my @leftBitsArr = ();
my @rightBitsArr = ();
for ($j=0; $j<32; $j++) {
   $leftBitsArr[$j] = bitsArray_ip[$j];
   $rightBitsArr[$j] = $bitsArray_ip[$j+32];
}

There's an interesting trick in perl: You can create a list of values from an array and a list of indices. This is called array slicing (you'll find it described in perlvar). Using the range operator in conjunction with array slicing we can turn your code into:

my @leftBitsArr = @bitsArray_ip[0 .. 31];
my @rightBitsArr = @bitsArray_ip[32 .. 63];

Sorry, but I'm out of time for the moment. I've done a few other things to your code (such as removing some pack and unpack operations that were confusing me). If yo have any questions about anything I've written, please let me know, and I'll try to clarify things. The modifications I've made to your code while playing around with it:

sub createRoundKeys {

    my $key = $_[0];
    if(length $key != 8) { die "#ERROR: DES key is not 64 bit#\n";}

    my ($i, $j);

    # to hold references to sub-keys for each round according to array
+ index.
    # the function returns a reference of this array to be farther use
+d.
    my @subKeys = ();

    # unpack returns the key string as a corresponding bit string
    # 64 bit where B indicates highest first
    my @tempArr = unpack("B64", $key);

    # split bit string to corresponding bits array
    my @keyBitsArr = map { $_+0 } split("", $tempArr[0]);

    #------------------------------------------------------------
    # permuted choice one(@PC_1)
    # each index in the keyBitsArr56_PC1 gets some bit from the 64-bit
+ original key according to some mapping, PC-1

    my @keyBitsArr56_PC1 = map { $keyBitsArr[$PC_1[$_]-1] } 0 .. $#PC_
+1;
    my @leftBitsArr = @keyBitsArr56_PC1[0..27];
    my @rightBitsArr = @keyBitsArr56_PC1[28..55];

    # create sub-keys for each round
    @tempArr = ();
    for($i=0; $i<16; $i++) {

        # shift each part individually

            for (0 .. $ScheduleOfLeftShifts[$i]-1) {
                # shift left part according to round
                push(@leftBitsArr, shift(@leftBitsArr));
                # shift right part according to round
                push(@rightBitsArr, shift(@rightBitsArr));
            }

        # PC_2, get 48 bit round sub key

            @tempArr = (@leftBitsArr, @rightBitsArr);

        # permuted choice two

            @{$subKeys[$i]} = map { $tempArr[$PC_2[$_]-1] } 0 .. $#PC_
+2;
    }

    return \@subKeys;
}

sub des {

    my ($i, $j, $k, $tempVar, @tempArr);

    # iterate over input file in chunks of 64 bit, DES ECB-mode of ope
+ration
    for($i=0; $i<=$#FileArray; $i++) {

        # convert block read from file to its binary rep
        $tempVar = unpack("B64", $FileArray[$i]);

        #----------------------------------------
        # DEBUG/PoC
        my $hex = join("", map { sprintf "%02X", $_ } unpack("C*",$Fil
+eArray[$i]));
        print("($i): $hex <$FileArray[$i]>\n");
        #----------------------------------------

        # an array of bits as numeric values, the block rep as numeric
+ binary numbers
        my @bitsArray = map { $_+0 } split("", $tempVar);

        # initial permutation (IP) for each block/64 bit chunk before 
+the 16 rounds
        my @bitsArray_ip = map { $bitsArray[$IP[$_]-1] } 0 .. $#IP;
        my @leftBitsArr = @bitsArray_ip[0 .. 31];
        my @rightBitsArr = @bitsArray_ip[32 .. 63];

        # 16 DES rounds per 64 bit chunk treated as two 32 bit chunks
        for($j=0; $j<16; $j++) {

            my @nextLeftBitsArr = @rightBitsArr;

            # curr right bits chunk expansion/permutation (E)
            @rightBitsArr = map { $rightBitsArr[$E[$_]-1] } 0 .. $#E;

            # XOR with round sub-key: check function bool param for en
+cryption/decryption action
            my $ref;

            if($action eq "e") {
                $ref =  $SubKeys[$j];# j - index of curr round
            }
            elsif($action eq "d") {
                $ref =  $SubKeys[15-$j];# j - index of curr round reve
+rsed
            }

            @rightBitsArr = map { $rightBitsArr[$_] ^ $ref->[$_] } 0 .
+. $#rightBitsArr;

            # S-box
            my $sBoxResult = 0;
            for($k=0; $k<8; $k++) {
                my $sBoxRow = $rightBitsArr[$k*6]*2   + $rightBitsArr[
+$k*6+5];
                my $sBoxCol = $rightBitsArr[$k*6+1]*8 + $rightBitsArr[
+$k*6+2]*4 
                            + $rightBitsArr[$k*6+3]*2 + $rightBitsArr[
+$k*6+4];
                $sBoxResult = ($sBoxResult<<4) + $SBOXES[$k][$sBoxRow]
+[$sBoxCol];
            }
            my $sBoxResStr = unpack("B32", pack("N", $sBoxResult));

            @rightBitsArr = map { $_+0 } split("", $sBoxResStr);# now 
+32 bits, $sBoxResStr was loop concat.

            # Permute the bits, then xor the resulting bit with leftBi
+tsArr
            @rightBitsArr = map { $rightBitsArr[$P[$_]-1] ^ $leftBitsA
+rr[$_] } 0 .. $#P;

            # assign next values
            @leftBitsArr = @nextLeftBitsArr;
        }

        # swap two sides
        {
            my @temp = @leftBitsArr;
            @leftBitsArr = @rightBitsArr;
            @rightBitsArr = @temp;
        }

        # merge the left and right halves, invert the permutation, the
+n convert back to binary
        # and store the result
        @bitsArray = (@leftBitsArr, @rightBitsArr);
        my @bitsArray_ip_inverse = map { $bitsArray[$IP_INVERSE[$_]-1]
+ } 0 .. $#IP_INVERSE;
        $FileArray[$i] = pack("B64", join("", @bitsArray_ip_inverse));
+ #$tempVar);
    }
}

...roboticus

When your only tool is a hammer, all problems look like your thumb.