Thinking About Encryption, Part 67


Nihilist Transposition revisited

I first wrote about the Nihilist Transposition cipher back in October, 2018. It’s a variation on Complete Columnar, where you’re using a square instead of a rectangle and you’re reordering both the rows and the columns with the same numbered key (you can check the original entry for details). Sorting on row and then column is the same as sorting on column then row. However, you can choose to pull off the cipher text either by rows, or by columns, which gives you different cipher messages.

Because the examples and descriptions in the ACA Cm newsletter use numbered keys spanning from 1 to 9, that’s how I wrote my VBScript bruteforce solver. And, because the ACA guidelines state that NT can only be 10×10 maximum, and I’d never seen anything larger than 8×8, I figured that hardcoding the keys to be 1-9, max, would be fine.

Naturally, the NT cipher in the May-June, 2019, CM turned out to be 10×10, and that crashed my script. It had been so long since I last looked at it, I didn’t remember which sections needed to be modified and which didn’t. It took me a couple hours to get the script working for a key string of “1234567890”, where I had to monitor for “0” and convert it to 10, and vice versa. And then, it would take 3 hours for the permutating incrementer to get up to “09876543321” and exit out without finding the solution, showing that I was still doing something wrong. After going through several iterations of the new permutator, I realized what the problem was. At that point, I figured out that I should be running the incrementer in hexadecimal format (i.e. – “123456789abc”), but if 10×10 takes 3 hours to max out, 11×11 just isn’t going to be feasible, even if it were allowed by the ACA guidelines (which are just guidelines, so someone could still come out with an 11×11 NT anyway).

The moral is… I’m not sure there is one. I write my cipher solvers as I’m learning the rules of the type, and as I’m trying to figure out how to solve them. I don’t know everything there is to know about any given type, so I’m going to overlook things as I go along, and I won’t know that until some time later when I encounter crypts that crash the script. On the other hand, it’s better to assume the worst case up front and softcode everything I can right from the beginning so that I don’t have to rip stuff out later to correct my earlier oversights. This presents me with a tradeoff – either get the script working quickly for the CONs in the Cm I’m trying to solve now, or spend more time softcoding everything and doing more debug on sections I can’t fully test until harder CONs come out several months later.

Regardless, once I had the new NT script running, it solved the 10×10 NT in 1.5 hours (the key was in the “5712346890” range). The more common 8×8 squares take about 1 minute to solve. That’s a big difference in expectations.

Wiggles, part 61


Just a little ongoing story to give you something to play with until the next blog post.

TVOCO DNZ FR LRRG DNM TR LOT RBT RJ TVHZ, ZR H JHLBCOG TVNT TVO ZHAESO KNENFOZO NEECRNYV DRBSG PO POZT, NFG TVNT DRBSG PO TR HFTCRGBYO AMZOSJ, NFG NZU HJ TVOM YRBSG VOSE AO SONIO VOCO. H REOFOG AM ARBTV, PBT DVROIOC DNZ VRSGHFL TVNT JSNZVSHLVT ZERUO JHCZT. “GR MRB DNFT AO TR LOT MRB ZRAO DNTOC, RC N JNYOYSRTV?” HT DNZ “ANAN’Z” IRHYO, PBT JCHOFGSM, FRT ZFNUOSHUO. ZTHSS, H DNZF’T ECOENCOG JRC TVHZ NFG H TRRU N VNSJ-ZTOE PNYU, CBFFHFL HFTR TVO GRRC POVHFG AO. TVNT YNBZOG AO TR SRRU GRDF. DVOCO AM JRRTECHFTZ ZVRBSG VNIO POOF HF TVO ZNFG RF TVO JSRRC, DOCO TDR ZOTZ RJ ZANSSOC ECHFTZ – RFO SONGHFL BE TR NSARZT DVOCO H DNZ ZTNFGHFL, NFG TVO RTVOC COTBCFHFL TR TVO ANHF TBFFOS. AM VONG ZDBA NZ H TCHOG TR GONS DHTV TVHZ. HF TVO RFO RC TDR AHFBTOZ JCRA DVOF TVO UHGZ DOFT BEZTNHCZ, “ANAN” VNG LRTTOF HFTR TVO TBFFOS, ZFBYU BE POVHFG AO DHTVRBT AO VONCHFL HT, NFG TVOF ZFBYU PNYU TR TVO ANHF TBFFOS TR DNHT JRC AO TR TBCF NCRBFG? ANMPO NSS RJ TVHZ DNZ KBZT N CONSSM PNG GCONA, NFG H’G JNSSOF NZSOOE HF TVO CHYUH VRBZO LCOOF CRRA DHTVRBT CONSHWHFL HT.

Book reviews: Secret and Urgent


I recently received four cryptography-related books for my birthday: One was Fletcher Pratt’s Secret and Urgent, one was Helen Fouche Gaines’ Cryptanalysis, and two were by H.O. Yardley. I’ll make comments as I finish each one.

I first learned of Fletcher Pratt back between the late 1970’s and early 80’s, when someone recommended “The Incompleat Enchanter” fantasy series, co-written with L. Sprague De Camp. In the last couple of years, I’ve seen Secret and Urgent mentioned many times as a good history of cryptanalysis, especially as recommended by members of the ACA as far back as the 1939 publication date. It’s important to note that Fletcher was well-established as a military historian, and that he tended to specialize on the American Civil War. In writing Secret and Urgent, he had assistance from Major D.D. Millikan, O.R.C., as well as access to Millikan’s extensive library. Also, in the Prefactory Note, he mentions that the ACA and Helen Gaines were in the process of preparing their “Elementary Cryptanalysis” for publication, so he at least knew of the ACA at that time, if not worked with them much.

