Assignment 3

Due Tuesday, July 10, in class

Recommended reading (from Stallings, unless otherwise stated):

• Modular Arithmetic: Sections 7.1, 7.2
• Euclid's Algorithm (see below): Section 7.5
• Big Oh Notation: Appendix 6A
• DES: Chapter 3
• Triple-DES: Section 4.1
• AES: The AES home page

1. (20 points) Write a program that takes two integers as input and outputs their greatest common divisor.

   Notes:

   • 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.
   • You should use Euclid's algorithm for the computation. There is a discussion of the algorithm in section 7.5 of the Stallings book; pseudocode appears at the top of page 224.
   • There is a built-in gcd function. You can use it to confirm your answers, but please don't hand in code that calls it.
   • Don't forget: you need to handle large integers, using BigInteger or some equivalent. Euclid's algorithm is fast enough that you can test it on 200-digit numbers.
   • Your program should take numbers from standard input (the keyboard) and write to standard output.

   Problems 2-5 should be submitted in class, on paper.

2. (5 points) Stallings, Problem 7.2.
3. (15 points) Problem 7.10. Note: On part (a), the problem should read: Suppose that m = qn + r with q a positive integer, r a nonnegative integer, and 0 <= r < n. Show that m/2 > r.
4. (10 points) Problem 3.12.
5. (10 points) Recall from class that Deep Crack can recover a DES key in an average of 4 days, by checking roughly 92 billion keys per second. You ask a friend how to make DES more secure, and your friend suggests making one of the following two changes:
   1. Increase the number of rounds from 16 to 32.
   2. Increase the number of key bits used from 56 to 64.
   How long would it take Deep Crack to attack each modified version? (For extra credit, you can discuss the effects of these changes on differential and linear cryptanalysis.)