All of the cypher systems we have looked at so far have been single-key character cyphers. By this, we mean that the same key which is used to encrypt the plaintext into the ciphertext is used to recover the plaintext from the ciphertext, and the cypher operates on only one character at a time. In these discussions the plaintext character space is taken to be the ASCII character set, as is the ciphertext character space. The key space is not necessarily the ASCII character set, but is a function, such that p=D(C(p)), where p is the plaintext, C is the encryption algorithm and key, and D is the decryption algorithm and key. Clearly, D is the inverse operation of C.

As it happens, character cyphers, even with the spreading algorithms we have been investigating, are not the only way to go. There is a class of cyphers, referred to as “Block Cyphers”, in which the encryption algorithm and key operate on groups of characters, not simply on single characters. While these cyphers do not fall to the statistical techniques of character cyphers, they do have their own weaknesses, and they are vulnerable in particular to known text (KTA) attacks, in which the cryptanalyst has some plaintext and the known corresponding cyphertext.

We open with the Hill Cypher.

Lester Hill was a mathematics professor at a (US) Northeast university in 1926 when he devised the cypher which bears his name. It is based on some results from linear algebra. Consider the following:

a = lx + my
b= nx + py.

This can be written as a l m x
b = n p * y,

where the characters (a, b) are the cyphertext obtained by multiplying the plaintext characters (x, y) by the two by two matrix (l, m ; n, p). (Sorry about the funky typesetting, this is an artifact how this stuff is printed). This is the essence of a Hill cypher with a 2 by 2 encryption matrix. To recover the plaintext from the ciphertext, one (in theory) need only to invert the encryption matrix and then to premultiply (math majors will know what this means) the cyphertext with the encryption matrix and out will pop the cleartext. It follows on inspection that while the example uses a 2 by 2 encryption matrix, this is not the only size matrix allowed, and indeed you may have a matrix as large as you like. The only requirement is that the matrix be invertible, though this in itself places a set of constraints on the nature of the matrix.

Notice in our opening paragraph we defined the cyphertext space to be the ASCII character set. In the old (pre-computer) days, both the plaintext space and cyphertext space were defined to be (for English) to be the characters in the alphabet, and that these characters were represented by numbers - 0 for A and 25 for Z. Immediately we see that these restrictions require that all arithmetic be modulo-26 (such that we count 0, 1, 2, 3...24, 25, 0, 1, 2, 3...). There necessarily follows from ring theory a requirement that not only must the encryption matrix have anon-zero determinant, but that it also be co-prime with 26. All of this is driven by the requirement, stated last week, that message expansion (cyphertext longer than the plaintext) is not desirable. The result is that generating a set of invertible encryption matrices is not so easy. Further, while it is not easy but possible to invert a matrix of size 3 by 3, it becomes very difficult to do such an inversion for matrices of size greater than 3 by 3. All arithmetic to be modulo-26, mind you.

But the restriction concerning message expansion was emplaced during the days when everything was hand processed, and hand transmitted. These days with the Internet and high-speed transmission links a packet is a packet, and the length of the packet is much less important. What do we get if this restriction is removed?

Consider the following: we go into our Hill cypher with an 8-bit ASCII character. We come out with a 32-bit word. For every character we go in with, we come out with one word, giving us a message expansion of four-to-one. For this, we forego the requirement that all arithmetic be modulo-26 (actually, modulo-256 in our case), and we can use some quite large Hill matrices, as long as they are invertible. However, since we have a personal computer, we can take advantage of the glories thereof to do our inversion and (by now floating point) arithmetic, and using the Hill cypher is now much less daunting than it once appeared. But for our efforts, if done properly we do get the much-desired spreading algorithm, and (hopefully) confusion to the Thought Police.

There are some loose ends. Communicating the key is still no simple task, and the cypher still falls to a KTA. But, if we both know (for example) to make a 9 by 9 array (this being Tuesday, the 9th of June) of the first 81 telephone number suffixes, starting from the third down, on page 342 of the Manhattan telephone directory for Spring, 1967, this could constitute a suitable key. Further, if I were to know that for each 9 character group I make a new encryption matrix by moving to page 353 (this being Tuesday I know that the page stride is 11) and grabbing 81 suffixes starting with the third down (June) we have once again what is very close to a one-time pad system. While not unbreakable, it is a two-bottle problem (problem difficulty rated in number of bottles of Aspirin) to solve, at the very least.

We now turn to the Playfair cypher. The Playfair cypher was the first modern block cypher, and was invented Charles Wheatstone in 1854, and was named after and promoted by Baron Playfair of St. Andrew. It enjoyed wide use throughout the world well into the 20th Century, is thought to have been used by the British during the Boer War, and was still in use as an emergency cypher during World War II by the Americans. It is a digraph cypher, which is to say that it takes two characters at a time.

English has 26 characters. However J is not a commonly used letter (try doing a frequency analysis on this text and you will see), so it is possible to dispense with the use of the letter J when encrypting without garbling the message beyond recovery by substituting the letter I for all occurrences of the letter J. Then, we need a keyword, for which as an example we use the word MAGNETO. We form the following five by five array:

M A G N E
T O B C D
F H I K L
P Q R S U
V W X Y Z.

We take the transpose of this array to get, as our key,

M T F P V
A O H Q W
G B I R X
N C K S Y
E D L U Z.

Now, the fun. We take two characters at a time in the plaintext, and apply the following rules (there are minor variations in the rules, but this is one set).

(1) All repeated characters are separated by an “x”.

(2) If the two characters are in the same row, the encryption is to take the two characters immediately to the right of the plaintext characters, with wraparound.

(3) If the two characters are in the same column, the encryption is to take the two characters immediately below the plaintext characters, with wraparound.

(4) If the two characters are in different rows and columns, the encryption is to form a box, and then to take the two characters in the opposite corners of the box.

For example, to encrypt the phrase “yngvi is a louse”, we would get (rule 1) “yngvixisalouse” (spaces squeezed out), and then get NCMXRGKRHEQDNU. Keep with tradition and break this into five letter groups, and we get NCMXR GKRHE QDNUR, where the last character in the last group is a null or padding. (Note, I did the encryption in my head, so if I made a mistake I made a mistake. Work out the cyphertext for yourself.)

The Playfair cypher is not a simple cypher, but it will fall to a known text attack, or if you have sufficient cyphertext it will fall to a digraph-based frequency analysis. For these reasons it should not be considered to be secure. However it does provide an interesting jumping off point for development of OTP methods, to try to make an at least two-bottle problem.

You may be interested to know that the Playfair cypher was considered to be much too esoteric and difficult for diplomats to use during the 19th Century, so they used less secure systems for critical state traffic, because those they could handle. We shall not discuss what this says about statesmen and world leaders in either the 19th or 21st Centuries.

Next week we will look at some of the early spreading algorithms, and some of the techniques (specifically the phi statistic) used to defeat them.

Susanna Harding holds the degrees of Bachelor of Science in Engineering Physics, Master of Science in Nuclear Engineering, Master of Science in Astrophysics, and am ABD in Astrophysics. She has been in industry for more than twenty years, and teaches at a major Canadian university.