[Next] [Up] [Previous] [Index]
Main : Index : Pencil and Paper Systems : Improving Substitution : Polygraphic Ciphers and Fractionation : The Bifid, the Trifid, and the Straddling Checkerboard

The Bifid, the Trifid, and the Straddling Checkerboard

The Bifid and Trifid ciphers

The first of the three rules for Playfair encipherment changes one two-letter group, or digraph, to another by exchanging column co-ordinates. This suggests using row and column co-ordinates in a more general fashion. Let's take the 5 by 5 square above, but number the rows and the columns, like this:

   1 2 3 4 5
1) T X V H R
2) L K M U P
3) N Z O J E
4) C G W Y A
5) F B S D I

Then, another method of encipherment would be as follows: Divide a message into groups of letters of a fixed length, say five letters, and write the row and then the column co-ordinate of each letter beneath it, like this:

11555 52453 41312 35544 3
14535 33435 15513 53352 5

and then, going across within each group, read the numbers in order, and turn them, in pairs, into letters: that is, read 11555 14535 52453 33435... and turn them into the letters corresponding to 11, 55, 51, 45, 35, 52, and so on.

1155514535 5245333435 4131215513 3554453352 35
 T I F A E  B A O J E  C N L I V  E D A O B  E

This is the Bifid cipher of Delastelle, and the general principle of this form of cipher is called seriation. This is one of the most secure pencil-and-paper ciphers that is still used by hobbyists as a puzzle. It isn't hard to make this kind of cipher just a little bit more complicated, and thereby obtain one that is genuinely secure. It belongs to the class of cipher methods known as fractionation, where letters are divided into smaller pieces, or "fractions". Just as two symbols from 1 to 5 give 25 letters, three symbols from 1 to 3 give 27 letters; and five binary bits provide a 32-character alphabet.

The Trifid, also due to Delastelle, is the analogous cipher using a 27-letter alphabet represented by three symbols from 1 to 3:

W 111   M 121   Z 131   N 211   O 221   L 231   C 311   T 321   U 331
A 112   & 122   Y 132   E 212   V 222   P 232   X 312   J 322   G 332
K 113   B 123   H 133   Q 213   R 223   S 233   I 313   F 323   D 333

to encipher a message by seriation like this:

3132321 1223223 1222132
2313132 3311212 2133131
1333331 2321321 1233222

which again is read off horizontally after being written in vertically, yielding a cipher message like this:

313 232 123 131 321 333 331
 I   P   B   Z   T   D   U

122 322 333 112 122 321 321
 &   J   D   A   &   T   T

122 213 221 331 311 233 222
 &   Q   O   U   C   S   V

Representing the letters as combinations of two groups of from one to five signal fires was originally proposed by Polybius in his Histories, as being a general method of communications, unlike ones he noted as being previously used that depended on a small list of pre-arranged messages. It looked like this:

with the letters of the Greek alphabet placed on five numbered tablets, and each letter being numbered on each tablet.

Other forms of dividing a character into smaller pieces, such as ASCII or Baudot, or Morse Code (to be seen below) were also developed to allow communications over various types of channel, as were the signal flags used by ships, to use an example of a different type.

The Straddling Checkerboard

Some ciphers actually used by Soviet spies used a square like this:

    9 8 2 7 0 1 6 4 3 5
    A T   O N E   S I R
 2  B C D F G H J K L M
 6  P Q U V W X Y Z . /

Eight of the most common letters are translated to a single digit. The two digits not used in this way begin two-digit combinations that stand for the remaining letters. This is an example of a variable length code with the prefix property. When it is possible to tell, from the digits one has already seen of a symbol, whether or not one needs to include the next digit in the symbol, then spaces between the digits of a symbol are not needed, and this is what is known as the prefix property.

At one time, telephone numbers in North America had this property, because the middle digit of an area code was always 0 or 1, and the first three digits of a regular telephone number, also known as the exchange, never had 0 or 1 as the middle digit. Therefore, it was possible to dial 1 plus the seven-digit number to make a long-distance call within one's own area code, since the first three digits could not possibly be an area code. However, the increased need for more telephone numbers made it necessary to abandon this rule, in January 1995 and therefore when dialing a long-distance call within one's own area code, it is now still necessary to dial the area code. This method of dealing with the increased demand for telephone numbers had the advantage that the number of digits in a telephone number did not have to be increased, and this avoided problems with computer data-processing systems that allocated the fixed minimum amount of space for a telephone number, as well as limiting the amount of alteration needed for older telephone equipment.

In Britain, on the other hand, it was necessary to lengthen every telephone number by one digit, and this was done by inserting the digit 1 in every number in the second position on a day called "phONE day", April 16, 1995, although permissive dialing remained in effect until April 22, 2000. A number of other countries also modified their systems of telephone numbers during roughly the same period; Australia began in 1996, and Finland changed over its phone system on October 12, 1996.

Since in Morse code, a dot is the letter E, and a dash is the letter T, but other Morse code symbols also begin with a dot or a dash, Morse code is a variable-length code that does not have the prefix property, and so spaces are required between letters in Morse code.

Of course, the second digit of a two-digit combination could also have stood, by itself, for another letter; but because when you start from the beginning and move forwards, there is no chance of confusion, this is a workable and usable system.

Thus, the message SENDMONEY would become 4 1 0 22 25 7 0 1 66, or, rather, 41022 25701 66 because spaces to show where the letters begin are not needed; the first digit representing a letter determines if its substitute is one or two digits long.

More complicated codes that work this way, using only the two binary digits 0 and 1, are used as a form of data compression. The most famous variable-length prefix-property binary codes are the Huffman codes; but this term only applies to such a code when symbols were assigned in it by a specific algorithm, which has been proven to be optimal, within the limitations of only considering single-symbol frequencies, and only using this kind of code: arithmetic coding, which doesn't work in whole bits, can be more efficient. Before Huffman's proof, codes of that nature assigned in a different fashion, which are known as Shannon-Fano codes, were the best known.

In one case, the VIC cipher used by Reino Hayhanen (the message in that cipher on microfilm, inside a hollow nickel, was the background to the page introducing this section) the digits produced by a straddling checkerboard were then subjected to a form of columnar transposition which was varied by selecting triangular areas to be filled with plaintext last.

In other cases, after the message was converted to digits, encipherment similar to the Vigenère to be described in the next section was performed. Since Vigenère is a form of addition, doing addition on digits is easier for most people, without special equipment, than doing it on letters.

[Next] [Up] [Previous] [Index]

Chapter Start
Skip to Next Section
Table of Contents
Main page
Home page