Making, Breaking Codes

Subsection 2.1 Rail 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.

Subsection 2.2 Rectangular 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.

Subsection 2.3 Keyword 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.

Subsection 2.4 Word 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.

Activity 2.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.

Answer

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.

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

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.

Subsection 2.5 Cardano 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.

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?

Answer

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.

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.

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.

This give the following grid.

One can explore encrypting and decrypting Cardano grills with a known keyword in Computation 2.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

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

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

OPTION 1

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

OPTION 2

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

OPTION 3

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

OPTION 4

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

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