Hill Encryption/Decryption Cipher in Perl

By Jari Perkimki

The following implementation of the Hill Cipher in Perl is adjusted to the Finnish alphabet, based on my earlier Perl codes of the Affine Cipher and the Vigenre Cipher. This is a simplified implementation of the cipher, using a 2x2 matrix. Much more sophisticated systems can be made, using the ideas below.

The summary

The Hill Cipher, developed by Lester S. Hill and originally described 75 years ago (March 1931), is an example of so-called polygraphic systems where a group of plaintext letters is replaced by a group of cipherletters. When the group of plaintext to be processed at a time consists of 2 characters, as is the case here, the system is called digraphic. You can make the cipher more secure by using e.g. trigraphic, tetragraphic or pentagraphic transformation matrices.

The encipherment process using a digraphic system is based on the following formulas:

C1 = a * P1 + b * P2 (mod 29)
C2 = c * P1 + d * P2 (mod 29)

where P1 and P2 = two successive plaintext letters, C1 and C2 = cipher equivalents of the plaintext letters. The four numbers a, b, c, d are the encryption key. These numbers are usually written in the form of a matrix.

Encipherment

Let us assume we want to encipher the text "HELLO", using a matrix of 3, 7, 11, 20.

First of all, the text to be enciphered needs to have an even number of letters so we add a dummy "x" (or any other dummy letter of your choice) at the end. Then we apply the formulas above in three rounds (processing 2 letters in a round):

Plain:   H E  L  L  O  X
Numeric: 8 5 12 12 15 24

Round 1 (letters H and E):

C1 =  3 * 8 +  7 * 5 =  59 mod 29 =  1 (= A).
C2 = 11 * 8 + 20 * 5 = 188 mod 29 = 14 (= N).
[...]

So, the plainletter H will be the cipherletter A. E will be N. In the end, the result will be:

Plain:  HELLOX
Cipher: ANDXJG

Using our Perl script, you would say:

echo "hellox" | ./hill.pl -m 3,7,11,20 -v

Plain:  hellox
Cipher: andxjg

where the option -m is followed by our encipherment matrix (a,b,c,d). The option -v makes verbose output.

Decipherment

To decipher a text with our Perl script, you will use the same matrix you used for encipherment, plus the option -d (= decipher). You may, for instance, try the following:

echo "hellox" | ./hill.pl -m 3,7,11,20  | ./hill.pl -m 3,7,11,20 -d -v

Plain:  andxjg
Cipher: hellox

In reality, you will not use the same matrix of 3, 7, 11, 20 for decipherment but the inverse of that matrix. See the code for details.

Using user-defined character set (-f FILE)

User-defined character sets can be used. They are read from a file where the characters are separated by a comma. If the option -f is not used, the software uses its built-in 29-character set.

Let us assume a file named "ba", including the following characters:

b,a,d,c,f,e,h,g,j,i,l,k,n,m,p,o,r,q,t,s,v,u,x,w,z,y,,,,,

To use the same example as above, now enhanced with our own character set, just enter the following:

echo "hellox" | ./hill.pl -f ba -m 3,7,11,20 | ./hill.pl -f ba -m 3,7,11,20 -d -v

Plain:  blrxo
Cipher: hellox

The syntax

Hill Cipher: a polygraphic encryption/decryption system
Usage: ./hill.pl [options] [files]
Options:
-d          Decipher mode. Default: encipher mode.
-f FILE     Read comma-separated characters (alphabet) from FILE
-m A,B,C,D  2x2 matrix for encipherment/decipherment
-v          Verbose: show the plaintext and the ciphertext.
-h          Show this help.

Files: Multiple files are accepted. No files means using STDIN.

The code

#!/usr/bin/perl
# 02 Apr 06: Initial Code.
# 28 Apr 06: Added support for user-defined character sets
# Author: Jari Perkimki, jpe@uwasa.fi
#

$i = 1; $infile = 0;

use Getopt::Long;
GetOptions ('d'   => \$d,        # decipher
            'f=s' => \$infile,   # read abc from file
            'h'   => \$help,     # help
            'm=s' => \$kw,       # matrix
            'v'   => \$verbose); # show plain/ciphertext

help() if ($help || $kw eq "");
chomp $kw;
@matrix = split /,/, $kw;

if (-e $infile) {
    open (IN, $infile);
    while (<IN>) {
        chomp;
        @fabc = split /,/;
    }
    close IN;
}

$le = scalar @fabc;

if ($le > 0) {

    foreach $letter (@fabc) {
        $abc{$letter} = $i++;
        $xyz{$letter} = ($le + 1) - $j++;
    }

} else {

    foreach ('a' .. 'z', '', '', '') {
        $abc{$_} = $i++;
        $xyz{$_} = 30 - $j++;
    }

    $le = 29;

}

%cba = reverse %abc;

$det = $matrix[0] * $matrix[3] - $matrix[1] * $matrix[2];
$idet = divmod($det, $le);
$im1 = ($idet *  $matrix[3]) % $le;
$im2 = ($idet * -$matrix[1]) % $le;
$im3 = ($idet * -$matrix[2]) % $le;
$im4 = ($idet *  $matrix[0]) % $le;

undef $/;

while(<>) {

    tr/A-Z/a-z/;
    tr|/#+%&=,;:!\?\.\"\'\-<>\(\)\[\]@\\_| |;
    s/\s+//g;
    $plain = $_;

    @byte = split //, $_;
    $len = scalar @byte;

    if ($len % 2) {
        $verbose ? print "Odd # of letters: adding extra \"x\" at end.\n" : print "";
        push(@byte,"x");
        $plain .= "x";
        $len++;
    }

    for ($i = 0; $i < $len; $i++) {
        if (!($i % 2)) {

            $d ? ( decipher() ) : ( encipher() );

        }
    }

}

$verbose ? print "Plain:  $plain\nCipher: $cipher\n" : print "$cipher\n";

sub encipher {

    $c1 = mat($matrix[0],$matrix[1]);
    $c2 = mat($matrix[2],$matrix[3]);
    $cipher .= $cba{$c1} . $cba{$c2};

}

sub decipher {

    $c1 = mat($im1,$im2);
    $c2 = mat($im3,$im4);
    $cipher .= $cba{$c1} . $cba{$c2};

}


sub mat {

    my $m1 = $_[0];
    my $m2 = $_[1];
    my $c  = 0;

    $c = ($m1 * $abc{$byte[$i]} + $m2 * $abc{$byte[$i+1]}) % $le;
    $c = $le if $c == 0;
    return $c;

}

sub help {
    print <<EOF;
Usage: $0 [options] [files]
Hill Cipher: a polygraphic encryption/decryption system
Options:
-d          Decipher mode. Default: encipher mode.
-f FILE     Read comma-separated characters (alphabet) from FILE
-m A,B,C,D  2x2 matrix for encipherment/decipherment
-v          Verbose: show the plaintext and the ciphertext.
-h          Show this help.

Files: Multiple files are accepted. No files means using STDIN.
EOF
exit(1);
}

sub divmod {
    my $m = abs($_[1]);
    my $a = $_[0] % $m;
    my($b, $x, $y, $n) = ($m, 1, 0);

    while (0 != $a) {
        $n = int($b / $a);
        ($a, $b, $x, $y) = ($b - $n * $a, $a, $y - $n * $x, $x);
    }

    $y % $m;
}