CS547A 2001 Homework set #2

Due Monday October, 22 2001 in class at 13:00 SHARP

Exercises (from Stinson’s book)

1. Decrypt the following cipher:

JCWEH SNDFS BNJIV TEAGV DHOCQ QIQFR PHFKQ

EARFQ ARFAH FQEJC BNJNH BEOCB NLNOV HBLFQ

JBNAB LFVHC AJIVB NWNST BLEAG VAJNS RFWNS

YRVSS CAEHV AQFCJ EAGJN AWNSO VBVCQ YDCSP

HEHOC SPEAG BEONA FRLCA GNEAK CSONS HACBE

FACQX

It is one of the ciphers described in Section 1.1 of Stinson.

Use the techniques described in Section 1.2, keeping a log

of the methods you used: how you were able to determine

the cipher method, how you were able to find the key, etc.

Just giving the decryption of the above cipher will not earn

much credit.


Exercises (Home made)

  1. Consider the following two sets of hash functions on m bit inputs:
  2. H0 = { h(x) = (x+ b)M |M is an mxn binary matrix and b is an m bits string }

    H1 = { h(x) = (x +b)M | M is an mxn binary invertible matrix and b is an m bits string }

    For each of these two sets prove whether or not they are Universal2 classes of hash functions. Here, the product z of a bit vector v with a matrix M is done by apply the * (AND) operation bitwise and then the + (XOR) operation on the results. ( zj = i vi * Mij )

    For example (10010) [010] = ( 0+0+0+1+0 , 1+0+0+0+0 , 0+0+0+0+0 ) = (110).
                                           [111]
                                           [001]
                                           [100]
                                           [101]

  3. MAPLE™ 7.

HILL CIPHER

Extend the alphabet used in the Hill cipher with three new symbols: " " (spacebar), " ." (dot), "," (comma) to improve readability of texts. We encode these new symbols numerically as 26 (" "), 27 ("."), 28 (","). We now consider the Hill cipher with an alphabet of 29 symbols (instead of 26) and thus perform all operation mod 29.

  1. Using MAPLE™ decrypt the following ciphertext c encrypted with matrix K

          [1, 2, 3, 4]
K : = [2, 3, 4, 0]
          [3, 4, 0, 0]
          [4, 0, 0, 0]

c: =
23 06 16 08 12 10 26 18 20 21 13 14 22 04 27 18 25 07 06 24 21 20 16 18 17 08 02 23

  1. Using MAPLE™ find the number of invertible 2x2 matrices over F29.
  2. (use without proof the following claim: [ M is not invertible iff det(M)=0 ] over F q )

  3. Give an expression for the number of invertible nxn matrices of F29.
  4. Using MAPLE™ find a counter-example to the above claim over Z26:
  5. A 2x2 matrix M which is not invertible over Z26 but such that det(M)>0 over Z26.

  6. Using MAPLE™ find the number of invertible 2x2 matrices over Z26.
  7. Hint : read page 16 of Stinson’s book.

  8. In the light of the above questions, explain why I changed the alphabet size to 29?
  9. AUTHENTICATION CODES and finite fields

    You are now asked to setup an authentication code over F2 1000.

  10. Using MAPLE™ find a random irreducible polynomial P of degree 1000 over F 2 .
  11. Build the field F2 1000with the irreducible polynomial P found above.
  12. Find a primitive element g of F21000 . HINT: 21000 -1 =
    (31*601*4710883168879506001*269089806001*1801)*
    (3*11*251*229668251*5519485418336288303251*4051)*
    (54 *94291866932171243501*268501*28001*96001)*
    (41*101*47970133603445383501*3775501*7001*8101)*
    (17*61681*401*3173389601*2787601*340801)*
    8877945148742945001146041439025147034098690503591013177336356694416517527310181938001
  13. Pick two random elements (i,j) in F21000 .
  14. Tell us x,y, 0<= x,y <= 2 1000-1 such that gx=i and gy =j .
  15. Pick a message m of 1000 bits that you like and calculate the corresponding tag t made of the 50 least significant bits (the coefficients of the terms of degree less than 50) of m*i+j over F2 1000. (no credit question: tell us why you like m.)
  16. Send us (P,i,j) and (m,t) via e-mail to cs547@cs.mcgill.ca before this HW deadline.