MATH/CMSC 456, Section 0101
Cryptology

Spring 2010

Class, Exam, and Homework Schedule

(Updated due to Snow)

Unless otherwise stated, readings and exercises are from Trappe-Washington. "Additional problems" are at the bottom of this web page. Some problems are best done with a computer. You can use any language you want, but I'd recommend one of Mathematica, Maple, or MATLAB, for which some programs to help you are available. Please turn in your output so I can see what you used and how you got your answer. There are 11 homework assignments, each worth 10 points, and the lowest homework grade will be dropped. Effective with the 3rd assignment, homework will be marked down if late and will not be accepted after homeworks have been returned to the rest of the class.

After homeworks or exams have been graded and returned, (password-protected) solutions will be posted here.

WeekNotes ReadingHomework
Jan. 25 - Jan. 29 For more practice on substitution
ciphers, check out
cryptograms.org.		 2.1-2.4 due Mon., Feb. 1:
Feb. 1 - Feb. 5 Parts of Ch. 2 not explicitly
assigned are interesting, but
we won't cover them in class.
Shannon's classic paper on security
is available here.		 2.6-2.11 due Mon., Feb. 15
because of snow:
Feb. 8 - Feb. 12 The lecture schedule has been shifted
due to snow. Please finish studying
the material from Ch. 2 and read
these notes on Shannon's theorem. 		  none because of snow days
Feb. 15 - Feb. 19 Ch. 3 is the mathematical
underpinning of the course. Make sure
you know the basics!		 3.1-3.5 due Mon., Feb. 22:
  • 3.13, #1, 3, 4, 12, 18, 19, 40
  • 3.14, #1, 5, 6
Feb. 22 - Feb. 26 Discussion of Ch. 3 will
continue into the week of Feb. 22
because of snow days.		 3.6-3.10 due Mon., Mar. 1:
  • 3.13, #16, 22, 26, 27, 29
  • 3.14, #7, 8
Mar. 1 - Mar. 5 Exam #1 Fri., Mar. 5, on the
sections we've covered of Chs. 2-4.
For practice, see this old exam,
ignoring the questions on RSA for now.
(That will be on Exam #2.)
Calculators are allowed!		 Ch. 4 - 5 (Don't worry
about the technical stuff.) 		due Mon., Mar. 8:
  • 4.9, #2, 4, 6, 7
Mar. 8 - Mar. 12 Ch. 6 begins the serious use
of number theory in cryptography,
the heart of the course.		 Ch. 6 due Mon., Mar. 22:
  • 6.8, #1, 3, 5, 10, 14, 15
Mar. 15 - Mar. 19 Spring Break
Mar. 22 - Mar. 26   Ch. 7 due Mon., Mar. 29:
Mar. 29 - Apr. 2 Week of Passover and Good Friday
no written homework
a useful link on hash collisions		 8.1-8.4 none because of holidays
Apr. 5 - Apr. 9   8.5-8.7, Ch. 9 due Mon., Apr. 12:
  • 8.8, #1, 2, 4
  • 9.6, #1, 3
  • 9.7, #1, 2
Apr. 12 - Apr. 16   10.1-10.5 due Mon., Apr. 19:
Apr. 19 - Apr. 23 Exam #2 Fri., Apr. 23 on Ch. 6-10 10.6-10.8 none because of exam
Apr. 26 - Apr. 30   Ch. 16 due Mon., May 3:
  • 16.7, #16
  • 16.8, #1, 2, 3, 4
May 3 - May 7   Ch. 15, 18.1-18.2 due Mon., May 10:
May 10 Last class, review for the final exam
May 19 Final exam, 8 - 10 AM. To help you study,
here are a final exam from last year and solutions.

Additional Problems

  1. A familiar text was encrypted with an affine cipher to give the following ciphertext (broken for convenience into lines of 80 letters each):
    ulfihxlivzmwhvevmbvzihztllfiuzgsvihyilftsguligslmgsrhxlmgrmvmgzmvdmzgrlmxlmxvrev
    wrmoryvigbzmwwvwrxzgvwglgsvkilklhrgrlmgszgzoonvmzivxivzgvwvjfzomlddvzivvmtztvwrm
    ztivzgxrerodzigvhgrmtdsvgsvigszgmzgrlmlizmbmzgrlmhlxlmxvrevwzmwhlwvwrxzgvwxzmolm
    tvmwfiv
    Find the plaintext. If you want to use MATLAB, the M-files affinecrypt.m or substitution.m are useful. Why was this particular cipher easily broken?
  2. This problem illustrates the difficulty with the one-time pad (section 2.9) if the key is not really random. Suppose the plaintext and key are both sequences of n bits. Let the key be k1, ..., kn, and suppose the key is given by a two-step recurrence, so that there exists a function f (which Eve doesn't know) such that kj = f(kj-1, kj-2) for j > 2. How can Eve decode a given ciphertext?
  3. The prime p = 999999937 (= 109 - 63) has the property that p - 1 has only small prime factors. You can take for granted that α = 11 is a primitive root mod p. Use the Pohlig-Hellman algorithm to find L11(123456789). This problem illustrates that discrete-log systems based on primes for which p - 1 has only small prime factors are not very secure, even if the prime is reasonably large.
  4. Suppose Alice and Bob decide that Alice will send Bob a secret key K using the three-pass protocol of Section 3.6.1 in the textbook. Explain (in detail) how Mallory can mount a man-in-the-middle attack to intercept communications between Alice and Bob without their realizing immediately that something is wrong.
  5. Consider the elliptic curve E: y2 = x3 + 2x + 6 mod 53. First show that the point P = (4, 5) lies on the curve and has order 48. Then use Hasse's theorem and Lagrange's theorem to deduce that E has exactly 48 points with P as a generator ("primitive element"). What is the discrete log of Q = (1, 3) with respect to P? I.e., what is the smallest positive k for which kP = Q? The most efficient method is to use the analogue of Pohlig-Hellman, i.e., to find k mod 3 and k mod 16, and to put these together using the Chinese Remainder Theorem. For example, to find k mod 3, multiply both sides of the equation kP = Q by 16. Since 16P has order 3, there are very few possibilities to check. Similarly, to find k mod 16, multiply both sides of the equation kP = Q by 3. Since 3P has order 16, there are at most 16 possibilities to check. This problem illustrates that discrete logs over elliptic curves do not make for a secure cryptosystem if the order of the group has lots of small divisors.