The Basics

On March 8, 2004 a poster named "Roy" wrote to the usenet newsgroup sci.crypt with a method of shuffling playing cards systematically to get a key stream for a stream cipher. It occurred to me that the same method of shuffling could be applied to a row of letter tiles such as those used in the game Scrabble®. That lead me to the following exploration of what I call Game Tile ciphers, or Sliding Tile Ciphers.

Sliding Tile Ciphers are a class of poly-alphabetic ciphers that can be implemented using letter tiles. They can range from the very simple to the very complex, and from easy to crack to the nearly impossible.

The first class of ciphers we will explore is those where a set of alphabet tiles are arranged in a single "circulating" row. I call this a circulating row because we can imagine a line of letter tiles wrapped around the outside of a cylinder, or arranged in a circular race track. If I shift the whole alphabet to the left by one tile, whatever tile is on the left end of the row ends up on the right end, as if the two ends were connected.

If we did wrap the tiles around in a circle we would still have to keep track of which spot in the circle was the beginning of the row, so we would add a mark of some kind to the circle or cylinder, called the index mark, to show us which letter was the beginning of the row. The reason that this is necessary will become clear as we begin to look at the details of shuffling methods.

Sliding tiles arranged in a circle

Poly-alphabetic vs Mono-alphabetic Ciphers

Simple single-alphabet substitution ciphers such as seen in the newspaper crypto quote puzzles, substitute one letter for another, and that substitution remains unchanged for the entire puzzle. If plaintext 'A' is changed to ciphertext 'X' then 'A' will always be 'X', no matter where it appears in the puzzle.

By contrast, a poly-alphabetic cipher changes the substitution alphabet for every letter enciphered. The first 'A' might be enciphered as 'X', and the very next 'A' might become 'Q'. This changing nature of the encryption alphabet is what makes poly-alphabetic ciphers harder to crack. Sliding tile ciphers are of the poly-alphabetic type. The whole alphabet will be changed in some way after enciphering every letter.

Because the alphabet will be changing, it is important to know how long it will be before we return to the original alphabet. The longer this period of time the more secure the cipher will be. In addition to the cipher's period, we would like to know just how mixed up the alphabet becomes when we shuffle it. These, then, are the two attributes we need to look at; period and mixing.

To illustrate these attributes consider the simplest sliding tile cipher of all. A row of 26 letter tiles is arranged in alphabetical order. After each letter is enciphered the alphabet is shifted to the left by one tile. Remember that the alphabet is "circulating", so that the left and right ends are connected. Here is what the alphabet looks like after a few shuffles:

The simplest sliding tile cipher

After shuffling the alphabet 26 times it will return to its original order, so the period of this shuffle is 26. Notice again that the alphabets alwasy wrap around as if their ends were connected in a circle.

Also note that each alphabet is in the same alphabetical order, but is shifted over compared to the ones that come before and after. The alphabet remains very orderly, and the pattern is easy to detect.

There are numerous ways that the row of tiles can be scrambled after each letter is enciphered. All of those methods involve moving some of the tiles around in some way. But we need our correspondent to be able to decipher the message at the other end, so we need to move the tiles around in an orderly manner that is easy to remember. We will call this sequence of tile moves the shuffling schedule for the cipher.

Types of Tile Moves

There are four basic "simple" tile moves we can make. First, as we have already seen, we can shift the whole alphabet row over one or more tiles to the right or left. Second, we can move a tile or group of tiles from one place in the alphabet row to a different place in the row. Third, we can take a group of tiles and reverse their order, changing ABC to CBA for example. And finally, we can swap two tiles or groups of tiles from two different locations in the letter row.

Those four simple moves are illustrated below.

The fours simple tile moves.

From the first to the second row the whole alphabet is shifted one tile to the left. In the next row the B tile is moved to a spot after the G tile. Next, the DEF group is reversed, and finally, the C and G tiles are swapped.

Some of these basic moves can be combined into a more complex move. For example, a group of four tiles could be reversed and moved to a different location in the row, all in one move. Here we reverse the group ABC and move it to a spot after the M tile.

And don't forget that ALL sliding tile alphabet wrap around in a circle, even though I have drawn them flat in these examples. And if you use real tiles to work a sliding tile cipher just remember that whenever you take a tile off one end of the row, it gets moved to the other end of the row, just as if it were arranged in a circle.

A group of three is reversed and moved in one operation.

Shuffling Both Alphabets

