# Cryptanalysis

XanthosNZ
Posers and Puzzles 21 Mar '06 00:57
1. XanthosNZ
Cancerous Bus Crash
21 Mar '06 00:57
I plan on starting from simple Caesar shifts up to perhaps Enigma. As the codes get harder more contextual information will be given to give that first leg up that's needed.

Caesar Shift Cipher:
Basically every letter of the code is shifted a certain number of letters in the alphabet. For example with a shift of 3; a in the plain text becomes D in the coded text (convention is for lower case for plain text [the message] and upper for the code), b becomes E etc.

Techniques required:
Basic frequency analysis will suffice. In the english language some letters are used more often than others. For example e is very common while q is rather rare (added bonus is that q is always [almost always] followed by a u perhaps giving another foothold for attack). You can use this distribution to find which plaintext letter the code letters are most likely to represent. For example if you have a code where the most used code letter is Y you could posulate that Y represents e. In a Caesar shift this one guess gives you the entire code and you can decode the message and see if it makes sense. If not then try another letter.
One thing that makes a Caesar shift easy to solve is that the distribution is moved left or right not scrambled (r, s and t are all used rather a lot, these peaks will also be next to each other in the code letter distribution). Use this to your advantage.
Shortcuts could work if enough context was known (what type of message is being sent, likely words it contains etc.).