I want to immediately start by comparing SaU with Simon Singh’s “The Code Book.” I read The Code Book 2 years ago, and that’s largely what got me started on writing this blog series. But, on reflection, a lot of what Simon included in his book also appeared in SaU, with some rearrangement. Fletcher begins by stating that all language is actually ciphers that can be understood by those that know the language, and a form of secret message to those that don’t. He then gives a few semi-recent examples of archeologists and language experts decoding ancient languages. Simon moves this section to the back of his book, as he talks about Linear A and B. Conversely, Simon starts with the Mary, Queen of Scots trial, while Fletcher has this in the middle of his book, placed more chronologically. Fletcher covers more of the ciphers used in the Civil War, while Simon plays those down in favor of more British systems, and those that were used in WW II. SaU was published in 1939, and my edition by Blue Ribbon Books was printed in 1942, so naturally Fletcher doesn’t say anything about WWII German codes, and anything more recent, like RSA. Singh goes into some detail for RSA, but his discussion of quantum computing for password protection added nothing to his book.

Secret and Urgent is 2/3’s history, and 1/3 how-to. After mentioning the decoding of Egyptian hieroglyphs and ancient Greek script, he goes into analyses of the Voynich manuscript, and the various “proofs” people have put forward to show that Francis Bacon wrote Shakespeare. He does talk about Elizabeth Gallup and Colonel George Fabyan, but there’s no mention of William Friedman or his wife Elizebeth (Smith), who had worked with Fabyan for Gallup before William moved on to found what later became the NSA. (Friedman was working for the government in the Signals Intelligence Service at the time Yardley published “The Black Chamber” in 1931. Fletcher mentions Yardley a couple times in conjunction with MI-8, and quotes him on “You need to treat each new cipher as its own system.” So, Fletcher knew of Yardley, and should have been aware of Friedman, but there’s nothing on either William or Elizebeth in regards to Gallup and Fabyan, or William’s work for the government during WWI.)

Along with all of the other history, Fletcher spends a lot of time describing how Complete Columnar, simple substitution, simple substitution with frequency suppression, Vigenere, Gronsfeld, Nihilist transposition, and Playfair all work, both for encryption and decryption. He also walks through the steps for solving each cipher type, and provides examples for the reader to play with (answers in the back of the book), and extensive frequency tables for English, French, German and Spanish letter distributions, and English digraphs, trigraphs and pattern words.

Fletcher also covers Louis XIII’s Grand Cipher, the work of Rossignol and Bazeries, Samuel Pepys’ diaries, and the codes and secret languages of hobos and gangsters in different ages. While the discussions of ciphers and codes during WWI are interesting, a lot of the material generated during that time was still somewhat restricted or undocumented, so there was only so much Pratt had at his disposal to write about. He is also kind of tight-lipped regarding Yardley, preferring to refer the reader to Yardley’s books (Fletcher gives the impression that he personally liked Yardley and his cryptographic work).

As I wrote above, a lot of what appeared in SaU gets duplicated in Singh’s The Code Book. But, Pratt is much better at showing how to attack most of the earlier, simpler ciphers than Singh is. I highly recommend reading Secret and Urgent first, followed by Yardley’s The Black Chamber before focusing on the last half of Singh’s book (specifically the sections on the Enigma machine and RSA). One other thing that Fletcher doesn’t mention, that Simon does, is that one of the people who had first cracked Vigenere was Sir Charles Babbage, inventor of the Babbage analytical engine. Fletcher assigns Babbage’s method to Kasiski, as was common at the time.

Overall, SaU is a fun, fast read if you already know the principles he describes for solving ciphers. And it’s a great introduction to solving those types if you’re new to the science. Highly recommended if you can find a copy.

Thinking About Encryption, Part 66


NULL revisited

I wrote about NULL ciphers quite a while ago, and since then I’ve encountered a few different ways the rules can be established. NULLs are more mind benders than real ciphers, and can use whatever rules the author desires, such as “the first letter of each word,” “the last letter,” “the first letter after each vowel,” “the odd letter out for each word, for curved and straight letters,” etc. However, the most common approach is to use position patterns. For example, in the string “ACTIVE BEDLAM BLATHER ABSORBS CITRON UNEXPECTEDLY”, the pattern is “2-5-4” and my original plaintext message was “cat box”.

The primary way of solving a NULL is to try to place the crib, which may fit multiple locations, and then determine if there are any patterns that can be replicated throughout the entire message. If there is a clear pattern, it will produce a readable plaintext message from all of the words in the crypt. I’ve been able to solve most of the NULLs that have appeared in the ACA’s Cm newsletters since July 2018, but the one in the May-June 2019 issue stumped me. It was numbered E-6, out of 25 CONs, meaning that it was supposed to be easy, but I couldn’t extend the patterns I was extracting to read the plaintext. I eventually decided to try a different approach.

Say we have the message (I’m kind of mimicking E-6, but with different words and different rules):

Title: A proverb (hint: "the").
ADAPTIVE PRESUMABLE OCCUPATION KEYSTROKE CHLORIDE
RADIOTHERAPY AEROSPHERE STARTLED ORTHOGONAL DANGEROUS
AGITATED MICROCOSM MATHEMATIC BARISTA SALTBOXES
WHITEBOARD USEABILITY BUTTONHOOK GOALLINE MIDWESTERN
PIPEFIT

Normally, the first step would be to place “the” in the message. Unfortunately, we have an embarrassment of riches. “RADIOTHERAPY” and “MATHEMATIC” both contain “the” in its entirety, and the successive words “KEYSTROKE CHLORIDE RADIOTHERAPY,” “RADIOTHERAPY AEROSPHERE STARTLED,” “STARTLED ORTHOGONAL DANGEROUS,” “SALTBOXES WHITEBOARD USEABILITY” and “USEABILITY BUTTONHOOK GOALLINE” have “t” “h” and “e” in them in different sequences which could be used to spell out “the” in some way.

We could try counting the letter positions in each set of words and see what that gets us. For “KEYSTROKE CHLORIDE RADIOTHERAPY”, it’s “5-2-8”. Other patterns are “6-7-7”, “2-4-5”, “5-4-5”, “4-2-3” and “9-7-8”. Just looking at “5-2-8”, “KEYSTROKE” is the 4th word in the list, and assuming the pattern is exactly 3 digits long, it would repeat for the first three words. That is, “ADAPTIVE PRESUMABLE OCCUPATION”, using the “5-2-8” pattern, would give us “TRI”, for a full “word” of “TRITHE”. This is going to take a while, especially if the pattern is more than 3 digits.

