## Fractionating Ciphers

What is it?  A fractionating cipher is generally a multistep cipher. The first step is a simple substitution, except multiple characters are substituted for single letters in the message. Then, the message is transposed. Following are some examples of fractionating ciphers:

The ADFGVX cipher was used by the Germans during World War I. The substitution step is a digraph substitution based on a 6 * 6 key square and the transposition step is a columnar transposition based on a keyword:

A  D  F  G  V  X

Ex. P = HELP                                                 A   A  B  C  D  E  F

keyword = NOPE <--> (2, 3, 4, 1)           D   G  H  I   J   K  L

F    M  N  O  P  Q  R

G    S   T   U  V  W  X

V    Y   Z   0   1   2   3                                                                                                                                                          X    4   5   6   7   8   9

Step 1 - substitution: HELP --> DD AV DX FG

1  2  3  4

Step 2 - columnar transposition:   (2, 3, 4, 1)              Grid:        D D  A  V

D X  F  G

C = DXAFVGDD

Notice that during the transposition step, the bigrams that corresponded to each individual letter got broken apart. This is the diffusion step, and it is the reason why the cipher is so secure. Frequency analysis proves to be futile on the ciphertext.

The Trifid cipher is a fractionating cipher that employs a very unique transposition algorithm. Even the substitution step is quite unique since it relies on a 27-letter alphabet. First, each letter is replaced with 3 digits, each digit being either 1, 2, or 3. Then, a period is chosen, and the message is broken into n-grams where n = (3 * the period). Finally, each n-gram is read off vertically and the resulting text is spliced together. An optional final step is to convert the 3-grams in the ciphertext back to letters according to the substitution table. A sample encryption is shown below:

Substitution Table

A = 332  B = 123  C = 132  D = 222  E = 311  F = 111  G = 212  H = 322  I = 333

J = 121  K = 323  L = 231  M = 213  N = 312  O = 131  P = 232  Q = 331 R = 112

S = 133  T = 233  U = 321  W = 223  X = 122  Y = 113  Z = 221  . = 313

Ex. P = HELP

period = 2

Step 1 - substitution: HELP --> 322 311 231 232

Step 2 - break into 6-grams (3 * period): 322311 | 231232

Step 3 - Read off each 6-gram vertically (apply a Swagman cipher to each 6-gram):

3  2         |       2  3

2  3         |       1   2   (read down)

1  1         |       3   2

C = 321231213322

Optional Final Step: Convert 3-grams back to letters

C = ULMH

This is a very unique transposition algorithm because instead of transposing the entire message, the Trifid cipher transposes individual chunks of the message and then splices them together. You can learn more about this algorithm by playing around with nFid.py under Tools. For a Trifid cipher, n = 3 because the substitution is done in trigrams, but theoretically, the substitution step could be done in bigrams (n=2), quadrigrams (n = 4), or any value for n.

How do I recognize it?:  Recognizing a fractionating cipher can be difficult. Part of the reason is that you will want to deny that you are working with a fractionating cipher because they are not easy to decode. The other part is that a fractionating cipher's frequencies can often be mistaken for polyalphabetic frequencies. There are two key qualities that make fractionating ciphers stand out:

1. There are very few distinct individual characters present in the message.

2. No matter whether you analyze the bigrams, trigrams, quadrigrams, ... n-grams in the message (in a blocks window), the frequencies will reveal nothing about the message and the number of distinct n-grams will be equal to the probabilistically expected number.

Here are sample bigram, trigram, and quadrigram frequencies of an ADFGVX cipher:

Only parts of the trigram and quadrigram frequencies are shown, but hopefully, you get the idea. The frequencies are FLAT. The bigram frequencies may look similar to the frequencies of a Vigenere cipher, but once you look at the trigram and quadrigram frequencies you can confirm that the message has been fractionated.

How do I break it?:  Breaking a fractionated cipher can be very tedious and is a worthy challenge. Here, I will tell you briefly how to crack an ADFGVX cipher. To get you thinking about how this might be done, first consider how many distinct characters appear in the message. In our example above, there are six distinct characters: A, D, F, G, V, and X. So the question is, how can I group together 6 distinct characters to represent the 26 letters of the alphabet? Would I use bigrams? Trigrams? Quadrigrams? If I use bigrams, then I can make 36 different possible 2-letter combinations. This is more than enough characters to represent the 26 letters in the alphabet. But thinking back to the substitution step when encrypting with the ADFGVX cipher -- is it really likely that any of the digits [0-9] will appear in the message? Probably not. So I want to find a transposition algorithm that transposes the message in a way such that the result has close to around 26 distinct bigrams. I can use the brute-force method and score based on how far the distinct bigram count is from 26. Then, I can choose the message with the closest score and decrypt it as a bigram substitution cipher.

Takeaway + Additional Notes: You WILL need a computer to solve a fractionating cipher. Unless it has not been transposed, there is no way that you can do it by hand because you need to use a brute-force method. To solve an untransposed fractionating cipher, which is essentially just an n-gram substitution cipher, you need to replace the n-grams with letters in the English alphabet. Then, you can use a cryptogram solver or manually decrypt the substitution cipher. I made a tool in Python that does the replacement called ngramSubstitution.py (look under the fractionating ciphers folder in Tools). Overall, fractionating ciphers are the cream of the crop when it comes to challenging classical ciphers.   