## Section2Transposition Ciphers

A transposition cipher involves rearranging each letters in the original (or plaintext) message according to some pattern agreed upon by sender and recipient. There are many different patterns that may be used, varying from quite simple to very complex. Remember that a cipher alters the plaintext by operating individually on the letters. A simple example of a transposition cipher would be to write the message backwards. So a plaintext message MEET AT DAWN would given a ciphertext message of NWADTATEEM. Generally all transposition ciphers involve some way or arranging the letters of the plaintext, and then some way of reading off the letters to obtain the ciphertext. In our simple example for writing backwards, we arrange the letters of the plaintext in order, and read them off backwards to obtain the ciphertext.

### Subsection2.1Rail Fence Ciphers

A rail fence cipher is a transposition cipher where we arrange the plaintext letters in a zig-zag form as if they were the rails of a fence. For example, to encrypt the plaintext message ABCDEFGHIJKLMO a rail fence cipher with three rails, we arrange the plaintext letters in a zig-zag fashion, by going down 3 letters than back upward to the top of the line, then continue to alternate downward and upward as in Table Table 2.1.

The ciphertext is formed by reading off the letters based on their horizontal rows: first, AEIM, then BDFHJLO, and last CGK. Thus, the ciphertext for this plaintext message using a rail fence transposition cipher with three rails is AEIMBDFHJLOCGK.

To decrypt a ciphertext message, one needs to reverse the process by first using the number of letters in the text and the number of rails to figure out how many letters would be in each row. Then arranging the ciphertext letters in the rail shape horizontally for each row. Then read the plaintext message by zig-zagging up and down the rails. For example, for the ciphertext message FIRUCPENH and three rails, we note that there are 9 letters, so a rail fence cipher arrangement would be as given in Table Table 2.2.

From this we see that the first 3 letters of the ciphertext will go in the first row, the next 4 letters will go in the middle row, and the last 2 letters will go in the third row, as in Table Table 2.3.

To recover the plaintext message we read the letters down and up the diagonal rails to get FUN CIPHER. It is important to note that encryption and decryption are not the same, but are generally the reverse process. In this case to encrypt, we arrange the plaintext letters in the zig-zag rail system and read the ciphertext horizontally across the rows. However, to decrypt a ciphertext message, we arrange the ciphertext letters horizontally across the rows and read the plaintext letter down and up the zig-zag rail system.

There is nothing special about using three rails. In fact, any number of rails may be chosen. We will explore using different number of rails in Computation Computation 2.4.

### Subsection2.2Rectangular Ciphers

Another common way to create a transposition cipher is to arrange the letters into a rectangle by specifying the number of columns. In this case we encrypt a message by arranging the letters of the plaintext into a rectangle horizontally across the rows, and read off the ciphertext letters vertically down the columns. We decrypt a message by arranging the letters of the ciphertext vertically into columns, and read off the plaintext horizontally across the row. If our plaintext does not evenly fill out the rectangle we could fill in those spots with random letters or leave them blank.

For example to encrypt the plaintext message TOP SECRET CIPHER with a rectangular cipher and three columns we arrange the plaintext letters horizontally as in Table Table 2.5. We use as many rows as necessary based on the length of the plaintext message. In this case, five rows are necessary since there are 15 letters in the plaintext.

We read off the ciphertext by reading vertically down the columns in order from left to right. Thus the ciphertext is TSRCHOEEIEPCTPR.

To decrypt the ciphertext message MTTLEAWVETEE with a rectangular cipher and three columns we separate the text into three groups (one for each column), MTTL, EAWV, ETEE. Then we arrange these letters vertically down the columns as in Table Table 2.6. In this case, there will only be four rows based on the length of the ciphertext.

We read off the plaintext by reading horizontally across the rows from top to bottom. Thus the plaintext is MEET AT TWELVE.

More examples of encrypting a rectangular cipher with any number of columns can be generated with Computation Computation 2.7.

### Subsection2.3Keyword Rectangular Ciphers

Of course, once we arrange the plaintext letters into rectangular shape there are many other ways we could read off the letters to create a more complicated transposition cipher. We will only talk about one other way, using a keyword to rearrange the columns for reading off the ciphertext.

For example to encrypt the plaintext message TOP SECRET CIPHER with a rectangular cipher and keyword of SPY we write the plaintext letters horizontally into three columns since the keyword has three letters. See Table Table 2.8. We need five rows since there are 15 letters in the plaintext.

