Assignments‎ > ‎

HW5: Cryptography

DUE: November 8, 2012

Problem 1 (10 points)

The following cipher text is written in a Caesar shift cipher:

  TUCESHQSO YI JXU FHESUII RO MXYSX FUEFBU SXEEIU JXU CQD MXE'BB WUJ JXU RBQCU.

(a) (5 points) Decrypt the message and write down what it says.

(b) (5 points) What method did you use to decrypt it? Describe why you chose to use that method and how you proceeded with the decryption.


Problem 2 (20 points)

Using a shift cipher is very easy to break with a brute force attack because there are only 25 different keys for encoding. An alternative is to allow any arbitrary mapping of each letter occurring in the plain text to a different letter in the cipher text. This makes it quite hard to remember which letter maps to which, so it was common to have a keyphrase that produced the key. For example, using the keyphrase “JULIUS CAESAR”, we need to remove any spaces and duplicate letters, which gives us “JULISCAER” and then reproduce the rest of the remaining letters in the alphabet, in alphabetic order (and starting from the last letter of the key phrase). This produces the following key:

Plain alphabet:  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
Cipher alphabet: J U L I S C A E R T V W X Y Z B D F G H K M N O P Q

(a) (8 points) If one wants to use the keyphrase “THE DOG ATE MY HOMEWORK”, what is the key? Give it in the same format as above, with the plain alphabet written on top and the cipher alphabet on the bottom.

(b) (7 points) Encode the message “meet me at dawn” using this key.

(c) (5 points) Even though the use of keyphrases permits the use of a much greater number of keys than using a shift cipher, it is not secure. What is the major weakness of simple substitution ciphers? Use details of the above message and its encoding as an example.


Problem 3 (30 points)

The following is cipher text that was encoded using a monoalphabetic cipher:

