Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Main Examination period 2021 – January – Semester A
MTH6115 / MTH6115P: Cryptography
You should attempt ALL questions. Marks available are shown next to the
questions.
In completing this assessment:
? You may use books and notes.
? You may use calculators and computers, but you must show your work-
ing for any calculations you do.
? You may use the Internet as a resource, but not to ask for the solution
to an exam question or to copy any solution you find.
? You must not seek or obtain help from anyone else.
All work should be handwritten and should include your student number.
The exam is available for a period of 24 hours. Upon accessing the exam, you will
have 3 hours in which to complete and submit this assessment.
When you have finished:
? scan your work, convert it to a single PDF file, and submit this file using the
tool below the link to the exam;
? e-mail a copy to [email protected] with your student number and the module
code in the subject line;
? with your e-mail, include a photograph of the first page of your work together
with either yourself or your student ID card.
You are expected to spend about 2 hours to complete the assessment, plus the time
taken to scan and upload your work. Please try to upload your work well before the end
of the submission window, in case you experience computer problems. Only one
attempt is allowed – once you have submitted your work, it is final.
Examiners: B. Noohi, S. Sasaki
c? Queen Mary University of London (2021) Continue to next page
MTH6115 / MTH6115P (2021) Page 2
Question 1 [25 marks].
(a) Which method gives ciphers that are harder to break: 1) an affine cipher
composed with a substitution cipher; 2) a Caesar shift composed with a
substitution cipher then composed with another Caesar shift? Justify your
answer. [4]
(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.
[4]
(c) Write down two affine substitutions on the English alphabet that encrypt the
letter f to the letter H. How many such affine substitutions are there? [5]
(d) Is the following definition correct? If the definition is incorrect, explain why it is
not equivalent to the correct definition 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-defined.
Give an example of a substitution table that is not a Latin square. [6]
(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
[6]
c? Queen Mary University of London (2021) Continue to next page
MTH6115 / MTH6115P (2021) Page 3
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 Vigene`re 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? [6]
(b) Can the following sequence be the output of a primitive 5-bit shift register?
1000010001100101011110001100011
Justify your answer. [3]
(c) The following is the output sequence of a 5-bit shift register.
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. [5]
(d) Is the keystring in Part (c) suitable for use as a one-time-pad? Very briefly
explain your answer. [3]
(e) Determine (with proof) whether x5 + x4 + 1 is
(i) irreducible over Z2, [4]
(ii) primitive. [4]
c? Queen Mary University of London (2021) Continue to next page
MTH6115 / MTH6115P (2021) Page 4
Question 3 [25 marks].
(a) The (multiplicative) order of x modulo p is defined to be the least positive
integer m such that xm ≡ 1 mod p. Explain why the multiplicative order of x
exists. [4]
(b) In Part (a) explain why the definition does not make sense if either of the words
(i) least or (ii) positive is omitted. [4]
(c) Is the following definition correct? If the definition is incorrect, explain why it is
not equivalent to the correct definition and give a corrected version of it: [4]
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). [5]
(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. [8]
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.) [7]
(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. [6]
(c) Explain why Vigene`re ciphers are not suitable for public-key cryptography. Would
a combination of a Vigene`re and a transposition be suitable? [6]
(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 find it. Explain carefully why this is the case.
For the same sequence a1, a2, a3, a4, find a positive integer b
′ such that the Greedy
algorithm does find a solution. [6]