1. (a) • Confusion. The relationship between the key and the ciphertext is as complex
as possible (2 marks). (Could be more precise, e.g. giving the strict avalanche
condition, but I won’t insist.)
• Diffusion. The relationship between the plaintext and the ciphertext is as
complex as possible (2 marks).
(b) Should cover iteration and key schedule, S-boxes, permutation and key mixing (4
marks).
(c) Should explain that it is a chosen plaintext attack, aiming to obtain targetted bits
of the final round key (2 marks). 6 further marks for a clear explanation correctly
explaining propagation ratio, differential trail, candidate key and right pair.
(d) Using ECB, identical blocks of plaintext are ecrypted as identical blocks of ciphertext
(2 marks). Alternatives: I would accept any of CBC, OFB, CFB or counter mode,
with an accurate definition (2 marks).
2. (a) An easily computed function mapping data of arbitrary length to a fixed length
output (2 marks). SHA-2 or SHA-3 (1 mark).
(b) A collision for a hash function h : X → Y is a pair of distinct values x 6= x′ such
that h(x) = h(x′) (1 mark). h is collision resistant if finding a collision requires
approximately
√
|Y| operations (2 marks). Collision resistance does not imply
preimage resistance, since finding a pre-image by brute force requires |Y| operations,
so any function which yields pre-images more quickly is not pre-image resistant, but
may be collision resistant (alternatively, it may be theoretically possible to easily
find a single pre-image, but not two or more which collide). (2 marks).
(c) Integrity — only authorised principals may alter data. Message authenticity —
assurance that the source of a message is accurately represented (2 marks). Alice
may assure authenticity and integrity by sending Bob (m,hk(m)), where h is a
message authentication code and k is their shared private key. If Bob receives
(m, y), he may compute hk(m): if it is equal to y, he knows that the creator of the
message used the key (i.e. is Alice) and the message m, so it has not been altered
(3 marks).
(d) This attempt to define a MAC is vulnerable to length extension attack — an attacker
who knows the length of k‖m may apply the compression function to h(k,m) and
an extension m′ of his choice, padded with the total length of k‖m‖m′ to obtain
a valid authentication tag for m‖m′ without knowledge of k (5 marks). A secure
HMAC may be obtained as hk(m) = h(k ⊕ opad‖h(k ⊕ ipad‖m)) (2 marks).
Page 2 of 3 CM30173
3. (a) Encryption modulus is 17.13 = 221. Its totient is 16.12 = 192, so we need to find
the inverse of 5 in the multiplicative group of integers modulo 192, which is 77 (by
extended Euclidean algorithm).
(b) Description of H̊astad’s broadcast attack to recover a plaintext encrypted using a
public exponent of 3 for three recipients with different moduli of encryption, using
Chinese remainder theorem (5 marks).
(c) Semantic security – a computationally bounded attacker who knows only the public
key should not be able to derive any information about an encrypted message (2
marks). Basic RSA encryption is not semantically secure becuase of its malleability
and determinacy. (2 marks).
(d) Description of search for a factorization of n, given the encryption and decryption
exponents a, b, using the fact that xab − 1 ≡ 1 mod(n) for any x, so by repeatedly
taking square roots, for trial initial values of x, we find y such that y2 ≡ 1 mod(n)
and y 6≡ 1 mod(n), and hence y+ 1, y− 1 share non-trivial factors with n (5 marks).
The RSA problem is not equivalent to integer factorization, as it only requires the
efficient recovery of the plaintext of a message from the ciphertext using only the
public key (1 mark).
4. (a) Description (bookwork) of key generation (2 marks), signature generation (2 marks)
and verification (2 marks).
(b) 3 marks for proving that a correctly generated signature passes verification, 3 marks
for showing that if a value passes verification then it was correctly generated using
the private key (bookwork).
(c) When generating keys, a multiplicative group should be chosen such the that there
are no known efficient methods of finding discrete logarithms. (1 mark). When
signing messages, a different ephemeral key should be chosen each time. (1 mark).
(d) An attacker with a public key (p, α, β) (such that β ≡ αa mod(p) for an unknown
private key a) can create an existential forgery of a signature by choosing 0 ≤ i, j ≤
p− 2, and taking γ = αiβj mod(p), δ = −γj−1 mod(p− 1) and x = iδ mod(p− 1).
Then βγγδ ≡ βγα(i+aj)δ mod(p)
≡ βγαiδ+ajδ mod(p)
≡ βγαx−aγ mod(p)
≡ βγ−γxa mod(p)
≡ xa mod(p) (5 marks).
This forgery is prevented by hashing any message before signing. (1 mark).
JDL/RJB Page 3 of 3 CM30173