Monthly Archives: June 2018

Computer cipher solving – Patterns

Using word patterns to aid in solving cryptograms and other ciphers is very common and doesn’t require computers. Pattern words appearing in ciphertext like EDQDQD or VXQGDH might or might not require a dictionary search, but a computer will soon find BANANA and ROCOCO are the only two common English words matching the first pattern of letters. However there are thousands of words that match the second word, which has no repeating letters. If they appear together as a phrase, though, it is possible to cross-correlate the two words, using identical ciphertext letters in the two words to reduce that second list. It turns out there are only sixteen two-word combos in my basic word list that match the phrase pattern and BANANA SUNDAE appears to be the only one that makes sense.

What about when word divisions are not known? The problem becomes much harder. I decided to try to use patterns in English to aid in solving ciphers where word spacing is unknown. First it is necessary to have a standard format for patterns. I use what I believe is the most common method, which is to assign A to the first letter in a text string and to any other identical letters in the string, then B, C, etc. Thus EDQDOD has the pattern ABCBDB. BANANA and ROCOCO both have that pattern, although I am working with strings, not words. I next chose a string length to use. I experimented and settled on eight letters. I call these 8-grams. Any shorter and there were too few unique common patterns, more and there were too many.  I then tabulated the frequency of different 8-gram patterns by removing spaces and punctuation from over a dozen books and speeches in English downloaded from Project Gutenberg. The resulting list of unique patterns observed resulted in 2981 entries. By far the most common was ABCDEFGH, i.e. strings with no repeated letters, which represented about 18% of the total. The next most common was ABCDEFGA, followed by the 8-grams with a single letter repeat separated by four or five letters, such as ABCDEFAG and ABCDEFGC all of which had a frequency of about 2%.

My first idea was to use these frequencies to aid in solving ciphers where there has been a simple substitution combined with a transposition of some kind. If one could decrypt the transposition using patterns, it would then be a simple matter to solve the resulting intermediate ciphertext as a simple substitution cipher (in American Cryptogram Association or ACA terms, a Patristocrat). The only ACA cipher that uses a combination of simple substitution and transposition is the Bazeries, but it could be done with other types such as combining a columnar or route cipher with simple substitution. To accomplish this I had to devise a measure of how closely normal English adhered to these pattern frequencies and do the same for scrambled English text. I experimented with this and settled on using the 50 most frequent patterns as the basis. I assigned a score to a string of text as follows: for each ciphertext 8-gram in the text, find its pattern, search the list of fifty most common patterns and if a match is found, add the number of the match to a running total. Thus if the pattern is the third most frequent one, add 3. If no match is found in the 50, add the number 50 to the total. Divide the sum by the number of 8-grams in the text (i.e. the length of the text minus seven). The resulting number is the score for that text. For convenience I’ll call that the pat8 score. I found that normal English text averages about 25. When I tested 30 plaintext segments derived mostly from BION’s list of 10,000 book excerpts I found the median to be 25.25 and the range was from 19.95 to 37.52. The score did not correlate closely with the text length, but it did with index of coincidence (IC). Generally the higher the IC, the higher the Pat8 score. The 37.52 score plaintext had an IC over 0.09 (average for English is 0.067).

The next step was to scramble these texts and see if the pat8 score differed. I used random keywords to encipher these 30 texts using columnar transposition. The resulting pat8 scores had a median of 32.69, which is 28% higher than plaintext. This seemed promising for my purposes. There was more variation in the plaintext (standard deviation of 4.04) than in the scrambled text (SD of 2.82). Of the 30 tests only once did the ciphertext score lower than the original text and in one case they scored the same. In all the others, the plaintext had a lower score than the ciphertext. I also tried scrambling the plaintexts using the myszkowski cipher but there was no apparent difference between the columnar and the myszkowski. The correlation between IC and pat8 held for scrambled text as well.

Using this test I tried to solve some columnar ciphers, scoring the trial solutions only with the pat8 score. This was a total failure. Although the transposed text scores were mostly quite a bit higher than plaintext, there were always some keys that produced ciphertext with a lower pat8 score than the plaintext. I had the same result with myszkowski ciphers. I abandoned the idea of using the test as a solving aid. I invite others to try experimenting with this methodology to see if a useful solving aid based on patterns can be devised. If you would like my list of patterns and their frequencies, contact me in the comments or using the contact form link in the top menu.

Despite this setback, I then hoped that the test may be useful in diagnosing an unknown cipher type. I will discuss my experiments and results in my next post.

The Widow’s House by Carol Goodman

The Widow's HouseThe Widow’s House by Carol Goodman
My rating: 4 of 5 stars

Clare and Jess are struggling writers. They choose to move from their trendy digs in New York to a small town in upstate New York where they first met at college, an elite private school. It’s also Clare’s hometown. Jess has taken a job as caretaker of the house of their former English professor, “Monty” Montague. They both begin writing again, but strange things begin to happen. A freak storm floods the caretaker’s cottage and forces them to move into Monty’s big house, the widow’s house of the title. Clare begins to see ghosts. She rationalizes these away as figments of her imagination or flukes of vision induced by fog or rain. The house has a history of murder and lunacy. A baby crying in the dumbwaiter. The plot line turns spookier.

