Homework Assignment 2   --------- Fall 2009
              ***due April 13        ***


   Do either Unit 1 OR (don't do both)  Unit 2. Each is worth 33 points
   when all problems are done correctly.



   Unit 1*** ....
   
   be sure to show all work

   1. The random variable X takes the integer values 1,2,3,...,N
      with equal probability. The random variable Y is defined by
      Y = 0 if X is even, but Y = 1 if X is odd.  Calculate

         H(X|Y) and H(Y|X) 


   2. In this problem let a = 100   ( x^2 ) in GF(2^3) with

      r(x) = 1011    ( x^3 + x + 1)

       a) show that  a's inverse is (100)^6 mod r(x)

         
       b) find the inverse of b = 011 in this field.


  3.  a) Prove for the CBC mode of encipherment that

               D(E(M)) = M


  4.  Randomly generate 5000 odd composite numbers between 100,000 and 
      200,000    

      Run the Solovay-Strassen test one time on each number. What percentage
      are able to past the test?

      Get code for test from link below *****

     Unit 2 *****  
     

   1.    Determine the gcd of the following pairs of polynomials:

      a)  x^5 + x^4 + x^3 - x^2 - x + 1 and x^3 + x^2 + x + 1 over Z/3.

      b)  x^7 + x^5 + x^3 + 1  and x^5 + x^4 + x + 1  over Z/2

      c) Determine the multiplicative inverse of x^3 + x + 1 in GF(2^4)

         where p(x) the reducing polynomial is x^4 + x + 1.

                                               15 points

   2. Download and compile the

    i)     entropy  computing program


      ii)   run the program on the file testinga  and check by hand to make sure the answer is correct for 2-gram entropy. 
  Show your  hand calculations 

     ii)  using the program calculate the 8-gram entropy of 
 the song lyrics "I Kissed a Girl" and

          the random file . 
          How do the entropies compare?
     
     iii)  Now compute the 8 gram entropy of the song lyrics by using a program
          which only computes with substrings representing test characters.
           Use  fEntropy.C 

    3.            Do a statistical study of the S-box below


               0   1   2   3

            0  11  2   7   12 

            1  1   15  0    8 

            2  14   4   5   9

            3  6    10  3   13

            four bits input and four bits output. First two (leftmost)
            bits determine row and second two determine column.

            Can your statistical tests discover biases? 
            Is this an affine S-box ?
            Tell me as much as you can. Best responses get the most
            points - others get less.

            here is  C code  by a former student.
            which analyses the above S-box. If you use it then you are
            obligated to improve it in some manner. Part of the solution
            will be your improved code. Describe how you have improved
            the analysis.                 

       4.   Randomly generate 5000 odd composite numbers between 100,000 and 
            200,000    

            Run the Solovay-Strassen test one time on each number. 
            What percentage are able to past the test?

            Get code for test from link below   ***********


             Primetime.c   or

             primenumbers.c