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)

- Consider the following two sets of hash
functions on
**m**bit inputs: .__MAPLE™ 7__

**H _{0}**

**H _{1}** =

**For each of these two
sets prove whether or not they are Universal _{2} 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.
( z_{j} = ∑_{
i} v_{i}
* M_{ij}
)**

**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.**

**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**

- Using
**MAPLE™**find the number of invertible**2x2**matrices over**F**._{29} - Give an expression for the number of invertible
**nxn**matrices of**F**_{29.} - Using
**MAPLE™**find a counter-example to the above claim over**Z**_{26}: - Using
**MAPLE™**find the number of invertible**2x2**matrices over**Z**._{26} - In the light of the above questions, explain
why I changed the alphabet size to
**29**? - Using
**MAPLE™**find a__random__irreducible polynomial**P**of degree**1000**over**F**._{ 2} - Build the field
**F**1000with the irreducible polynomial_{2}**P**found above. - Find a primitive element
**g**of**F**1000 . HINT:_{2}**2**^{1000}**-1 =**

(31*601*4710883168879506001*269089806001*1801)*

(3*11*251*229668251*5519485418336288303251*4051)*

(5^{4}*94291866932171243501*268501*28001*96001)*

(41*101*47970133603445383501*3775501*7001*8101)*

(17*61681*401*3173389601*2787601*340801)*

8877945148742945001146041439025147034098690503591013177336356694416517527310181938001

- Pick two
__random__elements**(i,j)**in**F**1000 ._{2} - Tell us
**x,y, 0<= x,y <= 2**such that^{ 1000}-1**g**and^{x}=i**g**.^{y}=j - 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**F**1000. (_{2}__no credit question:__tell us why you like**m.**) - Send us
**(P,i,j)**and**(m,t)**via e-mail to cs547@cs.mcgill.ca before this HW deadline.

(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 **Z _{26}** but such that

__Hint :__ read page 16
of Stinson’s book.

AUTHENTICATION CODES and finite fields

You are now asked to setup
an authentication code over **F _{2}**
1000.