I liked the book, but I think the fourth star is mostly a guilt star. By that I mean I feel like should have enjoyed the book more than I did. The author writes with the intelligence and even elegance you might expect from a university writing teacher, but with an “insider” quality to it. One almost feels like without being part of the effete intellectual New York scene one isn’t entitled to be reading the book. Stylistically the book is on a high tone, but there always seemed to be a falsity about it. For one thing, plausibility leaves the plot line early on and stays away to the end. More than that, the author seems to be play-acting at being scary like a grown-up dressed up as a cute witch to trick-or-treat with her kids. She just doesn’t have the authenticity of a Stephen King. Reading this, I’m reminded of Sedgwick, the rich kid in the Monty comic strip whose butler Jarvis helps him emulate a normal kid. Another drawback is that it’s a writer writing about writing. This is mainly interesting to writers. The public is more interested in product than process. I just tried to watch the boring documentary Score, in which a number of movie composers talk about the creative process. Their music is great; a bunch of talking heads bragging, not so much. Despite these criticisms, I was drawn into the plot of this book and found the tension rise enough to make me engrossed up to the end. It’s no Rebecca, but it will serve as a summer read.

View all my reviews

Our Ignorant Newsies redux

Two recent idiocies I heard in the last two days:

Elizabeth Cook of KPIX, talking about a car in Lafayette crashing into a house. “Firefighters extradited a 72-year-old woman from the house.” She was a fugitive? What was she wanted for?

On the radio: demonstrators somewhere were “mounting an armed resurrection.” So I guess Jesus has given up the peaceful approach.

I must hear a dozen of these a day, and these are from professional writers and talkers. Just imagine what it’s like listening to the average person all day.

The Truth About Animals by Lucy Cooke

The Truth About Animals: Stoned Sloths, Lovelorn Hippos, and Other Tales from the Wild Side of WildlifeThe Truth About Animals: Stoned Sloths, Lovelorn Hippos, and Other Tales from the Wild Side of Wildlife by Lucy Cooke
My rating: 5 of 5 stars

The author is a zoologist and naturalist, but perhaps is better known for her television work on comedy and nature shows. That might explain why this book, which I had thought was a scientific treatment of unusual or little-known animal facts turned out to be enormously amusing. Certainly her frequent treatment of the sex lives of the featured animals added some spice, but her sardonic wit was evident throughout. I suspect she could make the history of linoleum hilarious. Don’t mistake this for a dismissal of the book as frivolous, for it is very well documented and scientifically sound, at least so far as I can determine. I learned a lot and laughed a lot. It’s difficult to give much higher praise.

I cannot resist one smidgen of constructive criticism (a phrase that strikes fear or loathing into the heart of any author): she spends too much time debunking myths that were debunked decades ago, or even centuries ago. In other words, she tells us some of the ridiculous things people used to write or believe about various animals and then explains when and by whom those ideas were corrected. That really isn’t anything about the animals but merely illustrative of how bad “science” used to be. That’s a tad out of the description of the title, but the author was able to find a lot of humor there as well.

View all my reviews

The Woman Who Smashed Codes by Jason Fagone

The Woman Who Smashed Codes: A True Story of Love, Spies, and the Unlikely Heroine who Outwitted America's EnemiesThe Woman Who Smashed Codes: A True Story of Love, Spies, and the Unlikely Heroine who Outwitted America’s Enemies by Jason Fagone
My rating: 4 of 5 stars

This fascinating biography of one of America’s great woman sheds more light on a history little known to most Americans. Elizebeth Friedman was a cryptanalyst who helped the government chase smugglers during Prohibition and Nazis during WWII. The author has obviously dug deeply into archives to piece together her life. The author creditably relates the subject’s experience with discrimination in employment, unequal pay, and sexual harassment. Some things never change – or at least change all too slowly.

The book is not without its problems, though. For one thing, much of it is not new. It borrows heavily from The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet by David Kahn, among other sources. The author, who admits he knows little about cryptography, gets many things flat out wrong. Some of his work is just sloppy. For example, on P. 127 he copies the sentence from Elizebeth’s note to her husband wrong, omitting the final I in “mari.” Even my high school French taught me that husband is mari, not mar (not to mention you can see the I in the note). He also calls that note a Railfence cipher, but it is really just plaintext written in an alternating columnar route. I won’t bother to explain a Railfence; look it up in Wikipedia if you want to know. He repeats both of those errors later on, too. On p. 136 he writes the ciphertext word for “prospects” wrong, adding a letter. His cryptographic definitions at the beginning are misleading at best, just plain wrong in other spots. As a forty-year member of the American Cryptogram Association I am more sensitive to those issues than others, I’ll admit, but the serious crypto fan will have to grit his teeth in places.

Another problematic issue is the suggestion throughout the book, especially at the end, that E. Friedman never got her due, often overshadowed in government circles and even the press by her husband William. This is true to some extent, but is also misleading. First of all, William was, and is widely recognized as, the superior cryptographer of the two (Purple and SIGABA are each alone more significant than her entire body of work). Second, she often got more public notice than he did, especially when she was testifying against rumrunners and others. Reporters and the public alike were much entranced by the “attractive girl cryptographer.” She’s been the subject of much press in recent decades, too, including in Kahn’s seminal book, although much of it does not include her wartime feats which this author brings to light very well. Lastly, the very nature of cryptanalysis (the breaking of codes and ciphers) is a secret business and both Friedmans were often dismayed at any publicity about their craft. I think the author and women’s rights advocates are more upset than either Friedman ever was about her relative anonymity. The Friedmans were products of their time and she was very much one of the most liberated and professionally fulfilled women of her day.

View all my reviews