A cipher consists of two alphabets, the plaintext alphabet and the ciphertext alphabet. So far we have talked about shuffling the plaintext alphabet, but it is also possible to shuffle both of the alphabets between each letter. For this we need two rows of tiles (or two circular race tracks, or two rows wrapped around a cylinder). When shuffling both alphabets it is important that we use a different shuffling schedule for each alphabet. If we do not then the two will be shuffled in lockstep with each other and the net effect will be that the cipher becomes a simple mono-alphabetic one.

Here is an example of shuffling both alphabets. This particular sliding alphabet cipher, called the Chaocipher, was originally implemented by J. F. Byrne in 1918 and not cracked until 2010 when the blueprints were finally made public. His original model was made with tiles cut from cardboard and placed on wooden wheels. A complete description can be found here.

A primitive mechanical model of the Chaocipher device
Photo courtesy of National Cryptologic Museum

Here is the same cipher with the sliding tiles laid out in a flat row rather than a circle. The cipher shuffles both alphabets by shifting and then moving a single tile from one location to another. Note the "race tracks" in the illustration below which make it easier to move the tiles to their correct place in the alphabet row. Also notice the two index marks, one for each alphabet, which Byrne called the "zenith". Lacking the race tracks of the sliding tile model, Byrne also used another index mark he called "nadir" to show where to insert the two moved tiles into the alphabet row. Byrne also placed the two wheels side by side instead of concentricly. They were connected by gear-like teeth so that they would move together. Since the wheels will thus move in opposite directions, this requires that in the flat row version we arrange the ciphertext alphabet in the reverse order of the arrangement in Byrne's version.

In operation, whereas with the flat row we would look for the plaintext letter in the bottom row and then find the ciphertext letter in the row above it, in Byrne's version we would turn plaintext wheel until the desired plaintext letter touched the ciphertext wheel, at which time the ciphertext letter would be the tile where the two wheels touch. The net effect, however, is identical in every respect to the flat row version. Check out my proof of equivalence page where I demonstrate decrypting one of Byrne's own messages using my sliding tile machine.

The Chaocipher device implemented with sliding tiles

The Effect of Relocation

Now we can look at the first simple shuffle, which is to move a tile from one fixed location to another fixed location after each shift. For example, suppose we move the leftmost letter (i.e. the letter under the index mark) to a position 6 tiles to the right. Now the alphabet looks like this while being shuffled:

	ABCDEFGHIJKLMNOPQRSTUVWXYZ
	CDEFGHBIJKLMNOPQRSTUVWXYZA <- after shift left and move B 6 spaces right
	EFGHBIDJKLMNOPQRSTUVWXYZAC <- after shift left and move D 6 spaces right
	GHBIDJFKLMNOPQRSTUVWXYZACE <- after shift left and move F 6 spaces right
	BIDJFKHLMNOPQRSTUVWXYZACEG <- after shift left and move H 6 spaces right
	DJFKHLIMNOPQRSTUVWXYZACEGB <- after shift left and move I 6 spaces right
	FKHLIMJNOPQRSTUVWXYZACEGBD <- after shift left and move J 6 spaces right
    

As you can see the alphabet is beginning to get more scrambled than it did with the simple shift alone.

The Effect of Block Moves

Now we can take a look at the same process, but moving a block of two or more letters at a time. For example, suppose that after we shift the alphabet we remove and relocate 3 tiles, reversing them as we do. We will move them, in this example, 11 tiles to the right. And just to make things interesting, we will shift two tiles to the left instead of one. This is what happens:

	ABCDEFGHIJKLMNOPQRSTUVWXYZ
	CDEFGHIJKLMNOPQRSTUVWXYZAB <- shift left AB
	FGHIJKLMNOP EDC QRSTUVWXYZAB <- flip and move CDE
	KLMNOPEDCQR JIH STUVWXYZABFG <- shift FG and move HIJ
	PEDCQRJIHST ONM UVWXYZABFGKL <- shift KL and move MNO
	RJIHSTONMUV QCD WXYZABFGKLPE <- shift PE and move DCQ
	TONMUVQCDWX SHI YZABFGKLPERJ <- shift RJ and move IHS
	VQCDWXSHIYZ UMN ABFGKLPERJTO <- shift TO and move NMU
	XSHIYZUMNAB WDC FGKLPERJTOVQ <- shift VQ and move CDW
    

As you can see the alphabet becomes scrambled more quickly and more thoroughly when we move and flip a block of tiles rather than a single one.

Choosing Parameters for Your Cipher

As we mentioned earlier, the two most important attributes of a sliding tile cipher are the period and the degree of mixing with each shuffle.

The in-place flip shuffles by removing some number of tiles from under the index (i.e., from the left end of the letter row), flipping them, and putting them back in the same place before shifting the alphabet by some number of tiles. The simplest of these uses the same number for the flipped tiles and the shift distance. For example, I can remove two tiles, reverse them, put them back where they were and then shift the row left by two tiles.

