Social Cryptogram Solving


I have recently joined the American Cryptogram Association and have been busy trying to solve the items in the November/December issue of The Cryptogram magazine.   Since I am still quite new to the world of cryptography and cryptograms, I am still building up my solving skills.

While attempting to solve a Patristocrat cryptogram, I began to wonder what processes or thoughts do other people use to solve Patristocrats?

Originally, I planned on having each person give one step in solving the below cryptogram.  After seeing some of the comments that came in so far, I actually think it would be more beneficial to have as much detail from each person as possible.  This way you can see more detail into how each person solves the same puzzle.   So if you would like to, please tell me how you would go about solving this puzzle.  You don’t have to explain from start to finish.  Mainly the idea is how to get started.  Most of the time, if you can get a little bit in then the rest starts to fall into place.

Thank you in advance for those who choose to participate. See the comments for all the great feedback!

Patristocrat   K3.   Attitude.    [95/18]   (LYUWN)

O P Q E C T B B J X R V A C C B Q X V X Q H O A R
– – – – – – – – – – – – – – – – – – – – – – – – –
I X R O T V D P Q D C X W T X B D T R N T E O T R
– – – – – – – – – – – – – – – – – – – – – – – – –
D J P Q D P Q N N T R B D A H T Q R V R X R T D L
– – – – – – – – – – – – – – – – – – – – – – – – –
N T E O T R D P A J X E T Q O D D A X D
– – – – – – – – – – – – – – – – – – – –

ct: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
pt: – – – – – – – – – – – – – – – – – – – – – – – – – –

Advertisements

