闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Main Examination period 2021 – January – Semester A

MTH6115 / MTH6115P: Cryptography

Question 1 [25 marks].

(a) Which method gives ciphers that are harder to break: 1) an aﬃne cipher

composed with a substitution cipher; 2) a Caesar shift composed with a substitution cipher then composed with another Caesar shift? Justify your

answer.

(b) Decrypt the ciphertext

SXNUM LUSVB XFSTP UUTSD

given that it has been encrypted using the substitution

a b c d e f g h i j k l m n o p q r s t u v w x y z T H E Q U I C K B R O W N F X J M P S V L A Z Y D G.

(c) Write down two aﬃne substitutions on the English alphabet that encrypt the letter f to the letter H . How many such aﬃne substitutions are there?

(d) Is the following deﬁnition correct? If the deﬁnition is incorrect, explain why it is not equivalent to the correct deﬁnition and give a corrected version of it:

A Latin square on an alphabet A is a square with entries from A such that the associated binary operation is well-deﬁned.

Give an example of a substitution table that is not a Latin square.

(e) Is the following substitution table on the alphabet A = (a, b, c, d} a Latin square?

Find its adjugate.

a b c d

a a b c d

b b c d a

c c d a b

d d a b c

Question 2 [25 marks].

(a) In a competition known as Cipher Challenge, a student claims that the cipher they cracked has been produced by composing two Vigen`ere ciphers with keywords JLQZ and QINTAR, but they did not specify the order in which these were applied.

(i) Does the order matter?

(ii) How did I know the student had cheated?

(b) Can the following sequence be the output of a primitive 5-bit shift register?

1000010001100101011110001100011

Justify your answer.

10001001101011110001

Suppose we now run this shift register with the initial state 11000. Determine the

next 5 bits in the output sequence. Justify your answer.

(d) Is the keystring in Part (c) suitable for use as a one-time-pad? Very brieﬂy explain your answer.

(e) Determine (with proof) whether x5 + x4 + 1 is

(i) irreducible over Z2 ,

(ii) primitive.

Question 3 [25 marks].

(a) The (multiplicative) order of x modulo p is deﬁned to be the least positive integer m such that xm 三 1 mod p. Explain why the multiplicative order of x

exists.

(b) In Part (a) explain why the deﬁnition does not make sense if either of the words (i) least or (ii) positive is omitted.

(c) Is the following deﬁnition correct? If the deﬁnition is incorrect, explain why it is not equivalent to the correct deﬁnition and give a corrected version of it:

For a positive integer n, the value of the Carmichael function λ(n) is equal to the order modulo n of an arbitrary integer a coprime to n.

(d) Let n be a positive integer. Prove that λ(n) divides ϕ(n).

(e) In lectures, you have seen a method to compute xa mod n with at most 2 log2 a multiplications and reductions modulo n (I called it “the fast method”). Illustrate this method by calculating 381 mod 31. Show your working.

Question 4 [25 marks].

(a) Show how RSA with modulus N can be broken if ϕ(N) is known. Illustrate this by factorising 9167, given that it is a product of two primes and ϕ(9167) = 8976. (The marks are for the method, not the factorisation.)

(b) Explain the concept of a digital signature. Why is it not needed in classical (as opposed to public-key) cryptography? Give an instance of a situation in which it might be used in real life.

(c) Explain why Vigen`ere ciphers are not suitable for public-key cryptography. Would a combination of a Vigen`ere and a transposition be suitable?

(d) Give an example of a sequence a1 , a2 , a3 , a4 of positive integers, and a positive integer b, such that the corresponding knapsack problem has a solution but the Greedy algorithm fails to ﬁnd it. Explain carefully why this is the case.

For the same sequence a1 , a2 , a3 , a4 , ﬁnd a positive integer b′ such that the Greedy algorithm does ﬁnd a solution.