A more complex sequence might take 2 tiles the first time, 5 tiles the next time, and 3 tiles the third time, repeating those three numbers in a cycle. That sequence may or may not result in a longer period.

Here is a random assortment of simple shuffle sequences for the in-place flip shuffle:

We can see that making the shuffle sequence longer does not always make the period longer. In fact, some longer shuffle sequences have shorter periods than the simpler sequences. So how does one select a good shuffle sequence? The only real way is by trail and error, possibly using a computer program to test a large variety of shuffling sequences until the best ones are discovered. The drawback, of course, is that if we can discover the sequences with the longest periods, so can the enemy.

None of these periods is long enough to be of much use in a serious cryptographic application, so we need to find a way of getting longer periods.

State-Dependent Sequences

Next we will look at shuffle sequences that are determined by the leftmost letter of the alphabet row (or the tile under the index in the circular version). Here is an example: The numbers 1, 2, 3, 4 will be assigned in that order to the letter tiles. In a permanent set of tiles meant for use with this method the numbers could be written on the tiles themselves perhaps in one corner of the tile like the letter counts found on Scrabble® tiles.

Using this assignment of flip numbers we will always flip 1 tile and shift left 1 when the index letter is A, E, I, M, Q, U, or Y. we will flip 2 tiles and shift left 2 when the index letter is B, F, J, N, R, V, or Z, and so on for 3 and 4 flip/shifts.

The flip schedule then looks like this:

        index letter:     ABCD EFGH IJKL MNOP QRST UVWX YZ
        number to flip:   1234 1234 1234 1234 1234 1234 12
    

We call it a schedule rather than a sequence because it is no longer a definite repeating sequence of moves, but a varying schedule that changes with state of the alphabet row.

The period for this schedule is 463,173,408. with the 100th alphabet HAGZLCBEPIJOTQFDXMNKSRWYVU. This type of shuffle looks much more promising for practical cryptographic purposes.

Assigning larger numbers to the letter tiles results in even better period lengths. For example, consider this set of assignments:

  	ABCDEFGHIJKLMNOPQRSTUVWXYZ
  	34567891234567891234567891
    

We begin with the sorted alphabets:

The starting alphabets

The shuffling is done as follows:

• Look at the leftmost letter in the bottom, or ciphertext row. (A to begin with)
• Find it's numeric value in the table. (A is 3)
• Take that many tiles off the left end of the ciphertext row.
• Move those tiles to the end, reversing their order as you move them.

After the first shuffling operation the three moved and reversed tiles are found at the end of the row like this:

After one shuffle that moved three tiles

Now D is at the head of the row. The numeric value of D in the table is 6 so for the second shuffle we remove the leftmost 6 tiles, reverse them and put them on the end like this:

The tiles after two shuffles

Using this numbering scheme and this starting arrangement the alphabet must be shuffled 45,351,815,892 times times before returning to the original letter arrangement. And yes, I did actually count all 45 billion of them! It took my 3.2 GHz PC nearly 7 hours with the program running in the background while I did other work.

This shuffling method also has the interesting property that it can be reversed by doing the same shuffle, but from the opposite end. For example, here is the arrangement we find after 10,000 shuffles:

      XBSOFULKVHQEPCNTWIZDRGJMYA
    

By treating the rightmost letter, A as the first letter, we look its value up in the table (3) and remove 3 letters from the right end of the alphabet and move them to the left end, reversing them as we go. Thus we know that after 9,999 shuffles it would have been:

      AYMXBSOFULKVHQEPCNTWIZDRGJ
    

Decoding a message or being able to reverse the shuffling process to discover the keyed starting alphabet requires knowing the numerical value assigned to each letter. If that is kept secret then the enemy will not be able to reverse the shuffling process, and will not be able to discover your starting arrangement if you are careless enough to leave your letter tiles laying out in the last arrangement you used.

The shuffle I called "Roy's Playing Card Shuffle" above, and which started me on this exploration of sliding tile ciphers, is of this type.

Another way of making the shuffle state dependent is to base the selection of tiles to move on the contents of the message being encrypted. For example, we could encrypt the letter T in the plaintext into M in the ciphertext, and then take whatever tile is to the right of the T tile and move it to a slot, say for example, 11 tiles to the right.

