CS4180 Network Security: Homework 4

This homework is due at the beginning of class 19 on November 9, 2000. Note: K2.3 denotes homework problem 3 from chapter 2 of the class text.

  1. Write a C(++) or Java program that computes exponents efficiently, using the mechanism described in the text. Your program should be able to deal with base and exponents of up to 32 bits and modulo value of up to 32 bits. Make use of the long long 64-bit arithmetic found on most modern machines. Your program should take base, exponent and modulus as arguments, such as
      exp 45678 123 6789
    Hints: use strtoll() for conversion from text to binary and printf("%lu",...) for printing. (16 pts.)
  2. Write a C(++) or Java program that converts between composite and common form, using the Chinese Remainder Theorem. Your program should take the number(s) and modulus as pairs of inputs. I.e.,
    crt -d 2 3 5
    converts the number 2 in modulo (z1,z2) = (3,5) = 15 to decomposed representation and
    crt -s 2 15 3 7 6 8
    converts the number (2,15), (3,7), (6,8) to standard representation. Note: The two examples do not represent the same number. (16 pts.)
  3. Using bc, compute a shared key using Diffie-Hellman key exchange. Assume p is 261-1, g is 23489. The secret numbers SA and B are 10480 and 15011. (8 pts.)
  4. (K5.2) In RSA, is it possible for more than one d to work with a given e, p and q? (8 pts.)
  5. (K5.3) In RSA, given that the primes p and q are approximately the same size, approximately how big is Ø(n) compared to n? (7 pts.)
  6. (K6.1) If m and n are any two positive integers, show that m/gcd(m,n) and n/gcd(m,n) are relatively prime. [Hint: use the result of Euclid's algorithm.] (8 pts.)
  7. (K6.2) If a and b are relatively prime, and bc is a multiple of a, show that c is a multiple of a. a, b and c are in Z. [Hint: use the result of Euclid's algorithm.] (9 pts.)
  8. (K6.7) For what type of number n is Ø(n) largest (relative to n)? (7 pts.)
  9. Implement Euclid's Algorithm in C(++) or Java. Output the multiplicative inverse, the gcd and the linear representation of the gcd (e.g., gcd(x,y) = ux + vy). Test with the examples given in the book (p. 167 and p. 168). (20 pts.)
  10. (Extra credit) Show that the relationship on pg. 133 holds, i.e., xy mod n = xy mod phi(n) mod n. (10 pts.)

Last updated by Henning Schulzrinne