Assignment 5

Due Tuesday, July 24, in class

Recommended reading (from Stallings):

• Fermat's Theorem, Euler's Theorem, and the phi function: Section 7.3
• RSA: Sections 6.1 - 6.3 (particularly 6.2)
• Hashing, MACs: Chapter 8
• Birthday attacks: Appendix 8A
• HMAC: Section 9.4

1. (due Friday, 7/27) (20 points) Write a program that takes three integers a, b, and m, and outputs a^b mod m.

   Notes:

   • You know the drill: Test your code. Make sure it runs on the UNIX machines. Make sure it works on large (e.g., 100-digit) integers. Use any language you like, but don't use a built-in exponentiation function. Take input from the keyboard, write to standard output. Use hwsubmit to turn in your code.
   • You should use some form of repeated squaring. (Your code should run in a reasonable amount of time even when b is very large.) The technique is discussed in Section 6.2.
   • One version of the pseudocode appears in Figure 6.7, on page 177. Another version is in exercise 6.13, on page 202 (except that "odd(e)" should say "odd(E)"). This second version is the same as the one I discussed in class. You may use either of these approaches, or some other equivalent approach.

2. (35 points) Write a program that takes a string as input, encrypts it with DES, and writes the key to a file and the ciphertext to a second file. Also write a program that reads the key and ciphertext from the files, decrypts the message, and outputs the correct version.

   Note:

   • If you wish, you can write your own DES code. It's probably much, much easier to use a standard package. Ian has come up with some hints on how to do this in java, and I've written up some hints on how to do this in python.
   • You can hardcode the file-names for the key and for the ciphertext. You can make encryption and decryption two different programs, or one program (ask the user which he/she wants to do, or read from the command-line). Whichever is easier for you.
   • Yes, I'm asking you to store the key in a file. Yes, this would normally be a bad idea. We'll fix it in a later assignment.
   • You should use the same language for all your assignments from this point on. We'll be combining this assignment with the math code. You could use CORBA to combine different languages, but you don't want to.
   • The usual rules apply: test your code. Make sure it runs on campus. "Input" means the keyboard. Turn in your assignment using hwsubmit.
   • It would be nice if you could generate a random key, using the built-in software, but that'll only be worth a few points. Feel free to hardcode a key until you have everything else working.
   • This is different from the other programming assignments so far. You don't have to think about algorithms; someone else has already done that. You need to interface with existing code. If you do that right the first time, the whole assignment could (in theory) take 15 minutes. But, in practice, it could reasonably take hours to work out exactly what to do. In the real world, if someone asks you to write code implementing cryptography, you'll use a pre-existing package, so this is a useful skill.
   • If you have questions, post them to the list. If you have answers, post them to the list. I appreciate people who post good questions, and people who give correct (or mostly-correct) answers.

   Problems 3-6 should be submitted in class, July 24, on paper.

3. (5 points) Stallings, Problem 6.2c.
4. (10 points) Problem 6.4.
5. (5 points) Problem 6.6.
6. (10 points) We said in class that repeated squaring is a polynomial time algorithm: given integers a, b, and m, we output a^b mod m in polynomial time.
   Consider repeated squaring without the mod: given integers a and b, we output a^b. Is this polynomial time? Justify your answer.