Assignment 4

Due Tuesday, July 17, in class

Recommended reading (from Stallings, unless otherwise stated):

• PKI in general: Austin, Chapters 1-3
• Modular Arithmetic: Sections 7.1, 7.2
• Fermat's Theorem, Euler's Theorem, and the phi function: Section 7.3
• Euclid's Algorithm: Section 7.5
• Hashing: Chapter 8 (this also includes Message Authentication Codes, which we'll discuss next week)
• Digital signatures: an article from Bruce Schneier's Crypto-Gram

1. (15 points) Write a program that takes two integers a and m as input and outputs their greatest common divisor. If the gcd is one, your program should also output a^{-1} mod m (i.e., a number b such that ab = 1 mod m).

   Notes:

   • You should be able to base this on your code from last week.
   • As before: you may use any language you like, but we need to be able to run your program on the department UNIX machines. Use hwsubmit to turn in your code.
   • Please test your code. Make sure it runs on the UNIX machines. If we can't get your code to compile, we can't give you any points. Make sure to test your code on large integers.
   • You should use the extended version of Euclid's algorithm for the computation. Pseudocode was discussed in class, and appears on the bottom of page 224 in Stallings.
   • As always, you can use built-in functions to check your answers, but don't call them in the final version.
   • Your program should take numbers from standard input (the keyboard) and write to standard output.

2. (Due Tuesday, 7/24) (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'm working on 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.
   • Don't wait for the last minute to do this assignment. There will be more homework assigned next week for July 24. I'm giving you the extra time because I don't want to see rush jobs.

   Problems 3-5 should be submitted in class, July 17, on paper.

3. (5 points) Stallings, Problem 7.8.
4. Let f(n) be the sum of phi(d), summing over all divisors d of n. For example, f(6) = phi(1) + phi(2) + phi(3) + phi(6) = 1 + 1 + 2 + 2 = 6. (We define phi(1) = 1.)
   1. (5 points) Compute f(n) for n = 2, 3, ..., 10, and conjecture a formula for f(n) in general.
   2. (15 points extra credit) Prove that your formula works for all n.
5. (10 points) In class, we discussed the Birthday Attack on a hash. This attack is also discussed on pages 256-257 of Stallings.

   I have written a simple hashing program, called hashme. You can download hashme, or just run it on the UNIX machines by typing ~kutin/hashme. This program hashes a line of text, and returns an integer between 0 and 63.

   Do a birthday attack on this hash, and find two different messages that hash to the same value. Indicate what inputs you tried, and how long it took you to find a collision.