Ok, so the second approach is to see what words can be formed from the words at the beginning of the message. What I did was write a VBScript to run through my dictionary file, and print out those words that have letters in the right place for the word list. That is, if the dictionary word is “TRUEHEARTED”, it will match my above word list with a pattern of “5 2 4 2 2 8 1 4 3 5 8”. Unfortunately, there are 627 other words in the dictionary that can also be formed here, so I’m not narrowing things down much, am I.

But, we do have a little bit more to work with. The title says that this is going to be a proverb of some kind, so we can eliminate words like “veneer”, “veto” and “vector” for the moment. Additionally, one of our “the”s has the pattern “2-4-5”, and “true” starts with “5-2-4”. Maybe the pattern is “5-2-4-5-2-4”.

5 ADAPTIVE - T
2 PRESUMABLE - R
4 OCCUPATION - U
5 KEYSTROKE - T
2 CHLORIDE - H
4 RADIOTHERAPY - I

“TRUTH” is in fact one of our legal words, so let’s use “5-2-4” in a cycle. This gives us:

"TRUTHISTHEGREATESTLIE"

And now we have our solution. The moral is that sometimes variants on anagramming can help break a NULL cipher when you have trouble placing the crib. Try to build a list of legal words starting from the beginning of the cipher message, and compare the letter positions from the words in the message to the positions for every place the crib can fit. As long as the plaintext doesn’t use proper names and foreign words that aren’t in the dictionary, this approach will work as a second resort. It also shows that part of the first resort should have included trying rotations of the crib positions (“2-4-5”, “4-5-2” and “5-2-4”) on the CON to see what comes out. At least now I have this VBScript written for the next time I need it.

Wiggles, part 60


Just a little ongoing story to give you something to play with until the next blog post.

B ORTTDF EAD FIIV MTILDF, MSVDXRT EI ZDDO EAD TSEMA XVIY MTBMZBCU EII TIRFTK. EAD LBFD ERCCDT LSCZ BCEI FSVZCDLL, JRE CIE SL FSVZ SL BE LAIRTF ASND JDDC. B MIRTF LDD S JBE IX YK LASFIQ MSLE IC EAD FIIV BC XVICE IX YD, YDSCBCU EASE LIYDEABCU QSL OVIFRMBCU TBUAE JDABCF YD. B QSLC’E STICD SXEDV STT. B LTIQTK ERVCDF MTIMZQBLD, TDEEBCU YK TDXE ASCF AITF YK XTSLATBUAE TBZD S MTRJ, ABFFDC JK EAD VDLE IX YK JIFK. KDL, EADVD QSL LIYDICD JDABCF YD, AITFBCU EADBV IQC XTSLATBUAE SE YD. BE TIIZDF TBZD ICD IX EAILD MADSO 100 KDC ($1 RLF) TDF ZDKMASBC TBUAEL, QABMA SVD LEBTT OVDEEK LEVICU. EADK QDVD LESCFBCU JSMZ JK EAD YSBC ERCCDT FIIV, LI B MIRTFC’E YSZD EADY IRE SE STT; BE QSL GRLE EABL QABED JSTT BC EADBV ASCF, SCF S ASTI IX TBUAE EAVIRUA EAD FRLE BC EAD LBFD ERCCDT.

Thinking About Encryption, Part 65


5×5 Bifid
6×6 Bifid

Sorry about the missed posting on Monday. Keyboard went out on the laptop and I needed to wait on the repairs.

I’ve mentioned a few times over the last year that I’m trying to pace myself in learning new cipher types. The ACA recognizes 60 different types for the Cipher Exchange department, and will allow maybe another 10 or so in the Analyst’s Corner department. My initial plan was to just go for maybe 1 or 2 new types a month, and spread things out over the course of many years. The reality, though, is that it’s been closer to 1 or 2 new types per week, depending on difficulty, and whether I have other things going on that I need, or want, to focus on more (work, or video games). One key limiter, though, is that I want to focus on ciphers in the latest ACA Cryptogram newsletter, and the deadline for handing in the solutions for a specific issue is the last day of the 4th month after the issue release (that is, for the March-April issue, the deadline is the end of June). In other words, although there are 60 recognized types, there will be only 26-30 CONs (puzzle constructions) in any given issue, and many of the same types (Cadenus, Route Transposition, NULL, etc.) appear consistently each time. Meaning that certain types almost never get used in the Cm, and I generally give those lower priority if they’re not used in the latest issue of the Cm that I have in my hands.

