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) What is a digital certificate — what information does it carry, how is it issued and
used and what is its role in a PKI? [7]
(b) Bob receives a message claiming to come from Alice, signed using the ElGamal
digital signature scheme. Explain what he should do to check that it was Alice who
signed it, show that verification is successful if the message is authentic. [6]
(c) What is the discrete logarithm problem, and what is its relevance to the security of
the ElGamal scheme? Describe Shanks’ algorithm for solving the problem. [7]
2. (a) Describe four general forms of attack on a symmetric key encryption system, in
terms of the information required by the attacker. [4]
(b) Describe the encryption of a block of plaintext using a subsitution-permutation
network and a key. [6]
(c) Explain in detail how to mount an attack on a SPN using differential cryptanalysis.
Which of the attacks described in part (a) is it? How can a SPN be designed to be
resistant to this attack? [10]
3. (a) What does it mean for a public key encryption system to be semantically secure?
Why is basic RSA not semantically secure? [4]
(b) Explain precisely why an efficient algorithm for integer factorization would
compromise the security of RSA encryption. [6]
(c) Show that if we can find values x, y such that x2−y2 ≡ 0mod(n) and x 6≡ ±ymod(n)
then n may be factorized. What is a factor base, and what does it mean for a number
to be B-smooth? Explain how a collection of B-smooth numbers can be used to
find such x and y and so factorize n. [10]
CM30173 continued
CM30173 continued 3.
4. (a) Explain briefly what is meant by each of the following security properties, and for
each one, give an example of the use of a cryptographic primitive to provide it.
• Confidentiality.
• Integrity.
• Authenticity
• Message Authentication.
[4]
(b) Describe the Merkle-Damg̊ard construction of an unkeyed hash function, as an
algorithm. Is the hash function so constructed provably secure? [8]
(c) Alice creates a message authentication code by applying an unkeyed hash function to
k‖m, where k is her key, and m her message. How could an attacker compromise the
integrity of this MAC? How could Alice protect against this attack? Be as precise
as you can. [8]
JDL/RJB CM30173