This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we’ll conclude looking at the cryptography problems from Phase II that we started looking at in a previous blog post and continued in a further blog post.

Cryptography Problem 3 – Playfair Cipher

Task 1 – Squaring Off

The first task is to convert a string into a 5×5 Playfair table. The solution makes straightforward use of APL primitives:

• Unique (∪) to remove duplicate characters from the string.
• Without (~) to find the rest of the alphabetic characters that are not mentioned in the string, and again to remove the character J.

PlayfairTable←{
    k←∪⍵
    5 5⍴(k,⎕A~k)~'J'
}

Here it is in action:

      ⊢table←PlayfairTable'KENNETHEIVERSON'
KENTH
IVRSO
ABCDF
GLMPQ
UWXYZ

Task 2 – Encryption

To encrypt a message we need to take two characters at a time, find their coordinates in the 5×5 Playfair table, swap their column coordinates and look up the letters at the new coordinates. There are lots of tricks in the code below of which we’ll describe just a few:

• To process the message two characters at a time, appending to the result as we go, we use a tail-recursive dfn whose left argument accumulates the result. For an introduction to this technique see this implementation of the Fibonacci function.
• To find letters in the Playfair table we first look them up in the ravel (i.e. the linearised form) of the table, and then use Encode (⊤) to convert this linear index into a pair of coordinates. Decode (⊥) does the opposite, converting a pair of coordinates back into a linear index.
• Mix (↑) and Split (↓) are used to convert between two different representations of the coordinates of the two characters we’re encoding: either as a flat 2×2 matrix, or as a nested 2-vector of 2-vectors. The choice of representation is largely a matter of taste, and it might be fun to play with this part of the code. You could tweak it to work entirely with the flat representation, or entirely with the nested representation, rather than converting back and forth between them.

