CS 4953 -- Cryptography
Homework 1
Due: Friday, 8 February 2002

 

 

The homework set, like the lectures, is based on the online lecture notes at the course web page: "The Laws of Cryptography".

  1. Exclusive-Or:

    1. What is a ^ a ^ a ^ a ^ a equal to for a bit string a?

    2. If c = a ^ b, then what is c ^ b ^ a equal to? (All are bit strings.)

    3. By any method, prove that

        
a ^= b;
b ^= a;
a ^= b;
      will interchange bit strings a and b in Java.

  2. Logarithms:

    1. Give code for a Java function log10 that will return the log base 10 of its argument.

    2. What is    blogba   equal to, where a and b are positive numbers?

    3. RSA laboratories recommends RSA keys with 1024 bits for corporate use, and with 2048 bits for the most valuable keys. Approximately how many decimal digits would a 2048-bit number be if converted to base 10?

  3. The integers mod n, Zn:

    1. Consider n = 10, the integers mod 10. Use ordinary addition and multiplication, followed by remainder on division by 10. Show that this doesn't work as a field because there are non-zero numbers without a multiplicative inverse, and there are non-zero numbers whose product is zero.

    2. Consider n = 11, the integers mod 11. Use ordinary addition and multiplication, followed by remainder on division by 11. (This really is a field.) Find the multiplicative inverse of each non-zero number.

  4. The Extended Euclidean ALgorithm:

    1. Use the Euclidean algorithm (by hand, pencil and paper) to find the greatest common divisor of 210 and 364.

    2. Consider the integers mod 29, Z29. Find the multiplicative inverse of 11 in the following way: use the extended Euclidean algorithm to find ordinary integers x and y so that x*11 + y*29 = gcd(11, 29) = 1. (One of the integers is positive and one is negative.) Then x taken mod 29 is the desired inverse.

  5. Entropy:

    1. Suppose messages X = {X1, X2, X3, X4} have probabilities p(X1) = 3/5, p(X2) = 1/5, p(X3) = 1/10, and p(X1) = 1/10. Find the entropy in this case. Use the Huffman algorithm to find an optimal code and calculate the average code length. Compare the two answers.

  6. ISBN Decimal Error Detection:

    1. Grab any random book. (Try not to have duplicates in the class, please.) Use the ISBN check and verify that the check digit is correctly calculated. (That is, just verify that the check equation is true.)

  7. Verhoeff's Decimal Error Detection:

    1. Use the combination of integers with the Dihedral group as shown in the section about Verhoeff's scheme. Verify that associativity holds for the three numbers 6, 3, and 8 that is, verify that (6 # 3) # 8 = 6 # (3 # 8).

    2. Verify that the group is not commutative by finding two numbers that give different results when combined in opposite order.

    3. Give the inverse of each element. (The inverse of x is an element y such that x # y = 0.)

Revision date: 2002-01-29. (Please use ISO 8601, the International Standard.)