PWC 162 › Wheatstone–Playfair Cipher

This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)

Challenge #2 this week asks us to implement a version of the Playfair Cipher, which is a simple symmetric key cipher, invented in 1854 by Charles Wheatstone, that was used with pencil and paper. It ended up being called the Playfair Cipher because⁠—as I understand it⁠—the ironically named Lord Playfair promoted its use and basked in the glory.

This cipher was used by the Brits up to and including the First World War, to encrypt messages sent via telegraph. Without the key, messages can be decrypted eventually (and it’s easier, the longer the ciphertext, as it is vulnerable to frequency analysis), but the British knew that by the time the enemy decoded the message, the information would no longer be relevant.

Perl Solution

The algorithm is quite involved, so I will refer you to the Wikipedia page for a description and worked example. In short, however, the algorithm works by first generating a 5×5 square containing the key, and filling the rest with the remaining letters. Since we only have 25 spots, we usually drop the J or Q. We’ll drop the J.

Here’s the function that generates the square for a given key:

sub __gen_square {
    my ($key, $int) = @_;

    my %left = map { $_ => 1 } 'a'..'z';
    delete $left{$int}; # Interchangeable letter (usually J or Q)
    my @rows = ([]);

    # We'll need this twice
    my $push = sub {
        push @rows, [] if @{$rows[-1]} == 5;
        push @{$rows[-1]}, $_[0];
    };

    for (split //, $key) {
        next unless $left{$_};
        delete $left{$_};
        $push->($_);
    }

    $push->($_) for sort keys %left;

    @rows;
}

Calling _gensquare('playfair example', 'j') gives the following square:

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

First, insert x between repeated letters in the text, and pad the end with an x if it is an odd length.

Then, for each pair of letters, perform the following rules:

1. If the letters are on the same row, replace them with the letters to their immediate right (wrapping around to the left if necessary).
2. If the letters are on the same column, replace them with the letters immediately below (wrap around to the top if necessary)
3. Else, they are in a rectangle. Replace them with the letters at the other corners of the rectangle. (Same row first, then column!)

Encryption and decryption are very nearly the same operation; the only difference is for rules #1 and #2, we shift in the opposite direction (left, and up, respectively). So rather than duplicating a bunch of code, I just define a couple of constants:

use constant {
    playfair_encrypt => +1,
    playfair_decrypt => -1,
};

I pass these constants to the __playfair($key, $plaintext, $ed) function that does the heavy lifting, like so:

sub encrypt { __playfair($_[0], $_[1], playfair_encrypt) }
sub decrypt { __playfair($_[0], $_[1], playfair_decrypt) }

__playfair Function

First, we do some initialization:

my @sq = __gen_square($key, 'j');
my %coords; # Coordinates of each letter within @sq
for my $x (0..4) {
    $coords{$sq[$_][$x]} = [$x, $_] for 0..4;
}

The %coords hash is a convenience optimization that gives us the <x,y> coordinates of any letter. For example, in the above square, $coords{b} is [0, 2]. This isn’t strictly necessary; we could loop through every time for not much overall penalty.

Next we munge the $plaintext a bit to make it work with the algorithm:

$plaintext =~ s/[^a-z]//g;
$plaintext =~ s/^((?:..)*?)(\w)\2/$1$2x$2/g;
$plaintext .= 'x' if length($plaintext) % 2;

1. Remove whitespace and any other non-letters (we’re quite permissive).
2. This one looks for pairs of the same letter and inserts an x in between. It’s important to only do this on pair boundaries, which is why we need the ((?:..)*?) to gobble up an even number of letters first. There are a few different ways I could have done this. What’s your favorite?
3. Finally, we pad with one more x if $plaintext is an odd length.

The meat and potatoes of the algorithm is the following loop, which operates on pairs of letters in $plaintext:

return join '', pairmap {
    my ($xa, $ya) = @{$coords{$a} // $coords{i}};
    my ($xb, $yb) = @{$coords{$b} // $coords{i}};

    ($xa, $ya, $xb, $yb) = 
        $xa == $xb ? ( $xa,      ($ya+$ed)%5,$xb,      ($yb+$ed)%5)
      : $ya == $yb ? (($xa+$ed)%5,$ya,      ($xb+$ed)%5,$yb       )
                   : ( $xb,       $ya,       $xa,       $yb       );

    $sq[$ya][$xa] . $sq[$yb][$xb];
} split //, $plaintext;

As you can see, we take each pair of letters (a and b) and fetch their %coords as <x_a, y_b> and <x_a, y_b>. We then transform those coordinates based on rules 1..3, above. The $ed variable is one of the playfair_encrypt or playfair_decrypt constants (1 or -1).

We then append the letters from the square at the transformed coordinates, and those are all join‘d together for the final result.

Limitations

While I think my code is pretty reasonable for a weekly challenge, there are a few ways in which it might fail, that I have not thoroughly tested. Certain sequences of repeated letters might not give the correct output; partly because I did not take the time to test, and partly because it wasn’t clear how a few of these edge cases are supposed to be handled.