CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM
May 2011
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) 5 Marks for defining a Feistel cipher, encryption and decryption, 3 marks for proving
that decryption is the inverse of decryption. It can be turned into a stream cipher
using output feedback mode (2 marks).
(b) 2 marks for defining a product cipher. Describe meet-in-the-middle attack to show
that a product cipher may be broken by exhaustive key search in time proportional
to the hardest of its components, although it may be more secure against statistical
attacks.(5 marks)
(c) Observe that DES is not secure (56 bit keys are too easy to find by exhaustive
search), and so neither is 2DES, but that 3DES is currently regarded as secure. (3
marks).
2. (a) 2 marks for defining a hash function. Applications include integrity of encrypted
messages and digital signatures and password storage. (1 mark each).
(b) 1 mark for each attack (first and second preimage, collision). E.g. hash functions
used for integrity of signatures need to be secure against collision attack, for
passwords, security against first preimage would suffice (1 mark each).
(c) A hash is certificationally secure if there is no better attack than exhaustive search (1
mark). Difficulty of preimage attacks is |N |, where N is the set of digests (1 mark),
but |N |
1
2 for collision attack (1 mark) because one may use a birthday attack (1
mark).
(d) Describe Merkle-Damgard construction (including iteration of the compression
function and length padding). If the compression function is collision resistant,
then the constructed hash function is (provably) collision resistant. (2 marks).
CM30173 continued
CM30173 continued 3.
3. (a) 2 marks for defining a public key encryption system. 2 marks for describing RSA
accurately, 3 marks for establishing that decryption and encryption are inverses.
(b) If I know n and φ(n), I can factor n by substituting n
p
for q in φ(n) = (p− 1).(q− 1)
and solving for p. (2 marks)
If I know d, e < n such that d.e ≡ 1mod(φ(n)) and thus m = d.e − 1 such that
xm ≡ 1mod(n) for any x by Euler’s theorem, then I can attempt to factor n using the
difference of squares: Taking y = x
m
2 we have y2 ≡ 12mod(n), and if y 6≡ 1mod(n)
then y− 1 and y + 1 are not coprime with n, and thus yield factors of n. Repeating
until we have an exponent which is not divisible by 2 yields a factorization with
probability 1/2 for each x. (6 marks)
(c) 3 marks for defining semantic security (indistinguishability under known plaintext
attack). A padding scheme such as optimal asymmetric encryption padding must
be used to make RSA semantically secure (2 marks).
4. (a) Alice should send the values 37, 2 and 27 (which is 26mod(37) (i.e. 64mod(37)) to
Bob (2 marks) who should reply with 17 (which is 27mod(37)) (2 marks). Their
shared key will be 32 (26.7mod(37) = 242mod(37) ≡ 25mod(37)) (2 mrks).
(b) Diffie Hellman problem is finding gabmod(p) given gamod(p) and gbmod(p). (2
marks). Describe a man-in-the middle attack by which an attacker establishes
shared keys with Alice (who thinks he is Bob) and Bob (who thinks he is Alice)
(4 marks).
(c) Should describe El-Gamal digital signatures (or DSA) generation and verification
(5 marks), noting requirement for hashing and a PKI (or other infrastructure) to
distribute and authenticate keys (3 marks).
JDL/RJB CM30173