CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173
May 2012
No calculators may be brought in and used.
Full marks will be given for correct answers to THREE questions.
Only the best three answers will contribute towards the assessment.
Examiners will attach importance to the number of
well-answered questions.
CM30173
CM30173 2.
1. (a) Should cover the main data included on certificates: (identity, encryption and public
key details, validity dates and certifying authority data and signature) and explain
how this information can be used to verify the authenticity of a signed document.
(b) 3 marks for describing digital signature verification, 3 for showing correctness.
(c) 2 marks for defining the DLOG problem and observing that solving it would allow
universal forgery of ElGamal digital signatures by finding private keys. 5 marks for
description of Shanks’ algorithm.
2. (a) 1 mark for 4 of (cipher text only, known plaintext, chosen plaintext, chosen
ciphertext, adaptive ciphertext).
(b) 4 Marks for correctly describing the components: substitution, permutations, key
mixing, round key selection, 2 for the overall iterated structure.
(c) 8 marks for describing the attack (computing difference distributions, using them to
find a differential trail, using plaintexts with the selected difference to test candidate
keys) 1 mark for observing that it’s a chosen plaintext attack, and 1 for suggesting
that S-boxes should have near uniform difference distribution.
3. (a) 2 marks for explaining semantic security as indistiguishability under chosen
ciphertext attack. 2 marks for observing that determinacy and/or malleability of
RSA mean that it isn’t semantically secure.
(b) Should explain how RSA private/public keys are generated (4 marks), and thereby
argue that factorization allows recovery of the private key from the public key and
the modulus of encryption (2 marks).
(c) 4 marks for proof that in this case, gcd(x − y, n) and gcd(x + y, n) are non-trivial
factors of n. 1 mark for defining factor based and B-smooth, 5 marks for reasonable
description of factor base method (collecting values for which the squares are B-
smooth, and using linear dependencies to find combinations for which all factors
have even exponents, and so find non-trivial differences of squares modulo n).
4. (a) 1 mark for each.
(b) 6 marks for a reasonably precise description of the algorithm. 2 marks for stating
that collision-freeness of the compression function implies collision-freeness of the
hash function.
(c) 3 marks for describing an extension attack. 5 marks for describing how HMAC
style padding defeats it (need not describe HMAC itself, but should avoid e.g. just
appending length padding).
JDL/RJB CM30173