This code was intercepted (it was still delivered and they don't know we have it) between two divisions of a army.

FNJCCJLTJCMJFWXWCQNRAUNOCOUJWT

What actions should you take?
I would appreicate it if people wouldn't blurt out the answer so others get the chance to solve it themselves.
2. royalchicken
CHAOS GHOST!!!
21 Mar '06 01:101 edit
Originally posted by XanthosNZ
I plan on starting from simple Caesar shifts up to perhaps Enigma. As the codes get harder more contextual information will be given to give that first leg up that's needed.

[b]Caesar Shift Cipher
:
Basically every letter of the code is shifted a certain number of letters in the alphabet. For example with a shift of 3; a in the plain text becomes D e it if people wouldn't blurt out the answer so others get the chance to solve it themselves.[/b]
In a proper Caesar cipher, the plaintext is written above some periodic keyphrase, and each letter in the plaintext shifted by the difference between the corresponding keyphrase letter and the beginning of the alphabet.

Come to think of it, that might not be Caesar at all; it might be Vignere, but I can't be bothered to look it up.

EDIT Yeah, sorry, ignore me.
3. XanthosNZ
Cancerous Bus Crash
21 Mar '06 08:01
I've had one person PM me an answer indicating they decoded the plain text correctly. I'll post the answer after it's been 24 hours since I posted it (3pm tomorrow my time). If anyone is completely stuck then feel free to ask questions.

Also something to note, this form of encoding has 26 possible settings meaning that even the dumbest brute force approach (decoding the entire message with each key) wouldn't take more than half an hour by hand.
4. 21 Mar '06 12:212 edits
Originally posted by XanthosNZ
Also something to note, this form of encoding has 26 possible settings meaning that even the dumbest brute force approach (decoding the entire message with each key) wouldn't take more than half an hour by hand.
I went for a lazy and dumb brute force approach:

my \$caesar = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ;
my \$enc = "FNJCCJLTJCMJFWXWCQNRAUNOCOUJWT" ;
for (my \$i = 0; \$i < 26; \$i++) {
\$caesar =~ s/(.....)(.*)/\$2\$1/ ;
my \$dec = \$enc ;
eval "\\$dec =~ y/[A-Z]/\$caesar/" ;
print "\$dec\n" ;
}

The 24th line of output is the only one that can be read as English text.
5. 21 Mar '06 17:00
Only takes about two minutes with MS Excel. See PM.
6. leisurelysloth
Man of Steel
22 Mar '06 00:17
By hand takes about 5 minutes. It helps to also consider that the text message will likely contain a reasonable assortment of vowels.
7. XanthosNZ
Cancerous Bus Crash
22 Mar '06 05:011 edit
Code:
FNJCCJLTJCMJFWXWCQNRAUNOCOUJWT

Key:
a=J b=K etc.

Plaintext:
weattackatdawnontheirleftflank
We attack at dawn on their left flank

Spaces are omitted as they make decyphering letter for letter cyphers (where one codeletter equates to one plaintext letter) easier (because there are only a few one and two letter words).

The next cypher will be a mono-substitution cypher. This is the same as the Caesar cypher except that that any letter could be any letter (ie. it's not a shift so much as a scramble). So it could be that a=R, b=W and c=P and so on.

This means that instead of the 26 possible keys there were in the Caesar cypher (however one of those was a shift of zero meaning no encoding) there are 26! (number of ways of picking 26 objects from a pool of 26 when order matters) possible keys (one of which is no encoding). This makes a brute force crack much much harder to do. It can still be done with an automated process (you also have to decide a way for the results to be pruned automatically).

Once again letter frequency is the way to go about it.

The code:

VORPWUDTRDBVORGLHUUVWMBWEUWGHUHLWGBRMLRJDTWMWIIDRSA
IDREUQDBBDBRVRRBGRXRBVQEWCIHAWCVHLHBGRBPIWMUDBFDBVORS
HIYBDFOVHEVRIBDFOVVORIRSFUWMWEODGTDFHIRVVREUWHVDBFHUWB
FVORAHTYGVIRRVGORMWCUSPHTREWIOWCIGORHSDBFBWMORIRDBVO
RGVHIUDFOVVOHVOHLLRIGSWMBVOIWCFOVORVODBHDIWEVORLRGHGV
ORPWUDTRMRIRBWVVORWBUQWBRGVWMWBSRIHVVORBHVDWBHUUHA
WIHVWIQGWLRPOQGDTDGVGOHSURHIBRSVOHVVORDIBRMRGVTWUURH
FCRMHGRJPRIDLRBVDBFMDVOVMRBVQGDJOWCISHQGMODTOLRHBVVOH
VODGMHYDBFGTORSCURMWCUSGUWMUQIWUUDBHBSWCVWEPOHGRMD
VOVORDIGVODGAWISRIRSWBGVIHBFRRXRBEWIVORVORWIRVDTHUSDXD
GWB

Line breaks are put there for clarity and to stop [WORD TOO LONG] no other reason.
I've made it long because that means frequency analysis works better (by the law of averages [a short sentence could have extremely skewed totals]). No I did not encode this by hand and I don't suggest anyone try to decode it by hand (just counting up the totals to start frequency analysis would be tiresome). Automate anything you can as some people did on the last problem.

Also, if you are confident you have the answer there is no need to decode the entire passage, a short section will do, especially if you lack the coding experience needed to do it automatically.

PMing me a comment related to the content or even just the first few words is enough to show you've solved it.

Good luck. As before any questions can be asked here. If I don't answer it I'm sure someone else will.
8. 22 Mar '06 12:15
For those of you who, like me, can't remember the letter frequency distribution of English, here's a useful web page:

http://en.wikipedia.org/wiki/Letter_frequencies

It has digraphs and trigraphs too.
9. XanthosNZ
Cancerous Bus Crash
22 Mar '06 12:291 edit
For those of you who, like me, can't remember the letter frequency distribution of English, here's a useful web page:

http://en.wikipedia.org/wiki/Letter_frequencies

It has digraphs and trigraphs too.
Thanks for that. I've had two people PM me the plaintext so far. One even pointed out that I made a few spelling mistakes in it (I had to type it all in lower case without spaces for my quick and dirty encoding algorithm to work). ðŸ˜ž

Both people used frequency analysis to solve it. However I believe I've worked out a method for a relatively simple brute force method. I'll detail it tomorrow when I give out the answer.
10. sonhouse
Fast and Curious
22 Mar '06 17:29
Originally posted by XanthosNZ
Thanks for that. I've had two people PM me the plaintext so far. One even pointed out that I made a few spelling mistakes in it (I had to type it all in lower case without spaces for my quick and dirty encoding algorithm to work). ðŸ˜ž

Both people used frequency analysis to solve it. However I believe I've worked out a method for a relatively simple brute force method. I'll detail it tomorrow when I give out the answer.
Thats got to be a first: XanthosNZ actually thanking someone!
11. leisurelysloth
Man of Steel
22 Mar '06 18:27
Originally posted by sonhouse
Thats got to be a first: XanthosNZ actually thanking someone!
AND making multiple spelling errors, all in one thread. He must be slipping!

XanthosNZ, pull yourself together man! ðŸ˜
12. XanthosNZ
Cancerous Bus Crash
23 Mar '06 08:071 edit
The solution (still sans spaces):

thepoliceinthesmalltownoflosalamosnewmexicoworriedbrieflyinnineteenseventyfour
downthroughthethinairofthemesasthepolicewerenottheonlyonestowonderatthenational
twentysixhourdayswhichmeantthathiswakingschedulewouldslowlyrollinandoutofphase
withtheirsthisborderedonstrangeevenforthetheoreticaldivison

Yes I missed the third i in division and an e from seen (buried somewhere in there). Congratulations to all those who solved it. Apparently the letters t and e were bang on predicted frequency which if you used those for a starting point (being the most used letters it makes sense) meant the problem wasn't too hard.

Interesting as a side note is frequency analysis in other languages. In English, e typically exceeds 10% of all letters (and is the only letter to do so) and 5 likely have frequencies below 1% (j, k, q, x and z). In Italian 3 letters exceed 10% and 9 are less than 1%. In German nearly 20% of all letters are e's. Note, thought that these are averages and a non-average passage may not conform to these patterns (see: The Void by Georges Perec)

Also a theoretical (if extremely ineffient) way to determine whether an attempt at decoding a mono-substitution cipher is gibberish would be to check for a series of common words. First you discard any attempt that doesn't contain the string 'the' somewhere in it, then discard all remaining ones which don't contain 'and' and so on through common words. This would only work with a long enough passage that you could be confident it would contain these common words.

Right next up is the Vigenère cipher (after mentioning it in the second post I expect you to solve this one RC). Basically it's a Caesar shift cypher except each position uses a different shift amount. It's kind of wordy to explain so I'll direct to an excellent and very useful Wikipedia page.

http://en.wikipedia.org/wiki/Vigenere_cipher

There you can find the exact details of the cipher, examples of it in use, the history of it and tips on how to crack it.

The challenge:

Ho qd uswqgn trm xwkf lkhmkbtk eadx bp dpp ljmnm jhkzea sywgn trm BJk pmlwidm zn zua ehcu wq mpbmkpexkp. Pw ua t mobupz bgvbvr mwwtwsm myaxaqmj fpta roiwtq avef ckup qffw aps yey ik m axuiyz lvv til zhyey ljmutaim qxxjadxtexb tv 1998. Zq ptz gbmlb htglpckt dsaxtl pnmtflazo lpzo, aamwp & IT hnn pp idew ahs k jlawnies bkkvojacgk, hkdtvy eqzuen etbz fpx Widbdjmdoa Wibiemk acm vf rqrp kophvl. Rm sik m amyoxo lze, m vbje actkc dmelacm lvv szxht zidaazo lrivtd, jmf px ps cbttd ewflwrie qfowgzicbpvl. Tm glena ew ayxkvvo wy pae wolrktw rmpoxtexb lvv pmvpsswy uswqgn, beb tb ae xkvbkjwg eazx vf k klaw an ehcu wq mpbmkpexkp. Ik tm vvndqycwe bh sekzy bg dmtk donpvkqa al wstw ljmutaimiwtq uuiyofm la s bttfeb. Pp usk ptce dpp paspxzt exdqvq wy ahsa rzggx, ubt sa azgniusy dpp ugeb "khw" yn epw qtbae aclzlqzuhcua pvlqzbug sv epw pztmt. Sn epw ZNE aeku epsf lkhfda sqe ua ihtsmyb, ltmr divt mm jqetydol tv luux didp lv wjkxslove xdmgxy.

I've left spaces and punctuation in this time to aid in the decoding process. Also I can tell you that the key isn't randomly generated (ie consists of real words) and it isn't the length of the code (that would be a one-time pad cipher which is uncrackable as long as each key is only used once) or even close to it.

Once again, PM me with either the key (which would show you've done the hard yards) or the plaintext if you solve it. Any questions can be asked either that way (if you feel you could be revealling something important) or in this thread.

Remember, your first step should be trying to find the length of the key.
13. XanthosNZ
Cancerous Bus Crash
24 Mar '06 04:49
For anyone who was confused due to RC's statement that the key wasn't words (gone now due to swearing) I can confirm that the key is a person's name. Those count as words in my book.
14. 25 Mar '06 19:26
I cannot quickly get this one, need more hours to work on than I have available I'm afraid, unless of course I were to trade off my chess playing time. Anyone close?
15. 26 Mar '06 01:12
Originally posted by SJ247
I cannot quickly get this one, need more hours to work on than I have available I'm afraid, unless of course I were to trade off my chess playing time. Anyone close?
I've managed to crack it, but it did take an hour or so even with a computer doing the donkey work. I'm pretty sure RC has solved it too because he complained about the key not being a word. See Xanthos' post above.