MA 479 / CSSE 479: Cryptography
Homework 2 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, especially on multi-part problems.

  1. [2 points.] Use the Euclidean Algorithm or the Extended Euclidean Algorithm to decrypt the following message written in the affine cipher "15x+13" (multiply by 15 and then add 13). (Remember we are using "a" = 01 for affine ciphers.)
    JPFKR UWPKJ L
    Show all of the steps.

  2. [1 point.] Use Criterion 3 to prove that the additive cipher achieves perfect secrecy, if each key is used with probability 1/26. (Hint: this is a very easy problem. Plus, we did it in class.)

  3. [4 points.] Without using Criterion 3, prove that the additive cipher achieves perfect secrecy, if each key is used with probability 1/26. You will need to use the definition of perfect secrecy.

  4. [12 points.] Using the definition of perfect secrecy, prove that if a system satisfies conditions (a) and (b) from Criterion 3, then the system has perfect secrecy. (Obviously, you cannot assume Criterion 3 is true.)

  5. [12 points.] Using the definition of perfect secrecy, prove that if a system has perfect secrecy, then the system satisfies conditions (a) and (b) from Criterion 3. (Obviously, you cannot assume Criterion 3 is true.)


The following problems are from your textbook.

  1. [1 point.] Problem 4.9(a). Use the Euclidean Algorithm. Show all of the steps.
  2. [4 points.] Problem 4.10. Be very complete.
  3. [2 points.] Problem 4.11.
  4. [6 points.] Problem 4.12. Be very complete.
  5. [1 point.] Problem 4.13(a). Use the Euclidean Algorithm or the Extended Euclidean Algorithm. Show all of the steps.
  6. [2 points.] Carefully write up your answer to Problem 3.3 in the textbook. (This is the same S-DES example that you did most of in class.)
  7. [4 points.] Problem 3.7. Show all steps. (Note that there is a typo in the problem: the binary notation for hexadecimal C should be 1100, not 0100.)