We read off the ciphertext by reading vertically down the columns in order of the alphabetic ordering of the letters in the keyword. For the keyword SPY, the alphabetic ordering of the letters would be P,S,Y. Thus we would read off the column corresponding to P first, the column corresponding to S second, and the column corresponding to Y last. Thus the ciphertext is OEEIETSRCHPCTPR.

To decrypt the ciphertext message EAWVMTTLETEE using the same system of a rectangular transposition with keyword SPY we separate the text into three groups (one for each letter in the keyword), EAWV, MTTL, ETEE. Then we arrange these letters vertically down the columns but putting the first group of letters under the P, the second group of letters under the S, and the last group of letters under the Y as in Table Table 2.9. In this case, there will only be four rows based on the length of the ciphertext.

More examples of encrypting a rectangular cipher with any keyword can be generated with Computation Computation 2.10.

### Subsection2.4Word Transposition Ciphers

The ciphers in this section date to the Civil War and were used primarily by Union cipher clerks. In this time period messages were transmitted by Morse Code and sent over telegraph lines. The telegraph was invented in the mid-1800's and vastly increased the speed of communication. Once telegraph lines were laid between locations, messages were transmitted very quickly. However lines could be tapped, so communicating by telegraph increased the need for encryption of messages.

The International Morse Code, named after Samuel Morse, one of the inventors of the telegraph, uses dashes and dots to send messages. A dot represents a sound burst of one unit, while a dash is three units of sound burst. Spaces between dashes and dots are one unit. Spaces between letters are three units, and spaces between words are seven units.

We can hear what morse code sounds like at https://morsecode.world/international/translator.html.

A simple type of transposition word cipher is described in Chapter IV of Lincoln in the Telegraph Office as in in Figure 2.13.

The book is digitally available at https://babel.hathitrust.org. https://babel.hathitrust.org/cgi/pt?id=uc1.32106006914730

During Burnside's Fredericksburg campaign at the end of 1862, the War Department operators discovered indications of an interloper on the wire leading to his headquarters at Aquia Creek. These indications consisted of an occasional irregular opening and closing of the circuit and once in a while strange signals, evidently not made by our own operators. It is proper to note that the characteristics of each Morse operator's sending are just as pronounced and as easily recognized as those of ordinary handwriting, so that when a message is transmitted over a wire, the identity of the sender may readily be known to any other operator within hearing who has ever worked with him. A somewhat similar means of personal identification occurs every day in the use of the telephone.

At the time referred to, we were certain that our wire had been tapped. In some way or other the Confederate operator learned that we were aware of his presence, and he then informed us that he was from Lee's army and had been on our wire for several days, and that, having learned all that he wanted to know, he was then about to cut out and run. We gossiped with him for a while and then ceased to hear his signals and believed that he had gone.

We had taken measures, however, to discover his whereabouts by sending out linemen to patrol the line; but his tracks were well concealed, and it was only after the intruder had left that we found the place where our wire had been tapped. He had made the secret connection by means of fine silk-covered magnet wire, in such a manner as to conceal the joint almost entirely. Meantime, Burnside's cipher operator was temporarily absent from his post, and we had recourse to a crude plan for concealing the text of telegrams to the Army of the Potomac, which we had followed on other somewhat similar occasions when we believed the addressee or operator a the distat point (not provided with the cipher-key) was particularly keen and alert. This plan consisted of sending the message backward, the individual words being misspelled and otherwise garbled.

###### Activity2.1.

Can you decrypt the messages below? Read each message out loud and backwards. That is start at the end of the message and read each word in reverse order.   Chapter IV of Lincoln in the Telegraph Office also describes a more complex type of word transposition cipher.

The first Federal ciphers were developed by Anson Stager in 1861 for General McClellan involved transposition ciphers at the word level. A cipher technique was indicated by 3 by 5 card and consisted of a series of keywords and a number of codewords, called “Arbitrary Words”. The keywords were used to indicate the number of lines and columns and the route or order in which the messages might be written. The codewords represented names of people or places. To encrypt the message, the cipher operator would write the words of the message in the appropriate number of columns, filling in extra words on the last line if it was not full.

For example, a keyword of “GUARD” could indicate a rectangle of five columns and seven rows and an encryption route to read off the ciphertext by going up the first column, down the second column, up the fifth column, down the fourth column, and up the third column. Null words were often added to make the code more complicated. In this case, we will create a null word every eight words. Codewords would be used to hide important names that could give away too much information even if the message can't be decrypted.

We will encrypt the following message:

