Tuesday, June 12, 2012

A Perl PDL Demonstration Using the Hill Cipher Algorithm


PDL is an excellent Perl module for anyone seeking to do any type of numerical computing that involves matrix math.  As an illustration of this, let’s take a look at a PDL implementation of a simple encryption algorithm that uses matrix math, the Hill Cipher.  As a starting point, the Hill Cipher assigns each letter in the alphabet a numerical value (e.g. a=0, b=1, c=2, … z=25).  The cipher works by taking n plain text letters and converting them to their numeric representation.  In the example code a n of 3 is used. We will refer to this set of numerically represented plain text letters as P. It then takes an nXn matrix, which is used as an encryption key (K), and performs the following matrix math operation to yield the numerical representation of n cipher text letters (C).  

C=P x K mod 26

If you look at the Perl code below, notice how easy PDL makes this operation.  There is no need to loop through the elements of an array and perform mathematical operations on each element.   One can simply process entire matrices as a single entity and as such this is one of the features that makes PDL such a huge asset to anyone that performs numerical computing in Perl. 

The reverse of this process is performed by taking the inverse matrix (K1) and performing the following math operation:

P=C x K1 mod 26

As a means of testing the example code, a known set of values from the book “Cryptography and Network Security” by William Stallings are used.  If run as is, the sample code should result in the cipher text RRLMWBKASPDH after encryption and the decryption should return the original plain text value.  

#usr/bin/perl

use PDL;
use strict;
use warnings;

my @letters = ('a'..'z');
my (%encoding,%encoding2);
my $i=0;
foreach my $letter (@letters){
    $encoding{$letter}=$i;
    $encoding2{$i}=$letter;
    $i++;
}

#encryption
my $plaintext='paymoremoney'; #length=multiple of 3
$plaintext=lc($plaintext);
my $ciphertext='';

#encryption key
my $k = pdl [[17,17,5],[21,18,21],[2,2,19]];

while($plaintext=~/(\w)(\w)(\w)/g){
    my $x=$encoding{$1};
    my $y=$encoding{$2};
    my $z=$encoding{$3};
    my $p= pdl [$x,$y,$z];
    my $c= $p x $k % 26;
    foreach (0 .. $c->nelem-1){
        my $j=$c->flat->index($_);
        $ciphertext.=$encoding2{$j};
    }
}
print uc($ciphertext)."\n\n";

#decryption
$plaintext='';
#inverse matrix
#hardcoded and not computed to simplify example code
my $k1= pdl [[4,9,15],[15,17,6],[24,0,17]];
while($ciphertext=~/(\w)(\w)(\w)/g){
    my $x=$encoding{$1};
    my $y=$encoding{$2};
    my $z=$encoding{$3};
    my $c= pdl [$x,$y,$z];
    my $p= $c x $k1 % 26;
    foreach (0 .. $p->nelem-1){
        my $j=$p->flat->index($_);
        $plaintext.=$encoding2{$j};
    }
}
print $plaintext;

No comments: