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 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 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
- [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
- [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.
- [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:
-
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.)
- 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.)
-
Find the number of matrices whose determinant is even because all of the
entries are odd.
-
Use inclusion-exclusion to find the total number of matrices whose determinant
is even.
-
Find the number of matrices whose determinant is a multiple of 13 because
the first column is a multiple of 13.
-
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.
-
Find the total number of matrices whose determinant is a multiple of 13.
-
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...
-
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 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:
-
Let a be a number relatively prime to 26. Find a 2 by 2 matrix
with determinant a.
-
Show that your matrix has an inverse modulo 26.
-
Use your matrix to establish a pairing between matrices with determinant
1 and matrices with determinant a.
-
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.
The following problems are from pages 51–53 of your textbook.
- [2 points.] Problem 2.6.
- [2 points.] Problem 2.7. Be very complete in your description.