The March-April, 2019 issue of the Cm had 102 CONs total (25 Aristocrats, 14 Patristocrats, 14 Xenos (ciphers in other languages), 26 English ciphers, 16 Cryptarithms, and 6 Analysts. As of the beginning of May, I had solved 73 of them, and was perfectly willing to submit my answers right then. I’d solved all but 5 ciphers (leaving a Bazeries, a Gromark, a Conjugated Matrix Bifid, a Quagmire III, and a 6×6 Bifid). As I ran through the newsletter one more time, I figured I’d at least see what the definitions of those 5 are, to get a feeling for how difficult it would be to attack them at that point. At the same time, I’d found an article on solving 5×5 Bifids in the ACA archives that I’m wading through, and it seemed interesting enough to justify writing up an encrypter/decrypter tool in VBScript. That only took a couple hours, and then I bought a used video game (Bravely Second), which I proceeded to play nonstop for 3 weeks.

When I reached a breaking point in the game, I came back to Bifids. There are several different variants (5×5, 6×6, Twin, Conjugated Matrix), making them almost as versatile as Vigenere. The simplest ones are 5×5 and 6×6 (6×6 uses the same rules, just a slightly longer alphabet).

5×5 Bifid is a combination of substitution and transposition, based on a 5×5 key square (which uses a 25-letter alphabet, where J=I). You start by picking a keyword or phrase, removing redundant letters, and appending the remaining letters to the right of the key. So, if the key is “teacher”, the alphabet is:

teachrbdfgiklmnopqsuvwxyz

Next, the keyed alphabet is written into the square in any way you like following a legal route transposition (rows, alternating rows, columns, diagonals, or spirals). Using columns:

.|12345
-------
1|triov
2|ebkpw
3|adlqx
4|cfmsy
5|hgnuz

The rows and columns are numbered, as used for a Checkerboard cipher. Then, pick a period for our plaintext message. Usually, this is an odd number between 5 and 11, and is used for the encipherment step. Say the period is 5, and the plaintext is “among my many accomplishments”:

among myman yacco mplis hment s

Now, take the row and column numbers representing each plaintext letter and write them vertically under each letter, in row-column order.

among myman yacco mplis hment s
34155 44435 43441 42314 54251 4
12432 35313 51114 34334 13131 4

Lastly, read the cipher text off in row-pairs and get the corresponding letters from the square, wrapping at the right end of the top row of the period block to the lower left row. Take the text off in period-length groups (for period 5, make the groupings 5-wide).

34 = Q, 15 = V, 51 = H, 24 = P, 32 = D


QVHPD SMNNI MSVTO FAMMQ UWTAA S

As mentioned above, the ACA generally uses cipher text grouping widths the same as the period. This just makes it a little easier to solve the CON, but not that much. If the CON is long enough, there are tests that can be used for determining the period, they’re just a bit fiddly. The ACA also has a practice of using cribs that can be placed in the CON through the use of “naturals”, which I’ll get to in a second. It’s just a courtesy to the people trying to solve these crypts (fun is good, frustration is not so much).

Decryption is just the reverse process. Write out the key square and the cipher text in period widths. Under the cipher text, write the letter positions from the square in 2-letter rows, wrapping at the end of the period block, and take the numbers in vertical pairs to look up the plaintext from the table.

Solving a Bifid can involve a bit of logic, using what the ACA calls “equations.” These are pretty simple, but it requires a little explanation first.

Using the above crypt, but not knowing the key square, write the letters out for one block:

QVHPD

If we had the key square, we’d get the row and column numbers for the letter “Q” and write that underneath the text in a row pair, in the form of row then column number. Instead, let’s use Qr and Qc.

Q. V. H. P. D
Qr Qc

And let’s do the same thing for the remaining letters.

Q. V. H. P. D
Qr Qc Vr Vc Hr
Hc Pr Pc Dr Dc

and then do this for the rest of the message.

QVHPD SMNNI MSVTO FAMMQ UWTAA S


Q. V. H. P. D. .. S. M. N. N. I. .. M. S. V. T. O.
Qr Qc Vr Vc Hr .. Sr Sc Mr Mc Nr .. Mr Mc Sr Sc Vr
Hc Pr Pc Dr Dc .. Nc Nr Nc Ir Ic .. Vc Tr Tc Or Oc


F. A. M. M. Q. .. U. W. T. A. A. .. S.
Fr Fc Ar Ac Mr .. Ur Uc Wr Wc Tr .. Sr
Mc Mr Mc Qr Qc .. Tc Ar Ac Ar Ac .. Sc

Notice that in the last column, for S, we get Sr and Sc. It looks a bit contrived, but Sr-Sc is by definition the plaintext letter “S”, and this is what’s called a “natural.”

If you have a regular ACA-approved CON and a crib, there should be 2-3 naturally occurring naturals, one of which should have a letter that matches the crib. Generally, the crib is written in period-width groupings as well, just to make placement a little easier. You might see something like:

QVHPD SMNNI MSVTO FAMMQ UWTAA S
..... ..... .acco mplis h.... .

to further help in crib placement if there are no corresponding naturals.

With this example, write out the letters with the “r” and “c” notations, just for the part that includes the crib.

M. S. V. T. O. .. F. A. M. M. Q. .. U.
Mr Mc Sr Sc Vr .. Fr Fc Ar Ac Mr .. Ur
Vc Tr Tc Or Oc .. Mc Mr Mc Qr Qc .. Tc
.. a. c. c. o. .. m. p. l. i. s. .. h.

Now, let’s remove the top cipher text line and move the crib to its place.

.. a. c. c. o. .. m. p. l. i. s. .. h.
Mr Mc Sr Sc Vr .. Fr Fc Ar Ac Mr .. Ur
Vc Tr Tc Or Oc .. Mc Mr Mc Qr Qc .. Tc

Remembering that the plaintext is written in vertical pairs:

.. a. c. c. o
.. ar cr cr or
.. ac cc cc oc

What the above crib placement is telling us is that Mc = Ar. Or, that the column number that identifies cipher letter “M”, is also the row number identifying the plaintext letter “A”.

.|12345
-------
1|
2|
3|
4|
5|

What we’re doing here is rebuilding the key square through the relative positions of the cipher letters and their corresponding plaintext crib equivalents. We have to go through the process several times to build up the full set of equations, but when we’re done, we should have something like:

.. a. c. c. o. .. m. p. l. i. s. .. h.
Mr Mc Sr Sc Vr .. Fr Fc Ar Ac Mr .. Ur
Vc Tr Tc Or Oc .. Mc Mr Mc Qr Qc .. Tc


1) Ar = Mc = Lr = Lc
2) Ac = Tr = Ir
3) Cr = Sr = Sc = Mr = Fr = Pc = Qc
4) Cc = Tc = Or = Hc = Vr
5) Pr = Fc
6) Ic = Qr
7) Hr = Ur

A couple comments here. Notice that in the “.acco” block, under the letter “o”, plaintext “Oc” corresponds to cipher text “Oc.” This happens sometimes, and is like saying “1=1”. It’s not useful and is not included in the equations.

Second, looking at the first and third lines of the equations, we have Lr = Lc and Sr = Sc.
What this is telling us is that “S” and “L” both lie on the main diagonal in the key square. This is a good thing to know.

