Main Examination period 2019
MTH6115: Cryptography
Duration: 2 hours
Apart from this page, you are not permitted to read the contents of this question paper
until instructed to do so by an invigilator.
You should attempt ALL questions. Marks available are shown next to the questions.
Calculators are not permitted in this examination. The unauthorised use of a calculator
constitutes an examination offence.
Complete all rough work in the answer book and cross through any work that is not to be
assessed.
Possession of unauthorised material at any time when under examination conditions is an as-
sessment offence and can lead to expulsion from QMUL. Check now to ensure you do not have
any unauthorised notes, mobile phones, smartwatches or unauthorised electronic devices on
your person. If you do, raise your hand and give them to an invigilator immediately.
It is also an offence to have any writing of any kind on your person, including on your body.
If you are found to have hidden unauthorised material elsewhere, including toilets and cloak-
rooms, it will be treated as being found in your possession. Unauthorised material found on
your mobile phone or other electronic device will be considered the same as being in posses-
sion of paper notes. A mobile phone that causes a disruption in the exam is also an assessment
offence.
Exam papers must not be removed from the examination room.
Examiners: J. N. Bray and S. Lester
c Queen Mary University of London (2019) Turn Over
Page 2 MTH6115 (2019)
We use the correspondence between the English alphabet and integers modulo 26 given by
A? 0,B? 1, . . . ,Z? 25. This is given in full in the table below.
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
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
For full marks, you will have to show all working.
Question 1. [22 marks]
(a) Describe the C?sar shift and Vigene`re cipher, either as applied to the English alphabet
or to Zn, the integers modulo n. [5]
(b) In an encryption competition called Cipher Challenge you are permitted to use one of
the following two methods to encrypt your message: (i) a combination of at most 3
Vigene`res with each key length at most 6, or (ii) a combination of at most 2 Vigene`res
with each key length at most 9. Which method will you use? Justify your answer. [5]
(c) The following ciphertext has been encrypted using a Vigene`re key of length 3.
AHTZ IDYA EOEC LADF
Decrypt it, given that the plaintext commences thi. [8]
(d) The Hebrew alphabet contains 22 letters. How many affine ciphers are there for this
alphabet? Justify your answer. [4]
Question 2. [14 marks]
(a) Define what an orthogonal array of degree k and strength t over an alphabet A of size
q is. [4]
(b) Describe the correspondence between orthogonal arrays of degree 3 and strength 2 over
A and Latin squares with rows and columns labelled by A . (You do not have to say
what a Latin square is, but you should state the correspondence both ways round.) [4]
(c) The following is an orthogonal array with some entries missing. 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 30 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
0 3 1 2 1 0
Write down the Latin square corresponding to the above orthogonal array, including
filling in the blanks. (Order the row and column labels 0,1,2,3.) [6]
c? Queen Mary University of London (2019)
MTH6115 (2019) Page 3
Question 3. [40 marks] Let n be a positive integer.
(a) Define the Carmichael function 竹(n) and the Euler function 耳(n). [6]
(b) Determine how many positive integers there are that are less than and coprime to 30000.
Find 竹(30000). [6]
(c) Prove, for all n ﹋ Z+, that a耳(n) √ 1 (mod n) whenever a is coprime to n. [8]
(d) Explain briefly the operation of the RSA cryptosystem. If Eve intercepts an RSA com-
munication, which ※hard§ problems does she have to solve in order to break the cipher? [8]
(e) You are given that N = 1147 is the product of two (odd) primes and that 竹(N) = 180.
Use this information to factor N. (The marks are for the method, not the factorisation.) [4]
(f) Let p be a prime, and let x be an integer such that p - x. Define the (multiplicative) order
of x modulo p. [3]
(g) Determine the order of 3 modulo 31. [5]
Question 4. [24 marks]
(a) Define an n-bit shift register, and give the Z2-polynomial corresponding to such a shift
register. Explain what it means for an n-bit shift register to be primitive. [7]
(b) You intercept the following bit string:
10111 11001 01001 10001 10101 01010 11100 11010 01010.
You have reason to believe that the message was converted into a bit string using the
International Teleprinter Code, and then encrypted using a keystring derived from a 5-bit
shift register. You have reason to believe that the message commences MI. Decrypt the
message (assuming that this is the case).
The International Teleprinter Code is given in the appendix at the end of the paper. [10]
(c) The first 40 bits of a 5-bit shift register (not the one used above) are
10000 10110 10100 01110 11111 00100 11000 01011.
Is this shift register primitive? Justify your answer. [2]
(d) Let f be the polynomial corresponding to the shift register in the previous part. (We have
f (x) = x5 + x3 + x2 + x+1.) Is f irreducible (over Z2)? Justify your answer. [3]
(e) Is the keystring in Part (c) suitable for use as a one-time-pad? Very briefly explain your
answer. [2]
End of Paper 每 An appendix of 1 page follows.
c Queen Mary University of London (2019) Turn Over
Page 4 MTH6115 (2019)
A 11000
B 10011
C 01110
D 10010
E 10000
F 10110
G 01011
H 00101
I 01100
J 11010
K 11110
L 01001
M 00111
N 00110
O 00011
P 01101
Q 11101
R 01010
S 10100
T 00001
U 11100
V 01111
W 11001
X 10111
Y 10101
Z 10001
Letters 11111
Figures 11011
Line feed 01000
Carriage return 00010
Word space 00100
All space 00000
Table 1: International Teleprinter Code
End of Appendix.
c Queen Mary University of London (2019)