PlayfairEncrypt←{
    ⎕IO←0                       ⍝ To aid arithmetic modulo 5.
    t←⍺                         ⍝ The Playfair table.
    m←⍵,(2|≢⍵)/'Z'              ⍝ Add a Z if the message length is odd.
    ((m='J')/m)←'I'             ⍝ Convert J to I in the message.
    ''{                         ⍝ Start with an empty accumulator.
        0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
        1=≢⍵:⍺ ∇ ⍵,'X'          ⍝ Only one character left: add an X.
        p←2↑⍵
        =/p:⍺ ∇(⊃⍵),'X',1↓⍵     ⍝ Duplicate character: insert an X.
        c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
        c←{
            =/1↑⍵:↑(⍴t)|0 1+↓⍵  ⍝ Same row: move to the right.
            =/1↓⍵:↑(⍴t)|1 0+↓⍵  ⍝ Same column: move down.
            0 1⌽⍵               ⍝ Else swap column coords.
        }c
        p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
        (⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
    }m
}

Here it is in action:

      ⊢cipher←table PlayfairEncrypt'HELLOWORLD'
KNMWQVZVVMCY

(Note that this result is slightly different from that given in the original problem description, because of some confusion about the rules for handling duplicate letters and odd message lengths, which were clarified later in the student competition forums.)

Task 3 – Decryption

Decryption is very similar to encryption. The differences are:

• Letters found in the same row of the table need to move left instead of right, and letters in the same column need to move up instead of down.
• We don’t need to worry about the input having an odd length, or containing the letter J.

Hence the code for PlayfairDecrypt is shorter than but very similar to PlayfairEncrypt:

PlayfairDecrypt←{
    ⎕IO←0                       ⍝ To aid arithmetic modulo 5.
    t←⍺                         ⍝ The Playfair table.
    ''{                         ⍝ Start with an empty accumulator.
        0=≢⍵:⍺                  ⍝ Finished: return the accumulated encrypt.
        p←2↑⍵
        c←(⍴t)⊤(,t)⍳p           ⍝ Coords of each letter in the table.
        c←{
            =/1↑⍵:↑(⍴t)|0 ¯1+↓⍵ ⍝ Same row: move to the left.
            =/1↓⍵:↑(⍴t)|¯1 0+↓⍵ ⍝ Same column: move up.
            0 1⌽⍵               ⍝ Else swap column coords.
        }c
        p←(,t)[(⍴t)⊥c]          ⍝ Look up new coords in table.
        (⍺,p)∇ 2↓⍵              ⍝ Tail recursion.
    }⍵
}

Here it is in action:

      table PlayfairDecrypt cipher
HELXLOWORLDX

Follow

This post is the continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. In this post we’ll continue looking at the cryptography problems from Phase II that we started looking at in a previous blog post.

Cryptography Problem 2 – Book Cipher Variation

Task 1 – Let’s Get Normal

The first task is to normalise some text by weeding out non-alphabetic characters, collapsing consecutive spaces and converting to upper case. It’s possible to do this all by hand with APL, but it’s much easier to use the ⎕R operator to search for and replace regular expressions.

Taking the transformations in turn, here’s how to convert non-alphabetic characters in message ⍵ to spaces:

('[^[:alpha:]]'⎕R' ')⍵

Here’s how to convert multiple consecutive spaces to a single space:

(' +'⎕R' ')⍵

And here’s how to convert every alphabetic character to upper case:

('.'⎕R'\u&')⍵

We can combine the first two of these, by converting any sequence of one or more non-alphabetic characters to a single space, giving the following implementation:

Normalise←{
    text←⎕SE.UnicodeFile.ReadText ⍵
    ('[^[:alpha:]]+' '.'⎕R' ' '\u&'⍠'Mode' 'D')text
}

The option 'Mode' 'D' tells ⎕R to operate in Document mode, which processes the whole file at once instead of line by line, as we are not interested in preserving the original line breaks. Here it is in action:

      70↑bor←Normalise'/home/jay/Desktop/BillOfRights.txt'
THE PREAMBLE TO THE BILL OF RIGHTS CONGRESS OF THE UNITED STATES BEGUN

Task 2 – Encryption

In this cipher there are lots of different ways of encoding each character of the message, and we are free to pick any of them. In order to try to “minimise the number of duplicated pairs in the result”, we simply pick randomly whenever we have a free choice. The function pickone helps with this. Given a boolean vector, it first uses {⍵/⍳⍴⍵} to get a vector of the indices of all the 1 bits, and then uses {⍵[?≢⍵]} to choose one of these indices at random.

In this coding of BookEncrypt, the anonymous inner dfn encodes a single character of the message into a (word offset) pair. These pairs are joined together with ⊃,/, a common pattern for catenating strings. The Disclose is required because, in Dyalog, reduction always reduces the rank of its argument, so ,/ on a vector of strings returns a scalar: the enclose of the catenated strings.

BookEncrypt←{
    pickone←{⍵[?≢⍵]}∘{⍵/⍳⍴⍵}
    b←' ',⍺                     ⍝ b has a space wherever a word starts in the key.
    s←{⍵/⍳⍴⍵}b=' '              ⍝ Get the indices of all the word starts.
    ⊃,/{
         p←pickone b=⍵          ⍝ Choose a random occurrence of letter ⍵
         p-←s                   ⍝ and get its offset within each word.
         w←pickone{(0<⍵)∧⍵≤20}p ⍝ Choose a word with a reasonable offset
         w(p[w])                ⍝ and return the (word offset) pair.
    }¨⍵                         ⍝ ... for each letter in the message.
}

Here it is in action:

      ⊢cipher←bor BookEncrypt 'MYSECRETMESSAGE'
480 11 523 11 440 6 115 5 78 16 579 18 696 20 330 16 544 4 658 17 400 9 661 11
      246 18 186 4 482 13

Task 3 – Decryption

Decryption is simpler then encryption, because there is no need to make random choices. All we have to do is:

• Find the index of the start of each word in the key, as before.
• Split the input into pairs of numbers.
• For each pair, find the character in the key at the specified offset from the start of the specified word.

There are various ways to split the input into pairs of numbers. Here, we do it with the Rank operator (⍤). Encrypting an N-character message gives a vector of 2×N numbers. To split it into pairs we first reshape it into a matrix with N rows and 2 columns; and then use f⍤1 to apply f to the rank-1 subarrays of this matrix, which are its row vectors.

Here’s the code:

BookDecrypt←{
    b←' ',¯1↓⍺                  ⍝ b has a space wherever a word starts in the key.
    s←{⍵/⍳⍴⍵}b=' '              ⍝ Get the indices of all the word starts.
    {
        (w o)←⍵                 ⍝ Get word number and offset
        b[s[w]+o]               ⍝ and find the character at that position
    }⍤1⊢(0.5×≢⍵)2⍴⍵             ⍝ ... for each pair of numbers in the input.
}

And here it is in action:

      bor BookDecrypt cipher
MYSECRETMESSAGE

To be continued…

Follow

This post is a continuation of the series where we examine some of the problems selected for the 2014 APL Problem Solving Competition. I’ll start by looking at the cryptography problems from Phase II.

Cryptography Problem 1 – Vigenère Cipher

The cipher is described using a large table of letters, but you don’t need to create this table in APL. Instead, you can convert each letter of the key and the corresponding letter of the message to numbers; add them together; and then convert the result back to a letter. Some subtleties:

• We want the result of the addition to “wrap around” at the end of the alphabet, so 25 + 1 = 26 (Z) but 25 + 2 = 27 which should wrap round to 1 (A). This is called modular arithmetic.
• We can implement modular arithmetic easily using APL’s Residue primitive, but this works most naturally when the alphabet is numbered from 0 to 25, rather than from 1 to 26. To use 0-based numbering, I’ll set ⎕IO←0 in the code below.
• An idiomatic way of converting letters to numbers is to look them up in the ⎕A, the upper case alphabet: ⎕A⍳⍵. To convert the other way we can simply index into ⎕A: ⎕A[⍵]. (For more comprehensive conversions between characters and numbers see the ⎕UCS system function.)

The code is then straightforward:

VigEncrypt←{
    ⎕IO←0                       ⍝ use 0-based numbering
    key←(⍴⍵)⍴⎕A⍳⍺               ⍝ convert key to numbers and expand to length of message
    ⎕A[26|(⎕A⍳⍵)+key]           ⍝ add key to message and convert back to characters
}

To encrypt the message we added the key (modulo 26). To decrypt, we need to subtract the key (modulo 26) instead, so we can go from VigEncrypt to VigDecrypt just by changing one character in the code. Note that the result of the subtraction might be negative, but Residue (unlike the remainder or modulo operations in some other programming languages you may have used) will still give us the correct result in the range 0 to 25. For example, 26|¯3 is 23.

VigDecrypt←{
    ⎕IO←0                       ⍝ use 0-based numbering
    key←(⍴⍵)⍴⎕A⍳⍺               ⍝ convert key to numbers and expand to length of message
    ⎕A[26|(⎕A⍳⍵)-key]           ⍝ subtract key from message and convert back to characters
}

Here are the functions in action:

      key←'KEIVERSON'
      key VigEncrypt'APLISFUNTOUSE'
KTTDWWMBGYYAZ
      key VigDecrypt key VigEncrypt'APLISFUNTOUSE'
APLISFUNTOUSE

To be continued…

Follow