1.   (a)  suppose  Alice is using  M  = （  1(3)   8(4) )  as  an  encryption  matrix  in  a 2 x 2 Hill/Block cipher. Find two diferent plaintexts that encrypt to the same cipher- text. using the encryption matrix M given above, can there be three diferent plaintexts which encrypt to the same ciphertext？ If yes, give an example; if no, prove that it is impossible.

(b)  suppose a one time pad was used to encrypt a message to obtain the following ciphertext:

TIUBSRBEW KTY.

suppose you know that the irst four letters in the plaintext are SELL.  Then use this information to guess the keypad and further decipher the plaintext. Give rigorous reasoning.

solution:

(a) we will begin by  computing vectors which  satisfy  M从  =  0  modulo  26.    If 从  = (a, b)t  then this gives two equations.  3a + 4b  =  0 and a + 8b = 0.  All operations here are modulo 26.  This gives a = -8b and -20b = 0 mod 26.  This is true if and only if 13 | -10b which means 13 | b. Thus, b = 0, 13 and in each case the corresponding value of a = 0 mod 26.  Thus, (0, 0) and (0, 13) both give ciphertext to (0, 0).  Moreover, these are the only two plaintexts that map to (0, 0).

Note that the plaintexts (0, 0, 0, 0), (0, 0, 0, 13), (0, 13, 0, 0), (0, 13, 0, 13) all give the same ciphertext (0, 0, 0, 0).

(b) The ciphertext written as an array is:

20, 9, 21, 2, 19, 18, 2, 5, 23, 11, 20, 25.

The irst four letters of the plaintext are (19, 5, 12, 12).  This gives the irst 4 entries of the keypad: 20 - 19 = 1, 9 - 5 = 4, 21 - 12 = 9, 2 - 12 = -10 = 16. Thus, it is fair to guess that the i-thentry of the keypad is given by i2    mod 26. The the 12 entries of the keypad are

1, 4, 9, 16, 25, 10, 23, 12, 3, 22, 17, 14.

subtracting from the ciphertext, the plaintext is

19, 5, 12, 12, 20, 9, 5, 19, 20, 15, 3, 11.

Thus the plaintext is sELL THE sTOcK.

2. Let E : g2  = x3 + Ax + B be an elliptic curve deined over a inite ield rp.  Let 企 denote the standard group operation on E(rp ).

P ① Q = 一(P 企 Q),                                        (1)

for any P, Q e E(rp ). Is this operation associative？Give rigorous reasoning.    (b) Let E : g2  = 从3  一 从 be deined over r3 .  prove that in this case, the operation

① as deined in (1) indeed gives a group structure on E(r3 ).

(c) Let E be an elliptic curve over rp  such that E(rp ) is a group under operation ① deined in (1). prove that the cardinality of E(rp ) is at most 4.

solution:

(a)  This operation is not associative, as (P ① Q) ① R = (P 企 Q 企 (一R) and P ① (Q ① R) = (一P) 企 Q 企 R. These two are equal if and only if [2](P 一 R) = 有 for all P, R. This is if and only if order of each element is less than or equal to 2.

(b) E(r3 ) = {有 , (0, 0), (1, 0), (2, 0)}. Thus, every element here has order at most 2. Thus, ① is indeed associative. similarly 有 ① P = 一P = P = P ① 有 for any P. Moreover, P ① (一P) = 有, and thus every element has a multiplicative inverse. Therefore this is a group operation here.

(c) we have seen that this operation is associative only if every element has order at most 2.  There is only one element of order 1 (identity).  The only elements of order 2 are of type (从, 0).  Thus, 从 here must be a solution of 从3 + A从 + B . There are only three roots here (at most), and therefore E has at most four points.

5.   (a)  suppose Alice is sending a message 0 参 m < n to Bob using the RsA public key protocol with RsA modulus n = pq and public encryption key e.  Bob re- ceives Alice,s corresponding ciphertext ① , but instead of the standard decryption modulus d, he uses d\  deined by

d\ e = 1 mod λ(n).

Here, given n = pq as above, we deine λ(n) = l.c.m.(p - 1）q - 1) where l.c.m. denotes the least common multiple function. will Bob be able to recover m by computing ①d、 mod n？Give rigorous reasoning.

(b)  Let p = 3 mod 4 denote a large prime.  Let 0 < m < p denote a message and let h denote a hash function

h(m) = m2  mod p.

Prove that  h  is  not  pre-image  resistant.   Is  it  strongly  collision  free？  Give thorough reasoning.

(Hint:  gou mag use heTe that -1 is not a quadTatic Tesidue modulo p.) (c)  Let E be an elliptic curve deined by the equation

g2  = ①3 + 376①.

Determine the set of torsion points E(Q)tors  explicitly.  Give careful reasoning of each step.

(Hint:  gou mag Teduce the  equation modulo suitable PTimes.)

solution:

(a)  Bob will indeed be able to recover m.  Note that ① = me  modn. Therefore ①d、 = md、e  Note that since both p - 1 and q - 1 divide d\ e, therefore ①d、 = mmodp and ①d、 = m mod q.  Now, using the chinese remainder, this is true if and only if ①d、 = m mod n.

(b)  suppose that we want to solve for h(m) = g, i.e.  ine m such that m2   = g modulo p.  using Fermat,s little theorem, gp   =  g  and therefore, g(p+1)   = g2 . This means g((p+1)/4)根4  = g2 .  Thus,  (从2  - g)(从2  + g) = 0 where 从  =  g(p+1)/2 . since -1 is not a QR, only one of g or -g can be a QR. Therefore, either g is not a QR or g = 从2 , where 从 = g(p+1)/2, which means that we have found a pre-image of g.  Note that only doable if 4 divides p + 1.

This is clearly not strongly collision free since h(m) = h(-m).

(c) we will reduce the equation modulo diferent primes.  we begin by reducing modulo 3.  The discriminant of this curve is 4  0.  we compute the points on this curve 求）(0）0)）(2）1)）(2）2).  This is  a group with four elements.  only one of these points has order 2  ((0）0)).  Therefore, order of (2）1) and  (2）2) must be 4 and this group is isomorphic to z/4z.  we do a similar process over F5 . clearly 5 t 4, discriminant.  The squares in this ieldare 0）1）4.  Thus, the points are 黄 , (0, 0), (2, 0), (3, 0),.  In this group, every non-zero element is of order  2. Therefore, it is isomorphic to z/2 根 z/2.

since 3 and 5 are of good reduction, E(Q)toTS  can be seen as a subgroup of both z/4 and z/2 根 z/2. Therefore, it can only be trivial or z/2. However, (0, 0) is already a torsion point of order 2.  Therefore, this must be the only point and thus, E(Q)toTS  = {黄 , (0, 0)}.

6.   (a)  suppose Alice is using the ElGamal digital signature scheme with a prime p and a primitive root g modulo p to sign a message m.  suppose her random number generator machine is broken.  Therefore, she instead chooses k = a, where a is her secret key and computes the signature  (T, s).   suppose  Eve  intercepts the  signed  message.   show  how  Eve  can  use  this  information  to  break  this cryptosystem.

(b)  For a in z, a 持 0, let Ea  be an elliptic curve deined over Q by the equation

g2  = ①3 + a.

Find the values of a for which Ea (Q) has torsion points of order 2, and specify these points. Do the same for order 3. Explain each step carefully.

solution:

(a)  since Alice is using k = a, her T = gk  = ga  = g, which is the public key of Alice. Further, s = k-1 (m — aT) mod p — 1 = a-1m — T mod p — 1. knowing m,s and T , thus Eve can compute what a is.  Note that she will know that k = a since she will note that T = g which was Alice,s public key.

(b)  By Nagell-Lutz theorem, each non-trivial torsion point must have integral coef- icients. E(Q) has a point of order 2 if there is an integral solution to ①3 +a = 0. This is true if and only if a = n3  for some integer n.

on the other hand, E(Q) has a point of order 3, (①1 , g1 ) if and only if [2]P = —P =  (①1 , —g1 ).  This must mean that g1    0, since other wise P is of order 2, and  [3]P = 有 means that P = 有, which is not of order 3.  we may thus apply the addition formula.  Thus by equating ① co-ordinates of [2]P and — P , we must have ①1  = (3①1(2)/2g1 )2  — 2①1 . This means 3①1  根 4g1(2) = 9①1(4). If ①1  = 0, then we must have g2   = a, or if a = n2 , for some integer n, and the points of order 3 are equal to (0, n), (0, —n).  otherwise, we must have a non-trivial solution for (2g)2  = 3①3. This must mean 3 | g and 2 | ①.  Let g = 2k1 3m1 从1  and

let ① = 2k2 3m2 从2 . Then we should have 22(k1 +1) 32m1 从1(2) = 23k2 33m2 +1 从2(3).

This implies that k1  = 2 mod 3, 2 | k2  and m1  = 2 mod 3 and m2  = 1 mod 2. we may now write g = 22  根 32 从3  and ① = 22  根 3从2 , for some integer 从 .

since (①, g) must lie on the curve, 2434 从6  = 2633 从6 +a, and therefore a = —432从6 . If a is of the form —432从6  for some integer 从 , then (12从2 , 干36从3 ) are the points of order 3.

3.   (a)  Let C 己 r7(6)  be the code generated by

Find a check matrix for C.

(b)  By considering the syndrome of g  = (1）2）1）4）0）1) E r7(6), determine whether g is a codeword of C or not.

solution:

(a) weirst need to put G into RREF, which gives (via the sequence A32 (1), M2 (5), M3 (4), A31 (1) for example)

G(~) =  l0(1)   0(2)   0(4)   1(0)   0(0)   6(6))

