CSC 290A: Cryptology E3: Substitution, Vigenere

What To Hand In

Spend about a week on each part, structure your writeup to reflect the two parts (but if there are any commonalities, be sure to exploit them).

Substitution

Write a set of tools to create and decrypt substitution ciphers. In particular, perform monoalphabetic encryption and decryption using a permutation derived from a specified key phrase (Singh, page 13). For encryption, remove all non-alphabetic characters and print output in groups of 5.

The encryption is a one-line program in a shell script or Perl, so do it immediately (overnight) so you can produce ciphers for your classmates to try to break.

For decryption, print output in one long string of lower-case letters for ease of reading. Encrypt two samples of English prose with at least 200 characters using different keys. Prose can be anything that is not offensive, or engineered to be difficult to crack.

Debug your tools on your own input of course. Trade encrypted files with two classmates. When you get an encrypted file, break it and report your results.

To repeat from the previous Aristocrat assignment, here's a challenge from Greg Rubin (from 2004 course), ho submits what he swears is an aristocrat that is immensely long and therefore should be easy. He says it's hard. Hint: it's a poem. The Rubin Challenge. Greg's a smart guy, and so this one might provide a more interesting story. Bonne chance, mes amis! Courage! In your writeups, document to whom you gave your encryptions, AND you should document from whom you got your encryptions. You lose credit if you don't use others' encryptions and you lose credit if your encryptions aren't used, so be conscientious about doing and reporting this aspect.

Some useful techniques:

• En- and de-crypting of substitution cipher given key (or permutation) (this is a one-liner in PERL).
• Text frequency histogram.
• Repeated and reversed digram counts.
• Contact chart.
• Contact statistics, especially the range of frequencies of contacted letters measured somehow (min and max? variance or standard deviation?...
• Use of dictionary (e.g. /usr/dict/words ) and regular expressions to find pattern words (simple in PERL). For example, what word matches the pattern ABCCDDE? Or even pairs of words related by patterns: (simple example. Suppose you have ABCB and DABCB ... search the dictionary for pairs matching this pattern).
• Anagrammer? you might want an automated tool to perform substitutions and display the result, take back or change substitutions, etc. CB made one but can't decide if it's any better than pencil and paper.

Your cryptograms might have accompanying stories to provide probable words, or they might have no word boundaries (or disguised word boundaries), use telegraphic text, might avoid common words, etc.). Remember the Golden Rule and don't be too nasty, but on the other hand nobody will get the fun and credit of solving something clever if all the examples are too easy. You might rate the difficulty as "easy", "medium", "hard" when you distribute them.

In a TR-style manner describe your investigations and the process of solution. How did the tools you wrote help you? What other ideas for helpful tools do you have?

Chris Brown's code for patterns is a couple of 20-line PERL programs that get edited for each word. You could do the same thing in the UNIX shell with egrep, awk, or sed probably... Everything else is about 400 lines of lines of Matlab (maybe less: it's too boring to count exactly since I did a couple of versions of a lot of it).

Vigenere

Five or six weeks later, she asked me if I had deciphered the manuscript which had the transmutation procedure. I told her that I had.

"Without the key, sir, excuse me if I believe the thing impossible."

"Do you wish me to name your key, madame?"

"If you please."

I then told her the word, which belonged to no langauge, and I saw her surprise. She told me that it was impossible, for she believed herself the only posessor of that word which she kept in her memory and which she had never written down.

I could have told her the truth -- that the same calculation which had served me for deciphering the manuscript had enabled me to learn the word -- but on a caprice it struck me to tell her that a genie had revealed it to me. This false disclosure fettered Madame d'Urfe' to me. That day I became the master of her soul, and I abused my power. Every time I think of it, I am distressed and ashamed, and I do penance now in the obligation under which I place myself of telling the truth in writing my memoirs. [I took my leave] bearing with me her soul, her heart, her wits and all the good sense that she had left.

-- Casanova

(P.S. The key was NABUCODONOSOR. -- CB)

So, in case you run into a wealthy person you'd like to enslave spiritually and sensually, you should write a set of tools to create and decrypt Vigenere ciphers.

For encryption, remove all non-alphabetic characters and print output in groups of eight (8), eight (8) to a line.

The encryption is a one-line program in a shell script or Perl (or 4 lines in MatLab, plus file I/O and some initialization), so do it immediately (overnight) so you can produce ciphers for your classmates to try to break.

For decryption, print output in one long string of lower-case letters for ease of reading. Encrypt two samples of English prose with at least 1000 characters using different keys of length between 10 and 20 characters. Prose can be anything that is not offensive, or engineered to be difficult to crack.

Debug your tools on your own input of course. Trade encrypted files with two classmates. When you get an encrypted file, break it and report your results. Trade at least two ciphers with classmates and break them. In your writeups, document to whom you gave your encryptions, AND you should document from whom you got your encryptions. You lose credit if you don't use others' encryptions and you lose credit if your encryptions aren't used, so be conscientious about doing and reporting this aspect. At least do this much:

• En- and de-crypting of Vigenere cipher (with simple, shifted alphabets), given a key. This is easy, do it quickly.
• Kasiski attack for finding the key length
• Friedman attacks, both index of coincidence and average index of coincidence, including finding the key.

• Use sum of squared differences or another matching metric along with the correlation to compute shifts when comparing group pdfs in the key-finding half of decryption. (And comparing performances, of course!).
• Investigating whether Iavg or IOC works better in the key-finding phase.
• How could you pull together various techniques you know about to deal with general substitution alphabets (not simple shifts, or Caesars, as in the classic Vigenere.)...this problem opens the door to heuristic methods, anagramming etc. as in the monoalphabetic substitution work you have done.
• Solve a famous difficult cryptogram submitted to Edger Allen Poe .

Chris Brown's code to do all this is about 350 lines of Matlab, including scrapped versions of routines.

This page is maintained by CB.

Last update: 29.07.01.

This page is maintained by CB.

Last update: 21.8.03.