Name(s)                                                                                          :
Math 390 Cryptography Exam 1
March 6,2001
This part of the exam may be done in your groups. You may use your text, notes, computers, whatever, but the work you submit should be your own (or your group's). Basically you can use whatever tools you desire, except other people's brains. Turn in one copy per group.
  1. (10 points) Decrypt the following, showing your work. All these ciphers are substitutions (monoalphabetic) of some form.
    1. FXIABGUROEFXCYMGBFXIAFILAOBDFXIABGUNROMIADVCPIBTEFXIUCBDRGGMIDTROYMCBF

      2. XIXIODRCSXFAGNFXIYOV
    2. VUJ QJEGVD YH EV ETI SPP EMJUEIHYO KSNEVTYSP XVHHYWPJ HBWHEYEBEYVUH EGSE YH PYHE SPP EGJ XVHHYWPJ MSIH EGSE VUJ PJEEJT NSU WJ TJXPSNJD WI SUVEGJT PJEEJT VK EGJ SPXGSWJE SUD VUNJ IVB GSAJ DVUJ EGYH DJNTIXE EGJ QJHHSRJ

      3.  

       

  2. (5 points) A novice at encryption uses the affine cipher f(x) = 8x + 13 to encrypt "not ideal" (remove the space).
    1. What is the result.
    2. List several other plain texts that give the same cipher as part (a). Your plain text need NOT be English. Can you find another decryption that is English?

      3.  

       

  3. (20 points) The message below was encrypted with a combination of techniques we've seen thus far in class. For starters the text was written out in the same fashion as an m x 3 block transposition cipher. Column 0 (i.e. characters 0, 3, 6, 9, 12, ... of the plain text) was encrypted with a shift cipher, f(x) = x + k mod 26. Column 1 (characters 1,4,7,10, ... of the plain text) was encrypted with an affine cipher, g(x) = a*x + b mod 26. Column 2 (characters 2,5,8,11, ... of the original message) was encrypted with a keyword substitution cipher (cryptogram). However, unlike the m x 3 block transposition cipher, this message was simply put back together the same way it was written out (read the rows instead of the columns). Thus, the cipher text characters are in the same positions as the plain text characters from which they came. Decrypt this message. You should try to decrypt column 0 first, then column 1, and finally column 2. I would guess that you'll need to rely quite heavily on single letter frequencies for much of this problem. Here is the cipher text:

    4.  

     
     
     
     

QWRHJEZSOZXTUWPGOCFEBONTTQDFKTOJXWDTFOXOJNGSOZXTUWETLPZEEHWSKENVNJSJTT
QYAWSQPDFSJWBEAWYWSEWBNSJRONPCBEZYNIHWDJOUJEAYTGNEPXPGPTRYPBSTWBMZCSSX
OBHOBORRWAGWLSBHZORRLYOBMSODGNYWOADOPBMTLEMCGEZWAOBSHPTBWNVWYZORRYUWNJ
OBPBYNWNDHEOBOXSMCVOAWYPBSYCYAQCXHCYOXAHCSMBTOJX



 
 
 
 
 
 
 

  1. (15 points) The cipher below was encrypted using a permutation, say f, from S10. The plain text was cut up into chunks of 10 characters; the first 10 chars, the second 10 chars (or chars 11 to 20), the third 10 chars and so on. Gibberish was added to the end of the plain text, if the original message did not have a number of characters that was an even multiple of 10. A random integer, say n, from 1 to the order of f was selected. The first block of 10 characters was encrypted using the anagram (shuffle, or permutation) fn (f repeated n times, or shuffle with f, shuffle that with f, shuffle that with f etc. until n shuffles were completed). The next block of 10 characters was encrypted with the anagram fn+1, then fn+2 was used on the next block of 10 characters, and so. Note that if the order of f is k, then applying f  "p times", is the same as applying f  "p mod k" times. For example, if f has order 3, then f5 = f2 (since each application of fk does nothing). Here is the cipher:
KRSIFWTOERHREEISTHESITLOOFROUNSOFOIPSERNAWPLABHGERICSDESIGNAORDTDCINPU
SETIHOTINFDSURIPCRTOTIONENVIROTNMVTOENEOTSMOERHECPAILCELLCAHENGESFACIN
GBWHRPIGEAGRSEECNIDSUDCNAREOPDRSUSEFIREWTSRSOEIOKDTLDEBGAINEHBIEWRCAGP
SANDANIMATFSOWIEOINRMNCSIRBOKETOMBSHABTIPANDVECTORITDONTOEIGIWNIELRFSO
YSTKRVHEERINGISEDITALALELHTBETDUAEOIYNMCAATNATEOUMTHEWORKFLOEMTHETEWOT
DFAMODSNEEATTIDUEPSDSANDCHANGEERFKWRSSIOREETTIAGNSRTOIWMMAHCEDIAPRODUC
CUSMHSATSADDMOACIERREMRAEEAAWVNDFLASHASWSALEOHRELTIGOVEFTRARPHPPACLSIA
ICATIONSANLMHTEIODTDRIOTVROPSDNTTAEUEERIGRATEDWEBSITLOOYUOUNSYENLCIAAE
ROEPXTWFRIORKSGRAPHITISMHTLCWHVCJDSAAANRCTUPIOSDCETOMIZEDFORTHHDMEITEL
UEYRRTAOOU
    1. Explain why, every so often, the cipher will contain blocks of plain English.
    2. Use the frequency (or pattern) of these blocks of plain text to determine the order, say p, of f.
    3. How many elements of S10 are there with order p? Describe the different forms (in terms of cycles) these elements can have. How many of each form are there? Would it be reasonable (from a computational time perspective, i.e. would we still be alive when the program finished running) to search through all of these?
    4. The anagram f (that is f to the first power) is applied to every block that immediately follows a plain text block. Likewise, the permutation f -1 (the inverse of f) is applied to every block immediately preceeding the plain text blocks. Explain these facts (why are they true) and use them to find both f and its inverse. Write both in disjoint cycle notation.
    5. Write out all (different) powers of f in cycle notation.
    6. Decrypt the message above.