(0   0   0   0   1   5) .

we can now apply the G 今 H algorithm to ind the check matrix for C.  The leading 1s are in columns 1,4 and 5, so we have L = {1）4）5} and a basis for the dual code is {o2）o3）o6 } where

o2  = (5）1）0）0）0）0)

o3  = (3）0）1）0）0）0)

o6  = (1）0）0）1）2）1)）

so a check matrix for C is

H =  l3(5)   0(1)   1(0)   0(0)   0(0)   0(0))

(1   0   0   1   2   1)

(b) we have S(g) = gHt  = (0）4）6).  For any codeword X E C we have XHt  = 0 by the deinition of a check matrix, and so since S(g)  0, g cannot be a codeword. 

4.   (a)  show that 从2 + 从 + 1 is irreducible in r2 [从], and is a primitive polynomial over r2 .

(b) Let r4  := r2 [从]/(从2 + 从 + 1). construct a decoding array for C =〈(从, 1)）己 r4(2) , and use it to decode (从, 0) and (从, 从).

(c)  suppose that  C is transmitted over a 4-ary symmetric channel with symbol error probability p. Find p such that the chance that a received word is decoded correctly is equal to 1/2.

solution:

(a)  since f (从) = 从2  + 从 + 1 is quadratic, if it is reducible it must factor into two linear factors, and hence have two roots.  since  f (0) = f (1) = 1, f (从) has no roots, and hence is irreducible in r2 [从].

since f (从) is irreducible in r2 [从], F4  := r2 [从]/(f (从)) is a ield. f (从) is a primitive polynomial over r2  if 从 is primitive in r4 .   we  have  从2   = 从 + 1,  and  hence 从3   = 从2  + 从  =  1.   since  all  three none-zero elements of r4  can therefore be written as 从i  for 0  三 i  三  2,  从 is primitive in r2 , and so f (从) is a primitive polynomial.

(b)  The code contains four words, 0 . (从, 1) =  (0, 0), 1 . (从, 1) =  (从, 1), 从 . (从, 1)  =

(从 + 1, 从) and 从2  . (从, 1) = (1, 从 + 1).  A possible decoding array is then

(0, 0)         (从, 1)        (从 + 1, 从)        (1, 从 + 1)

(从, 0)         (0, 1)         (1, 从)        (从 + 1, 从 + 1)

(从 + 1, 0)     (1, 1)         (0, 从)           (从, 从 + 1)

which contains all 42   elements of r4(2)  as required.   using  this  array,  (从, 0)  is decoded as (0, 0), and (从, 从) is decoded as (从 + 1, 从).

(c)  A received word is decoded correctly if the error is one of those in the irst column of the decoding array.  By proposition 2.11, with ao  = 1 and a1  = 3, and with the required probability being equal to 1/2, we have

(1 — p)2 + p(1 — p) = 1 — p = 1/2,

and so the symbol-error probability p = 1/2.

7.   (a)  Let C =〈(2, 1, 0), (0, 2, 1)）己 r3(3). Find a generator matrix and check-matrix for C, and state the parameters [n,k, d] for this code.

(b)  Find a generator matrix and a check-matrix for CT , and state the parameters [n\ , k\ , d\] for this code.

(c)  show that the permutation automorphism group of both C and CT  is S3 .

Hint:  Recall that S3   is geneTated bg the tWo  elements  WTitten in  cgcle foTm  as (12) and (123) .

(d)  show that

|MAut(C)| = 2|PAut(C)| .

solution:

(a) An acting generator matrix for C is

G = (0(2)   2(1)   1(0)) ,

and looking at the irst and third columns shows that the two rows of G are linearly independent, and so G is a generator matrix for C. C therefore clearly has n = 3, k = 2.

The RREF of G is

G(~) = (0(1)   1(0)   2(2)) ,

and so (by propositions 4.5 and 4.7)

H =(1   1   1)

is a check-matrix for C.

since any two columns of H are linearly dependent, but there is no column of zeros, C has minimum distance d = 2.

(b)  By proposition 4.7, H is a generator matrix for CT , and either of G or G(~) is a check-matrix for CT .  since all words are scalar multiples of (1, 1, 1), CT  is a [3, 1, 3] code.