Some of the equations only have 1 letter each with “r” or “c” designators (such as, Ic = Qr). These we can safely ignore for the moment. All they’re telling us is that those letters are reflected along the diagonal from each other.

However, we can group the other letters with the same designators as follows:

Ar = Lr
Tr = Ir
Cr = Sr = Mr = Fr
Or = Vr
Hr = Ur


Lc = Mc
Pc = Qc = Sc
Cc = Hc = Tc

And, what this is telling us is that these groups of letters are all on the same row, or column. If we were to write them in a preliminary table format, we could have something like:

. 1 2 3 4 5
.-----------
1| S M . C . | CSMF
2| . L . . . | AL
3| . . . T . | TI
4| . . . . . | OV
5| . . . H . | HU
. -----------
.. S L . C
.. P M . H
.. Q . . T

Any places where the rows and columns have shared letters, we can write in that letter at the intersection. It’s important to only put letters on the diagonal when their row number equals their column number (Sr = Sc, Lr = Lc). Otherwise, move the equations to different rows or columns to make things work out right.

Once we’ve gotten this far, we can try to figure out the placement of the key alphabet (was it written in rows, columns, diagonals or spirals?) The only suggestive patterning is in column 1 (PQS), which could mean columns, alternating columns or a spiral, assuming those letters are not part of the key. Otherwise, use the table we’ve got to try obtaining as much plain text as we can get (using the faked numbers for right now).

Q. V. H. P. D. .. S. M. N. N. I. .. M. S. V. T. O.
Qr 1. 4. Vc 5. .. 1. 1. 1. 2. Nr .. 1. 2. 1. 1. 4.
4. Pr 1. Dr Dc .. Nc Nr Nc 3. Ic .. Vc 3. 4. 4. Oc
-- -- -- -- -- .. -- -- -- -- -- .. -- -- C. C. --


F. A. M. M. Q. .. U. W. T. A. A. .. S.
1. Fc 2. Ac 1. .. 5. Uc Wr Wc 3. .. 1.
2. 1. 2. Qr 1. .. 4. 2. Ac 2. Ac .. 1.
M. -- L. -- S. .. H. -- -- -- -- .. S.

We’re only getting part of our plaintext back out: “?cc?m?l?sh”.

Now, we know that the fourth letter is supposed to be “O”, but right now the coding is just 4-Oc. It is entirely possible that “O” is in the same column as “L” and “M”. We may want to experiment with that later. “Fc-1” = “P”, and from the equations we know that Fc = Pr. No new information here. All that’s really useful and new is that 23 = A. We can at least add that to the table.

. 1 2 3 4 5
.-----------
1| S M . C . | CSMF
2| . L A . . | AL
3| . . . T . | TI
4| . . . . . | OV
5| . . . H . | HU
. -----------
.. S L A C
.. P M . H
.. Q . . T

At this point, I could argue that this is as far as we can go, with such a short plaintext, and so many blanks showing up in the crib placement. But, there are a few more observations worth mentioning. If the key alphabet was indeed written in columns, then by reordering “SPQ” to “PQS” and “ML” to “LM” in the table vertically, we’re confronted with “CHT” not making any sense, unless it’s part of the key. If it is part of the key, then “CHT” should be in column 1, which changes the ordering of the associated letters in the other rows. Then, if we assume that “SPQ” and “LM” are not in the key, they need to change columns too. But, where to? If we write in an unkeyed alphabet in columns, we get:

.|12345
-------
1|aflqv
2|bgmrw
3|chnsx
4|dioty
5|ekpuz

This implies that if the alphabet is not displaced too badly by whatever was used by the keyword or phrase, “LM” should be roughly around column 3, and “PQS” should be in column 4. More importantly, whatever row we put “H” on will force “U” to be on the same row. That will help us place “VWXYZ” in column 5. Let’s try that.

1) Ar = Mc = Lr = Lc
2) Ac = Tr = Ir
3) Cr = Sr = Sc = Mr = Fr = Pc = Qc
4) Cc = Tc = Or = Hc = Vr
5) Pr = Fc
6) Ic = Qr
7) Hr = Ur


. 1 2 3 4 5
.-----------
1| . . . . V | OV
2| . . . . W |
3| . . L . X | AL
4| C . M S Y | CFMS
5| . . . . Z |
. -----------
.. C . L P V
.. H . M Q W
.. T . . S X
.. . . . . Y
.. . . . . Z

Tc = Vr = 1 forces “V” to the top row, giving a strong indication that column 5 is “VWXYZ”. If “T” is in the key and “U” isn’t, then “U” should follow “S” in column 4, placing “H” at 15. We can also fill in “F” at 24 while we’re at it. Then, there’s the string “MNO”. If “O” is not in the key, it has to be in either column 3 or 4. Since we already know that it’s on row 1, if it’s not in the key it has to be at 41, and “N” has to be at 53. With the string “FGHIKL”, “H” is in the key, “J” isn’t used in this alphabet, and we already have “F” and “L” placed. fill those letters in now.

. 1 2 3 4 5
.-----------
1| . . I O V | IOV
2| . . K . W | KW
3| . . L . X | ALX
4| C F M S Y | CFMSY
5| H G N U Z | HGNUZ
. -----------
.. C F L P V
.. H G M Q W
.. T . N S X
.. . . I O Y
.. . . K . Z

Ok, what we really needed to know was where “I” goes. With Ir = 1, and Ir = Tr = Ac, we get:

. 1 2 3 4 5
.-----------
1| T . I O V | IOTV
2| . . K . W | KW
3| A . L . X | ALX
4| C F M S Y | CFMSY
5| H G N U Z | HGNUZ
. -----------
.. C F L P V
.. H G M Q W
.. T . N S X
.. A . I O Y
.. . . K . Z

The missing letters are B, D, E, P, Q and R. Anagramming those letters with “TACH” is going to give us “TEACHER”, and the remaining letters easily fall into place, giving us the expected key square we really did start with. If there was any doubt about this, we’d just use this table to decrypt the cipher text, and any mistakes would show up as unreadable plaintext.

This is not intended as a real world application of the 5×5 Bifid solving process, but I think it demonstrates the concepts.