The Chaocipher device pictured above is of this type. In the ciphertext alphabet it takes the tile to the right of the last used ciphertext letter and moves it 12 slots to the right (or 12 slots clockwise if the rows are arranged in a circular track). With the plaintext alphabet, it takes the tile second to the right from the last plaintext letter used and moves it to a slot 11 tiles to the right. It then shifts the plaintext row one tile to the left. (Or we could say it shifts the ciphertext row one tile to the right since the net result is the same.)

Byrne's actual operating instructions of the Chaocipher device are considerably more complicated than that, but if you actually perform the operations described above and the operations described by Byrne you will see that the end result is identical, and that the same message will be encrypted the same way by both systems.

Broken Row Shuffles

A variation on the method is to break the alphabet row into sections and shuffle each section independently. For example, the shuffle might consist of a shuffle using only the leftmost 11 tiles as a unit, and a separate shuffle using the rightmost 15 tiles as another unit. Of course such a shuffle would leave all the letters trapped in their own units unless an end-around shift of the whole row happened before or after each broken row shuffle.

Here is an example:

The starting alphabets divided into shift groups

The alphabets have been divided into several shift groups which will be treated individually. After each letter is encrypted we perform these operations. On the top row (the plaintext row), take the rightmost letter of each color group and slide it in front of the rest of that color group. On the bottom row (the ciphertext row), take the leftmost letter of each color group and slide it to the end of that color group. Then slide the lower alphabet one tile to the left. The illustration below shows the tiles after one shuffling operation.

The divided alphabets after one shuffle

The alphabet rows could be broken at fixed points, or the location of the breaks could vary according to a pre-set sequence, or according to a state-dependent variable such as the last letter encrypted.

Reflexive Alphabets

A reflexive alphabet is one that reflects back on itself. This is a special case that doesn't really belong in the above family of ciphers, but some of the same shuffling methods above could be applied to the rows of a reflexive alphabet. In a reflexive alphabet there are no separate plaintext and ciphertext alphabets. Instead, a single alphabet is used, but arranged in some manner that allows one letter in that alphabet to be associated with another letter in the same alphabet.

For example, suppose a scrambled alphabet is broken into three rows:

A Reflexive Alphabet

To use this alphabet reflexively find the plaintext letter and then read off the ciphertext letter as the one below the plaintext letter. When looking for the letter below, wrap around from bottom to top so that 'E' is considered to be below 'W'. Wherever the empty slot appears, simply skip over it and take the next letter below.

Shuffling operations might work like the moves of a sliding block puzzle, sliding a row or column, or some portion of a row or column, into the empty spot. A fixed sequence of operations could be performed, or the sequence could be determined by the plaintext or ciphertext letters that come up.

The alphabet could also be arranged as two rows of 13, or as 4 rows of seven tiles with two empty spots distributed somewhere in the matrix. The ciphertext letter might also be taken as a diagonally adjacent tile, or a tile a knight's move away from the plaintext tile in some agreed upon direction.

Here's an example using the three-row reflexive alphabet:

1. Encipher one letter.
2. Slide one tile up and slide one complete row into the empty spot.
3. Encipher one letter.
4. Slide one tile up and slide one complete row into the empty spot.
5. Encipher one letter.
6. Slide one tile down and slide one complete row into the empty spot.
7. Encipher one letter.
8. Slide on tile down and slide one complete row into the empty spot.
9. Go to step 1 and repeat.

The above move schedule returns to the starting point after only 52 letters, but procedures could be chosen that would give longer periods.

Here's what the tile set looks like after each of those operations:

Original Alphabet

After step 2

After step 4

After step 6

After step 8 and ready to start over

Using these operations the plaintext word HELLO becomes QOSRU.

The best way to use this type of cipher would be to perform some complex schedule of moves between each letter that would more thoroughly scramble the alphabet. Such an operation would have to be one that could be repeated many times without returning to the original tile configuration. However, rather than performing a different operation between each letter as we did in the above example, it would be better to use the same operation over and over so that this single multi-move operation could be memorized and then repeated from memory after each letter without having to keep track of where we are in the sequence as with the above example.

As with all the other shuffling methods, this cipher could also use a state-dependent shuffle. Twenty six different moves could be written down and a different one used depending on which plaintext letter came up last. Like all state-dependent schedules that use the last plaintext or ciphertext letter, this creates what is known as an autokey cipher, and does not have a repeating period length. Autokey ciphers do, however, suffer from one drawback when the encryption and decryption is done by hand. If one error is made along the way it will cause the entire text after that mistake to become garbled beyond recovery.

Where to Find Letter Tiles

It turns out that Scrabble® letter tiles are very popular among crafters and they are very often offered for sale in large lots of several hundred letters on ebay with 2010 prices generally around $10 per 100 tiles. Check the latest prices at this link.