Registration for spring classes will take place in November. In October you should set up an advising appointment with Haley and Professor Veenstra. Almost time to think about spring classes.
We add NULL words every 8th word. This corresponds to adding a null word at the end of each column.
Registration for spring classes will take place NULL in November. In October you should set NULL up an advising appointment with Haley and NULL Professor Veenstra. Almost time to think about NULL spring classes. NULL
We will also use the following Code words: November = HOUSE, October = SMELL, Haley = JOHN, Professor = PLUTO, Veenstra = GERTRUDE.

The ciphertext for this message becomes

ABOUT GERTRUDE WITH REDLANDS IN TAKE REGISTRATION FOR PLACE SMELL UP JOHN ALMOST ORANGE WEATHER THINK PLUTO APPOINTMENT SET HOUSE WILL CLASSES IN SHOULD ADVISING MOUNTAINS TO CLASSES SPRING TIME AND AN YOU BULLDOG SPRING.

###### Activity2.2.
1. Decrypt the ciphertext message using the same pattern as above. Note the keyword “GUARD” indicates the pattern for a rectangle of five columns and seven rows and an encryption route to read off the ciphertext by going up the first column, down the second column, up the fifth column, down the fourth column, and up the third column. Null words were often added to make the code more complicated. For decrypting we will place the words in the ciphertext in the columns as indicated by this pattern. Every eightth word is ignored as a null. The codewords for this version are: VENUS=colonel, WAYLAN=captured, ODOR=Vicksburg, NEPTUNE=Richmond, ADAM=President of the United States, NELLY=4:30pm.

GUARD ADAM THEM THEY AT WAYLAN BROWN FOR KISSING VENUS CORESPONDENTS AT NEPTUNE ARE OFF NELLY TURNING UP CAN GET WHY DETAINED TRIBUNE AND TIMES RICHARDON THE ARE ASCERTAIN AND YOU FILLS BELLY THIS IF DETAINED PLEASE ODOR OF LUDLOW COMMISSIONER

2. The plaintext for a message is given in Figure 2.17 and its corresponding ciphertext is given in Figure 2.18. From this pairing, we can see the the keyword “BLONDE” must indicate a word transposition with seven rows and eleven columns. By matching the plaintext and ciphertext, determine what route is used for the encryption. That is, which column do you use first? Do you go up or down the column? In which order are the rest of the columns used? What are the null words? (Remember that they are added at the end of each column.) What are the code words?

3. Use the morse code in Figure 2.12 to answer the questions below.

1. - --- --- / -- .- -. -.-- / ... . -.-. .-. . - ...
2. .-- --- ..- .-.. -.. / -.-- --- ..- / .-.. .. -.- . / - --- / . -. -.-. --- -.. . / - .... .. ... / .-- .- -.-- ..--..
3. Which letters or numbers use only one Morse code symbol? Why might this be?
4. Which letters or numbers use only two Morse code symbols? Why might this be?
5. For the letters, E, G, X and the numbers 2,9 compute the time it takes to transmit each letter. In Morse code a dot is one unit, a dash is three units, the space between parts of the same letter is one unit, the space between different letters is three units, and the space between words is seven units. For example, R is dot, space, dash, space, dot so it takes 1+1+3+1+1=7 units of time to transmit.
6. Use your above work to theorize about how letters were assigned to the various morse code representations.

### Subsection2.5Cardano Grill Ciphers

The Turning or Cardano grill, was invented by Girolamo Cardano, 1501-1576. Cardano was physician, mathematician, popular science lecturer, ardent astrologer, prolific author, and all around interesting character. He is best known for being the first to publish a method to solve cubic equations (though this has its own controversy with use of work from Tartaglio). Cardano's general solution to a cubic $x^3+bx^2+cx+d=0$ relied on a solution from Tartaglia (nickname for Niccolo Fontana, nickname means the Stammerer) to a depressed cubic, $x^3 +mx=n\text{.}$ But Tartaglio was insistent on keeping his solution a secret (he liked to challenge other mathematicians to solve equations) and only gave Cardano this information after Cardano agreed to the following oath:

I swear to you by the Sacred Gospel, and on my faith as a gentleman, not only never to publish your discoveries, if you tell them to me, but I also promise and pledge my faith as a true Christian to put them down in cipher so that after my death no one shall be able to understand them.
Eventually, Cardano discovered that another mathematician, Scipione del Ferro, had also discovered this solution, so Cardano felt justified in using the result in his publication. In this book, Ars Magna, he was also the first to make use of complex numbers in a calculation. He was a fond of gambling, and authored the first book, Book on Games of Chance on the mathematics of probability. He suffered from a multitude of health issues throughout his life (at least he was fond of complaining about them), and had many issues keeping a job. He was arrested and jailed in 1570 for casting the horoscope of Jesus, and writing a book In Praise of Nero.

