COMP90043 Assignment 1 Solution

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
c = E(a,b)(p) = (ap + b) mod 36,
where a and b are integers less than 36.
(a) What is the decryption function for the scheme?
(b) A key is called trivial if c = p for all input p. How many non-trivial keys are possible for this scheme?
(c) Would this cipher be considered as mono-alphabetic cipher or poly-alphabeticcipher? Why?
(d) You are given a large amount of ciphertext characters encrypted using thisscheme. Assuming its plaintext was written in English, show how an attacker can retrieve the key.
(e) An oracle is available to you which can output the encrypted ciphertext forarbitrary plaintext you give. Briefly describe an efficient way to retrieve the key using the oracle.
Which of the following factors might be the most concern by the public in regards to using the COVIDSafe app ? Justify your answer in a few sentences.
(a) Confidentiality (b) Integrity (c) Availability
(a) Implement the extended GCD algorithm as discussed in lectures and print thecode 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 16777259), where X is your student number. You don’t need to show steps for the calculation.
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 space, which corresponds to integers 0 to 36. 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 37 c2 = (k2,1p1 + k2,2p2 + ··· + k2,mpm) mod 37
···
cm = (km,1p1 + km,2p2 + ··· + km,mpm) mod 37
Note: For this question, correspondence between plaintext and number modulo 37 are as follows “A” ↔ 0,“B” ↔ 1,“C” ↔ 2, ..., “Z” ↔ 25,“0” ↔ 26,“1” ↔ 27, “2” ↔ 28, ...,“9” ↔ 35 and “ ” (space) ↔ 36
(a) How many different keys are possible in this system?
(b) This cipher is easily broken with a known plaintext attack. An adversary discovers the following ciphertext is encrypted using this cipher with m = 5 (55 characters in total, no spaces):
A8VS3XRDEON6JEVXGJID13C07L4C1R4Q965XWRA5DQGYWTNHYO4ND8Z
If the following combination of plaintext and ciphertext is given (please replace both “?????” by the last five digits of your student number), decrypt the cipher by giving the plaintext as well as both encryption and decryption keys.
Plaintext X9B6T6JAW3UEY7FHIW?????5Z
Ciphertext 2Q59ZZ1Z?????UMDNY2JHINTS
Let x be the fourth digit of your student ID (without leading zero), y be the sixth digit of your student ID. The value N used in this task is given by 5x +6y +15.
For the below tasks, you need to show your working by providing formula used, and/or short explanation. Also give the numerical final answer (e.g. 1024 instead of 210).
(b) Assuming that we have 230 students enrolled in this subject, and all studentnumbers are randomly generated. What’s the probability that at least one of your classmate shares the same N with you? Your result should be rounded to three digits after the decimal point.
(c) How many ways to place N different balls into five different bins?
(d) How many ways to place N identical balls into five different bins, so that all bins are non-empty?
(e) How many ways to place N identical balls into five different bins?
(f) How many ways to place N identical balls into five identical bins, so that at most two bins are non-empty?
Submission and Evaluation
• We expect your work to be neat — parts of your submission that are difficult to reador decipher will be deemed incorrect. Make sure that you have enough time towards the end of the assignment to present your solutions carefully. Time you put in early will usually turn out to be more productive than a last-minute effort.
Please see https://academicintegrity.unimelb.edu.au