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)
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]
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, 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
(use without proof the following claim: [ M is not invertible iff det(M)=0 ] over F q )
A 2x2 matrix M which is not invertible over Z26 but such that det(M)>0 over Z26.
Hint : read page 16 of Stinson’s book.
AUTHENTICATION CODES and finite fields
You are now asked to setup an authentication code over F2 1000.