Cardano wrote on a wide variety of topics, so it is not surprising that he was also interested in ciphers. Its unknown if he actually used a cipher to store the information from Tartaglia and how he used the cipher known as the Cardano grill. This grill is an adaptation of some of the masks or grills that were used for steganography to hide the message in a cover message. For example, a variety of masks were used in the American Revolutionary War. Cardano grilles were used as recently as World War I by the Germans, but French cryptanalysists learned to break these so they were eventually replaced by the ADFGX cipher.

A Cardano grill may be constructed from an equilateral shape, but most commonly uses squares. To encrypt a message, holes are placed in a square, and then letters of the plaintext message are written into a grid based on the holes in the square, and rotating the holes in the square.

To see how to encrypt with this method, we begin with an example. Suppose we begin with a $4 \times 4$ square. There are sixteen entries in a $4 \times 4$ square so we must pick a message with less than 16 letters. The location of the holes is the key to encrypting and decrypting the message, and must be agreed upon in some method. We will discuss a method shortly, but for now we will assume we have agreed upon the starting grid in Table 2.19. We pick a short message “WELCOME FALL TO ALL”. This message has exactly 16 letters, but we could fill it with extra letters if it did not. We use the holes in the grid in Table 2.19 to place the first four letters of the plaintext into a $4 \times 4$ square.

To place the next four letters, we rotate the grill 90 degrees in a clockwise direction, and continue for all remaining letters.

This gives us the following ciphertext grid.

The ciphertext message can be read off horizontally, so as to disguise the technique used, AWEOA OLMLL LEFLT C.

Let's use the same grid to see an example of decryption.

To decrypt the message, we want to apply the grill to reveal letters instead of write letters.

What should we do to create our own grid? We must choose where to place holes in the grid. How many holes can we place and where can we place them? There are limits on where we can places holes. For example, we could not choose the following two holes for our initial grid. Why not?

 O $\;\;$ $\;\;$ O $\;\;$ $\;\;$ $\;\;$ $\;\;$

When we rotate the grill we would need to place different letters in the same hole.
 $1$ $\;\;$ $\;\;$ $1_r$ $\;\;$ $\;\;$ $1_t$ $\;\;$ $1_s$

Note that each hole is rotated four times in a square grid, so each hole should correspond to four different locations in the grid for each rotation. This means that the number of holes we can pick is the number of spots in the grid divided by 4. In this case, we can pick $\frac{16}{4}=4$ holes. In general, for an $n \times n$ grid, we can pick at most $\frac{n^2}{4}=4$ holes. We can certainly choose less and fill any extra spots in the grid with null letters or leave empty spaces.

The easiest way to think about how to choose holes so that they create distinct spaces after rotation is to divide the square into grids and think about how each grid rotates. This is easiest if our grid has an even length. That is, if we have an $n \times n$ grid, where $n$ is even.

 $1$ 2 $3_r$ $1_r$ 3 4 $4_r$ $2_r$ $2_t$ $4_t$ $4_s$ $3_s$ $1_t$ $3_t$ $2_s$ $1_s$

If $n$ is odd, then we need to use a rectangular shape and cannot use the middle square of the grid. For example, we examine a $5 \times 5$ grid, we can pick at most $\frac{5^2}{4}=\frac{25}{4}$ holes. In this case, since we have to remove the middle hole, we can really pick at most $\frac{5^2-1}{4}=\frac{24}{4}=6$ holes. This case is more complicated so normally even sides were used.

 $1$ 2 $3$ ${4_r}$ $1_r$ 4 5 $6$ $5_r$ $2_r$ $3_t$ $6_t$ $\;\;$ $6_r$ $3_r$ $2_t$ $5_t$ $6_s$ $5_s$ $4_s$ $1_t$ $4_t$ $3_s$ $2_s$ $1_s$

We can also use a keyword to assign holes to form a Cardano grid. Let's examine a $6 \times 6$ grid, we can pick at most $\frac{6^2}{4}=9$ holes. Let's pick “REDLANDS” for a keyword. We need nine letters to pick the nine holes, so we repeat the word until we get enough letters. “REDLANDSR” We then list the alphabetic order of the letters of the keyword, ordering from left to right if the same letter appears multiple times.

 R E D L A N D S R 7 4 2 5 1 6 3 9 8
