The University of Melbourne
School of Computing and Information Systems
COMP90043 Cryptography and Security
Assignment 1
Objectives
This assignment is designed to improve your understanding of the Euclid’s algorithm,
classical ciphers and basics of probability. It’s also aimed at improving your problem-solving
and written communication skills.
Questions
1. General Security [8 marks]
Which of the following factors might be the most concern by the public in regards to
the COVID passport?
(https://tinyurl.com/y2nxykaw)
Justify your answer in a few sentences.
(a) Confidentiality (b) Integrity (c) Availability
2. Classical Ciphers [20 marks]
Consider the following version of a classical cipher where plaintext and ciphertext
elements are the integers from 0 to 27. Note that this alphabet may be used when
the characters of plaintexts are elements the language A consisting of the 26 English
characters (A−Z) along with space. The encryption function, which maps any plaintext
p to a ciphertext c, is given by
c = E(a,b)(p) = (ap + b) mod 27,
where a and b are integers less than 27.
(a) For what values of a and b does a decryption function of E(a,b) exist? Write down
the decryption function.
(b) How many keys are possible for this scheme? Explain your reasoning.
(c) Would this cipher be considered as mono-alphabetic cipher or poly-alphabetic
cipher? Why?
(d) You are given a large amount of ciphertext characters encrypted using this scheme.
Assuming its plaintext was written in English, show how an attacker can retrieve
the key.
1
https://tinyurl.com/y2nxykaw
(e) An oracle is available to you which can output the encrypted ciphertext for
arbitrary plaintext you give. Briefly describe an efficient way to retrieve the
key using the oracle.
3. Euclid’s algorithm [15 marks]
Perform the following implementation tasks in a language of your choice. You are free
to employ any underlying integer arithmetic library. In order to get full marks, your
algorithm has to be able to work in realistic cryptographic environments (consider
101000 as input).
(a) Implement the extended GCD algorithm as discussed in lectures and print the
code here.
(b) Implement a function which takes two positive integers a, n as inputs, and returns
the inverse of (a mod n) based on your extended GCD algorithm (that you just
implemented above). Print the code for this function.
(c) Use the above function to find the inverse of X( mod 16811891), where X is your
student number. You don’t need to show steps for the calculation.
4. Poly-alphabetic Cipher [21 marks]
For this question, we consider the Hill cipher given in the textbook on an alphabet A
consisting of 26 English characters (A-Z), 10 numeric characters (0-9) and the following
special characters:
: ; < = [ (1)
which corresponds to integers 0 to 40. Here the plaintext is processed successively in
blocks of size m. The encryption algorithm takes a block with m plaintext digits and
transforms into a cipher block of size m using a key matrix of size m×m by the linear
transformation, which is given by:
c1 = (k1,1p1 + k1,2p2 + · · ·+ k1,mpm) mod 41
c2 = (k2,1p1 + k2,2p2 + · · ·+ k2,mpm) mod 41
· · ·
cm = (km,1p1 + km,2p2 + · · ·+ km,mpm) mod 41
Note: For this question, correspondence between plaintext and number modulo 41 are
as follows “A” ↔ 0, “B” ↔ 1, “C” ↔ 2, . . . , “Z” ↔ 25, “0”↔ 26, “1”↔ 27,
“2” ↔ 28, . . . , “9” ↔ 35, “ : ” ↔ 36, “; ” ↔ 37, “ < ” ↔ 38, “ = ” ↔ 39,
“[” ↔ 40
(a) The following is ciphertext where the encryption method described above has
been employed:
0ANJASCDOP7A4R82YQR[N11Z;AXCJNV9