6×6 Bifid
The 6×6 alphabet is “A1B2C3D4E5F6G7H8I9J0KLMNOPQRSTUVWXYZ”.
Although the additional digits might give the impression that 6×6 is harder to solve than 5×5, the fact is that the associated digits will ALWAYS follow the letters A-J. This will aid in determining how the key alphabet was written into the square, and also in recreating the square during the solving stage. As an example, if the key is still “teacher” (TE5A1C3H8R), and the alphabet is written in diagonals, we get:

T5CRFJ
E1849N
AHDIMS
327LQW
BGKPVY
60OUXZ

After this, all the rules for 5×5 Bifid apply to 6×6.

As hinted at the beginning, I was thinking that I’d be able to tackle the 6×6 before submitting my solutions to the Cm editor, and that it’d be a pretty easy process. The article I was using for learning the Bifid rules presented a fully solved 5×5 crypt, and I could go through each step one by one as I wrote my VBScript solver tool to make sure my code worked right. Because my target was the Mar.-Apr. 2019 issue 6×6 Bifid, I added switches for choosing table sizes right from the start. It took me a full evening to finish the solver and remove all the bugs for handling the 5×5 Bifid. At the end of the night, I tried tackling the 6×6 crypt and just got garbage out. Ok, time to shelve the project and go to bed.

The next day, I had a couple free hours in the evening, and I tried again. The 6×6 garbage didn’t make any sense, so I went through the ACA archives for a comparable 6×6 crypt that had the solution printed in a later issue. I found one, but the solution only contained the first few words of the first sentence, and that wasn’t enough to tell me what was wrong with my script. I switched to hand-solving the test crypt, and comparing the intermediary numbers with what my script was producing, and eventually I realized that in one specific line, I’d hardcoded the table width to 5×5. Sigh. I fixed that, and things went a lot smoother. Until I hit a second bug that turned out to have been a stupid mistake on my part. After fixing that one, I was able to fully solve the test 6×6.

A few nights later, I came back to the project, and returned to that MA2019 6×6 Bifid. Because I had fewer clues to work with on a “live” crypt, and a longer alphabet than for a 5×5, I’d gotten the equations to come out right but there wasn’t enough information for completely filling in the key square. Up to this point, the Bifids I’d used for testing simply had the keyed alphabet written in rows. What I was seeing for the MA2019 crypt was more like “STUE5” in a row. Having “S” and “T” together in a row kind of ruled out “in by columns” and “in by diagonals”, unless they were part of the key. In by rows was a possibility, except that I had the equations for both “Er” and “Ec”, and when I tried placing “E” and “5”, it would shift the entire group of letters to different rows. This implied that the author had used “in by spiral”, but I was hanging up on the idea that the entire string was either “E5STUW” or “E5STUY”, and that was making it really hard to figure out which corner to start writing in the alphabet from. It was getting really late, and I was feeling like I was doing something really wrong again. I posted a plea for help on the ACA Facebook page and went to sleep. The next day, 2 people had “liked” my request, but no one had trying helping me. I had to go to work, but when I got home that evening, one of the guys who’d helped me out before had messaged me with 3 hints. The first one (“the alphabet is in by spirals”) just reassured me that I was on the right track after all. The second (“the keyword is very long and starts with ‘QU'”) was even more information than I actually needed. If the string on the line I was focusing on was “e5qstu”, then OF COURSE it started with “quest”. I didn’t even bother trying to decipher the third hint (which had been Caesar-shifted). I started filling in the key square, and a few minutes later, I had the plaintext out. (The keyword, including the 6×6 digits after the letters A-J, was “QUE5STI9ONA1B2LY”.)

Looking back at it, after all the bugs had been fixed, I’d had all the pieces to the puzzle right in front of me. I just didn’t have enough experience with the different ways the key alphabet can be written into a key square to recognize a spiral when I saw one. Or to realize that “estu” fits a very common word that I should have tried testing automatically (“quest”). Chalk this one up to experience. After all the smoke had cleared, I added this 6×6 Bifid solution to the rest of the crypts I’d solved for the issue, bringing my totals to 74, and submitted the list the next day. Yay me.

Summary:
1) Bifid is a combination of substitution and transposition.
2) It consists of a key square with the alphabet written in using any legal route transposition cipher pattern (rows, columns, diagonals, spirals). For a 5×5 square, J = I. For 6×6, use “A1B2C3D4E5F6G7H8I9J0KLMNOPQRSTUVWXYZ”.
3) Once the square is ready, pick a period, and group the plaintext in period-width blocks.
4) Write the row and column numbers for each plaintext letter vertically in row then column order.
5) Pull the numbers off in row pairs, and encipher them using the table, in row-column order.
6) For odd-length periods, wrap at the end of the top row of the period block.
7) Write the cipher text either in groups of 5 (traditional), or in period-length groups (ACA standard practice).
8) Deciphering works in reverse.
9) For solving Bifid, attempt to place the crib, aligning it with naturals if possible (naturals are plaintext letters that are formed when the row and column indicators of a letter occur in the same column, in r-c order (i.e. – Dr and Dc = D).
10) Once the crib is placed, write out the cipher text letters in Xr-Xc order in rows, and use the Cr = Pr / Cc = Pc associations to create equations that can be used to recreate the key square.
11) Switch between attacking the key square, and attacking the plain text to figure out more of the alphabet. Use known properties of the English alphabet to try to determine how the key alphabet was written into the square.
12) Having a script for automating the process for assigning numbers to the equations really does help a lot.
13) Overall, the simple Bifid is a challenging, but fun cipher type. I can’t vouch for conjugated matrix, though…

Wiggles, part 59


Just a little ongoing story to give you something to play with until the next blog post.