We then rotate through quadrants, starting with the top left quadrant, picking the hole corresponding to $7,4_r,2_s,5_t,1,6_r,3_s,9_t,8$ as in Table 2.37.

This give the following grid.

 $1$ $\;\;$ $\;\;$ $\;\;$ $4_r$ $\;\;$ $\;\;$     7 8   $6_r$    $9_t$     $5_t$        $3_s$ $2_s$ 

One can explore encrypting and decrypting Cardano grills with a known keyword in Computation 2.38.

###### Computation2.38.

But what if we do not know the keyword or grill? How do we perform cryptanalysis to discover the message? Suppose we have the following ciphertext

and we know the word “FUN” occurs in the plaintext. What does that tell us about where the holes in the grill can occur? Firstly, its a $2 \times 2$ grid, so we know that there are at most four holes in the grid. We can see where the letters F, U, and N are. In general, we don't know if all letters of “FUN” will be in the same rotation, but given that we can find the letters in order, we guess that they correspond to holes in the same rotation. Thus, at some stage in the process we have

 $\;\;$ $\;\;$ $\;\;$ $\;\;$ F $\;\;$ U N $\;\;$ $\;\;$

There is at most one more hole, and considering all the rotations of letters F, U, and N, there is at most four places where the hole could be on this rotation. If we place x's in all the rotation spots for F,U,N we have

 $\;\;$ $x$ $x$ $\;\;$ F x x U x N x x x x

We now try each of the four options and its rotation to try to make sensible words.

OPTION 1

 O $\;\;$ $\;\;$ $\;\;$ O O O $\;\;$
 C $\;\;$ $\;\;$ $\;\;$ F $\;\;$ U N $\;\;$ $\;\;$
 $\;\;$ $\;\;$ O O O $\;\;$ O $\;\;$
 $\;\;$ $\;\;$ O T D $\;\;$ X $\;\;$

This gives the portion of the message “C FUN OTDX”.

OPTION 2

 $\;\;$ $\;\;$ $\;\;$ O O O O $\;\;$
 $\;\;$ $\;\;$ $\;\;$ T F $\;\;$ U N $\;\;$ $\;\;$
 $\;\;$ $\;\;$ O $\;\;$ O $\;\;$ O O
 $\;\;$ $\;\;$ O D $\;\;$ X C

This gives the portion of the message “T FUN ODXC”.

OPTION 3

 $\;\;$ $\;\;$ $\;\;$ $\;\;$ O O O O
 $\;\;$ $\;\;$ $\;\;$ $\;\;$ F $\;\;$ U N $\;\;$ C
 $\;\;$ $\;\;$ O $\;\;$ O $\;\;$ O O $\;\;$
 $\;\;$ $\;\;$ O D $\;\;$ E X $\;\;$

This gives the portion of the message “FUN CODEX”.

OPTION 4

 $\;\;$ $\;\;$ $\;\;$ $\;\;$ O O O O $\;\;$
 $\;\;$ $\;\;$ $\;\;$ F $\;\;$ U N E $\;\;$
 O $\;\;$ O $\;\;$ O $\;\;$ O $\;\;$
 C $\;\;$ O $\;\;$ D $\;\;$ X

This gives the portion of the message “FUN ECODX”.

For all of these options, OPTION 3, looks the best and if we continue with the other rotations we get

 O $\;\;$ $\;\;$ $\;\;$ O O O $\;\;$
 C $\;\;$ $\;\;$ $\;\;$ R A C $\;\;$
 $\;\;$ O $\;\;$ O $\;\;$ $\;\;$ O O $\;\;$
 $\;\;$ K T $\;\;$ $\;\;$ H E $\;\;$

Thus we obtain the full message “CRACK THE FUN CODE X” where the last letter is a filler letter.

###### Activity2.3.Cardano Grills Activity.
1. For an eight by eight grid, what is the maximum number of holes you can put in the grid?

2. For a nine by nine grid, what is the maximum number of holes you can put in the grid?

3. For a ten by ten grid, what is the maximum number of holes you can put in the grid?

4. Pick your own message and keyword and encrypt it with a Cardano grill.

5. Decrypt the message below which was encrypted with a 10 by 10 grid and keyword wonderful world. LRILMEIOSA GARNIVFET RNOIAHMTY EOUTLIFYIL EOERAOFNGI DSYOEXPTEU VROLDRREAR EESNUISIEA WNINGNXCGS XESMSXCXUXIX

6. Decrypt the following. Hint: the word “quickly” occurs somewhere in the message.

 M T E O A A D N P S S S D E Q D A U C E G R I E S C T K R E T E L R Y O