COMP41280: First Assignment
Upload a single PDF file with your answers through Brightspace.
Only one submission attempt is allowed, so please double-check your assignment before
submitting.
Your answers must be typed and the PDF must be searchable; no handwritten scanned
materials are allowed.
Your submission is individual work; by submitting your assignment you acknowledge
that you have read and understood the plagiarism policies discussed in the course intro-
duction.
Do not submit any programs that you may have created to complete the assignment.
Indicative submission length: around three pages, please.
Exercise 1:
Assume a cryptosystem with only two possible plaintexts, a and b. Plaintext a occurs with
probability 23 and plaintext b occurs with probability
1
3 . There are two keys, k1 and k2, and
each is used with probability 12 . Key k1 encrypts a to A and b to B. Key k2 encrypts a to B
and b to A.
a) Calculate H(L) (the entropy of the plaintext), and H(L|C) (the conditional entropy of
the plaintext given the ciphertext). Give your results in bits, and discuss their meaning.
[10 marks]
b) Discuss your findings in a) from a purely probabilistic viewpoint (i.e., it terms of proba-
bility only). [5 marks]
Exercise 2:
Answer the following two questions:
a) Assume that L and C are the random variables representing plaintext and ciphertext,
respectively, in some encryption system.
1. Show that H(C|L) = H(K)?H(K|C,L). Hint: use the chain rule of joint entropy.
[5 marks]
2. Show that I(L;C) ≥ H(L)?H(K). [7 marks]
b) Consider a plaintext with alphabet L = {0, 1, 2, 3, 4} and a cryptosystem c = τ(l, k)
defined by c = l + k (mod 5) with l ∈ L and k ∈ K = L. Assuming that the random
variable K from which k is drawn has entropy H(K) = log2 5 bits, show that this cipher
is perfect. Hint: use the probabilistic definition of a perfect cipher. [10 marks]
? UCD 2023 Page 1 of 3
Exercise 3:
You play the role of Mallet (man-in-the-middle) and you know the following two facts: a)
plaintexts produced by Alice are in English (26 lowercase letters, with no spaces or punctuation
marks), and b) a Caesar cipher has been used to obtain the ciphertext.
a) Decipher the ciphertext below using brute force and frequency analysis, and give the key
that you have found in each case.
Can you break the cipher in both cases? Discuss. [15 marks]
b) Alice sends Bob the ciphertext otmuzrgeuaz. Can Mallet decipher this ciphertext? Can
Bob? Discuss your answer. Note: the key is not necessarily the same as in a). [5 marks]
Exercise 4:
Consider a version of the CFB mode using DES in which the plaintext is broken into 32-bit
pieces: l = l1‖l2‖l3 . . . , where each li is 32-bit long (rather than the usual 8 bits). Encryption
proceeds as follows: an initial 64-bit x1 is chosen; then, for j = 1, 2, . . . , the following operations
are carried out:
cj = lj ⊕A32(τ(xj , k))
xj+1 = B32(xj)‖cj
where A32(x) and B32(x) denote choosing the 32 leftmost and 32 rightmost bits of x, respec-
tively, and ‖ means concatenation
1. Give the decryption algorithm. [5 marks]
2. The ciphertext consists of 32-bit blocks c1, c2, c3, . . . Assume that a transmission error
causes c1 to be received as c?1 6= c1, but that all subsequent ciphertext blocks are received
correctly by Bob, who decrypts the received ciphertext blocks to yield plaintext blocks . . .
Discuss which is the first block of decrypted plaintext for which l?i = li. Your explanation
must be broken down into explicit steps. [10 marks]
UCD 2023 Page 2 of 3
Exercise 5:
Answer the following questions related to block ciphers:
1. Consider a simplified form of triple DES (3DES) using two keys k1 and k2 (with k1 and
k2 not being weak keys, or a pair of semiweak keys)
(a) Assume that c = τ(τ(τ(l, k1), k2), k2). Show how to attack this modified version of
3DES with a meet-in-the-middle attack, in which the attacker knows one single (l, c)
pair. Is there any possibility that the attacker cannot find k1 and k2 through this
attack? Discuss. [5 marks]
(b) Assume that c = τ(τ ′(τ(l, k2), k1), k2) (note the use of τ ′ in the middle now). Discuss
whether this is safer or not than the scheme in (a) in the same conditions. [5 marks]
2. Consider the following DES-inspired toy block cipher: a plaintext message block of 2n
bits of length is divided into two blocks of length n bits each (left half l0 and right half
l1). In other words, the input to the algorithm is l0‖l1, where ‖ denotes concatenation.
One round of encryption takes the input li‖li+1 and produces the output li+1‖li+2, where
li+2 = li ⊕ f(li+1,k). The same n-bit long key k is used in all rounds. The function
f(l,k) = l⊕k (bitwise, modulo 2 addition) is used instead of the standard DES function.
(a) Discuss whether this is a Feistel network, and what is the obvious weakness (or
weaknesses) of this algorithm. [5 marks]
(b) Describe how would Bob perform decryption of this scheme. [8 marks]
(c) What is more secure, using two rounds or three rounds? Justify your answer, and
point out what is the most important weakness of the proposed scheme. [5 marks]