(c)  since the composition of two automorphisms is an automorphism,  and  S3  is generated by  (1 2) and  (1 2 3), if both  (1 2 3), (1 2)  E  PAut(C) for a code C, then S3   己  PAut(C).   since  by  deinition,  for  a  code  of block  length  3, PAut(C) 己 S3 , this then implies Paut(C) = S3 .

Letting Ⅱσ M denote the action of the permutation σ on a matrix M, we clearly have Ⅱ (1  2  3) H = H, and therefore (1 2 3) E PAut(CT ).  similarly, Ⅱ (1  2) H = H , and so (1 2) E PAut(CT ). we therefore have that PAut(CT ) = S3 .

Let G2  = Ⅱ (1  2  3) G, then the series of EROs S12 , A21 (1), M1 (2) transforms G2 back to G. The images of G2  and G are therefore the same, and so G2 generates the same code as G, giving (1 2 3) E PAut(C).

similarly, we have Ⅱ (1  2) G =（ 2(1)   0(2)   1(0)) = G3. Applying the EROs A12 (1) then M1 (2) transforms G3  to G, and hence (1 2) E PAut(C1 ), and so PAut(C) = S3 . (d) we know that any monomial matrix can be written in the form M = PD, for P

a permutation matrix, and D a diagonal matrix with non-zero elements on the diagonal. By the previous part of the question, we know that any permutation in S3 written in matrix formsends a generator matrix G for C to another generator matrix G、for C. we therefore only need to consider the efects of the diagonal part of the monomial matrix.

consider the efect of a diagonal part with a single 2 on the diagonal (and the other diagonal elements equal to 1).  This necessarily sends one of the rows of the generator matrix to a word with two positions equal and the inal position equal to zero (the only way not to send the irst row of G to such a word is if the 2 acts on the inal column of G, in which case the second row of G is sent to such a word). If such a word is in the code, then by linearity and the fact that (1 2 3) E Paut(C), we would have (1, 1, 0) E C.  However, using the check-matrix for C found in the irst part of the question, s((1, 1, 0)) = (1, 1, 0)H1(t)  = (2)  0, and hence (1, 1, 0)  C.

similarly, if the diagonal part of M has two 2s on the diagonal, and one 1, then again one of the rows of G1  is sent to a word with two positions equal and one zero (the irst row, unless the single 1 acts on the inal position of G1 , in which case the second row), and as above such a word is not in C.

The only diagonal matrices which can therefore act as the diagonal part of a monomial automorphism are I3   and 2I3 .   By  linearity,  2I3   acts  on  G  as  an automorphism, and I3   acts on G as a  (trivial) automorphism.  Therefore for any element of the permutation automorphism group, written as a permutation matrix P, there are 2 monomial matrices in the monomial automorphism group, namely P and 2P. Hence |MAut(C)| = 2|PAut(C)| .

8.   (a)  show that linear binary self-dual codes exist if and only if the block-length is even.

(b) Let C1  己『2(8) be the code generated by

'（ 0(1)   1(0)   0(0)   0(0)  1(0)   0(1)   1(1)   1(1) )

( 0   0   0   1  1   1   1   0 )

By considering the Hamming bound, show that C1  is not perfect.

(c)  For c）g e『2(n), let cU g denote the vector which has a 1 only in positions where

both c and g have a 1, and is 0 elsewhere.

show that c . g = 0 if and only if 山 (c U g) is even.

(d) we say that a code is doublg-euen if the weight of any codeword is a multiple of four.   Let  C  be  a linear binary code with generator matrix  G, such that every row of G has weight divisible by four, and any two distinct rows of G are orthogonal. show that C 己 C「 , and that C is doubly-even.

Hint:  You mag use the fact that foT c）g e『2(n) ,

山 (c + g) = 山 (c) + 山 (g) — 2山(c U g).

(e)  show that the matrix deined in block form as

G2  = (1     1 ) ）

where 0(教) denotes a matrix of all zeros of the appropriate dimension, is the gen-

erator matrix for a binary doubly-even self-dual code.

solution:

(a)  Let n be the block length of C, and k the dimension of C. If C = C「 , dim(C「 ) = n — k = k = dim(C), and therefore n = 2k for some k e z.

To show that a self-dual code exists when n = 2k, consider the code generated by G = (Ik | Ik ), which clearly has dimension k and n = 2k.  since this generator matrix is in standard form, then by proposition 4.5, a generator matrix for C「 is H = ( —Ik | Ik ) = (Ik | Ik ) = G since we are working over『2 , and so C「 = C.

(b) C1  clearly has block-length n = 8 and dimension k = 4.  By proposition 4.5, a check-matrix for C1  is

（ 1(0)   0(1)   1(1)   1(1)  0(1)   1(0)   0(0)   0(0) )

(  1    1    1   0  0   0   0    1 )