JRUURVPTKSAZRQNVHEXDUPALHGUSAZVHHISDRXZSVPGHAEQHSGHYSPUCXUTHQSDPUPZNPTCRUCPTKVHS
IFQNEZRKQSELPFIHNAANAZHYSGYPTPAZQSZRQASZYSTNFRYESTPHASQRXTGZLHVRQUGDHKSTZRFLHFIZ
LHPQGTAQHFRQGAZRYSIHAXQHZLSZZLHGIPYIHNAZLHNVHQHXAPTKZRSXZLHTZPFSZHZLHPQHYSPUVHQH
SZUHSAZDPZAPTUHTKZLZLHQHFRYYHTGHGAZSTGSQGJRQAHFXQHSXZLHTZPFSZPRTRJHYSPUTRGRXDZPJ
ZLHNJRXTGZLHNVHQHXAPTKAXDAZSTGSQGIHNASZUHTKZLARJDPZADPZASTGDPZAZLHNQHEUSFHGZLRAH
IHNAVPZLAZQRTKHQRTHAZRAHFXQHZLHPQFRQERQSZHDXAPTHAAHYSPUDXZSFFRQGPTKZRRTHQHAHSQFL
HQVLRFRTZSFZHGXASJZHQZLHAZRQNQSTZLHAHFRYESTPHAYSNDHRCHQURRIPTKRTHEQRDUHYZLPQGESQ
ZNHYSPUHQAVLRSQHQHAERTAPDUHJRQAHTGPTKRXZYSQIHZPTKTHVAUHZZHQASTGRZLHQFRYYXTPFSZPR
TZRFXAZRYHQARTZLHPQDHLSUJPTJSFZRTHHYSPUYSQIHZPTKFRYESTNVLPFLZLRXKLZPZLSGJPBHGZLH
EQRDUHYSNHSQSKRLSGUHJZXADSTIFSEPZSURTHVSUYSQZZGSYHQPZQSGHZPCRSTGRZLHQAREHTZRHSAN
AERRJPTKSFRYESTNYSNJPBZLHEQRDUHYVPZLGIPYIHNAZLHNKHTHQSZHGZLHYAHUCHADXZJRQKHZZLSZ
ZLPQGESQZNHYSPUHQASUARLSCHZRJPBZLHIHNAZLHNXAHZRAHTGHYSPURTZLHFRYESTNADHLSUJRJZHT
ZPYHAZLHHYSPUHQVPUUKHTHQSZHPZARVTGIPYIHNZRAHTGAXFLFRQQHAERTGHTFHSTGANAZHYSGYPTPA
ZQSZRQAYSNRQYSNTRZDHSVSQHRJZLHAHRQDHSDUHZRGHUHZHZLHYJQRYZLHPQGTAQHFRQGAVPZLRXZFS
XAPTKEQRDUHYAJRQZLHHYSPUHQZLHQHAHSQFLHQVLRSAIHGXAZRXAHLPALSFIHQLSTGUHWXPTFNQRDHQ
ZARTXTFRCHQHGZLHGIPYEQRDUHYVPZLZLPQGESQZNHYSPUHQAUSAZNHSQSJZHQSTRZLHQQHAHSQFLHQT
SYHGORLTKQSLSYFXYYPTKJRXTGZLSZJSFHDRRIVSAXAPTKSVHSIGIPYIHNPTJSFHDRRIJPBHGPZAGIPY
IHNSJZHQKQSLSYFXYYPTKTRZPJPHGZLHFRYESTNDXZQRDHQZARTDHKSTVRTGHQPTKPJRZLHQFRYESTPH
AYPKLZLSCHZLHASYHEQRDUHYSJZHQGRPTKSUPZZUHQHAHSQFLLHJRXTGZLSZSTXYDHQRJUSQKHFRYEST
PHADSTIAQHZSPUHQASTGPTCHAZYHTZJPQYASYRTKZLHYVHQHSUUXAPTKZLHHBSFZASYHVHSIIHNSDPZI
HNZRSXZLHTZPFSZHZLHPQHYSPULHZLRXKLZZLPAVSARGGXTZPULHZQSFHGZLHIHNDSFIZRSZLPQGESQZ
NHYSPUHQFSUUHGHEAPURTPTZHQSFZPCHPTAHEZQRDHQZARTFRTZSFZHGXAFHQZSZFSQTHKPHYHUURTXT
PCHQAPZNZRQHERQZZLHEQRDUHYSTGXAFHQZQHSFLHGRXZZRHEAPURTRTLPADHLSUJPGPGTZVSTZZRSTK
HQHEAPURTAUSVNHQAGPQHFZUNQRDHQZARTASNAQHJHQQPTKZRZLHURTKAZSTGPTKPAAXHZLSZYSTNAHF
XQPZNQHAHSQFLHQALSCHVLHTZLHNZQNZRGPAFURAHCXUTHQSDPUPZPHASTGZLHSJJHFZHGFRYESTNHPZ
LHQQHERQZAZLHQHAHSQFLHQZRUSVHTJRQFHYHTZRQAHTGAZLHQHAHSQFLHQSZLQHSZHTPTKUHKSUUHZZ
HQPTZLPAFSAHHEAPURTGPGZLHQPKLZZLPTKSJZHQDHPTKFRTZSFZHGDNXAFHQZSTGEQRYEZUNQHPAAXH
GDPZIHNAJRQZLHHYSPUPZVSAAHTGPTKRXZRTDHLSUJRJPZAFUPHTZADXZSJZHQRXQAZRQNQSTUSAZVHH
IQRDHQZARTFLHFIHGZLHGTAQHFRQGAJRQGRYSPTADHURTKPTKZRSTXYDHQRJHEAPURTAFXAZRYHQASTG
JRXTGZLSZYSTNRJZLHYAZPUULSGZLHRUGDPZIHNPTZLHPQGTAQHFRQGASURTKVPZLZLHAZQRTKHQDPZI
HNSAYSZLHYSZPFPSTMSFLSQNLSQQPAHBEUSPTHGPTRXQJPQAZGIPYAZRQNSAURTKSASVHSIGIPYIHNQH
YSPTAPTSGTAQHFRQGHCHTPJSFRYESTNPATRURTKHQXAPTKPZZRSXZLHTZPFSZHPZAHYSPUSLSFIHQFST
AZPUUXAHZLHVHSIHQIHNZRAERRJHYSPUSTGAHTGPZRXZSAPJPZFSYHJQRYZLSZFRYESTNPTHEAPURTAF
SAHZLHEQRDUHYVSAHBSFHQDSZHGDNZLHJSFZZLSZZLHHYSPUHQLSGXAHGZLHASYHGIPYYSAZHQIHNJRQ
SUURJPZAFXAZRYHQAQHGXFPTKZLHSYRXTZRJVRQISLSFIHQVRXUGLSCHZRGRZRAERRJZLHPQHYSPUPZZ
RRIARYHVLHQHSQRXTGJPCHLRXQAZRDQHSIPZRTYNWXSGFRQHANAZHYSZLRYHXAPTKEXDUPFUNSCSPUSD
UHARJZVSQHYAPHCHJSFZYAPHCHSTGKKTJAQRDHQZARTASNAZLHQHSQHARYHZHGPRXAJRQYSZFRTCHQAP
RTATHHGHGZRKHZZLHJSFZRQPMSZPRTQHAXUZAZXQTHGPTZRSEQPCSZHIHNLHASNADXZTRZHAZLSZLHFQ
HSZHGSJXUUNSXZRYSZHGAFQPEZZRGRZLPAVLPFLVPUUKHTHQSZHZLHEQPCSZHIHNJRQSFRYESTNXAPTK
ZLHFRYESTNAGRYSPTTSYHSTGGIPYAHUHFZRQSYRTKZLHHEAPURTFXAZRYHQAZLSZAZPUULSGZLHDPZIH
NPTZLHGTAQHFRQGARJARYHRJZLHPQAXDGRYSPTAVHQHXADSTIDSQFUSNAFSEPZRURTHAFRZZQSGHZGSY
HQPZQSGHVSUYSQZGPATHNYSQQPRZZQPZMFSQUZRTZLHSYHQPFSTSXZRYRDPUHSAARFPSZPRTVSUYSQZZ
LHLRYHALREEPTKTHZVRQIZPCRSTGEPMMSLXZWXPTTOSUUPAHTPRQCPFHEQHAPGHTZRJYSQIHZPTKZHFL
TRURKNJRQHEAPURTSFITRVUHGKHGZLHPAAXHSTGASPGLPAZHSYVSAPTZLHEQRFHAARJFUHSTPTKRXZZL
HRUGIHNAJQRYGTAQHFRQGAVHGPGTRZITRVZLSZVSAZLHPAAXHLHZRUGVPQHGPZVSATZSTSFZRJTHKUPK
HTFHQHYRCPTKZLHYVRXUGLSCHDHHTJSPQUNAPYEUHDXZVHGPGTRZITRVZLSZUHSCPTKZLHIHNAVRXUGF
QHSZHZLSZCXUTHQSDPUPZN