RYJX Z DAYNIT QZL HRYT WX ZK A EZK LRAYH ZJJ IQAK IQAYPAYH, ZYL IQAYHK QZL HRIITY BNATI NMKIZAVK. KIVZYHT. IQT EZX “DZDZ” QZL ZOITL, A PAYL RC CTJI JAPT KQT EZK MJZYYAYH KRDTIQAYH. KQT’L WTTY ZYHVX EAIQ IQT WRX CRV LAKRWTXAYH QTV RVLTVK, WNI QTV IRYT OQZYHTL EQTY QT DTYIARYTL “Z VZI.” AYAIAZJJX, A’L IQRNHQI QT EZK SNKI IVXAYH IR DZPT TUONKTK CRV HRAYH WTQAYL QTV WZOP. WNI, QT’L KZAL KRDTIQAYH IR QAK KAKITV, ERYLTVAYH ZWRNI EQZI EZK IZPAYH “QAD” KR JRYH. DZXWT IQTVT EZK KRDTRYT TJKT AY IQT INYYTJK IQT WRX EZK EZAIAYH CRV, RV DZXWT QT’L IQRNHQI A’L IVX CRJJREAYH QAD QTVT. AY EQAOQ OZKT DZXWT A ORNJL SNKI HR NMKIZAVK ZYL WJNCC DX EZX IQVRNHQ IR IQT KIVTTI. WNI, AC “QTZVAYH Z VZI” EZK ORLT CRV “ET QZFT AYIVNLTVK,” IQTY DZDZ’K VTZOIARY ERNJL WT DRVT EZVX RV QRKIAJT IQZY KNVMVAKTL. YRI HRRL.

Thinking About Encryption, Part 64


Revisiting AMSCO

AMSCO is a variation on Incomplete Columnar Transposition, where the text is written in alternating single and pair blocks, and taken off in block columns. The columns are rearranged based on some numerical key. Say we have a key of 31452, and the text “in the morning we picked flowers.”

.3 .1 .4 .5 .2
.i nt .h em .o
rn .i ng .w ep
.i ck .e df .l
ow .e rs


ntick eoepl irnio whnge rsemw df

To solve AMSCO, it helps to do a column and row count. Note that the creator can choose to start with a pair, rather than a single, on the first row.

1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 . . (5)
-------------
6 6 6 5 4 (27)

I was reading the Facebook group for the ACA, and several people had written that they found AMSCO difficult to solve, both in software and pencil on paper. I got to thinking about this, and the following is what I came up with.

If we have an odd-numbered key width and a crib, we’ll get two possible conditions. First, the crib will fit exactly within the column block, and the column lengths will be as they’re given in the above counts (6,6,6,5,4). Second, the crib wraps around to the next row down, and the effective distances between the crib segments for each column will be +1 for the last column (6,6,6,5,5).

.1 .2 .3 .4 .5
.x xx .x xx .x
xx .x SO .L UT
.I ON .x xx .x
--------------
.4 .5 .4 .5 .4


xxxIx xxONx SOxxx LxxxU Tx

If we remove the spaces and divide the line into rows of 4, we get:

xxxI (1)
xxxO (2)
NxSO (3)
xxxL (4)
xxxU (5)
Tx

See how the crib largely drops into one column? The trick is then to rearrange the columns so that we can pull the plaintext back out, even if we don’t know whether the crypt started with a single or double letter on the first row. The first step is to see how the crib was divided. We can get the following 3 arrangements:

1) S OL U TI O N?
2) ?S O LU T IO N
3) SO L UT I ON

The simplest way is to pick one 2-letter pair from each arrangement, and see if it exists in the ciphertext. Since my example lacks any real plaintext, it’s obvious that the crib is in arrangement 3, using OL, LU and SO for the text searches.

xxxIx xxONx SOxxx LxxxU Tx

Therefore, we will be using the 2-1-2-1-2 pattern with the column arrangement:

1 2 1 2 1
2 1 2 1 2
1 2 1 2 1
2 1 2 1 2

Take the first letter to the left of “SO”, and the next one to the right:

.x
SO
.X

Take the first 2 letters to the left of “L”, and the next 2 to the right, and repeat

xx
.L
xx


.x
UT
.x


xx
.I
xx


.x
ON
.x

Put them in order:

.x xx .x xx .x
SO .L UT .I ON
.x xx .x xx .x

If we have real plaintext, what we’re going to find is that the message is starting in the middle of the sentence, and that the crib wraps across rows. But, this illustrates my point, and the clean-up details are pretty easy to figure out.

The real secret lies in placing the crib within a real message.

ELASW NDYFO MTHBE AHENE LCOFS STILL UURTA NEPTH EYOOI NPHII TOEFW FISHE YVE

Start with a character count (63), and build up the two column patterns, one starting with a single letter, and the other with the 2-letter pair.

1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2
-------------
1 1 1 1 1
3 4 2 2 2 (63)


2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1 2 1 2 (8)
1 2 1 2 1 (7)
2 1
-------------
1 1 1 1 1
4 3 2 2 2 (63)

The crib is “you find.” This can be

y-ou-f-in-d
?y-o-uf-i-nd
yo-u-fi-n-d?


ELASWNDYFOMTHBEAHENELCOFSSTILLUURTANEPTHEYOOINPHIITOEFWFISHEYVE

