A.
Consider the following two sets
of hash functions on m bit inputs:
H0 = { h(x) =
(Mx)(+)y | M is an mxm binary matrix
and y is an m bits string }
H1 = { h(x) =
(Mx)(+)y | M is an mxm binary invertible
matrix and y is an m bits string }
For each of these two sets prove
whether or not they are Strongly Universal2 classes of hash functions.
Here, the product z of a matrix M with a bit vector
v is done by apply the /\ (AND) operation bitwise
and then the (+) (XOR) operation
on the results.
zj
= (+)i (Mij /\ vi)
For example (10010) [010] = ( 0(+)0(+)0(+)1(+)0 , 1(+)0(+)0(+)0(+)0, 0(+)0(+)0(+)0(+)0 ) = (110).
[111]
[001]
[100]
[101]
B.
MAPLE
AUTHENTICATION
CODES and finite fields
You are now asked to setup an
authentication code over F21000.
1.
Using MAPLEª find a random
irreducible polynomial P of degree 1000 over F2.
WARNING: do not use MAPLE functions Randprime and Randpoly
!!!
Suggestion: Generate your own random polynomials...
For extra bonus credits: explain the source of the problem with Randpoly.
2.
Build the field F21000 with the irreducible
polynomial P found above.
3.
Find a primitive element g of F21000.
4.
Pick two random elements
(i,j) in F21000.
5.
Tell us x,y, 0<= x,y <
21000-1 such that gx=i and gy=j.
6.
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 F21000. (no credit
question: tell us why you like m.)
7.
Send us (P,i,j) and (m,t) via e-mail to gsavvi1@cs.mcgill.ca
before this HW deadline.
Useful info:
21000-1 = (2500-1)*(2500+1)
2500-1 = (2250-1)*(2250+1)
2250-1 = (2125-1)*(2125+1)
2250+1 = (2125-263+1)*(2125+263+1)
2500+1 = (2100+1)*(2400-2300+2200-2100+1)
2125-1 = 31 * 601 *
4710883168879506001 * 269089806001 * 1801
2125+1 = 3 * 11 * 251
* 229668251 * 5519485418336288303251 * 4051
2125-263+1
= 54 * 94291866932171243501 * 268501 * 28001 * 96001
2125+263+1
= 41 * 101 * 47970133603445383501 * 3775501 * 7001 * 8101
2100+1 = 17 * 61681
* 401 * 3173389601 * 2787601 * 340801
2400-2300+2200-2100+1
= 4001 * 1074001 * 2020001 * 22624001 * 1481124532001
* 8877945148742945001146041439025147034098690503591013177336356694416517527310181938001
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.
8.
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 26 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
9.
Using MAPLEª find the number
of invertible 2x2 matrices over F29.
(use without proof
the following claim: [ M is not invertible iff det(M)=0
] over Fq)
10.
Give an expression for the number
of invertible nxn matrices of F29.
Hint: Stinson's
book, exercise 1.12
11.
Using MAPLEª find a counter-example
to the above claim over Z26:
A 2x2 matrix M which is not invertible
over Z26 but such that det(M)>0 over Z26.
12.
Using MAPLEª find the number
of invertible 2x2 matrices over Z26.
Hint : read
page 16 of Stinson's book.
13.
In the light of the above questions,
explain why I changed the alphabet size to 29?