Note that all spaces and punctuation in the original plaintext have been removed. Also, numbers were removed, so there will be a few odd looking phrases where something like “for 1 in 10 individuals” comes out as “for in individuals”. (Note: this examples does not come from the text, so it won't be helpful as a clue.)

In this problem, you'll exploit the major weakness of monoalphabetic ciphers to decode this message using frequency analysis. The text is somewhat long. Don't be intimidated by this – it actually makes the problem easier. You will only need to write down the decoded plaintext for the first two lines. (But, you get to use the rest of the text as part of cracking the encoding.)

The relative frequency of a character is the number of tokens of that character divided by the total number of character tokens. For example, in ABCADEAFG the relative frequency of A is 3/9 = 1/3 = .3333 = 33.33%. In the ciphertext above, A has a relative frequency of 2.54%. The following is the relative frequency distribution for all the characters in the ciphertext.


Cipher character 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
Relative frequency 6.510.190.781.841.703.24
3.8112.801.731.971.864.730.142.240.056.656.817.218.326.323.621.590.082.493.599.728.9


Here is the same information graphically, ordered alphabetically: 



Here it is ordered by frequency:


(a) (20 points) Decode the first two lines of the cipher text. Look at the relative frequencies of letters in the English language provided in Wikipedia. Compare the relative frequency distribution given above to the distribution given in Wikipedia, using it to generate hypotheses about which ciphertext characters might correspond to which plaintext characters. Test those hypotheses on small segments of the ciphertext to see if they make sense; then using the process of elimination and some educated guesses based on the words you are starting to see appear, determine the rest of the key and decode the message. Write down the decoded plaintext for the first two lines of the cipher text.

TIP: You should put the cipher text into an editor like Microsoft Word or Google Docs and use Find and Replace as you test different guesses. It will be especially helpful if you can replace the capital letters of the cipher with lowercase plain text characters.

If you are able to use Unix, use the 'tr' function like I did in class, e.g. if you think cipher text X is plaintext a:

$ echo 'XYZ' | tr 'X' 'a'
aYZ

(b) (5 points) Describe the major aspects of the process you went through to decode the message. Which strategies did you use? How did your knowledge of English help in the decoding?

(c) (5 points) Write down the key showing which plaintext character corresponds to which ciphertext character.

(d) (Extra credit, 4 points) The key was generated in a systematic way. How was it done? (This is not easy.)

(e) (Extra credit, 1 point) Can you find the web page that contains the plaintext?


Problem 4 (20 points)

The following message is encrypted with the Vigenere cipher, using the key phrase “NOISYCHANNEL”:

  NDZGZNLMYVOPGVQKGUVNGUIQVBIDCZHM

(a) (10 points) Decrypt the message and write down what it says.

(b) (10 points) Now, encrypt the message using the key phrase “BAYESRULE”.

Note: there are tools on the Internet for encoding and decoding with the Vigenere cipher. You are welcome to use them to check your work – but make sure you understand the principle to what is going on (keep in mind that these tools won’t be available during the exam)


Problem 5 (20 points)

Give two reasons why the Navajo code talkers were so effective for secure communication in WWII and explain one strategy that they had to employ to avoid being “decoded”.

You are encouraged to use outside sources for answering this question, including Wikipedia's code talker page.

Comments