The University of Melbourne
School of Computing and Information Systems
COMP90043 Cryptography and Security
Assignment 1, Semester 2 2023
Due Date: August 21, 23:59 AEST
Objectives
This assignment is designed to improve your understanding of the Euclid’s algorithm, clas-
sical ciphers and basics of probability. It’s also aimed at improving your problem-solving
and written communication skills.
Questions
1. One-time pad (OTP) [23 marks]
One-time pad is an elegant and theoretically unbreakable encryption scheme. However,
it is rarely used in practice. In this question, we will explore some of the reasons why
it is not widely used.
(a) Recall that the one-time pad encryption is defined as c = p ⊕ k, where p is the
plaintext, k is the key, c is the ciphertext, and k, p, c ∈ {0, 1}n. Suppose that the
key is random, and the key is only used once. Is the one-time pad encryption
scheme perfectly secure? Justify your answer. [5 marks]
(b) Two-time pad: suppose the encryption algorithm works as Question 1(a), but the
key is reused. Now suppose you have intercepted two ciphertexts:
c1 = 1111100101111001110011000001011110000110
c2 = 1111101001100111110111010000100110001000
You know that the two ciphertexts are encrypted using the same key and EI-
THER c1 is an encryption of a string “alpha” and c2 is an encryption of a string
“bravo” OR c1 is an encryption of a string “delta” and c2 is an encryption of a
string “gamma”. Can you recover the plaintexts? If so, what are the plaintexts?
If not, explain why. (All characters are encoded in ASCII code) [5 marks]
(c) There is nothing exclusively special about strings and XOR in OTP, arithimitic
operations can also be used. Suppose n is a prime, we have a plaintext p ∈ Zn and
a key k ∈ Zn that are both integers. We can encrypt the plaintext by computing
c = pk mod n. [5 marks]
1. Show the corresponding decryption scheme.
2. Is this encryption scheme perfectly secure? Justify your answer.
1
(d) Sometimes hackers do not even need a key to decrypt a ciphertext. Still, we inherit
the encryption scheme from 1(a). Suppose you know length of k, |k| = 10, and
a ciphertext
c=0x2D00554402091D4E0845101C20746F206C696D69742E204F73636172205769
6C6465.
Identify the vulnerability of this scheme and try to recover the plaintext and the
key. Note that we use ASCII encoding for the plaintext, the ciphertext, and the
key. [8 marks]
With those questions, we get a sense of why OTP is not widely used. First, for security,
every key can only be used for once. If you are using this scheme to message your
friends, you are supposed to manage tons of keys. Second, the key must be as long as
the plaintext. Otherwise, we are at risk of reusing the key or even leaving part of the
plaintext not encrypted. Third, the key must be truly random.
2. A practical content delivery encryption system. [10 marks]
A game company tends to protect game content delivery on PS/Switch/Xbox through
DVDs. Here is one possible approach. Suppose there are at most a total of n consoles
in the world (e.g. n = 232). We view these n consoles as the leaves of a binary tree
with height log2 n. Every node vj in this binary tree contains a key kj ∈ K. These
keys are kept secret from consumers and are fixed for all time. At manufacturing
time every console is assigned a serial number i ∈ {0, · · · , n − 1}. Let Si be the set
of 1 + log2 n nodes along the path from the root of the binary tree to leaf number i.
The manufacturer embeds in player number i the 1 + log2 n keys, which is its unique
key associated with the keys in nodes in Si. In this way, each console ships with
1 + log2 n keys embedded in it, and these keys are supposedly inaccessible to the end
user. Ideally, a game m is encrypted as
Console := E(kroot, k)︸ ︷︷ ︸
header
||E(k,m)︸ ︷︷ ︸
body
where E(key,message) is an encryption scheme, || denotes string concatenation, and
k
R← K is fresh random key called a content key (you can think key k is fully random
and unique for different m simply). Since all consoles have the key kroot, all consoles
can decrypt the content m. We refer to E(kroot, k) as the header and E(k,m) as the
body. In what follows the console header may contain multiple ciphertexts where each
ciphertext is the encryption of the content k under some key kj in the binary tree.
That’s because if some consoles are hacked, the industry can use keys {kj} in the
binary tree to encrypt a newly released game to revoke access to this game of the
hacked console. Let’s see some examples.
(a) Let’s say that 1 + log2 n keys embedded in console number i are exposed by
hackers and disclosed to the public. Show that when a new game m is about
2
to release (Baldur’s Gate 3 for example), m can be encrypted by using a header
containing log2 n short ciphertexts so that all consoles can decrypt the game m
except for console number i. In effect, the industry disables the game for console
number i. [5 marks]
[Hints] The header will have log2 n ciphertexts where each ciphertext is the en-
cryption of the content key k under certain log2 n keys from the binary tree.
(b) Now suppose the keys embedded in s consoles, I = {i0, · · · , is−1}, which are
exposed by hackers, where s > 1. At this time, the industry needs to ban all
the consoles in the console set I from decrypting the game. Show a way that
the industry can encrypt the contents of a new game using a header containing
O(s log2 n) short ciphertexts so that all the consoles can decrypt the game except
for the console set I. [5 marks]
[Hints] What you just did is that all hacked devices can be revoked without
affecting other consumers.
3. Classical Ciphers [42 marks]
(a) Affine Ciphers [20 marks]
Consider the following version of a classical cipher where plaintext and ciphertext
elements are from Z28. The encryption function, which maps any plaintext p to
a ciphertext c, is given by
c = E(a,b)(p) = ap+ b mod 28,
where a and b are from the Z28.
i. Derive the decryption function for the scheme. Show your work. [5 marks]
ii. A key is considered to be trivial if c = p for all input p. How many non-trivial
keys are possible for this scheme? [5 marks]
iii. Should this cipher be considered as mono-alphabetic cipher or poly-alphabetic
cipher? Why? [5 marks]
iv. Assume there is a helper which can output the corresponding ciphertext for
arbitrary plaintext you supply. Describe an efficient way to retrieve the key
using this helper. [5 marks]
(b) Poly-alphabetic Cipher [22 marks]
For this question, we consider a cipher working on an alphabet consisting of 26
English characters (A-Z), plus underscore ( ), comma (,) and full stop (.), which
corresponds to integers 0 to 28. The encryption is done by:
c = E2(E1(p))
Here E1 is the encryption function used in Hill cipher. The plaintext is processed
successively in blocks of size m. The encryption algorithm takes a block with
3
m plaintext digits (p1, p2, · · · , pm) and transforms into a cipher block of size m
(c1, c2, · · · , cm) using a key matrix of size m × m by the linear transformation,
which is given by:
c1 = (k1,1p1 + k1,2p2 + · · ·+ k1,mpm) mod 29
c2 = (k2,1p1 + k2,2p2 + · · ·+ k2,mpm) mod 29
· · ·
cm = (km,1p1 + km,2p2 + · · ·+ km,mpm) mod 29
E2 is the encryption function used in Vernam cipher. It processes a block of
plaintext at a time, and produces a same length ciphertext. In this task, our
Vernam cipher uses the same block size m as used in Hill cipher. The encryption
is performed by:
c1 = p1 +K1 mod 29
c2 = p2 +K2 mod 29
· · ·
cm = pm +Km mod 29
Note: For this question, correspondence between plaintext and number modulo
29 are as follows “A” ↔ 0, “B” ↔ 1, “C” ↔ 2, . . . , “Z” ↔ 25, “ ”↔ 26,
“, ”↔ 27 and “.”↔ 28. All following tasks use block size m = 5.
i. This cipher is easily broken with a known plaintext attack. Given the fol-
lowing combination of plaintext and ciphertext, your task here is to recover
the encryption keys (for both Hill cipher and Vernam cipher). Please map
the last five digits of your student number using the above correspondence,
and use it as the “?????” in plaintext and ciphertext. For example, if your
student number is 1234567, you should take the last five digits 34567 and
use DEFGH to replace both “?????” below.
Plaintext ZQIUOMCEFZGVRGTB?????JRTKENSNQ
Ciphertext WUJQYGCAH?????GDPQXUXHIDTDLIRG
Make sure to show details of your working, including any tool/package/library
used, and/or programs developed (If you developed codes, you should pro-
vide codes in text format, NOT in screenshots. Screenshots are NOT allowed
and will attract penalty. If you type in Latex, there are packages which can
help you to write codes). Only showing the final result and/or a program
may attract penalties. [12 marks]
4
ii. An adversary discovers the following ciphertext, which is encrypted using
keys found in (a). There are 60 characters in total.
OKCZKNCSQ ULYOKPKW,PL.UXIWX,YCLXZFGBM SUJLSCOXZT.AIGFZRDCIX,
Discuss how to recover the plaintext. Show the decryption key(s) used and
the decrypted plaintext. [5 marks]
iii. How many different keys are possible in this system? Briefly justify your
answer. [5 marks]
4. Additional Question: Probability [NO marks]
*******************
This question is NOT counted to your marks of this assignment. However,
we strongly encourage you to have a try.
*******************
Consider the following two experiments:
• Experiment 1: Alice flips a fair coin (0.5 probability of getting HEADS and 0.5
for TAILS), and shares the result with Bob.
• Experiment 2: Alice flips a fair coin, and always sends HEADS to Bob.
After each experiment, Bob needs to guess which experiment they were in. We can
quantify the quality of Bob’s guess using the following formula:
Q = |P (W1)− P (W2)|
Here Wi refers to the event that Alice performed experiment i (i ∈ {1, 2}), while Bob
guessed they were in experiment 1. We can see that Q = 0 indicates Bob cannot dis-
tinguish the two experiments, while Q = 1 suggests Bob can always correctly identify
which experiment they were in.
For the below tasks, apart from giving a numerical answer, please also show your
working by providing formula used, and/or a short explanation.
(a) For each of the following strategies used by Bob, calculate the quality of Bob’s
guess, Q.
i. Always guess experiment 2.
ii. Ignore the result reported by Alice, and randomly guess experiment 1 and
experiment 2 with equal probability.
iii. Guessing experiment 1 if TAILS was shared from Alice, otherwise guess ex-
periment 2.
iv. Guessing experiment 1 if HEADS was shared from Alice, otherwise guess
experiment 2.
5
v. Guessing experiment 1 if TAILS was shared from Alice, otherwise randomly
guess experiment 1 or 2 with equal probability.
(b) What is the highest quality of Bob’s guess, Q? Briefly elaborate the strategy and
justify your answer.
6
Submission and Evaluation
• You must submit a PDF document via the COMP90043 Assignment 1 submission
entry on the LMS by the due date. Handwritten, scanned images, screenshots,
and/or Microsoft Word submissions are not acceptable — if you use Word, create
a PDF version for submission.
• Late submission will be possible, but a late submission will attract a penalty of
10% per day (or part thereof). Requests for extensions on medical grounds will
need to be supported by a medical certificate. Any request received less than 48
hours before the assessment date (or after the date) will generally not be accepted
except in the most extreme circumstances.
• This assignment will be marked out of 75 marks, and will contribute to 7.5% of
your total marks in this subject. Marks are primarily allocated for correctness of
your thinking and clarity of your communication, rather than (only) the correct
result without justification.
• We expect your work to be neat — parts of your submission that are difficult to
read or 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.
• You are reminded that your submission for this assignment is to be your own
individual work. For many students, discussions with friends will form a natural
part of the undertaking of the assignment work. However, it is still an individual
task. You are welcome to discuss strategies to answer the questions, but not to
share the work (even draft solutions) on social media or discussion board. It is
University policy that cheating by students in any form is not permitted, and
that work submitted for assessment purposes must be the independent work of
the student concerned.
Please see https://academicintegrity.unimelb.edu.au
If you have any questions, you are welcome to post them on the Ed discussion board
so long as you do not reveal details about your own solutions. We encourage you to
make your questions public, as your classmates could have similar concerns.