20 thoughts on “Social Cryptogram Solving”

  1. I use hillclimbing to solve Pats. You have to be a programmer to use this method, but from your name and this website I suspect you are. If you just want one step, here’s the first thing you need to do: accumulate frequency data on n-grams for the target language. Tetragrams are probably the handiest. SCBsolvr has such a data table if you don’t want to generate one yourself from raw text.

  2. I’ve often felt my pat skills are weak – I’ve spent so much time using pattern words to solve aristos that I am almost crippled, when I can’t use them.

    How to deal with a pat?

    First step is to look at the crib. “LYUWN” is “react” Caesar-shifted six places.

    It has no pattern, so it could fit in a lot of places. If the crib had been “happens”, for example, it would have fit in only two places. But “react” can fit in dozens.

    If there are only a few places where a crib might fit, I might try each of them and see how the rest of the cipher works. I’ve occasionally tried using statistical tests to determine which of the possible fits is most likely, but without computer support, it’s just too tedious.

    So absent a usable crib, I try to locate the vowels.

    Friedman’s “Military Cryptanalysis” describes what is probably the simplest method. The 18 most common digraphs make up 25% of normal English text. In nine of them, one the letters digraph is ‘E’: ED, EN, ER, ES, NE, RE, SE, TE, VE. The other nine are AN, IN, ON, ND, NT, OR, ST, TH, and TO.

    None of the 18 contains two vowels.

    So, from your text, pick out the nine most common letters, and the 18 most common digraphs.

    12 T
    11 D
    10 R
    9 X
    8 Q
    6 O
    5 A
    5 B
    5 P

    And:

    4 PQ
    4 TR
    3 DP
    3 NT
    3 OT
    3 XR
    2 BD
    2 DA
    2 EO
    2 JX
    2 QD
    2 RD
    2 RV
    2 TE
    2 TQ
    1 AC
    1 AH
    1 AJ

    In our case, we only have 15 digraphs that appear more than once, so we’ll limit ourselves to those.

    Of those 15 digraphs, which of the nine high-frequency letters appears most often?

    T = 14
    D = 11
    R = 11
    X = 5
    Q = 8
    O = 5
    A = 2
    B = 2
    P = 7

    So, “e” is most likely “T”.

    Next, the letters that most frequently appear with “T” in the high-frequency digrams are most likely the high-frequency consonants, “n”, “r”, “s”, and “t”.

    R = 4
    N = 3
    O = 3
    E = 2
    Q = 2

    Next, look at the letters in the 15 high-frequency digrams that never appear with a “T”.

    D = 11
    P = 7
    R = 7
    Q = 6
    X = 5
    B = 2
    A = 2
    E = 2
    O = 2
    J = 2
    X = 2
    V = 2

    So, what we have so far:

    “e” is most likely “T”
    “n”, “r”, “s” and “t” are most likely among “R”, “N”, “O”, “E”, and “Q”
    “a”, “i”, and “o” are most likely among “D”, “P”, “R”, “Q”, “X”

    Are these right, all the time? No. There are other methods for identifying vowels and consonants. Do a Google on “Lanaki’s Lessons” and you’ll find others, like the Consonant Line Method.

    What seems to work best is to use several of the techniques – what they agree upon is most usually right.

    You can validate your vowel assignment by placing a bar over each letter in the ciphertext that you think is likely a vowel. If your selection is correct, you should find a hard limit on the length of consonant clusters. In English words, a group of more than three consecutive consonants is rare. In a pat, you can sometimes see consonant clusters of four or five, when a word that ends with a cluster is followed by a word that starts a cluster. If your vowel assignments are right, you should see few clusters of length five, and none of length six or more.

    And when you’ve identified the vowels, try fitting the crib again, there should be far fewer possible locations,

    In our pat, the “e” is “T”, and the other high-frequency vowels (“a”, “i”, and “o”) are “A”, “Q”, and “X”. And possible locations for the crib “react”, in decreasing probability, are: “ETQOD”, “WTXBD”, “HTQRV”, and “VXQHO”.

  3. I hope I am not stating the obvious here, or repeating what other people have said: I see no comments (yet).

    But as a first step I would make a frequency count, i.e. how many times does the A occur, how many times does the B occur etc.
    And I would decode the LYUWN (by shifting the letters 6 positions) because I would need all the help I can get when doing this manually.

  4. I’ve written a hillclimber, with pluggable scoring routines, and when I’m stuck I’ll fire it off. But I do like to see what I can do by hand, or with computer-support, before I’ll resort to computer-heuristics.

    One thing I do is calculate chi^2 correlations for possible crib placements. The idea is that for each possible placement you multiply the frequency of the crib letter in normal English by the frequency of the matching letter in the ciphertext, and sum the products. The higher the number the better the match.

    In this pat, there are 33 possible crib locations, and the correct one has the second-highest score. (This I use a simple program to calculate,) Of these 33, there are eight that have the correct vowel assignments, and the correct one has the highest score. (This, I use the previous program and filter the results with grep.)

    With the crib in the correct place, and with the unassigned vowels (‘i’ and ‘o’) marked with ‘^’, we have:

    c _ a r _ e _ _ _ ^ _ _ ^ _ _ _ a ^ _ ^ a _ c ^ _ _ ^ _ c e _ t _ a t
    O P Q E C T B B J X R V A C C B Q X V X Q H O A R I X R O T V D P Q D

    _ ^ _ e ^ _ t e _ _ e r c e _ t _ _ a t _ a _ _ e _ _ t ^ _ e a _ _ _
    C X W T X B D T R N T E O T R D J P Q D P Q N N T R B D A H T Q R V R

    ^ _ e t _ _ e r c e _ t _ ^ _ ^ r e a c t t ^ ^ t
    X R T D L N T E O T R D P A J X E T Q O D D A X D

  5. I’d meant to add to the previous: at this point, some words should be jumping out at you. Particularly if you keep in mind that ‘A’ and ‘X’ are ‘i’ and ‘o’, or vice versa, and that ‘n’, ‘s’, ‘h’, and ‘d’ are the most frequent unassigned plaintext letters, and the most frequent ciphertext letters left unassigned are ‘R’, ‘B’, and ‘P’.

    Look at where ‘R’, ‘B’, and ‘P’ appear, and think of what the plaintext would look like, if any of them were ‘n’, ‘s’, ‘h’, or ‘d’. Do you see any likely words?

  6. I would start by looking for the frequency pattern of the plain tip. With H meaning high frequency and L meaning low frequency, REACT has the pattern HHHLH. I take the highest frequency cipher letter T and assume it to be plain e. Then I test every occurence of e with the pattern of the tip until I find a fit and substitute. If that fails, I work from the bottom – assume the least common cipher letter is the C in REACT and try for a fit. I have a computer program which makes substitutions and erasures very easy. This method works on most of the Pats with a reasonably long tip.

  7. I guess almost everything has been said by now.
    I can only add that there is a Suchotin algorithm
    that finds vowels. In this case it tells that
    T D X A Q are very likely vowels. While this is true
    for T X A Q, ciphertext D turns out not to be a vowel,
    but the consonant T (which can happen with this
    algorithm). I also agree with PERISTALSIS’ crib placement,
    done with the same method he used.

  8. As with Peristalsis, my pat skills are weak, generally never solving anything after P7. Tools such as the consonant-line and most-common-digraphs were more exercises in frustration than solution.

    I wrote a program that would take the crib and slide it through the crypt showing what the crypt looked like at each position. Again, this was fine for the lower-numbered guys.

    Recently, however, salvation rose above the horizon–Anchises’ website (can be found on the ACA website) contains a tutorial on programming in Python. Within that tutorial is a program that contains his CHURN algorithm (related to hill-climbing and simulated annealing) for solving crypts. I took that code, tweaked it a bit, and am now able to complete through P12.

    To paraphrase an old saying, all’s fair in love, war, and cryptanalysis.

  9. I usually try crib placement first. If there are only a few possibilities, I’ll try each and look at the results. Incorrect placements often result in very low-probability letter combinations elsewhere in the text.

    If there are more than a handful of possible crib placements, I’ll try several vowel-distinguishing methods – Friedman’s digraph method I described above, consonant line, Sukhotin’s, and a program that works through all possible assignments of the high-frequency vowels and for each calculates a score based on the sum of the squares of consonant cluster lengths (which I wrote following an email discussion with CryptoRat),

    Generally, what the multiple methods agree upon is right. So from them all, I’ll have a couple of possible vowel assignments. And for each, I’ll have a handful of crib placements. I’ll try the most likely crib placements for each likely vowel set, and look at completing likely digrams and trigrams. For the low pats, I’ll usually find the right place.

    For the high pats, I usually don’t. For those, I throw hillclimbers at it.

    I have collected several, but I usually use one of two. There’s one I wrote that uses log-quadgram scoring that runs pretty fast, and usually works. And one I got from an internet acquaintance that uses word scoring that is astoundingly slow but which works in cases in which simpler scoring methods don’t.

  10. I’m pleasantly surprised at how many people use computers to solve the patristocrats. As The Rat correctly surmised, I am a computer programmer by trade. I love messing with new programs and finding new ways to solve problems with computers. Do the majority of solvers use some form of computer assistance? At first I felt bad for using a word list look-up program that I wrote. Thank you for all your comments, these have been very enlightening. I look forward to reading other people’s methods as they come in.

  11. I am a computer-solver as well, and I expect that most of the top-solvers are. (However, it is amazing what some people can do armed with just pen, paper and a wealth of knowledge.)
    At first, I also felt bad about using some brute-force methods, but not any longer. That said, I limit myself to programs that I made myself (although often based on algorithms from others), and refrain from googling cribs, which will sometimes immediately give you the entire plaintext.
    But as indicated by ANAPEST, this is purely a self-imposed restriction.

  12. This thread has already engendered a discussion of the ethics of computer solving of ACA ciphers. I have an interactive solver in QBASIC, too, very similar to what BION and others now have on their websites, but I, too, use only programs I wrote myself, so I feel I solved the con. At some point it takes away the fun to just plug something into your program, walk away, and come back later for the solution. What’s the point? But the magazine always has ciphers that challenge me and don’t break with my programs so I have to solve at least partly by hand. My programming has greatly increased my skill at this because I have to really learn exactly how a cipher works when programming it. I look at the computer solving as training in cryptanalysis in general. And there is no type of ACA cipher I haven’t solved by hand.

  13. I’ve tried hard to stick to pencil and paper solutions. I try placing the crib but that only works for the first few. I don’t really like Pats as I find them to frustrating for such little gain.

    I spend most of my time in the Cipher Exchange. I like the challenge of trying something new and am trying to pencil and paper as many as I can. I will say, trying to get all JF done has worn me out. PNP is such a tedious way to do some things, but I refrain from whipping out the code editor as I want to understand the underlying process first. It is very rewarding to crack a new cipher type. When I used my computer for some, it just isn’t the same. I don’t think PNP only will last much longer as it takes more time than I have.

    I’ve tried some of the ‘hill climbing’ and such solutions but find they never work very well for the amount of effort they do, granted computer time is pretty cheap. I’ve recently been solving more ciphers based on finding the Key. Before I never did that but am surprised how fast it works. Being a computer programmer also by trade, I think I’d like to try key based solutions. All the programs I’ve seen seem to try to solve a completely random ptct mapping which is usually not a good approach to me, it seems like to much known information is being thrown away.

    I’m amazed that there are so many with perfect solutions for the whole year in all categories. I wonder how many are mostly PNP vs. computers.

    I like this discussion, it would be nice to have it in the multiply site for others to follow as well.

    1. fastercat,

      I hear you. I have a tendency to start with pen and paper hobbies (puzzles, sudoku, etc.) and then flip over to writing a computer program that can do it the same way that I would. I’m currently working on my won helper library that won’t solve it for me but will do tedious things if I get stuck (frequency counts, digraph counts, crib placement locations, word lookups, etc.). That way I’m still doing the pen and paper but I don’t get stuck as often and I still learn the techniques.

      As for Multiply, I’m just not a big fan of it. The interface is not intuitive at all. I wish there was an official ACA members area that we could all post to and interact more as a community. Multiply just doesn’t seem to offer the same feel as a normal community website. (Just my own opinion)

  14. My take is simple.

    For me to accept that I have conquered a specific cipher type, I need to be able to:

    1: Solve it by hand,
    2: Create computer programs that eliminate some of the tedium involved in solving it by hand, and
    3: Create a computer program that will solve it without any manual help.

    I want to be able to do all of these. Hence my claim, above, that I feel that I am weak with respect to Pats. I need more practice at picking out patterns by eye, without the crutch of word divisions. That I’ve written a hill-climber that works doesn’t mean that I no longer practice manual solves.

  15. Also, I have found that by writing an autosolver (hill-climbing, brute force, or any other type) I can often find how to construct a con to submit that will foil such programs. It is interesting to see how humans can spot plausible patterns that involve infrequent combinations of letters, and so on. I rarely do this, however, because they also make paper and pencil solving very difficult and do not produce enjoyable plaintext. I believe the solver should be rewarded with a text that is fun or interesting in some way. Just coming up with a jumble of obscure words in a grammatical mess isn’t really in the spirit of the ACA, I feel. So even when trying to construct a submission at the extreme difficulty level, I try to make it read like a normal sentence with good grammar and a clear meaning.

  16. I recently joined the ACA, though I’ve looked at its site
    occasionally for going on 10 years. Work just recently let
    up a bit and I surprised myself by spending some free
    time over Christmas revisiting some C++ crypto code I wrote way back when.

    I wonder how many ACA folks are programmers…

    1. Don B,

      Welcome to the ACA! I’ve only been a member for a couple of years now but it has definitely been a lot of fun. This last summer I was able to go to the conference in Albuquerque and got to meet a lot of the members that you see in the Cryptogram. They are wonderful people and there are quite a few programmers in the group. The programming languages vary from Basic, Python, Pascal, C++ and pretty much anything else you can think of. There is a little bit of everyone in here. Have fun solving!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s