MA 479 / CSSE 479: Cryptography
Homework 1 problems inspired by Mathematics

Rose-Hulman Institute of Technology
A joint effort of the
Department of Mathematics
and the Department of Computer Science & Software Engineering
Spring term, 2003-2004

All these problems are paper-and-pencil problems. Please do not use a (digital) computer when doing these problems. Calculators are okay.

You may turn these problems in electronically to the drop boxes or on paper. If you do your problems electronically, please use a proper equation editor rather than trying to fake the mathematical symbols!

Drop box submissions are due at midnight on the due date. Paper submissions are due in class or in the box outside my office by 5:00 p.m.

Show your work on all problems.

I will give some partial credit, esepcially on multi-part problems.

  1. [1 point.]
    The following text has been encoded using an additive cipher. Break the cipher and find the encryption key. Show all your work, including guesses, errors, and dead ends. (This includes a frequency table if you make one, or part of one.) You do not need to finish deciphering the message if you are sure of your key.

    Hint: recall that we claimed in class that you only need to get one letter right in order to find the key.

    IWTCI WTGTL PHPLX ASNTA EDUPV DCNPC SIWTE DDSAT LTCIH PXAXC VJEIW TPXHA
    TIWTN TAEHR DCIXC JTSPC SHDSX SIWTS DVWTR GDHHT SIWTW DJHTX CUGDC IDUIW
    TPAIP GWTUA TLSDL CIWTD IWTGP XHATW TRGDH HTSQT UDGTI WTSDD GHWTR APBDG
    TSJEI WTWDB THIGT IRWWX HPCVJ XHWVG TLLXI WWXHE GDVGT HHIXA AEGTH TCIAN
    WTLPH QJIPL DDAAN RDBTI BDKXC VXCXI HDGQX ILXIW IWTVA TPBPC SIWTH ETTSD
    UAXVW I
    

  2. [2 points.]
    The following text has been encoded using the affine cipher with key "9x+3". (That is, multiply by 9 and add 3 to encode.) Decipher the text. Show all your work, including guesses, errors, and dead ends. (Remember we are using "a" = 01 for affine ciphers.)
    EJYBF AWLEE FYVDF QWVIF YN
    
  3. [2 points.]
    The following text has been encoded using an affine cipher. Break the cipher and find the encryption key. Show all your work, including guesses, errors, and dead ends. (This includes a frequency table if you make one, or part of one.) You do not need to finish deciphering the message if you are sure of your key. (Remember we are using "a" = 01 for affine ciphers.)

    Hint: to find the key, you may want to look at the ciphertext letters corresponding to plaintext letters that are early in the alphabet, such as a and e.

    QBVDL WXTEQ GXOKT NGZJQ GKXST RQLYR XJYGJ NALRX OTQLS LRKJQ FJYGJ NGXLK
    QLYUZ GJSXQ GXSLQ XNQXL VXKOJ DVJNN BTKJZ BKPXU LYUNZ XLQXU JYQGX NTYQG
    XKXQJ KXULK QJNQN LQBYL OLKKX SJYQG XNGLU XRSBN XOFUL YDSXU GJNSX DNVTY
    RGXUG JNLEE SXLYU ESLYY XUQGX NSLTD GQXKB AVBKX JYYBR XYQNQ GXKXZ LNYBS
    LRPBA VLQXK JLSOB FNGLE EXYXU LSBYD XWXKF SJQQS XZGJS XQGXF RLVXQ BMXXK
    OTQKX VLJYX UQBZG JQXZL NG
    

  4. [1 point.] How many possible different blocks of 10 letters are there? (E.g. when considering a Hill cipher.) Express your answer as an approximate power of two.

  5. [12 points.] Find the number of different (good) keys there are for a 2 by 2 Hill cipher without counting them one by one. Remember that the determinant has to be relatively prime to 26. Here is an outline you may want to follow:
    1. Find the number of matrices whose determinant is even because one or both rows are even. (A row is "even" if both entries in the row are even.)
    2. Find the number of matrices whose determinant is even because one or both columns are even. (A column is "even" if both entries in the column are even.)
    3. Find the number of matrices whose determinant is even because all of the entries are odd.
    4. Use inclusion-exclusion to find the total number of matrices whose determinant is even.
    5. Find the number of matrices whose determinant is a multiple of 13 because the first column is a multiple of 13.
    6. Find the number of matrices whose determinant is a multiple of 13 where the first column is not a multiple of 13 but the second column is a multiple of the first modulo 13.
    7. Find the total number of matrices whose determinant is a multiple of 13.
    8. Find the number of matrices whose determinant is a multiple of 26 because they fit case (a) and (e). (b) and (e). (c) and (e). (a) and (f). And so on...
    9. Use inclusion-exclusion to find the total number of matrices whose determinant is neither a multiple of 2 nor a multiple of 13. You should get 157248.

  6. [6 points.] Now that you have the number of 2 by 2 Hill cipher keys whose determinant is relatively prime to 26, you can find the number which have determinant 1 as follows:
    1. Let a be a number relatively prime to 26.  Find a 2 by 2 matrix with determinant a.
    2. Show that your matrix has an inverse modulo 26.
    3. Use your matrix to establish a pairing between matrices with determinant 1 and matrices with determinant a.
    4. Now you know that there are the same number of matrices with determinant 1 as there are with determinant a, for every a which is relatively prime to 26. Find the number of matrices whose determinant is 1.
  7. The following problems are from pages 51–53 of your textbook.

  8. [2 points.] Problem 2.6.

  9. [2 points.] Problem 2.7. Be very complete in your description.