FSem 132 Methods and Issues in Cryptology Fall 2006

Homework 2

due Friday, Oct 27 in class


In this homework, you'll get to carry out some of the computations used to break Enigma codes (and gain an appreciation for why machines were needed to help search for keys).


You have intercepted the following message: (spaces added for readability)

ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM

Based on previous intercepts, you suspect that the message contains the plaintext CELEBRATEVICTORY.

Section 15.1 of Körner discusses the use of cribs to discover scrambler settings, and illustrates how the process is independent of the plugboard settings. His discussion (some of which is summarized here) is an elaboration on the ideas behind Turing's bombes as discussed in class. You will be using the method he describes to check scrambler settings for the message.

  1. While you suspect the presence of the crib CELEBRATEVICTORY, you are not sure where that text occurs in the message. Using the ciphertext below, mark the first five places where the crib cannot begin. (Cross off the ciphertext letter if the crib cannot begin at that letter.) You may find it useful to copy the crib and the ciphertext onto two separate strips of graph paper, with one letter per box.
    ZDOCF CDFAZ QBVZD FAWBC AYPDK MHWIN ELTKL IRDUJ PEMMK CQDHX RPNIM
    

    Hint: remember that the Enigma machine cannot encrypt a letter as itself.

  2. Even if all of the places where the crib can't be aligned are eliminated, there are still many places where the crib can be aligned. So that you don't have to test them all, you may assume that the crib should start at either the 15th ("D") or the 25th ("K") letter of the ciphertext. Only one of these can be right. Which one is it? _________

  3. You have been assigned two of the 263 possible scrambler settings to test. The alphabets generated by successive scrambler positions are shown in the following tables, along with the crib:

    setting #1
    plain
    letter
    cipher alphabetcipher
    letter
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    CSXJMWHZFLCTIDVQROPAKYNEBUG 
    EYFZPHBUEWSLKNMXDTVJQGRIOAC 
    LLDEBCTSNXYWAOHMUVZGFPQKIJR 
    EXIDCLROTBWVEPSGMUFNHQKJAZY 
    BNPKJWLSORDCFTAHBZIGMXYEUVQ 
    RPLMSFEUQVORBCTJAHKDNGIXWZY 
    AIXRFLDVQAZMEKSTWHCNOYGPBUJ 
    TMZNJIYPQEDUVACSGHTORKLXWFB 
    EIDUBXVRLAPTHZSWJYGNKCFOEQM 
    VWLDCQPZUOTVBXRIFENYJHKAMSG 
    ILXFPKCVSNTEARIWDZMHJYGOBUQ 
    CLDNBRUPJTHXAQCVGMEZIFOYKWS 
    TGCBNSOATQXWRYDFUILEHPZKJMV 
    OWRMOUHIFGZLKCYDVSBQXEPATNJ 
    RDEZABMJXYGOVFTKRSPQNWLUHIC 
    YSNUTRZHGXMOQJBKWLEADCYPIVF 
    setting #2
    plain
    letter
    cipher alphabetcipher
    letter
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    CYFZPHBUEWSLKNMXDTVJQGRIOAC 
    ELDEBCTSNXYWAOHMUVZGFPQKIJR 
    LXIDCLROTBWVEPSGMUFNHQKJAZY 
    ENPKJWLSORDCFTAHBZIGMXYEUVQ 
    BPLMSFEUQVORBCTJAHKDNGIXWZY 
    RIXRFLDVQAZMEKSTWHCNOYGPBUJ 
    AMZNJIYPQEDUVACSGHTORKLXWFB 
    TIDUBXVRLAPTHZSWJYGNKCFOEQM 
    EWLDCQPZUOTVBXRIFENYJHKAMSG 
    VLXFPKCVSNTEARIWDZMHJYGOBUQ 
    ILDNBRUPJTHXAQCVGMEZIFOYKWS 
    CGCBNSOATQXWRYDFUILEHPZKJMV 
    TWRMOUHIFGZLKCYDVSBQXEPATNJ 
    ODEZABMJXYGOVFTKRSPQNWLUHIC 
    RSNUTRZHGXMOQJBKWLEADCYPIVF 
    YTZVYLPIXGMQEJURFKOWANCSHDB 

    Write the ciphertext letters corresponding to the correct position for the crib (as determined in the previous problem) in the right column of both tables.

  4. Using the method described in Körner 15.1, determine which of the scrambler settings is the correct one. Is it setting #1 or setting #2? _________ Show your work, including any plugboard settings you derive.

  5. Now that the scrambler setting for the start of the crib has been found, it is possible to conceptually turn the machine backwards to find the setting that was used at the start of the message. A longer sequence of scrambler alphabets is shown below. The settings are numbered so that #1 and #2 are the same as in the previous problem. Determine the scrambler setting at the start of the message: _________

    setting #cipher alphabet
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    -34ULGJQZCWYDTBPONMESRKAXHVIF
    -33HNQWKLOAUYEFRBGVCMXZIPDSJT
    -32LMIRWXZVCSPABTYKUDJNQHEFOG
    -31FSPKWAZTLVDIYRUCXNBHOJEQMG
    -30EINJAYORBDTWUCGVSHQKMPLZFX
    -29RKOIZYSVDWBTUQCXNAGLMHJPFE
    -28FUMZXAJQPGVSCRTIHNLOBKYEWD
    -27WVUYSXLNPKJGQHRIMOEZCBAFDT
    -26OHYMWGFBRKJUDPANZITSLXEVCQ
    -25UTWXPQSVJIMRKONEFLGBAHCDZY
    -24KVEXCLNTMOAFIGJSZYPHWBUDRQ
    -23DSVAKYLPUREGQXWHMJBZICONFT
    -22VUTOPLHGKSIFRYDEXMJCBAZQNW
    -21VOMLTPXJNHWDCIBFUYZEQAKGRS
    -20NDXBHOLERQYGTAFWJIUMSZPCKV
    -19OPXVIJZKEFHSUTABYWLNMDRCQG
    -18JNPXFEZVRAQUSBWCKIMYLHODTG
    -17BAONURQJZHPTSDCKGFMLEYXWVI
    -16VGIMPYBWCZURDTXESLQNKAHOFJ
    -15FSWUGAEQPVTROYMIHLBKDJCZNX
    -14UILXONWVBRQCTFESKJPMAHGDZY
    -13TZWXPGFONQRVSIHEJKMAYLCDUB
    -12HNUXKSYARQEMLBPOJIFVCTZDGW
    -11MENVBZLQSYWGACRXHOIUTDKPJF
    -10OVRUGHEFYMNZJKAXSCQWDBTPIL
    -9QEGYBKCVMOFTIZJXASRLWHUPDN
    -8OWPFGDEVTNSXQJACMYKIZHBLRU
    -7IFRYJBNZAEWOPGLMVCUXSQKTDH
    -6YSEMCWXPZRNQDKUHLJBVOTFGAI
    -5LMVJUNWZRDPABFTKYIXOECGSQH
    -4DKEACURQYNBXTJSWHGOMFZPLIV
    -3PSIZOTJYCGWNXLEAVUBFRQKMHD
    -2CHAIRXQBDUZTNMWVGEYLJPOFSK
    -1ZGYKXQBLMUDHIVWSFTPRJNOECA
    0CGASKWBJTHEYRQUXNMDIOZFPLV
    1SXJMWHZFLCTIDVQROPAKYNEBUG
    2YFZPHBUEWSLKNMXDTVJQGRIOAC
    3LDEBCTSNXYWAOHMUVZGFPQKIJR
    4XIDCLROTBWVEPSGMUFNHQKJAZY
    setting #cipher alphabet
    ABCDEFGHIJKLMNOPQRSTUVWXYZ
    5NPKJWLSORDCFTAHBZIGMXYEUVQ
    6PLMSFEUQVORBCTJAHKDNGIXWZY
    7IXRFLDVQAZMEKSTWHCNOYGPBUJ
    8MZNJIYPQEDUVACSGHTORKLXWFB
    9IDUBXVRLAPTHZSWJYGNKCFOEQM
    10WLDCQPZUOTVBXRIFENYJHKAMSG
    11LXFPKCVSNTEARIWDZMHJYGOBUQ
    12LDNBRUPJTHXAQCVGMEZIFOYKWS
    13GCBNSOATQXWRYDFUILEHPZKJMV
    14WRMOUHIFGZLKCYDVSBQXEPATNJ
    15DEZABMJXYGOVFTKRSPQNWLUHIC
    16SNUTRZHGXMOQJBKWLEADCYPIVF
    17TZVYLPIXGMQEJURFKOWANCSHDB
    18RHVUSGFBKLIJQYWZMAEXDCOTNP
    19SGRLHPBEMTQDIZXFKCAJVUYOWN
    20OUFNMCYKLRHIEDAQPJWXBZSTGV
    21NMIGJWDYCESQBAZVLUKXRPFTHO
    22WMQTKVHGXNERBJYZCLUDSFAIOP
    23PINMTJLXBFSGDCZAYWKEVURHQO
    24NIDCSWHGBXMYKAQVOUEZRPFJLT
    25ZFOQWBMUJIYNGLCXDSRVHTEPKA
    26ICBTPVJLAGRHWXUEYKZDOFMNQS
    27CNAJVHYFSDLKXBPOUWIZQERMGT
    28CIASNOPKBZHYWEFGTUDQRXMVLJ
    29EPZLAJWMXFRDHTVBUKYNQOGISC
    30ZDOBUYWMLVXIHSCRTPNQEJGKFA
    31HLFIWCUADQSBYVZTJXKPGNERMO
    32FVIJTANYCDRUWGQSOKPELBMZHX
    33FCBRHAVETYUPSWZLXDMIKGNQJO
    34ZSFKUCVQTWDXRPYNHMBIEGJLOA
    35JSEQCVKTOAGZWRIUDNBHPFMYXL
    36WCBRXSTZVKJYOQMUNDFGPIAELH
    37KPGYTNCSLZAIQFXBMWHEVURODJ
    38GEQTBHAFJIZUPXVMCWYDLORNSK
    39FDTBSANKUWHPOGMLXZECIYJQVR
    40BAGLQWCIHVMDKYSTEXOPZJFRNU
    41NSKLOZURMPCDIAEJWHBVGTQYXF
    42XKTILNWVDRBEPFZMSJQCYHGAUO
    43KESOBWJLXGAHPTDMUZCNQYFIVR

  6. Decipher the entire message. You may need to find additional plugboard settings; if so, list the settings and explain how you figured them out.

    Hint: First decipher the letters that you are sure about, that is, those for which you've already determined the necessary plugboard settings. Now attempt to fill in the rest of the plaintext - you can try to guess a plaintext letter and then work out the necessary plugboard setting(s) to turn that letter into the known plaintext, or you can try guessing a plugboard setting and working that through to find a contradiction (or not) like you did in problem 4. Each time you find a new plugboard setting, use that to decipher as many other plaintext letters as possible.

    Hint #2: Filling in the rest of the plaintext can be tricky! Consider what you know about the topic of the message from the crib and any parts you are able to discover. If you can't decipher the whole message, write what you did decipher.


Imagine doing all this for every possible position of the crib, and for all 263 scrambler settings (and then for all of the different choices and orderings for rotors) - this is why the bombes were so important!


chris@cs.colgate.edu