It’s easy to do a text search on “yo”, “ou” and “uf”. Of the three, only “yo” appears in the string (in group 9).
There are five crib segments, meaning that if the key width is 5, there’s a very good chance of wrapping, and the spacing between segments from column 5 to 1 is going to be 13. Let’s pick a row length of 13, and break the cipher line into 5 rows of 13 (the last row will be a bit short.

ELASWNDYFOMTH
BEAHENELCOFSS
TILLUURTANEPT
HEYOOINPHIITO
EFWFISHEYVE

Here comes the magic. If all the crypt columns were exactly 13 characters long, the crib segments would align exactly with each other. But, the distance from “yo” to “u” could be 12, 13 or 14 characters off, if they were in adjacent rows. If they’re two rows apart, then the spacing could be 24, 25, 26, or 27. Three rows apart: 37, 38, 39, or 40. Four rows apart: 50, 51 or 52. This gives us a “golden zone” (the bold area in the figure below) for searching for the other parts of the crib relative to the part we have. This is especially useful for confirming that the key is width 5. One consideration, though, is that the zone needs to be one character wider to the right, because the next segment could be a 2-letter pair.

ELASWNDYFOMTH row 1
BEAHENELCOFSS row 2
TILLUURTANEPT row 3
HEYOOINPHIITO row 4
EFWFISHEYVE ..row 5

“yo” is in row 4. “u” is in row 3. “fi” is in row 5. “d” is in row 1. “n” is in rows 1 and 2, but “d” eliminates row 1 and we settle for row 2.

Now, line up the crib segments, using what we know about the column structures, including some of the text plus/minus the segment location.

.4 .3 .5 .2 .1
.E LL .W HE .N
YO .U FI .N DY (you find)
.O UR .S EL .F
IN .T HE .C OM

Yes, proof we have the right key width (if we didn’t, we’d just go to 7 columns and try again). At the moment, we don’t know where the wrap occurs, so we can’t say that we have the correct key, yet. But, we can continue extending the columns up and down for each of the rows, until we either run out of characters at the front or back of the line, or we start producing gibberish.

.4 .3 .5 .2 .1
NE .S IT .H EL
.P ST .O BE .A
TH .I EF .A SW
.E LL .W HE .N
YO .U FI .N DY
.O UR .S EL .F
IN .T HE .C OM
.P AN .Y OF .T
HI .E VE .S HB
.I PT


NES IT HELPS TO BE A THIEF AS WELL WHEN YOU FIND YOURSELF IN THE COMPANY OF THIEVES HBIPT.

Yes, we’re getting gibberish to the left of “It helps”, and to the right of “thieves.” This indicates that the text starts with column 5, making the key 52143.

.5 .2 .1 .4 .3
it .h el .p st
.o be .a th .i
ef .a sw .e ll
.w he .n yo .u
fi .n dy .o ur
.s el .f in .t
he .c om .p an
.y of .t hi .e
ve .s

Note that this crypt started with the 2-letter pair on row 1, which we recovered without even thinking about it. I think that writing a program to automate all this work would be very simple. But, since I already have a bruteforce solver, and I mainly work in VBScript, I’m not going to bother writing another solver myself.

Fortunately, the ACA members generally use odd-length keys. It is possible to use even lengths, but crib placement becomes extremely ugly because, with possible row wrapping, nearly every conceivable segmentation is possible.

1 2 1 2 1 2
2 1 2 1 2 1
1 2 1 2 1 2
2 1 2 1 2 1
1 2 1 2 1 2
2 1 2 1 2 1
...

“youfind” could be “yo-u-fi-n-d?”, “y-ou-f-in-d”, “?y-o-uf-i-nd”, “yo-uf-i-nd”, “?y-ou-f-in-d”, etc. We just have to search the cipher string for 2-letter pairs until we start finding ones that can help us narrow things down.

Anyway, I don’t consider this approach to be all that hard to implement. If you preload the column tables into Excel for arbitrary string lengths, for keys 5-, 7-, 9- and 11-wide, and print them out when you need them, the process will be that much easier to finish.

Wiggles, part 58


Just a little ongoing story to give you something to play with until the next blog post.

V XQCNE YMB HQVRH CPJYSVMJ SRE KNCZZVRH AB FSB YQ SR ILVY, YUIR ASTI S ASE ESJU ZQM YUI JYMIIY. QM, V XQCNE HQ KSXT YQ YUI YCRRIN SRE JII VZ YUI QYUIM IRE QPIRIE CP JQAIFUIMI INJI. YUSY PQJJVKVNVYB JIIAIE YQ ASTI S NQY QZ JIRJI. VZ YUIMI FIMI ZVRVJUIE YMVXT EQQMJ UIMI SRE SY MVXTV’J UQCJI, YUIMI’E USWI YQ KI SY NISJY QRI AQMI JVEI YCRRIN YQ JQAIYUVRH INJI SJ FINN. QM, V’E HIY NCXTB SRE ZSNN VRYQ YUI JIFIM NVRI, SRE DCJY ZNQSY YQ S PMQXIJJVRH PNSRY EQFR KB YUI KSB. V FSJ MISNNB HIYYVRH RSCJIQCJ, SRE AB JUQCNEIM SXUIE AQMI YUSR VY IWIM USE KIZQMI. V RIIEIE JNIIP, IWIR YUQCHU VY JYVNN FSJR’Y YUSY NSYI.

Wiggles, part 57


Just a little ongoing story to give you something to play with until the next blog post. Sorry about missing the last update on Friday. I’ve been distracted. I’m posting this on Wednesday, and I’ll be back on track with the next update on schedule.

MGFBF RGYWNA OF RGWMMFBR YX MGF AYYBR, OWM WXNFRR MGF NKXANYBA CKR BFKNNL KEBKUA YE MBFRSKRRFBR, MGF KNKBP RLRMFPR RGYWNA OF AFKDMUTKMFA. PKLOF MGKM’R CGL “PKPK” KXA MGF MCY VUAR CFBF KONF MY IY OKDV KXA EYBMG. UE U’A BWX UXMY K SKDV YE RZWKMMFBR, MGFX KNN OFMR CFBF YEE. UE MGFL NUTFA UX KX KSKBMPFXM YX K GUIGFB ENYYB, MGFL’A OF WRUXI K RFSKBKMF RMKUBCFNN EYB IFMMUXI MY MGF RMBFFM, UXAFSFXAFXM YE MGF RGYSR. MGF EUNP SBYDFRRUXI RGYS CYWNAX’M GKTF K RGYCFB, RNFFSUXI KBFK YB VUMDGFX, RY PKPK KXA MGF VUAR CYWNAX’M OF MGFBF NFIUMUPKMFNL. UE MGFL CFBF RZWKMMFBR, KXA LFR, U’TF GWXI YWM KM K EFC RZWKMMFB DKPSR UX URYNKMFA SKBVR OFEYBF, MGFL DYWNA SYRRUONL OF DKPSFA BUIGM KM MGF MYS YE MGF RMKUBR. IBFKM.