CSC 290: Cryptology 2003: Exercises

Enigma in foreground, English bombe in background.

---

Programming Exercises

Plato thought that certain natural gifts were required for the pursuit of learning. He stressed that anyone seeking wisdom in this way should be aware `how many subjects there are to study, how much hard work theyh involve, and how indispensible it is for the project to adopt a well-ordered scheme of living.'

--Anthony Gottlieb

An expert problem solver must be endowed with two incompatible qualities -- a restless imagination and a patient pertinacity.

-- Howard W. Eves

---

I recommend you use the computer language you are most proficient in, given it has adequate non-numeric facilities. I like PERL and Matlab for these exercises. Both offer "one-liner" capabilities for otherwise messy operations on strings and arrays, and both have an interactive interpreter. By no means do you have to be expert at either of these languages: Matlab has particularly good on-line help, and I did all the PERL work for my versions of these assignments with the manual in my lap. In general don't forget the Homework Helper page. What I'd like to see handed in (presumably through the WebCT mechanism) is the following.

  1. Well-organized source code.
  2. A complete Readme file (manifest, interfaces, functionality, example sequences of operations, sample results, etc.
  3. A further write-up, presumably in PDF, giving your main results, perhaps for this case ciphers you broke, passwords you found, etc. Here are some guidelines for the format and my expectations for these reports. Simply describe your work to an audience that knows the context (don't need stand-alone explanations of concepts etc.). As your work gets more advanced and the techniques more difficult you may need to say more to describe them and how you orchestrated your solution. When you write software, describing its motivation, methods, validation and use always takes more space than you think.
  4. Always welcome are graphs or charts.
  5. What did you try, what did you learn, what is original or unusual about your work?

For all of these exercises, hand in your writeup in PDF through webCT and hardcopy of everything to the prof.

Here are the exercises:

  1. Substitution and Various Attacks Substitution
  2. Vigenere: Kasiski and Friedmen Attack: Vigenere
  3. RSA Public Key and Factoring Attack: RSA public key cipher
  4. Unix Passwords and Dictionary Attack: Dictionary Attack
For these topics, assume your audience knows the subject, so you don't need to do a lot of elementary explaining about what the technical terms mean or what the algorithms are, etc. etc.

Cryptanalytic Exercises

This kind of work, particularly in the early stages of a difficult cryptanalysis, is perhaps the most excruciating, exasperating, agonizing mental process known to man. Hour after hour, day after day, sometimes month after month, the cryptanalyst tortures his brain to find some relationship between the letters that hangs together, does not dead-end in self-contradiction, and leads to additional valid results. "Most of the time he is groping in the darkest night," one solver has written. "Now and again a little flicker of light gleams accross the darkness, tantalizing him with a glimpse of a path. Hopefully he dashes to it only to find himself in another labyrinth. His knowledge that night is inevitably followed by day keeps his waning courage up, and he steers his course towards where the morning sun is soon to appear. Except that sometimes he is engulfed in an interminable polar night."

-- David Kahn

---

For all of these exercises, hand in your writeup in PDF through webCT and hardcopy of everything to the prof. The writeups have the same spirit as those for the programming work. They should be as long as necessary, as short as possible. Some of these reports will be mere placeholders (for the Zurbian Rotating Grill exercise there is almost nothing to say, I think). Others might be a few paragraphs (how you broke a simple substituation cipher and what capabilities you think might be useful in general) to a few pages.

  1. Aristocrat Substitution Cryptogram.

    You've been handed some aristocrat cryptograms (simple substitution, word divisions and punctuation preserved). At this point we have not discussed how to solve these in class. Do it anyway, recording in a TR-style manner the methods you used, looked up, invented, or think might be useful. Attach all extra "scratch", intermediate, hand-written work you do.

  2. Rotating Grille . FYI, the prof did this in thirty minutes. Nothing to hand in here but the answer (decrypts and the grille), along with all your intermediate work, scratch paper, scribblings, etc.

  3. Autokey Cipher

    Here's my idea for the equivalent of one-time-pad, infinitely secure encryption. Start out with Vigenere of some key, but instead of repeating the key, substitute in the plaintext instead of the key repetitions. No key period, cipher varies with each message, never repeats, completely secure! So the situation could look like:

    Autokey: COMETSENDSUPPLIESTOMORLEYS
    Plain: SENDSUPPLIESTOMORLEYSSTATI
    Cipher: USZHLMTCOAYHIZUSJESKGJEERA

    Or somesuch. How about that? Assignment is to outline as many weaknesses and resulting attacks on this cipher as you can. HINT: This is NOT the equivalent of a one-time pad. If things were that simple, the field would have been over in 1577 instead of 1977! There are exploitable weaknesses: what are they?

    Variant. If I wanted to be really clever, why wouldn't I use the emerging cipher itself as a key? Is that devious or what? MWAH-Hah-hahhaha! Something like

    Autokey: COMETUSZHLMTCOAYHIZUSJESKGJEERA
    Plain: SENDSUPPLIESTOMORLEYSSTATI
    Cipher: USZHLOHOST....whatever
    So analyze this idea too. Turn in the usual nicely-written and formatted page or two of thoughts on this problem.

  4. Hill's Cipher.

    You may well want to use the computer to help with this assignment, or possibly it's just fine as a written exercise. Especially if you want to try the 5x5 case.

    The following plaintext is encoded with Hill's cipher, using a block size of 2.

    Here is known plaintext and resulting cipher.

      CENTRAL TO OUR FEELINGS OF AWARENESS IS THE SENSATION OF THE
      PROGRESSION OF TIME*
      

      GKGZRRE XC QLC JNPAVIYQ TY WSRIREWOA IL ELP WAFXTMWKB PY RLP
      GXUAVZKCWKB PY RUGQC*
      

    Here is the cipher to be solved. Use the known plaintext to to construct the inverse of the key matrix.

      AE LEDS TM DOIMNL QEHUKB TOTELLKO OKBU UHMYWO TBOS BBWHFMCQJH
      NA EFPAUIZK UQLPVZ LWAOLE ZUVM MAAHVM VJME MU SS QENOVIHK JD
      BBQT KORVRR DVHVVZ NA ZVLPVZ TM LW SZICJB TY AH HKYW AH XQQCDR
      AS AHTM DKKM VJRV SKGUKSTMWO EMAH AH PAZY NCRI HV FF NNYRVMBPBO.
      'ZQPANA' - GJVMOY DDDLWO*
      

    Rather tougher, strictly for extra credit. Same thing again! Hill's Cipher, with block size 5 this time. That means you are looking for the inverse of a 5x5 matrix. First you need to write a modular matrix inverse program, (I'd use the adjoint method), and then you may have to try several choices of encrypt-decrypt 5-tuples before you find five pairs that give you an invertible matrix. If you want to try this and remember your adjoint method, don't panic, it's in all linear algebra texts (and Mollin's Cryptography book, for that matter).

    Here is known plaintext...

      JE VOUDRAIS QUE MON AMOUR MEURE
      QU'IL PLEUVE SUR LE CEMETIERE
      ET LES RUELLES OU JE VAIS
      PLEURANT CELLE QUI CRUT M'AIMER
      1948 S. BECKETT
      

    and its encipherment...

       QHDIU URAAS  OYEAO HUUIU SBPLR
      'HDNTL TETPV  SOWCL AWUQE AHZVE
       EAHWS LUAWL  NJRDJ ZVAAS
       PAPLR MMZGE KZOKU OGENT 'KYYQE
       1948 . QZHGC CSOVC
      

    Here is the cipher to be solved. This

      ESUYYOGOGTQJFNNDAVKW
      GYLFEKRVRNDKDZHQIVPEQQDAHSOLRE
      QXQMUKYMIRMMERAOGTBNIWYNF
      VRDQEIWYNFTPIIREGYLFODZVN
      OIPBTLTSOIBOBTGKCJRN
      
      GDRTEGGEASZGZVEZRELEENJHDVNAUI
      SAHLEFSKYYCAWWEPKTFTGPLLIXKELEIQMBN
      SMUNFNUMZTBUDZH
      UGVSAERODVAWDWSJUUSOKFFCO
      KTATTMYJFSPPCZH
      XDKSAWKQMBNJHXTMTEQMEMERNYSHZH
      DEFGH
      

  5. Mystery Ciphers! Your choice of two for credit, one for fame! Look them over and pick one to work on for credit and if you like, go for the glory as well. First is Diplomatic Code: Transposition? FYI, the prof has spent a lot of time on this, has discovered some things, but hasn't really found a way in. Many heads are better than one, so he won't say more here. If you can break the cipher or not, detail your thinking, attempts, and discoveries in a TR-style If you want to form teams , that's fine, just make sure your writeup details who did what.

    Second is an Original Cipher used for an encrypted part of a document in the prof's past.

  6. Extra Opportunity for Fame! This is the cipher that stumped E.A. Poe, handed out in class. Here's The Story.

Textbook Exercises (names: TX)

Speculations apparently the most unprofitable have almost invariably been those from which the greatest practical applications have emanated.

--John Herschel

---

  1. T1: 1.1.05, 13,15,16. 1.2.04, 10,13,15,17,21,22,23 (worth 2) 1.3.04, 07 1.4.04, 07, 10, 11,14,19,20,21 Appendix 1.05, 06, 07,10, 11,12,13,14
  2. T2: 2.1.02, 04,07,10,11,12 2.2.01,03,06,08,10,11,12,14 (worth 3) 2.3.01, 02,03 2.4.02,03
  3. T3: 3.1.01 (use your substitution crypto tools!), 04 3.2.01, 03, 06, 09 3.3.01, 03, 06,08, 10, 12 (and why?) 3.4.01, 02,07, 09,10 3.5.01, 04,05
  4. T4: 4.1.01,06,07 4.2.07,10 4.3.01, 03, 04, any two of 06,07,08,09,10 4.4.07,08,10,14 4.5.01, 02, 05, 06. (6.0.01, 02, or 03 -- pick one) (6.2.01, 02, 03 -- pick one)
  5. T5: Appendix 3.01, 3.05, 3.07 Appendix 4.01, 4.03, 4.05, 4.06, 4.07 7.1.03,07,08,11, 14, 17, 19 (worth 2), 20 (worth 3). 7.2.04, 08, 12 (famous proof!) 7.3.01,04,09
  6. T6: 7.4.04,10 7.5.04 7.6.01,03 7.7.04, 06,09,11, 13, 14, 17,20 (note misprint (he means "sub zero", not "sub <=") this is a -- famous Victorian method of checking your arithmetic!), 22. 7.8.01,09,12,13. 8.1.01, 02 (good warmups for the cryptanalysis problem!). 8.2.02 (worth 2)

    The Cocoanut problem: Three sailors are shipwrecked on an island where they find a monkey and a lot of cocoanut trees. They pick N nuts for a food supply and put them in a pile. During the night, the most distrustful sailor sneaks up and takes his fair share by dividing the pile into three and hiding his third. There is a nut left over, which he gives to the monkey before going back to sleep. Each of the other sailors does the same thing: divides the remaining pile into three, taking and hiding his third, and giving the lone remaining nut to the monkey. In the morning the 3 sailors meet, divide the remaining pile into three, each taking his third. Surprisingly, there is a nut left which, believe it or not, is given to the monkey. What is the minimum number of cocoanuts that could have been in the original pile?

  7. T7: 9.1.02, 04 9.2.01, 02, 05, 06, 08 10.2.01,04, 10.4.01, 02, 03.
  8. T8: 12.1.05, 07, 08 (worth 3) 12.4.01 (worth 3), 04 12.5.01,05,09,10, 12.6.06 12.7.04
  9. T9: 16.01.06,07 16.02.01,04(worth 3) 16.6.02 24.1.02 24.2.02 24.3.02
  10. T10: 13.1.01 13.2.01, 06 13.3.01, 03, 06,07 13.4.01, 06(worth 3) 13.5.01 (worth 3), 02 (worth 3) 13.6.01 13.7,01, 03, 06 13.8.01, 05, 09
  11. T11: 21.3.01, 21.3.03, 21.4.01, 21.4.02, 21.4.04, 21.10.01, (21.10.04 or .05 ... worth 3), 21.11.02.

    ---

    This page is maintained by CB.

    Last update: 29.07.01.