CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173: CM30173: Mark Scheme
CM30173
CM30173
1. (a) 1 mark for definition of a cryptosystem, 2 for a Feistel cipher, 3 for showing that
it meets the definition (mostly bookwork, a little proof required that each round of
decryption reverses a round of encryption). [6]
(b) 1 mark for a chosen plaintext attack, 1 more for saying that plaintexts are chosen in
pairs having a difference yielding a high-probability differential trail. Attack requires
c/p plaintexts, where p is the probability of the trail (2 marks).
DES S boxes (1 mark) were designed to have a near-uniform difference distribution
(some explanation – 2 marks). Therefore differential trails have low probabiility
and hence a large number of ciphertexts for chosen plaintexts are required (1
mark). [8]
(c) 1 mark for describing 3DES. Mention of meet-in-the-middle attack – 1 mark.
Inference that computational feasibility of MITM on 2DES is similar to brute force
attack on DES, 2 marks. Explanation of why MITM fails for 3DES – 2 marks. [6]
2. (a) 1 mark for definition of ECB, 1 mark for observation that patterns of repeated
plaintext blocks are preserved as repeated ciphertext blocks. 1 mark each for
definition of CBC and CFB, and 2 marks for a simple proof that encrypting and
then decrypting each block using CFB [6]
(b) 1 mark for definition of a hash function (compression and computability properties).
1 mark for knowing what a collision is, and that they should be hard to find, 1 more
for knowing that finding a collision for a collision restant function with N outputs
should require O(
√
N) operations, 2 more for justifying this in terms of the birthday
attack. 1 mark for either an attack based on collisions (e.g. existential forgery of
digital signatures) or observing that failure of collision resistance can lead to chosen
prefix attacks. 1 mark for basic description of Merkle-Damg̊ard construction, 1 more
for knowng that it requires a collision-resistant compression function. [8]
(c) 2 marks for a brief explanation of verification of integrity and authentication of a
message by computing and comparing authentication tag using a shared key. 1 mark
for knowing that SHA-2 is based on the Merkle-Damg̊ard construction, and 2 more
for describing a length extension attack. 1 mark for defining HMAC. [6]
Page 2 of 3 CM30173
CM30173
3. (a) 3 marks for defining RSA and 3 for proving it correct (bookwork). [6]
(b) 6 marks available for an argument that shows that the decryption key can be used to
factorize the modulus using Fermat’s little theorem to find non-trivial congruences
of squares to 1. (3 marks for approach, 3 for details).
2 marks for knowing that the RSA problem is determining the plaintext from a RSA
ciphertext, knowing only the public key, and that it is not known whether this is as
hard as factorization. [8]
(c) 3 marks for an explanation of H̊astad’s broadcast attack, 2 marks for an explanation
of semantic security as resistance to distinguishability of chosen plaintext attacks.
1 mark for a mention of randomized padding such as OAEP to give semantic
security. [6]
4. (a) Alice sends Bob 54mod(23), which is (52)2mod(23) — i.e. 4 (2 marks). Bob sends
516mod(23), which is (54)4mod(23) — i.e. 44mod(23), or 256mod(23), which is 3 (2
marks). Shared value is 54.16mod(23) which is 34mod(23) — i.e. 12 (2 marks). [6]
(b) 2 marks for: discrete log of 2 is 2 (as e.g. 2log(2) = log(4) = 4), discrete log of 3 is
16, as 516mod(23) is 3. Discrete log of 5 (the base) must be 1.
2 marks for an explanation of computing discrete logs by factorizing a multiple
of 5s over the factor base and taking the log. In the case of 19, we have
19.52 ≡ 38 ≡ 15mod(23) and thus log(19) + 2 ≡ log(5) + log(3)mod(22) and so
log(19) = 1 + 16 − 2 = 15 (4 marks). This method is not applicable in groups
without a notion of prime factorization (1 mark). [8]
3 marks for a correct definition of El Gamal signature scheme, 3 marks for proving
it correct (bookwork). [6]
JDL/RJB Page 3 of 3 CM30173